Probabilistic Models Used in the Demo Prototype

The word model: A word model describes how a person may try to type a word as a sequence of letters.

• Letters: In this programming assignment, we pretend that the 26 letters in the English alphabet are the basic phones. We treat the letters in a case-insensitively.
• States of the state transition diagram: In the state transition diagram for a specific word, the number of states equals one plus the number of characters in the word. There is a state for each character in the word, which models the stage of attempting to type the corresponding letter in that word, and it will generate an observable character output. In addition to these regular states, there is a special final state. The final state simply models the end of typing the word and it will not generate observable character output.
• Possible initial states: When we attempt to type the word, initially we can be in any of the states, but the likelihood is proportional to one over the ith power of the position of the character in the word. For example, let’s make i as 3. This means that it is possible (but very unlikely) that we may skip the first or first few characters of the word in our pronunciation.
• State transitions and the final state: When typing the word, we can start from one of the possible initial states, non-deterministically go through a number of states, and finally transition into and end in the final state. The final state simply models the end of pronouncing the word and it will not generate observable character output.
• State transition probabilities: In each state, there is a probability P_repeat (for example 0.1) that you may end up in the same state again after one state transition, and with a probability P_moveOn (for example 0.9) that you may end up in the final state or in one of the states representing the characters to the right of the current character. Let’s imagine the final state as kind of representing a imaginative character. Then among the characters to the right of the current character (including the imaginative character represented by the final state), the likelihood of ending up in a particular character c of them is proportional to one over the jth power of the distance (i.e. number of characters away to the right) c is away from the current character. For example, we can make j as 2.

The keyboard model (i.e. the acoustic model in speech recognition): The keyboard model tells us how likely we would generate a character c when we are in a mental state to type a character x.

• Probability of observing a letter when pronouncing a character in a word: there is a probability P_exact (for example 0.8) that the letter we generate is exactly the same as the character we want to type, and with a probability P_nearby (for example 0.2) that we may turn out to press a different nearby key of the keyboard. For the demo program, we look at the English alphabet as a circular double linked list of 26 letters, and let’s define the distance between two letters as one plus the minimal number of letters between them in the circular double linked list. When we are in a state of pronouncing a particular character c, the likelihood of observing a different letter l (other than c) is proportional to one over the kth power of the distance between l and c. For example, we can make k as 3.