A Tree.Trellis Based Fast Search for Finding the N Best Sentence Hypotheses in Continuous Speech Recognition

A Tree.Trellis Based Fast Search for Finding the N Best Sentence Hypotheses in Continuous Speech Recognition Frank K. Soong Eng-Fong Huang* AT&T Bell Laboratories Murray Hill, New Jersey 07974 ABSTRACT In this paper a new, tree-trellis based fast search for finding the N best sentence hypotheses in continuous speech recognition is proposed. The search consists of two parts: a forward, time-synchronous, trellis search and a backward, time asynchronous, tree search. In the first module the well known Viterbi algorithm is used for finding the best hypothesis and for preparing a map of all partial paths scores time synchronously. In the second module a tree search is used to grow partial paths backward and time asynchronously. Each partial path in the backward tree search is rank ordered in a stack by the corresponding full path score, which is computed by adding the partial path score with the best possible score of the remaining path obtained from the trellis path map. In each path growing cycle, the current best partial path, which is at the top of the stack, is extended by one arc (word). The new tree-trellis search is different from the traditional time synchronous Viterbi search in its ability for finding not just the best but the N-best paths of different word content. The new search is also different from the A* algorithm, or the stack algorithm, in its capability for providing an exact, full path score estimate of any given partial (i.e., incomplete) path before its completion. When compared with the best candidate Viterbi search, the search complexities for finding the N- best strings are rather low, i.e., only a fraction more computation is needed. I. Introduction In a spoken language understanding (recognition) system, the search space of possible sentence hypotheses are determined by many factors such as the size of recognition vocabulary, the rigidity of grammar, the system dependency on specific speakers, etc. When these constraining factors are relaxed, the space can be very large and the effort for finding a global optimal hypothesis may become expensive or even prohibitive. Sometimes, even for a smaller scale problem, certain * On leave from Telecommunication Labs, Chung-li, Taiwan. language constraints can not be easily incorporated into a low level, acoustic search. For example, a check-sum grammar used for detecting error in a digit string, due to its nonlinear and modulo arithmetic nature, can not be built into a continuous digit recognizer except for some trivial cases. To reduce the search effort, a spoken language system is in general divided into two stages: a continuous speech recognition system followed by higher level language processing modules. First, the frame level acoustic information is processed by a continuous speech recognizer. The output of a continuous speech recognizer, sn'ings of symbols or words, are then fed into higher level language modules such as a sentence parser, semantic analysis modules, etc. for further processing. Unforttmately, such a division was usually done at a price of sacrificing the optimality of solutions and the final output, in …

Content truncated to 500 words