An Efficient A* Stack Decoder Algorithm for Continuous Speech Recognition with a Stochastic Language Model

An Efficient A* Stack Decoder Algorithm for Continuous Speech Recognition with a Stochastic Language Model* Douglas B. Paul Lincoln Laboratory, MIT Lexington, Ma. 02173 ABSTRACT The stack decoder is an attractive algorithm for controlling the acoustic and language model matching in a continuous speech recognizer. A previous paper described a near-optimal admissible Viterbi A* search algorithm for use with non- cross-word acoustic models and no-grammar language models [16]. This paper extends this algorithm to include unigram language models and describes a modified version of the algo- rithm which includes the full (forward) decoder, cross-word acoustic models and longer-span language models. The resul- tant algorithm is not admissible, but has been demonstrated to have a low probability of search error and to be very effi- cient. 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 current partial sentence. Each of the branches leaving a junc- tion has a probability and each word has a likelihood of being produced by the observed acoustic data. The recognition problem is to identify the most likely path (word sequence, W*) from the root (beginning of the sentence) to a leaf (end of the sentence) taking into ac- count the junction probabilities (the stochastic language model, p(W)) and the acoustic match (including time alignment, p(OIW)) given that path [2]: W* =argmax p( OIW)p (W) (1) (w} where O is the acoustic observation sequence and W is a word sequence. This paper is concerned with the network search prob- lem and therefore correct recognition is defined as out- putting the most likely sentence W* given the language model, the acoustic models, and the observed acoustic data. If the most likely sentence is not the one spoken, it is a modeling error--not a search error. This paper *This work was sponsored by the Defense Advanced Research Projects Agency. The views expressed are those of the author and do not reflect the official policy or position of the U.S. Government. will assume for simplicity that an isolated sentence is the object to be recognized. (The algorithm extends trivially to recognize continuous input.) THE BASIC STACK DECODER The stack decoder [8], as used in speech, is an implemen- tation of a best-first tree search. The basic operation of a sentence decoder is as follows [2,5]: 1. Initialize the stack with a null theory. 2. Pop the best (highest scoring) theory off the stack. 3. if(end-of-sentence) output the sentence and termi- nate. 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 to compute the new theory output log- likelihood. i. if(not end-of-sentence) insert into the stack. ii. if(end-of-sentence) insert into the stack with end-of-sentence flag = TRUE. 6. Go to 2. The fast matches [4,5,7] are computationally cheap …

Content truncated to 500 words