Algorithms for an Optimal A* Search and Linearizing the Search in the Stack Decoder*

Algorithms for an Optimal A* Search and Linearizing the Search in the Stack Decoder. Douglas B. Paul Lincoln Laboratory, MIT Lexington, Ma. 02173 Abstract The stack decoder is an attractive algorithm for con- trolling the acoustic and language model matching in a continuous speech recognizer. It implements a best-first tree search of the language to find the best match to both the language model and the observed speech. This paper describes a method for performing the optimal A* search which guarantees to find the most likely path (rec- ognized sentence) while extending the minimum number of stack entries. A tree search, however, is exponential in the number of words. A second algorithm is presented which linearizes the search at the cost of approximating some of the path likelihoods. Introduction Speech recognition may be treated as a tree network search problem. As one proceeds from the root toward the leaves, the branches leaving each junction represent the set of words which may be appended to the cur- rent partial sentence. Each of the branches leaving a junction has a probability and each word has a likeli- hood of being produced by the observed acoustic data. The recognition problem is to identify the most likely path (word sequence) from the root (beginning) to a leaf (end) taking into account the junction probabilities (the stochastic language model) and the optimum acoustic match (including time alignment) given that path. This paper is concerned with the network search prob- lem and therefore correct recognition is defined as out- putting the most likely sentence given the language model, the acoustic models, and the observed acoustic data. If the most likely sentence is not the one spoken, that is a modeling error--not a search error. This pa- per will assume for simplicity that an isolated sentence is the object to be recognized. (The stack decoder can be extended to recognize continuous sentences.) The stack decoder [4], as used in speech, is an imple- mentation of a best-first tree search. The basic operation of a sentence decoder is as follows [1, 2]: 1. Initialize the stack with a null theory. *This work was sponsored by the Defense Advanced Research Projects Agency. 2. Pop the best (highest score) theory off the stack. 3. if(end-of-sentence) output sentence and terminate. 4. Perform acoustic and language-model fast matches to obtain a short list of candidate word extensions of the theory. 5. For each word on the candidate list: (a) Perform acoustic and language-model detailed matches and add the log-likelihoods to the the- ory log-likelihood. i. if(not end-of-sentence) insert into stack. ii. if(end-of-sentence) insert into stack with end-of-sentence flag = TRUE. (note: end-of-sentence may be optional) 6. Go to 2. The fast matches [2] are computationally cheap meth- ods for reducing the number of word extensions which must be checked by the more accurate, but computa- tionally expensive detailed matches) (The fast matches may also be considered a predictive component for the detailed matches.) Top-N mode is achieved by delaying termination until N …

Content truncated to 500 words