Computation of Upper-Bounds for Stochastic Context-Free Languages

Abstract

Automatic speech understanding and automatic speech recognition extract different kinds of information from the input signal. The result of the former must be evaluated on the basis of the response of the system while the result of the latter is the word sequence which matches the input signal. In both cases search has to be performed based on scores of interpretation hypotheses. A scoring method is presented based on stochastic context-free grammars. The method gives optimal upper-bounds for the computation of the best derivation trees of a sentence. This method allows language models to be built based on stochastic context-free grammars and their use with an admissible search algorithm that interprets a speech signal with left-to-right or middle-out strategies. Theoretical and computational aspects are discussed.