Computation of Upper-Bounds for Stochastic Context-Free Languages

Natural Language

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Perception

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 best 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.