Three New Probabilistic Models for Dependency Parsing: An Exploration

Three New Probabilistic Models for Dependency Parsing: An Exploration* Jason M. Eisner CIS Department, University of Pelmsylvaifia. 200 S. 33rd St., Philadelphia, PA 19104-6"{89, USA j eisner@linc, cis. upenn, edu Abstract Alter presenting a novel O(n a) parsing al- gorithm for dependency grammar, we de- velop three contrasting ways to stochasticize it. We propose (a) a lexical atfinity mode] where words struggle to modify each other, (b) a sense tagging model where words tluc- tuate randomly in their selectional prefer- ences, and (e) a. generative model where the speaker fleshes ()tit each word's syntactic and concep{.ual structure without regard to the implications :for the hearer. W(! also give preliminary empirical results from evaluat- ing the three models' p;Lrsing performance on annotated Wall Street Journal trMning text (derived fi'om the Penn Treebank). in these results, the generative model performs significantly better than the others, and does about equally well at assigning pa.rt- of-speech tags. 1 Introduction In recent years, the statistical parsing community has begun to reach out; for syntactic formalisms that recognize the individuality of words, l,ink grammars (Sleator and 'Pemperley, 1991) and lex- icalized tree-adjoining granunars (Schabes, 1992) have now received stochastic treatments. Other researchers, not wishing to abandon context-flee grammar (CI"G) but disillusioned with its lexica] blind spot, have tried to re-parameterize stochas- tic CI"G in context-sensitive ways (Black et al., 1992) or have augmented the formalism with lex- ical headwords (Magerman, 1995; Collins, 11996). In this paper, we 1)resent a [lexible l)robat)ilistic parser that simultaneously assigns both part-of- sl)eech tags and a bare-bones dependency struc- ture (illustrate.d in l!'igure 1). The choice ot'a simple syntactic structure is deliberate: we would like to ask some basic questions about where h'x- ical relationships al)pear and how best, to exploit *This materia.l is based upon work supported un- der a National Science I%undation Graduate Fellow- ship, and has benefited greatly from discussions with Mike Collins, Dan M(:lame(l, Mitch Marcus and Ad- wait Ratnaparkhi. (a) Tile man in the coiner taught his dachsht,ld IO play golf I';OS DT NN IN DT NN VBD PP.P$ NN TO VH NN /¢ man N ~.. phty~ j J-y, .% (b) The ill __ ~ /.~dachshund It) golf .)f COfllel his file Figure 1: (a) A bare-l>ones dependen(-y parse. ]']a<:h word points to a single t)arent, the word it modities; the head of the sentence points to the EOS (end-of: sentence) ma.rk. Crossing links and cycles arc not al- lowed. (b) Constituent structure and sub(:ategoriza- tion may be highlighted by displaying the same de- pendencies as a lexical tree. them. It is uscflfl to look into thes0 basic ques- tions before trying to tine-tmm the performance of systems whose behavior is harder to understand. 1 The main contribution of' the work is to I)ro- pose three distin('t, lexiealist hyl)otheses abou(. (,he probability space underlying seHl]ence structure. We il]ustrate how each hypothesis is (:xl)ressed in a depemteney framework, and how each can be used to guide our parser toward its favored so- lution. Finally, we point …

Content truncated to 500 words