The Viterbi algorithm is one of most common decoding algorithms for HMM. Its goal is to find the most likely hidden state sequence corresponding to a series of observations. The structure is very similar to the forward algorithm, but instead of computing the probability of a sequence of observations joined with the state at the last time instant, this algorithm looks for:

The variable v_tⁱ represents that maximum probability of the given observation sequence joint with x_t = i, considering all possible hidden state paths (from time instant 1 to t-1). We can compute v_tⁱ recursively by evaluating all the v_t-1^j multiplied by the corresponding transition probabilities p_ji and emission probability P(o_t|x_i), and always picking the maximum overall possible values of j:

The algorithm is based on a backtracking approach, using a backpointer bp_tⁱ whose recursive expression is the same as v_tⁱ, but with the argmax function instead of max:

Therefore, bp_tⁱ represents the partial sequence of hidden states x₁, x₂, ..., x_t-1 that maximizes v_tⁱ. During the recursion, we add the timesteps one by one, so the previous path could be invalidated by the last observation. That's why we need to backtrack the partial result and replace the sequence built at time t that doesn't maximize v_t+1ⁱ anymore.

The algorithm is based on the following steps (like in the other cases, the initial and ending states are not emitting):

1. Initialization of a vector V with shape (N + 2, Sequence Length).
2. Initialization of a vector BP with shape (N + 2, Sequence Length).
3. Initialization of A (transition probability matrix) with shape (N, N). Each element is P(x_i|x_j).
4. Initialization of B with shape (Sequence Length, N). Each element is P(o_i|x_j).
5. For i=1 to N:
   1. Set V[i, 1] = A[i, 0] · B[1, i]
   2. BP[i, 1] = Null (or any other value that cannot be interpreted as a state)
6. For t=1 to Sequence Length:
   1. For i=1 to N:
      1. Set V[i, t] = max_j V[j, t-1] · A[j, i] · B[t, i]
      2. Set BP[i, t] = argmax_j V[j, t-1] · A[j, i] · B[t, i]
7. Set V[x_Endind, Sequence Length] = max_j V[j, Sequence Length] · A[j, x_Endind].

8. Set BP[x_Endind, Sequence Length] = argmax_j V[j, Sequence Length] · A[j, x_Endind].
9. Reverse BP.

The output of the Viterbi algorithm is a tuple with the most likely sequence BP, and the corresponding probabilities V.