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