A* STACK DECODING
Algorithm
- Best-first decoding
- Start with an estimate for the likelihood of the
utterance
- At each step, keep an ordered stack of possible
word extensions and find their likelihood
- Combine with likelihood estimate of the remainder
of the sentence, and select word that maximizes this score
Advantages
- Look-ahead provides major reduction in wasted
computation
- Search complexity is controlled easily
- State-tying
Limitations
- Requires explicit knowledge of word boundaries
- Look-ahead computation may offset gain
- Stack size does not have a bound