Computational Properties of Environment-based Disambiguation

Computational properties of environment-based disambiguation William Schuler Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19103 schuler@linc.cis.upenn.edu Abstract The standard pipeline approach to se- mantic processing, in which sentences are morphologically and syntactically resolved to a single tree before they are interpreted, is a poor fit for ap- plications such as natural language in- terfaces. This is because the environ- ment information, in the form of the ob- jects and events in the application’s run- time environment, cannot be used to in- form parsing decisions unless the in- put sentence is semantically analyzed, but this does not occur until after pars- ing in the single-tree semantic architec- ture. This paper describes the compu- tational properties of an alternative ar- chitecture, in which semantic analysis is performed on all possible interpre- tations during parsing, in polynomial time. 1 Introduction Shallow semantic processing applications, com- paring argument structures to search patterns or filling in simple templates, can achieve re- spectable results using the standard ‘pipeline’ ap- proach to semantics, in which sentences are mor- phologically and syntactically resolved to a single tree before being interpreted. Putting disambigua- tion ahead of semantic evaluation is reasonable in these applications because they are primarily run on content like newspaper text or dictated speech, where no machine-readable contextual informa- tion is readily available to provide semantic guid- ance for disambiguation. This single-tree semantic architecture is a poor fit for applications such as natural language inter- faces however, in which a large amount of contex- tual information is available in the form of the ob- jects and events in the application’s run-time en- vironment. This is because the environment infor- mation cannot be used to inform parsing and dis- ambiguation decisions unless the input sentence is semantically analyzed, but this does not occur until after parsing in the single-tree architecture. Assuming that no current statistical disambigua- tion technique is so accurate that it could not ben- efit from this kind of environment-based informa- tion (if available), then it is important that the se- mantic analysis in an interface architecture be ef- ficiently performed during parsing. This paper describes the computational prop- erties of one such architecture, embedded within a system for giving various kinds of conditional instructions and behavioral constraints to virtual human agents in a 3-D simulated environment (Bindiganavale et al., 2000). In one application of this system, users direct simulated maintenance personnel to repair a jet engine, in order to ensure that the maintenance procedures do not risk the safety of the people performing them. Since it is expected to process a broad range of maintenance instructions, the parser is run on a large subset of the Xtag English grammar (XTAG Research Group, 1998), which has been annotated with lex- ical semantic classes (Kipper et al., 2000) associ- ated with the objects, states, and processes in the maintenance simulation. Since the grammar has several thousand lexical entries, the parser is ex- posed to considerable lexical and structural ambi- guity as a matter …

Content truncated to 500 words