# is a “word prediction” problem, applicable using HMMs?

I'm learning HMMs and decided to model a problem for learning purposes. I came to this idea of word predicting by letters. here is the model :

while typing, the word is typed letter by letter, so we can consider them as series of observations. let's say we have just 4 words in our database:

• Tap
• Trip
• Trap
• Trigger

and we want to predict the word after 1,2 or 3 written letters.

we have to define states and HMM parameters (state transitions, emissions and priors).

our [hidden ?] states would be :

• [ ][ ][ ][ ][ ][ ][ ] : no observations. I chose 7 [ ] because of the longest word
• T [ ][ ][ ][ ][ ][ ]
• T A [ ][ ][ ][ ][ ]
• T R [ ][ ][ ][ ][ ]
• … .

and we have to learn the transition probabilities of each state pairs (the pairs which come after each other like T,TR and TA. but not for TA and TR).

our prior probabilities are 1/3 because we have 3 words. but we may change it by learning which word is used more frequently.

Now, I have these questions :

1. is HMM suitable for this kind of problem ?
2. are my assumptions (about states and prior probabilities) correct ?
3. the states get out of hand when the word count increases. making the model very complex. is that deduction true?
4. how the emission probabilities are defined in this model ?
5. what do I miss in case of parameters or definitions ?

I'm a new contributor, be nice to me. regards :)

## 1 Answer

I think a HMM is overkill for this problem. You kind of have 'hidden' states, but they are very limited and dependent on the full sequence of previous states, which you probably want to avoid to make best use of the HMM's features. It also, as you rightly say, leads to a proliferation in states: each dictionary item adds as many states as it has letters to the model.

The way I would approach this it to use a trie which contains your dictionary, and then you traverse the trie as the user types characters. At each point you have a sub-trie which gives you the possible completions of the word. You could even (if available) augment this with probabilities to guess the most likely word (though this does not take into account the previous word in the sentence, which might be more useful).

If you want to learn about HMMs, one possible application would be a weather forecast (I thought this was an example Lawrence Rabiner uses in his tutorial, but it's actually on the HMM Wikipedia page). Or, if you want to work with texts, use parts-of-speech tagging. You want to have something where each observation can belong to several possible states (eg light can belong to adj, noun, and verb). Here you would have the words as observations and the part-of-speech tags as states, which keeps the model at a reasonably small size (and is thus easier to train).

• actually I'm planning to use HMMs for limited dictionary speech recognitions (one word commands) and tweak it for very low power microcontrollers. so I have to write it from ground up with many hardware side optimizations. I thought using this learning model would point me in the right direction. the tutorial you provided seems good for my purpose. and for a general opinion, do you think if HMMs are suitable for that low-vocab speech recognitions on low power hardware ? – Tirdad Sadri Nejad Sep 12 '19 at 19:28
• Yes, should be suitable. – Oliver Mason Sep 13 '19 at 8:12