Lexicalized Semi-incremental Dependency Parsing

International Conference RANLP 2009 - Borovets, Bulgaria, pages 128–134 Lexicalized Semi-Incremental Dependency Parsing Hany Hassan Khalil Sima’an Andy Way Cairo TDC Language and Computation School of Computing IBM University of Amsterdam Dublin City University Cairo, Egypt Amsterdam, The Netherlands Dublin, Ireland hanyh@eg.ibm.com k.simaan@uva.nl away@computing.dcu.ie Abstract Even leaving aside concerns of cognitive plausibil- ity, incremental parsing is appealing for applications such as speech recognition and machine translation be- cause it could allow the incorporation of syntactic fea- tures into the decoding process without blowing up the search space. Nevertheless, incremental parsing is of- ten associated with greedy parsing decisions and intol- erable loss of accuracy. Would the use of lexicalized grammars provide a new perspective on incremental parsing? In this paper we explore incremental left-to-right de- pendency parsing using a lexicalized grammatical for- malism that works with lexical categories (supertags) and a small set of combinatory operators. A strictly incremental parser would conduct only a single pass over the input, use no lookahead and make only local decisions at every word. We show that such a parser suffers heavy loss of accuracy. Instead, we explore the utility of a two-pass approach that incrementally builds a dependency structure by first assigning a su- pertag to every input word and then selecting an incre- mental operator that allows assembling every supertag with the dependency structure built thus far to its left. We instantiate this idea in different models that al- low a trade-off between aspects of full incrementality and performance, and explore the differences between these models empirically. Our exploration shows that a semi-incremental (two-pass), linear-time parser that employs fixed and limited look-ahead exhibits an ap- pealing balance between the efficiency advantages of incrementality and the achieved accuracy. Surpris- ingly, taking local or global decisions matters very lit- tle for the accuracy of this linear-time parser. Such a parser fits seamlessly with the currently dominant finite-state decoders for machine translation. 1 Introduction As it processes an input sentence word-by-word in some order (e.g., left-to-right for a language like English), an in- cremental parser builds for each prefix of the input sentence a partial parse that is a subgraph of the partial parse that it builds for a longer prefix. An incremental parser may have access only to a fixed, limited window of lookahead words. The lookahead is equivalent to buffering a number of words before processing them; as stated by [Marcus et. al., 1983], a deterministic parser can buffer and examine a small num- ber of words before adding them to the existing structure. A parser might also make multiple incremental passes over the input sentence where decisions made in an earlier pass are refined in a subsequent pass. In this paper we refer to an incremental, left-to-right parser without lookahead in- formation taking a single pass over the input as a fully in- cremental parser. We refer to an incremental left-to-right parser with limited lookahead capability as a weakly in- cremental parser. And when the incremental parser makes two passes over the …

Content truncated to 500 words