ITSVOX

A Controlled Skip Parser Kenji Yamada kyamada@isi.edu USC/Information Sciences Institute Abstract Real-world natural language sentences are long and complex, and always contain unexpected grammatical constructions. It even includes noise and ungrammaticality. This paper describes the Controlled Skip Parser, a program that parses such real-world sentences by skipping some of the words in the sentence. The new feature of this parser is that it can control its behavior to find out which words to skip, without using domain-specific knowledge. Statistical information (N-grams), which is a generalized approximation of the grammar learned from past successful experiences, is used for the controlled skip. Experiments on real newspaper articles are shown, and our experience with this parser in a machine translation system is described. 1 Introduction Parsing real-world natural language text is a difficult task. The difficulty comes from several sources. One is that a real-world sentences are long and complex, especially in newspaper articles. The average length of a sentence is 20 to 30 words, and it often exceeds 100 words. The sentence structure is complex and syntactically ambiguous due to the frequent usage of relative clauses, appositives, disjunctions, and other constructions. Also, there are always unexpected syntactic phenomena in real-world texts, which are beyond the formal grammar's coverage. Another difficulty conies from noise and ill-formedness of the input, typically in spoken language. Interjected words (ah, well), false starts (I'd like to do you have any flights from ...), or errors in speech recognition devices make parsing with a rigid grammar impossible. This kind of noise and ill-formedness is also seen in written text, for example, misspelled words, unbalanced parentheses, incorrect punctuation, symbol characters, and special formatting characters which fail to be filtered by text preprocessing modules. One extreme way to deal with these difficulties is to abandon syntactic analysis completely, instead relying purely on statistics for machine translation [Brown, et al. 1990], or using template matching for information extraction [Jackson, et al. 1991]. With these methods, no grammar rules are used, and no analysis of syntactic and semantic structure of sentences is performed. Target translation or extracted information is directly obtained from the surface input, using context sensi- tive word-by-word translation statistics or target-dependent database templates. These approaches, however, cannot fully utilize the semantic and pragmatic knowledge even when the syntactic struc- ture is easy to parse. When domain-specific semantic and pragmatic knowledge is available, a certain level of loose syntactic analysis has been shown to be useful, such as in [McDonald 1992], [Hobbs, et al. 1992], [Seneff 1992], and [Stallard and Bobrow 1993]. In these systems, a regular parser first attempts to parse a sentence, and when the parser fails, the parse fragments, which represent syntactic structure of parts of the sentence, are combined together using domain-specific semantics and pragmatics. 14 The upper tree is the result of parsing with two words skipped. The lower trees are from a non-skipping parser, producing 10 fragments. The meaning of those fragments (from left) are; 1. According to a source near the president, 2. …

Content truncated to 500 words