Pattern Recognition and Machine Learning

614 13. SEQUENTIAL DATA

Figure 13.9 Example of the state transition diagram for a 3-state

left-to-right hidden Markov model. Note that once a

state has been vacated, it cannot later be re-entered.

k=1 k=2 k=3

A 11 A 22 A 33

A 12 A 23

A 13

state transition diagram for a 3-state HMM in Figure 13.9. Typically for such models

the initial state probabilities forp(z 1 )are modified so thatp(z 11 )=1andp(z 1 j)=0

forj =1, in other words every sequence is constrained to start in statej=1. The

transition matrix may be further constrained to ensure that large changes in the state

index do not occur, so thatAjk=0ifk>j+∆. This type of model is illustrated

using a lattice diagram in Figure 13.10.

Many applications of hidden Markov models, for example speech recognition,

or on-line character recognition, make use of left-to-right architectures. As an illus-

tration of the left-to-right hidden Markov model, we consider an example involving

handwritten digits. This uses on-line data, meaning that each digit is represented

by the trajectory of the pen as a function of time in the form of a sequence of pen

coordinates, in contrast to the off-line digits data, discussed in Appendix A, which

comprises static two-dimensional pixellated images of the ink. Examples of the on-

line digits are shown in Figure 13.11. Here we train a hidden Markov model on a

subset of data comprising 45 examples of the digit ‘2’. There areK=16states,

each of which can generate a line segment of fixed length having one of 16 possible

angles, and so the emission distribution is simply a 16 × 16 table of probabilities

associated with the allowed angle values for each state index value. Transition prob-

abilities are all set to zero except for those that keep the state indexkthe same or

that increment it by 1, and the model parameters are optimized using 25 iterations of

EM. We can gain some insight into the resulting model by running it generatively, as

shown in Figure 13.11.

Figure 13.10 Lattice diagram for a 3-state left-
to-right HMM in which the state indexkis allowed
to increase by at most 1 at each transition. k=1

k=2

k=3

n− 2 n− 1 nn+1

A 11 A 11 A 11

A 33 A 33 A 33