Fast and Robust Multilingual Dependency Parsing with a Generative Latent Variable Model

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 947–951, Prague, June 2007. c⃝2007 Association for Computational Linguistics Fast and Robust Multilingual Dependency Parsing with a Generative Latent Variable Model Ivan Titov University of Geneva 24, rue G´en´eral Dufour CH-1211 Gen`eve 4, Switzerland ivan.titov@cui.unige.ch James Henderson University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW, United Kingdom james.henderson@ed.ac.uk Abstract We use a generative history-based model to predict the most likely derivation of a de- pendency parse. Our probabilistic model is based on Incremental Sigmoid Belief Net- works, a recently proposed class of la- tent variable models for structure predic- tion. Their ability to automatically in- duce features results in multilingual pars- ing which is robust enough to achieve accu- racy well above the average for each indi- vidual language in the multilingual track of the CoNLL-2007 shared task. This robust- ness led to the third best overall average la- beled attachment score in the task, despite using no discriminative methods. We also demonstrate that the parser is quite fast, and can provide even faster parsing times with- out much loss of accuracy. 1 Introduction The multilingual track of the CoNLL-2007 shared task (Nivre et al., 2007) considers dependency pars- ing of texts written in different languages. It re- quires use of a single dependency parsing model for the entire set of languages; model parameters are estimated individually for each language on the basis of provided training sets. We use a recently proposed dependency parser (Titov and Hender- son, 2007b)1 which has demonstrated state-of-the- art performance on a selection of languages from the 1The ISBN parser will be soon made downloadable from the authors’ web-page. CoNLL-X shared task (Buchholz and Marsi, 2006). This parser employs a latent variable model, Incre- mental Sigmoid Belief Networks (ISBNs), to de- fine a generative history-based model of projective parsing. We used the pseudo-projective transforma- tion introduced in (Nivre and Nilsson, 2005) to cast non-projective parsing tasks as projective. Follow- ing (Nivre et al., 2006), the encoding scheme called HEAD in (Nivre and Nilsson, 2005) was used to en- code the original non-projective dependencies in the labels of the projectivized dependency tree. In the following sections we will briefly discuss our modi- fications to the ISBN parser, experimental setup, and achieved results. 2 The Probability Model Our probability model uses the parsing order pro- posed in (Nivre et al., 2004), but instead of perform- ing deterministic parsing as in (Nivre et al., 2004), this ordering is used to define a generative history- based model, by adding word prediction to the Shift parser action. We also decomposed some parser ac- tions into sub-sequences of decisions. We split arc prediction decisions (Left-Arcr and Right-Arcr) each into two elementary decisions: first the parser cre- ates the corresponding arc, then it assigns a relation r to the arc. Similarly, we decompose the decision to shift a word into a decision to shift and a pre- diction of the word. We used part-of-speech tags and fine-grain word features, which …

Content truncated to 500 words