The Viterbi algorithm

So far, we have been trying to compute the different conditional and joint probabilities in our model. But one thing that we can't do with the forward-backward algorithm is find the most probable state of the hidden variables in the model given the observations. Formally, we can write this problem as, we know the observed variable, the transition probabilities and the emission probability of the network and we would like to compute Z^*, which is defined as:

Where,

Z={Z₁, Z₂, …, Z_n}

And,

X={X₁, X₂, …, X_n}

Properties of operations on probability distributions:
When we do operations on the probability distributions (marginalization, maximization, and so on), we can push in the operation through the independent terms of the distribution. We can see these examples in the case of marginalization and argmax:

Figure 3.6: HMM showing three...