5.5.3 The Viterbi Algorithm for HMM Tagging

For any model, such as an HMM, that contains hidden variables, the task of determining which sequence of variables is the underlying source of some sequence of observations is called the decoding task. The Viterbi algorithm is perhaps the most common decoding algorithm used for HMMs, whether for part-of-speech tagging or for speech recognition. The term Viterbi is common in speech and language processing, but this is really a standard application of the classic dynamic programming algorithm, and looks a lot like the minimum edit distance algorithm of Ch. 3. The Viterbi algorithm was first applied to speech and language processing in the context of speech recognition by Vintsyuk (1968), but has what Kruskal (1983) calls a 'remarkable history of multiple independent discovery and publication'; see the History section at the end of Ch. 6 for more details.

The slightly simplified version of the Viterbi algorithm that we will present takes as input a single HMM and a set of observed words $ O = (o_1 o_2 o_3 \ldots o_T) $ and returns the most probable state/tag sequence $ Q = (q_1 q_2 q_3 \ldots q_T) $, together with its probability.

Let the HMM be defined by the two tables in Fig. 5.15 and Fig. 5.16. Fig. 5.15 expresses the $ a_{ij} $ probabilities, the transition probabilities between hidden states (i.e. part-of-speech tags). Fig. 5.16 expresses the $ b_{i}(o_{t}) $ probabilities, the observation likelihoods of words given tags.

Fig. 5.17 shows pseudocode for the Viterbi algorithm. The Viterbi algorithm sets up a probability matrix, with one column for each observation $ t $ and one row for each state in the state graph. Each column thus has a cell for each state $ q_i $ in the single combined automaton for the four words.

function VITERB1(observations of len T,state-graph of len N) returns best-path

create a path probability matrix viterbi[N+2,T]

for each state s from 1 to N do

viterbi[s,1] ← $ a_{0,s} * b_{s}(o_1) $

backpointer[s,1] ← 0

for each time step t from 2 to T do

for each state s from 1 to N do

viterbi[s,t] ← $ \max_{s'=1}^{N} viterbi[s',t-1] * a_{s',s} * b_{s}(o_t) $

backpointer[s,t] ← $ \argmax_{s'=1}^{N} viterbi[s',t-1] * a_{s',s} $

viterbi[qF,T] ← $ \max_{s'=1}^{N} viterbi[s,T] * a_{s,qF} $

backpointer[qF,T] ← $ \argmax_{s'=1}^{N} viterbi[s,T] * a_{s,qF} $

return the backtrace path by following backpointers to states back in time from backpointer[qF,T]

Figure 5.17 Viterbi algorithm for finding optimal sequence of tags. Given an observation sequence and an HMM $ \lambda = (A, B) $, the algorithm returns the state-path through the HMM which assigns maximum likelihood to the observation sequence. Note that states 0 and $ qF $ are non-emitting.

The algorithm first creates N or four state columns. The first column corresponds to the observation of the first word i, the second to the second word want, the third to the third word to, and the fourth to the fourth word race. We begin in the first column by setting the viterbi value in each cell to the product of the transition probability (into it from the state state) and the observation probability (of the first word); the reader should find this in Fig. 5.18.

Then we move on, column by column; for every state in column 1, we compute the probability of moving into each state in column 2, and so on. For each state $ q_j $ at time t, the value $ viterbi[s,t] $ is computed by taking the maximum over the extensions of all the paths that lead to the current cell, following the following equation:

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)a_{ij}b_{j}(o_{t}) $$

The three factors that are multiplied in Eq. 5.38 for extending the previous paths to compute the Viterbi probability at time t are:

$ v_{t-1}(i) $ the previous Viterbi path probability from the previous time step

$ a_{ij} $ the transition probability from previous state $ q_{i} $ to current state $ q_{j} $

$ b_{j}(o_{t}) $ the state observation likelihood of the observation symbol $ o_{t} $ given the current state j

In Fig. 5.18, each cell of the trellis in the column for the word I is computed by multiplying the previous probability at the start state (1.0), the transition probability from the start state to the tag for that cell, and the observation likelihood of the word I given the tag for that cell. As it turns out, three of the cells are zero (since the word I can be neither NN, TO nor VB). Next, each cell in the want column gets updated with the maximum probability path from the previous column. We have shown only the value for the VB cell. That cell gets the max of four values; as it happens in this case, three of them are zero (since there were zero values in the previous column). The remaining value is multiplied by the relevant transition probability, and the (trivial) max is taken. In this case the final value, .000051, comes from the PPSS state at the

previous column.

The reader should fill in the rest of the trellis in Fig. 5.18, and backtrace to reconstruct the correct state sequence PPSS VB TO VB.