I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, that would leave us with $459^2$ states and $(459^2)^2$ transitions between them, which would require a massive amount of memory.

Are there any workarounds around this? What I thought of is considering only bigrams seen in the data, but it is still a lot of memory.


1 Answer 1


Actually, there are only $459^3$ transitions, not $459^4$ transitions. That helps a lot. This is because a state is a pair $(t,u)$ where $t,u$ are tags, and a transition has the form $(t,u)\to (u,v)$. In particular, you can't have $(t,u) \to (w,x)$ where $u \ne w$ (given that the state represents the last two tags). So, there are at most $459^3$ transitions, or at most about 100 million transitions. You should be able to store that a graph with 100 million edges in memory without too much difficulty.

My guess would be that not all transitions actually occur in the training set, so it's possible this might be a sparse graph, and that might reduce the graph size further.


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.