Stacking Dependency Parsers

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 157–166, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Stacking Dependency Parsers Andr´e F. T. Martins∗† Dipanjan Das∗ Noah A. Smith∗ Eric P. Xing∗ ∗School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, Lisboa, Portugal {afm,dipanjan,nasmith,epxing}@cs.cmu.edu Abstract We explore a stacked framework for learn- ing to predict dependency structures for natu- ral language sentences. A typical approach in graph-based dependency parsing has been to assume a factorized model, where local fea- tures are used but a global function is opti- mized (McDonald et al., 2005b). Recently Nivre and McDonald (2008) used the output of one dependency parser to provide features for another. We show that this is an example of stacked learning, in which a second pre- dictor is trained to improve the performance of the first. Further, we argue that this tech- nique is a novel way of approximating rich non-local features in the second parser, with- out sacrificing efficient, model-optimal pre- diction. Experiments on twelve languages show that stacking transition-based and graph- based parsers improves performance over ex- isting state-of-the-art dependency parsers. 1 Introduction In this paper we address a representation-efficiency tradeoff in statistical natural language processing through the use of stacked learning (Wolpert, 1992). This tradeoff is exemplified in dependency parsing, illustrated in Fig. 1, on which we focus in this paper: • Exact algorithms for dependency parsing (Eis- ner and Satta, 1999; McDonald et al., 2005b) are tractable only when the model makes very strong, linguistically unsupportable independence assumptions, such as “arc factorization” for non- projective dependency parsing (McDonald and Satta, 2007). • Feature-rich parsers must resort to search or greediness, (Ratnaparkhi et al., 1994; Sagae and Lavie, 2005; Hall et al., 2006), so that parsing solutions are inexact and learned models may be subject to certain kinds of bias (Lafferty et al., 2001). A solution that leverages the complementary strengths of these two approaches—described in de- tail by McDonald and Nivre (2007)—was recently and successfully explored by Nivre and McDonald (2008). Our contribution begins by reinterpreting and generalizing their parser combination scheme as a stacking of parsers. We give a new theoretical motivation for stacking parsers, in terms of extending a parsing model’s fea- ture space. Specifically, we view stacked learning as a way of approximating non-local features in a lin- ear model, rather than making empirically dubious independence (McDonald et al., 2005b) or structural assumptions (e.g., projectivity, Eisner, 1996), using search approximations (Sagae and Lavie, 2005; Hall et al., 2006; McDonald and Pereira, 2006), solving a (generally NP-hard) integer linear program (Riedel and Clarke, 2006), or adding latent variables (Titov and Henderson, 2007). Notably, we introduce the use of very rich non-local approximate features in one parser, through the output of another parser. Related approaches are the belief propagation algo- rithm of Smith and Eisner (2008), and the “trading of structure for features” explored by Liang et al. 157 Figure 1: A projective …

Content truncated to 500 words