Shortfall and Density Scoring Strategies for Speech Understanding Control

Abstract

This note describes two methods of assigning priority scores top artially developed hypotheses about a speech utterance for determining which hypotheses to extend further. These methods guarantee the discovery of the best matching interpretation of the utterance, when used in an appropriate control framework. Although presented in the speech context, the algorithms are applicable to a general class of optimization and heuristic search problems. The density method is especially interesting since it is not an instance of the general A, algorithm of Hart, Nilsson, and Raphael, and appears to be superior to it in the domains in which it is applicable. Proofs of the guaranteed discovery of the best interpretation and some empirical comparisons of the methods are given.