Dependency Parsing with an Extended Finite State Approach

Dependency Parsing with an Extended Finite State Approach Kemal Oflazer Department of Computer Engineering Bilkent University Ankara, 06533,Turkey ko©cs, bilkent, edu. tr Computing Research Laboratory New Mexico State University Las Cruces, NM, 88003 USA ko@crl, nmsu. edu Abstract This paper presents a dependency parsing scheme using an extended finite state approach. The parser augments input representation with "channels" so that links representing syntactic dependency rela- tions among words can be accommodated, and it- erates on the input a number of times to arrive at a fixed point. Intermediate configurations violating various constraints of projective dependency repre- sentations such as no crossing links, no independent items except sentential head, etc, are filtered via fi- nite state filters. We have applied the parser to de- pendency parsing of Turkish. 1 Introduction Recent advances in the development of sophisticated tools for building finite state systems (e.g., XRCE Finite State Tools (Karttunen et al., 1996), ATgzT Tools (Mohri et al., 1998)) have fostered the develop- ment of quite complex finite state systems for natu- ral language processing. In the last several years, there have been a number of studies on develop- ing finite state parsing systems, (Koskenniemi, 1990; Koskenniemi et al., 1992; Grefenstette, 1996; Ait- Mokhtar and Chanod, 1997). There have also been a number of approaches to natural language pars- ing using extended finite state approaches in which a finite state engine is applied multiple times to the input, or various derivatives thereof, until some stop- ping condition is reached. Roche (1997) presents an approach for parsing in which the input is itera- tively bracketed using a finite state transducer. Ab- ney(1996) presents a finite state parsing approach in which a tagged sentence is parsed by transducers which progressively transform the input to sequences of symbols representing phrasal constituents. This paper presents an approach to dependency parsing using an extended finite state model resembling the approaches of Roche and Abney. The parser pro- duces outputs that encode a labeled dependency tree representation of the syntactic relations between the words in the sentence. We assume that the reader is familiar with the basic concepts of finite state transducers (FST here- after), finite state devices that map between two reg- ular languages U and L (Kaplan and Kay, 1994). 2 Dependency Syntax Dependency approaches to syntactic representation use the notion of syntactic relation to associate sur- face lexical items. The book by Mel~uk (1988) presents a comprehensive exposition of dependency syntax. Computational approaches to dependency syntax have recently become quite popular (e.g., a workshop dedicated to computational approaches to dependency grammars has been held at COL- ING/ACL'98 Conference). J~irvinen and Tapana- ninen have demonstrated an efficient wide-coverage dependency parser for English (Tapanainen and J~irvinen, 1997; J£rvinen and Tapanainen, 1998). The work of Sleator and Temperley(1991) on link grammar, an essentially lexicalized variant of depen- dency grammar, has also proved to be interesting in a number of aspects. Dependency-based statistical language modeling and analysis have also become quite popular in statistical natural language process- ing (Lafferty …

Content truncated to 500 words