Continuous speech recognition based on A* search with word‐pair constraint as heuristics
Tatsuya Kawahara, Shuji Doshita, Shinji Matsumoto · Systems and Computers in Japan · 1994
Abstract This paper proposes an A* search algorithm for continuous speech recognition using phoneme HMM and Context‐Free (LR) parser. This best‐first search evaluates each sentence hypothesis with the matching score plus the heuristic score of the unsearched part. Heuristics computation is based on word‐pair constraint that is common to all the hypotheses. Word‐pair constraint, which is not computationally expensive, satisfies A*‐admissibility and provides powerful heuristics. The algorithm is guaranteed to obtain the optimal hypothesis and does not expand vain hypotheses very much. Compared with various kinds of beam search, therefore, it achieved better accuracy with less computation. This heuristics proved to be effective for beam search, too. Furthermore, it was implemented on stochastic grammar and some improved was obtained.