Optimal search strategies for speech understanding control

摘要

This paper describes two algorithms for finding the optimal interpretation of an unknown utterance in a continuous speech understanding system. These methods guarantee that the first complete interpretation found will be the best scoring interpretation possible. Moreover, unlike other optimal strategies, they do not make finite-state assumptions about the nature of the grammar for the language being recognized. One of the methods, the density method, is especially interesting because it is not an instance of the ‘optimal’ A∗ algorithm of Hart, Nilsson, and Raphael, and appears to be superior to it in the domains in which it is applicable. The other method, the shortfall method, is an instance of the A∗ algorithm using a particular heuristic function. Proofs of the guaranteed discovery of the best interpretation and some empirical comparisons of the methods are given. The relationship of these methods to strategies used in existing speech understanding systems is also discussed. Although presented in the speech context, the algorithms are applicable to a general class of optimization and heuristic search problems.