What is the difference between the Viterbi algorithm and beam search?

Question

I'm just confused because I'm having trouble wrapping my head around the difference. If we were to set the beam size to be equal to the number of possible states, wouldn't that mean the beam search algorithm is equivalent to the Viterbi algorithm?

The only true difference I can think of between the two is that beam search is not guaranteed to find the optimal solution whereas the Viterbi algorithm is. However, and assuming computing power isn't an issue, if we set the beam size to be equivalent to the output space, then wouldn't we also eventually find an optimal solution?

Answer 1

Yes, you're exactly right. If you set the beam size equal to the size of the HMM or CRF's state space (which is what I assume you meant by 'output space'), then you're guaranteed to find the optimal solution. This is because your search is now exhaustive.

The beam size is the number of candidates to expand in your search, as you move through the time series. If you expand all of them, then this is the Viterbi algorithm.

---

Recall that the time complexity of the Viterbi algorithm is $O(TN^2)$, where $T$ is the length of the time series, and $N$ is the size of the state space. The fact that this scales quadratically is what motivates beam search: reduce that $N^2$ to $K^2$ for some $K \ll N$, at the cost of exactness. If the state space is small, that's not a big improvement. But if thousands of states are possible (as with a WFSA language model), then this can make a big difference.

Answer 2

If we were to set the beam size to be equal to the number of possible states, wouldn't that mean the beam search algorithm is equivalent to the Viterbi algorithm?

Beam Search

• Choose beam of B hypotheses
• Do Viterbi algorithm, but keep only best B hypotheses at each step
• Definiton of "step" depends on task:
  • Tagging: Same number of words tagged
  • Machine Translation: Same number of words translated
  • Speech Recognition: Same number of frames processed

Source: NLP Programming Tutorial 13 - Beam and A* Search by professor Graham Neubig

Then the reverse is the process of converting beam search into Viterbi.

if we set the beam size to be equivalent to the output space, then wouldn't we also eventually find an optimal solution?

The optimal path guarantee is due to the Generalized Distributive Law(or refer to this).

Because in Beam Search some unpromising parts of search space are pruned, and then we cannot apply the Generalized Distributive Law, and hence it can not guarantee an optimal path. Along the same line, if all the search space is considered the optimal path can be led to.