Editing Viterbi algorithm (section)

== Algorithm ==
Given a hidden Markov model with a set of hidden states <math>S</math> and a sequence of <math>T</math> observations <math>o_0, o_1, \dots, o_{T-1}</math>, the Viterbi algorithm finds the most likely sequence of states that could have produced those observations. At each time step <math>t</math>, the algorithm solves the subproblem where only the observations up to <math>o_t</math> are considered.

Two matrices of size <math>T \times \left|{S}\right|</math> are constructed:
* <math>P_{t,s}</math> contains the maximum probability of ending up at state <math>s</math> at observation <math>t</math>, out of all possible sequences of states leading up to it.
* <math>Q_{t,s}</math> tracks the previous state that was used before <math>s</math> in this maximum probability state sequence.

Let <math>\pi_s</math> and <math>a_{r,s}</math> be the initial and transition probabilities respectively, and let <math>b_{s,o}</math> be the probability of observing <math>o</math> at state <math>s</math>. Then the values of <math>P</math> are given by the recurrence relation<ref>Xing E, slide 11.</ref>
<math display="block">
P_{t,s} =
\begin{cases}
\pi_s \cdot b_{s,o_t} & \text{if } t=0, \\
\max_{r \in S} \left(P_{t-1,r} \cdot a_{r,s} \cdot b_{s,o_t} \right) & \text{if } t>0.
\end{cases}
</math>
The formula for <math>Q_{t,s}</math> is identical for <math>t>0</math>, except that <math>\max</math> is replaced with [[Arg max|<math>\arg\max</math>]], and <math>Q_{0,s} = 0</math>.
The Viterbi path can be found by selecting the maximum of <math>P</math> at the final timestep, and following <math>Q</math> in reverse.