Efficiency of Viterbi Algorithm

Question

Considering that we have a sequence of observed states $\{y_1, y_2, \dots, y_T \}$ of length $T$.

We want to generate a path $\{x_1, x_2, \dots, x_T\}$, which is a sequence of states $x_n \in S = \{s_1, s_2, \dots, s_K\}$, that is, each $x_i$ can assume $K$ different values.

One lazy solution would be to evaluate the probability of each sequence and keep the one with the highest likelihood. This would require us to evaluate the probability of $K^N$ different sequences.

What if we use the Viterbi Algorithm? Given that it eliminates sequences along the way, how many different sequences we would be evaluating?

Answer 1

In a Hidden Markov Model, the Viterbi algorithm is the right way to find the highest-probability sequence of hidden states $\bf x$, given your sequence of observations $\bf y$. It will find an exact solution (not an approximation) in time $O(TK^2)$ instead of the $O(K^T)$ that you'd suffer with the brute force solution.

Given that it eliminates sequences along the way, how many different sequences we would be evaluating?

It prunes candidates that cannot have the highest probability, without fully forming the path. In a sense, every sequence is evaluated.

But you never fully materialize any of these until the backward pass of Viterbi. Along the way, you just keep $K$ partial paths for each $y_i$. These are the best paths ending at each of the $K$ possible values of $x_i$.