An Efficient Distribution of Labor in a Two Stage Robust Interpretation Process

An Efficient Distribution of Labor in a Two Stage Robust Interpretation Process Carolyn Penstein Ros6 Carnegie Mellon University Baker Hall 135F Pittsburgh, PA 15213 cprose@cs.cmu.edu Alon Lavie Carnegie Mellon University Center for Machine Translation Pittsburgh, PA 15213 alavie~cs.cmu.edu Abstract Although Minimum Distance Parsing (MDP) offers a theoretically attractive so- lution to the problem of extragrammat- icality, it is often computationally infea- sible in large scale practical applications. In this paper we present an alternative ap- proach where the labor is distributed be- tween a more restrictive partial parser and a repair module. Though two stage ap- proaches have grown in popularity in re- cent years because of their efficiency, they have done so at the cost of requiring hand coded repair heuristics (Ehrlich and Han- rieder, 1996; Danieli and Gerbino, 1995). In contrast, our two stage approach does not require any hand coded knowledge sources dedicated to repair, thus making it possible to achieve a similar run time advantage over MDP without losing the quality of domain independence. 1 Introduction The correct interpretation of spontaneous spoken language poses challenges that continue to fall out- side of the reach of state-of-the-art technology. The first essential task of a natural language interface is to map the user's utterance onto some meaning rep- resentation which can then be used for further pro- cessing. The three biggest challenges that continue to stand in the way of accomplishing even this most basic task are extragrammaticality, ambiguity, and speech recognition errors. In this paper we address the issue of how to handle the problem of extra- grammaticality efficiently, where extragrammatical- ity is defined as any deviation of an input string from the coverage of a given system's parsing grammar. We demonstrate the superiority of our approach by comparing performance between it and a set of alter- native approaches in terms of parse time and parse quality over the same previously unseen test corpus. The approach presented in this paper is the com- 26 pletely automatic portion of the ROSE 1 approach. ROSE, RObustness with Structural Evolution, re- pairs extragrammatical input in two phases. The first phase, Repair Hypothesis Formation, is re- sponsible for assembling a set of hypotheses about the meaning of the ungrammatical utterance. This phase is itself divided into two stages, Partial Pars- ing and Combination. A restricted version of Lavie's GLR* parser (Lavie, 1995; Lavie and Tomita, 1993) is used to obtain an analysis of islands of the speaker's sentence in cases where it is not possible to obtain an analysis for the entire sentence. In the Combination stage, the fragments from the partial parse are assembled into a set of alternative meaning representation hypotheses. A genetic programming approach is used to search for different ways to com- bine the fragments in order to avoid requiring any hand-crafted repair rules. In ROSE's second phase, Interaction with the User, the system generates a set of queries, negotiating with the speaker in order to narrow down to a single best meaning representa- tion hypothesis. In …

Content truncated to 500 words