Chart Parsing of Stochastic Spoken Language Models

Chart Parsing of Stochastic Spoken Language Models Charles Hemphill and Joseph Picone Texas Instruments Speech and Image Understanding Laboratory P.O. Box 655474, MS 238 Dallas, Texas 75265, USA Abstract Performance in speech recognition systems has progressed to the point where it is now realistic to begin integrating speech with natural language systems to produce spoken language systems. Two factors have contributed to the advances in speech: statistical modeling of the input signal and language constraints. To produce spoken language systems, then, the grammar formalisms used in natural language systems must incorporate statistical information and efficient parsers for these stochastic language models must be developed. In this paper we outline how chart parsing techniques provide advantages in both computation and accuracy for spoken language systems. We describe a system that models all levels of the spoken language system using stochastic language models and present experimental results. Introduction Speech technology has recently made tremendous progress toward speaker-independent large-vocabulary speech recognition (e.g., Lee and Hon, 1988). These sorts of systems rely on Hidden Markov Models (HMMs) of the speech signal and language constraints of the application to achieve good performance. It is important to observe that the language model provides top-down information to reduce the search space during pro- cessing. Kubala et al (1988) have shown that the perplexity (roughly the number of choices) of the language model correlates with recognition performance. Because of the tendency for Finite State language models to drastically increase in perplexity as coverage increases, it is unlikely that these systems will extend to spoken language systems. Natural language technology has steadily moved toward the unification grammar paradigm (Shieber, 1986). These formalisms allow various kinds of agreement by generalizing the notion of a grammar symbol to include features and variables. This approach offers advantages in elegantly integrating syntax, semantics and pragmatics while providing domain independence (Mani and Hemphill, 1988). The combination of these constraints during sentence processing can be used to greatly reduce perplexity, but unification grammars have not yet been integrated with speech systems. To do this, the parser must support stochastic grammars (grammars with rule probabilities), comprehend probabilistic hypotheses, and operate frame-synchronously to mesh with the speech system. Various bottom-up approaches to combining speech and natural language have been tried (e.g., Tomita, 1986). These systems suffer from many problems: top-down information is not available for lower levels, separate grammars must be used for both systems, missing words in the word lattice prove fatal, and probability is usually not available for pruning. Ney (1987) describes a combined top-down and bottom-up approach using the CYK algorithm, but this algorithm has bad average time complexity (the number of input frames cubed). 250 Our experience with unification grammars has shown us that word hypotheses may be efficiently produced during sentence processing (Hemphill et al, 1987). To facilitate integration with speech, we have developed a chart parser specialized to process N levels of stochastic regular grammars. This enables a conceptual shift from the paths and state probabilities found in current systems to …

Content truncated to 500 words