Search Algorithms for Software-Only Real-Time Recognition with Very Large Vocabularies

Search Algorithms for Software-Only Real-Time Recognition with Very Large Vocabularies Long Nguyen, Richard Schwartz, Francis Kubala, Paul Placeway BBN Systems & Technologies 70 Fawcett Street, Cambridge, MA 02138 ABSTRACT This paper deals with search algorithms for real-time speech recog- nition. We argue that software-only speech recognition has several critical advantages over using special or parallel hardware. We present a history of several advances in search algorithms, which together, have made it possible to implement real-time recogni- tion of large vocabularies on a single workstation without the need for any hardware accelerators. We discuss the Forward-Backward Search algorithm in detail, as this is the key algorithm that has made possible recognition of very large vocabularies in real-time. The result is that we can recognize continuous speech with a vocab- ulary of 20,000 words strictly in real-time entirely in software on a high-end workstation with large memory. We demonstrate that the computation needed grows as the cube root of the vocabulary size. 1. Introduction The statistical approach to speech recognition requires that we compare the incoming speech signal to our model of speech and choose as our recognized sentence that word string that has the highest probability, given our acoustic models of speech and our statistical models of language. The required computation is fairly large. When we realized that we needed to include a model of understanding, our estimate of the computational requirement was increased, because we assumed that it was necessary for all of the knowledge sources in the speech recognition search to be tightly coupled. Over the years DARPA has funded major programs in special-purpose VLSI and parallel computing environments specifically for speech recognition, because it was taken for granted that this was the only way that real-time speech recognition would be possible. However, these directions became major efforts in themselves. Using a small num- ber of processors in parallel was easy, but efficient use of a large number of processors required a careful redesign of the recognition algorithms. By the time high efficiency was obtained, there were often faster uniprocessors available. Design of special-purpose VLSI obviously requires consid- erable effort. Often by the time the design is completed, the algorithms implemented are obsolete and much faster gen- eral purpose processors are available in workstations. The result is that neither of these approaches has resulted in real- time recognition with vocabularies of 1,000 words or more. Another approach to the speech recognition search problem is to reduce the computation needed by changing the search algorithm. For example, IBM has developed a flexible stack- based search algorithm and several fast match algorithms that reduce the search space by quickly eliminating a large fraction of the possible words at each point in the search. In 1989 we, at BBN [1], and others [2, 3] developed the N-best Paradigm, in which we use a powerful but inexpen- sive model for speech to find the top N sentence hypotheses for an utterance, and then we rescore each of these hypothe- ses with more complex …

Content truncated to 500 words