Answers.Body: <p>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.</p>
  
  <p>The way I would approach this it to use a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a> 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).</p>
  
  <p>If you want to learn about HMMs, one possible application would be a weather forecast (I thought this was an example <a href="http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf" rel="nofollow noreferrer">Lawrence Rabiner uses in his tutorial</a>, but it's actually on the <a href="https://en.wikipedia.org/wiki/Hidden_Markov_model" rel="nofollow noreferrer">HMM Wikipedia page</a>). 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 <em>light</em> can belong to <code>adj</code>, <code>noun</code>, and <code>verb</code>). 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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T19:28:23.557Z
Answers.Text: 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 ?
Answers.UserDisplayName: Tirdad Sadri Nejad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-13T08:12:41.223Z
Answers.Text: Yes, should be suitable.
Answers.UserDisplayName: Oliver Mason
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-12T18:06:22.497Z
Answers.LastActivityDate: 2019-09-12T18:06:22.497Z
Answers.UserDisplayName: Oliver Mason
Body: <p>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 :</p>
  
  <p>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:</p>
  
  <ul>
  <li>Tap</li>
  <li>Trip</li>
  <li>Trap</li>
  <li>Trigger</li>
  </ul>
  
  <p>and we want to predict the word after 1,2 or 3 written letters.</p>
  
  <p>we have to define states and HMM parameters (state transitions, emissions and priors).</p>
  
  <p>our <strong>[hidden ?] states</strong> would be :</p>
  
  <ul>
  <li>[ ][ ][ ][ ][ ][ ][ ] : no observations. I chose 7 [ ] because of the longest word</li>
  <li>T [ ][ ][ ][ ][ ][ ]</li>
  <li>T A [ ][ ][ ][ ][ ]</li>
  <li>T R [ ][ ][ ][ ][ ]</li>
  <li>… .</li>
  </ul>
  
  <p>and we have to <strong><em>learn</em></strong> 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).</p>
  
  <p>our <strong>prior probabilities</strong> are 1/3 because we have 3 words. but we may change it by learning which word is used more frequently.</p>
  
  <hr>
  
  <p>Now, I have these questions :</p>
  
  <ol>
  <li>is HMM suitable for this kind of problem ?</li>
  <li>are my assumptions (about states and prior probabilities) correct ?</li>
  <li>the states get out of hand when the word count increases. making the model very complex. is that deduction true? </li>
  <li>how the emission probabilities are defined in this model ?</li>
  <li>what do I miss in case of parameters or definitions ?</li>
  </ol>
  
  <p>I'm a new contributor, be nice to me. regards :) </p>
  
Tags: <hidden-markov-model>
Title: is a "word prediction" problem, applicable using HMMs?
UserDisplayName: Tirdad Sadri Nejad
ThreadText: # is a "word prediction" problem, applicable using HMMs?
  
  (Asked by: username_0 on 2019-09-12)
  
  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 :)
  
  **Tags:** hidden-markov-model
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-09-12. Score: 1 | Accepted 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](https://en.wikipedia.org/wiki/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](http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf), but it's actually on the [HMM Wikipedia page](https://en.wikipedia.org/wiki/Hidden_Markov_model)). 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).
  
  > **Comments:**
  > **username_0**: 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 ?  
  > **username_1**: Yes, should be suitable.  
  
  ---
  
  