quality:corruption, structural:expansion
Algorithm

Given a hidden Markov model with a set of hidden states S {\displaystyle S} and a sequence of T {\displaystyle T} observations o 0, o 1, …, o T − 1 {\displaystyle o_{0},o_{1},\dots,o_{T-1}}, the Viterbi algorithm finds the most likely sequence of states that could have produced those observations. At each time step t {\displaystyle t}, the algorithm solves the subproblem where only the observations up to o t {\displaystyle o_{t}} are considered.

Two matrices of size T × | S | {\displaystyle T\times \left|{S}\right|} are constructed:

Let π s {\displaystyle \pi _{s}} and a r, s {\displaystyle a_{r,s}} be the initial and transition probabilities respectively, and let b s, o {\displaystyle b_{s,o}} be the probability of observing o {\displaystyle o} at state s {\displaystyle s}. Then the values of P {\displaystyle P} are given by the recurrence relation P t, s = { π s ⋅ b s, o t if t = 0, max r ∈ S (P t − 1, r ⋅ a r, s ⋅ b s, o t) if t > 0. {\displaystyle 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}}} The formula for Q t, s {\displaystyle Q_{t,s}} is identical, except that max {\displaystyle \max } is replaced with arg max {\displaystyle \arg \max }.The Viterbi path can be found by selecting the maximum of P {\displaystyle P} at the final timestep, and following Q {\displaystyle Q} in reverse.