Turbo Parsers: Dependency Parsing by Approximate Variational Inference

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 34–44, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Turbo Parsers: Dependency Parsing by Approximate Variational Inference Andr´e F. T. Martins∗† Noah A. Smith∗ Eric P. Xing∗ ∗School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA {afm,nasmith,epxing}@cs.cmu.edu Pedro M. Q. Aguiar‡ ‡Instituto de Sistemas e Rob´otica Instituto Superior T´ecnico Lisboa, Portugal aguiar@isr.ist.utl.pt M´ario A. T. Figueiredo† †Instituto de Telecomunicac¸˜oes Instituto Superior T´ecnico Lisboa, Portugal mtf@lx.it.pt Abstract We present a unified view of two state-of-the- art non-projective dependency parsers, both approximate: the loopy belief propagation parser of Smith and Eisner (2008) and the re- laxed linear program of Martins et al. (2009). By representing the model assumptions with a factor graph, we shed light on the optimiza- tion problems tackled in each method. We also propose a new aggressive online algorithm to learn the model parameters, which makes use of the underlying variational representation. The algorithm does not require a learning rate parameter and provides a single framework for a wide family of convex loss functions, includ- ing CRFs and structured SVMs. Experiments show state-of-the-art performance for 14 lan- guages. 1 Introduction Feature-rich discriminative models that break local- ity/independence assumptions can boost a parser’s performance (McDonald et al., 2006; Huang, 2008; Finkel et al., 2008; Smith and Eisner, 2008; Martins et al., 2009; Koo and Collins, 2010). Often, infer- ence with such models becomes computationally in- tractable, causing a demand for understanding and improving approximate parsing algorithms. In this paper, we show a formal connection be- tween two recently-proposed approximate inference techniques for non-projective dependency parsing: loopy belief propagation (Smith and Eisner, 2008) and linear programming relaxation (Martins et al., 2009). While those two parsers are differently moti- vated, we show that both correspond to inference in a factor graph, and both optimize objective functions over local approximations of the marginal polytope. The connection is made clear by writing the explicit declarative optimization problem underlying Smith and Eisner (2008) and by showing the factor graph underlying Martins et al. (2009). The success of both approaches parallels similar approximations in other fields, such as statistical image processing and error-correcting coding. Throughtout, we call these turbo parsers.1 Our contributions are not limited to dependency parsing: we present a general method for inference in factor graphs with hard constraints (§2), which extends some combinatorial factors considered by Smith and Eisner (2008). After presenting a geo- metric view of the variational approximations un- derlying message-passing algorithms (§3), and clos- ing the gap between the two aforementioned parsers (§4), we consider the problem of learning the model parameters (§5). To this end, we propose an ag- gressive online algorithm that generalizes MIRA (Crammer et al., 2006) to arbitrary loss functions. We adopt a family of losses subsuming CRFs (Laf- ferty et al., 2001) and structured SVMs (Taskar et al., 2003; Tsochantaridis et al., 2004). Finally, we present a technique for including features not at- tested in the training …

Content truncated to 500 words