# How do I represent a hidden markov model in data structure?

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.

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

## 1 Answer

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.

• I cannot use anything other than standard library, as mentioned in the question. – Aman Mathur Mar 17 '17 at 9:45
• @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. – Neil Slater Mar 17 '17 at 10:18
• 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. – Aman Mathur Mar 17 '17 at 10:27
• @AmanMathur: I have adjusted my answer to show there is not a problem with your representation. – Neil Slater Mar 17 '17 at 10:36