Probabilistic Models of Nonprojective Dependency Trees

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 132–140, Prague, June 2007. c⃝2007 Association for Computational Linguistics Probabilistic Models of Nonprojective Dependency Trees David A. Smith Department of Computer Science Center for Language and Speech Processing Johns Hopkins University Baltimore, MD 21218 USA dasmith@cs.jhu.edu Noah A. Smith Language Technologies Institute School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 USA nasmith@cs.cmu.edu Abstract A notable gap in research on statistical de- pendency parsing is a proper conditional probability distribution over nonprojective dependency trees for a given sentence. We exploit the Matrix Tree Theorem (Tutte, 1984) to derive an algorithm that efficiently sums the scores of all nonprojective trees in a sentence, permitting the definition of a conditional log-linear model over trees. While discriminative methods, such as those presented in McDonald et al. (2005b), ob- tain very high accuracy on standard de- pendency parsing tasks and can be trained and applied without marginalization, “sum- ming trees” permits some alternative tech- niques of interest. Using the summing al- gorithm, we present competitive experimen- tal results on four nonprojective languages, for maximum conditional likelihood estima- tion, minimum Bayes-risk parsing, and hid- den variable training. 1 Introduction Recently dependency parsing has received renewed interest, both in the parsing literature (Buchholz and Marsi, 2006) and in applications like translation (Quirk et al., 2005) and information extraction (Cu- lotta and Sorensen, 2004). Dependency parsing can be used to provide a “bare bones” syntactic struc- ture that approximates semantics, and it has the addi- tional advantage of admitting fast parsing algorithms (Eisner, 1996; McDonald et al., 2005b) with a neg- ligible grammar constant in many cases. The latest state-of-the-art statistical dependency parsers are discriminative, meaning that they are based on classifiers trained to score trees, given a sentence, either via factored whole-structure scores (McDonald et al., 2005a) or local parsing decision scores (Hall et al., 2006). In the works cited, these scores are not intended to be interpreted as proba- bilistic quantities. Here we consider weighted dependency parsing models that can be used to define well-formed con- ditional distributions p(y trees y and a sentence x.| x), for dependency Conditional distribu- tions over outputs (here, trees) given inputs (here, sentences) have certain advantages. They per- mit marginalization over trees to compute poste- riors of interesting sub-events (e.g., the probabil- ity that two noun tokens bear a relation, regard- less of which tree is correct). A probability model permits alternative decoding procedures (Goodman, 1996). Well-motivated hidden variable training procedures (such as EM and conditional EM) are also readily available for probabilistic models. Fi- nally, probability models can be chained together (as in a noisy channel model), mixed, or combined in a product-of-experts. Sequence models, context-free models, and de- pendency models have appeared in several guises; a cross-model comparison clarifies the contribution of this paper. First, there were generative, stochas- tic models like HMMs, PCFGs, and Eisner’s (1996) models. Local discriminative classifiers were pro- posed by McCallum et …

Content truncated to 500 words