Beam Search Decoding
Compare bounded beam decoding with exhaustive path probabilities, deterministic tie-breaking and zero-probability branches.
Free theory articleCompare bounded beam decoding with exhaustive path probabilities, deterministic tie-breaking and zero-probability branches.
Concept & interpretation
Beam Search is a heuristic search algorithm that explores a graph by expanding the most promising nodes in a limited set. In sequence decoding, it approximates the maximum joint probability path without exhaustive enumeration.
Experimenting with Beam Width
You can use the Beam Search Decoding module to verify how the beam width affects the final selected sequence.
- Set the Beam width control to
1. - Set the Output length control to
2. - Set the Transition table control to
Greedy trap. - Observe that the selected sequence is
AA(probability 3/10), while the exhaustive best sequence isBA(probability 99/250). - Now, increase the Beam width control to
2. - Observe that the selected sequence is now
BA, successfully matching the exhaustive best sequence, because the branchBwas retained at the first step.