# HMM tagger - Baum Welch training

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.

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.