Efficient, High-Performance Algorithms for N-Best Search

Efficient, High-Performance Algorithms for N-Best Search Richard Schwartz, Steve Austin BBN Systems and Technologies Inc. 10 Moulton St. Cambridge, MA, 02138 Abstract We present two efficient search algorithms for real-time spo- ken language systems. The first called the Word-Dependent N-Best algorithm is an improved algorithm for finding the top N sentence hypotheses. The new algorithm is shown to perform as well as the Exact Sentence-Dependent al- gorithm presented previously but with an order of mag- nitude less computation. The second algorithm is a fast match scheme for continuous speech recognition called the Forward-Backward Search. This algorithm, which is directly motivated by the Baum-Welch Forward-Backward training algorithm, has been shown to reduce the computation of a time-synchronous beam search by a factor of 40 with no additional search errors. 1. Introduction In a Spoken Language System (SLS) we must use all avail- able knowledge sources (KSs) to decide on the spoken sen- tence. While there are many knowledge sources, they are often grouped together into speech models, statistical lan- guage model, and natural language understanding models. To optimize accuracy we must choose the sentence that has the highest score (probability) given all of the KSs. This potentially requires a very large search space. The N-Best paradigm for integrating several diverse KSs has been de- scribed previously [2, 10]. First, we use a subset of the KSs to choose a small number of likely sentences. Then these sentences are scored using the remainder of the KSs. In Chow et. al., we also presented an efficient speech recognition search algorithm that was capable of comput- ing the N most likely sentence hypotheses for an utterance, given the speech models and statistical language models. However, this algorithm greatly increases the needed com- putation over that needed for finding the best single sen- tence. In this paper we introduce two techniques that dra- matically decrease the computation needed for the N-Best search. These algorithms are being used in a real-time SLS [1]. In the remainder of the introduction we review the exact N-Best search briefly and describe its problems. In Section 2 we describe two approximations to the exact algorithm and compare their accuracy with that of the exact algorithm. The resulting algorithm is still not fast enough for real- time implementation. In Section 3 we present a new sentence-level fast match scheme for continuous speech recognition. The algorithm is motivated by the mathematics of the Baum-Welch Forward-Backward training algorithm. The N-Best Paradigm The basic notion of the n-best paradigm is that, while we must ultimately use all the available KSs to improve recog- nition accuracy, the sources vary greatly in terms of per- plexity reduction and required complexity. For example, a first-order statistical language model can reduce perplex- ity by at least a factor of 10 with little computation, while applying complete natural language (NL) models of syn- tax and semantics to all partial hypotheses typically requires more computation for less perplexity reduction. (Murveit [6] has shown that the use of an efficiently implemented …

Content truncated to 500 words