1
$\begingroup$

My task involves a POS Tagging using HMM. I am given a training data set (word/tag). I have to write a file with transition probabilities and emission probabilities. I am currently using a nested dictionary of the form {State1: {State2: count, State3 :count}}. However, while calculating the probabilities now via the counts in nested dict, my program is running very slow for mid size files (e.g. 2000 sentences and tags)

Is there a better way to store a HMM in python? For my project, I cannot use any external library that already does this, I must use standard python libraries.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you implementing HMM from scratch or using some external libs? $\endgroup$
    – Icyblade
    Commented Mar 17, 2017 at 5:09
  • $\begingroup$ I am implementing it from scratch. $\endgroup$
    – Aman Mathur
    Commented Mar 17, 2017 at 6:41
  • $\begingroup$ How many states do you have, and how are states represented? $\endgroup$
    – Neil Slater
    Commented Mar 17, 2017 at 8:00
  • $\begingroup$ States are POS Tags. There are 29 tags from the training data. The transition ( edges) probabilities are P(State1|State2) $\endgroup$
    – Aman Mathur
    Commented Mar 17, 2017 at 9:44

1 Answer 1

Reset to default
0
$\begingroup$

With 29 states and 841 possible transitions to track whilst reading a file with 2000 entries (word, tag), then you should not be experiencing a speed problem when using a dictionary of dictionaries.

Assuming your data structure as described called transition_counts, and receiving data in pairs, (this_pos, next_pos) then running 2000 times:

transition_counts[this_pos][next_pos] += 1

takes only a fraction of a second. This is similar for code that calculates $p(POS_{t+1}|POS_t)$:

total_from_pos_t =  sum(transition_counts[pos_t].values())
prob_pos_tplus_one = transition_counts[pos_t][pos_tplus_one] / total_from_pos_t

This is very fast. Your problem is not with the representation.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I cannot use anything other than standard library, as mentioned in the question. $\endgroup$
    – Aman Mathur
    Commented Mar 17, 2017 at 9:45
  • $\begingroup$ @AmanMathur: Then you could use a list of lists to store values rather than a dictionary of dictionaries. That might speed things up a little. However, with only 29 states and 29 * 29 = 841 possible transitions, then your speed problem is probably not just the representation, but how you have structured the algorithm. You may be better off posting your code for analysis. I'm not sure if this site is the best for that - and if you do, don't post the whole thing but do some research yourself first to find out which part is slow, and post just that part. $\endgroup$
    – Neil Slater
    Commented Mar 17, 2017 at 10:18
  • $\begingroup$ Thanks a lot! I'll try and do that. Just a note, If i am storing it as a list, I will not be able to call the values by name, as needed. $\endgroup$
    – Aman Mathur
    Commented Mar 17, 2017 at 10:27
  • $\begingroup$ @AmanMathur: I have adjusted my answer to show there is not a problem with your representation. $\endgroup$
    – Neil Slater
    Commented Mar 17, 2017 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.