Three New Probabilistic Models for Dependency Parsing: An Exploration

By Jason Eisner. 1996

After presenting a novel O(n3) parsing algorithm for dependency grammar, we develop three contrasting ways to stochasticize it. We propose (a) a lexical affinity model where words struggle to modify each other, (b) a sense tagging model where words fluctuate randomly in their selectional preferences, and (c) a generative model where the speaker fleshes out each word's syntactic and conceptual structure without regard to the implications for the hearer. We also give preliminary empirical results from evaluating the three models' parsing performance on annotated Wall Street Journal training text (derived from the Penn Treebank). In these results, the generative model performs significantly better than the others, and does about equally well at assigning part-of-speech tags.

Subfields: Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Structured Attention Networks (2017, methodology): “It is possible to calculate the marginal probability of each edge p ( z ij = 1 | x, q ) for all i, j in O ( n 3 ) time using the inside-outside algorithm (Baker, 1979) on the data structures of Eisner (1996).”
Head-Driven Statistical Models for Natural Language Parsing (2003, methodology): “Eisner (1996b) originally used POS tags to smooth a generative model in this way.”
Easy-First Dependency Parsing with Hierarchical Tree LSTMs (2016, background): “ional RNN) may prove to work better. We leave this line of inquiry to future work. The head-outward modiﬁer generation approach has a long history in the parsing literature, and goes back to at least Eisner (1996) and Collins (1997). In contrast to previous work in which each modiﬁer could condition”
Non-Projective Dependency Parsing using Spanning Tree Algorithms (2005, methodology): “This formalization generalizes standard projective parsing models based on the Eisner algorithm (Eisner, 1996) to yield efﬁcient O ( n 2 ) exact parsing methods for non-projective languages like Czech.”
Algorithms for Deterministic Incremental Dependency Parsing (2008, methodology): “…recent years been used primarily in data-driven models, which learn to produce dependency structures for sentences solely from an annotated corpus, as in the work of Eisner (1996), Yamada and Matsumoto (2003), Nivre, Hall, and Nilsson (2004), and McDonald, Crammer, and Pereira (2005), among others.”
CoNLL-X Shared Task on Multilingual Dependency Parsing (2006, methodology): “(12)Many thanks to the SDT people for granting the special license for CoNLL-X and to Tomaž Erjavec for converting the Danish Dependency Treebank 13 (Kromann, 2003); Swedish: Talbanken05 14 (Teleman, 1974; Einarsson, 1976; Nilsson et al., 2005); Turkish : MetuSabancı treebank 15 (Oflazer et al.”
Intricacies of Collins’ Parsing Model (2004, background): “(cid:4) (cid:153) (cid:230) (cid:4) (cid:230) Bilexical statistics (Eisner, 1996), as represented by the maximal context of the and (cid:157) parameters, serve as a proxy for such semantic preferences, where the actual modi(cid:2)er word (as opposed to, say, merely its part of speech) serves to…”
Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT (2020, methodology): “Next, two parsing algorithms, namely, the Eisner algorithm (1996) and Chu-Liu/Edmonds (CLE) algorithm (1965; 1967), are utilized to extract the projective and non-projective unlabeled dependency trees, respectively.”
The Inside-Outside Recursive Neural Network model for Dependency Parsing (2014, methodology): “In the original models (Eisner, 1996a), each dependent D is a 4-tuple h dist, w, c, t • dist ( H, D ) the distance between D and its head H , represented as one of the four ranges 1, 2, 3-6, 7-∞ .”
Dependency Parsing by Belief Propagation (2008, methodology): “These are passed into a fast algorithm for maximum spanning tree (Tarjan, 1977) or maximum projective spanning tree (Eisner, 1996).”
Phrase Dependency Machine Translation with Quasi-Synchronous Tree-to-Tree Features (2014, methodology): “We begin with features based on the quasi-synchronous configurations from Smith and Eisner (2006), shown for lexical dependency trees in Figure 8.”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, background): “One of the earliest graph-based dependency parsing models (Eisner, 1996) is generative, estimating the probability of dependents given their head and previously generated siblings.”