Vine Parsing and Minimum Risk Reranking for Speed and Precision

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 201–205, New York City, June 2006. c⃝2006 Association for Computational Linguistics Vine Parsing and Minimum Risk Reranking for Speed and Precision∗ Markus Dreyer, David A. Smith, and Noah A. Smith Department of Computer Science / Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {markus,{d,n}asmith}@cs.jhu.edu Abstract We describe our entry in the CoNLL-X shared task. The system consists of three phases: a probabilistic vine parser (Eisner and N. Smith, 2005) that pro- duces unlabeled dependency trees, a probabilistic relation-labeling model, and a discriminative mini- mum risk reranker (D. Smith and Eisner, 2006). The system is designed for fast training and decoding and for high precision. We describe sources of cross- lingual error and ways to ameliorate them. We then provide a detailed error analysis of parses produced for sentences in German (much training data) and Arabic (little training data). 1 Introduction Standard state-of-the-art parsing systems (e.g., Charniak and Johnson, 2005) typically involve two passes. First, a parser produces a list of the most likely n parse trees under a generative, probabilistic model (usually some flavor of PCFG). A discrim- inative reranker then chooses among trees in this list by using an extended feature set (Collins, 2000). This paradigm has many advantages: PCFGs are fast to train, can be very robust, and perform bet- ter as more data is made available; and rerankers train quickly (compared to discriminative models), require few parameters, and permit arbitrary fea- tures. We describe such a system for dependency pars- ing. Our shared task entry is a preliminary system developed in only 3 person-weeks, and its accuracy is typically one s.d. below the average across sys- tems and 10–20 points below the best system. On ∗This work was supported by NSF ITR grant IIS-0313193, an NSF fellowship to the second author, and a Fannie and John Hertz Foundation fellowship to the third author. The views ex- pressed are not necessarily endorsed by the sponsors. We thank Charles Schafer, Keith Hall, Jason Eisner, and Sanjeev Khudan- pur for helpful conversations. the positive side, its decoding algorithms have guar- anteed O(n) runtime, and training takes only a cou- ple of hours. Having designed primarily for speed and robustness, we sacrifice accuracy. Better esti- mation, reranking on larger datasets, and more fine- grained parsing constraints are expected to boost ac- curacy while maintaining speed. 2 Notation Let a sentence x = ⟨x1, x2, ..., xn⟩, where each xi is a tuple containing a part-of-speech tag ti and a word wi, and possibly more information.1 x0 is a special wall symbol, $, on the left. A dependency tree y is defined by three functions: yleft and yright (both {0, 1, 2, ..., n} → 2{1,2,...,n}) that map each word to its sets of left and right dependents, respectively, and ylabel : {1, 2, ..., n} → D, which labels the relation- ship between word i and its parent from label set D. In this …

Content truncated to 500 words