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.
