Efficient Third-Order Dependency Parsers

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1–11, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Efficient Third-order Dependency Parsers Terry Koo and Michael Collins MIT CSAIL, Cambridge, MA, 02139, USA {maestro,mcollins}@csail.mit.edu Abstract We present algorithms for higher-order de- pendency parsing that are “third-order” in the sense that they can evaluate sub- structures containing three dependencies, and “efficient” in the sense that they re- quire only O(n4) time. Importantly, our new parsers can utilize both sibling-style and grandchild-style interactions. We evaluate our parsers on the Penn Tree- bank and Prague Dependency Treebank, achieving unlabeled attachment scores of 93.04% and 87.38%, respectively. 1 Introduction Dependency grammar has proven to be a very use- ful syntactic formalism, due in no small part to the development of efficient parsing algorithms (Eis- ner, 2000; McDonald et al., 2005b; McDonald and Pereira, 2006; Carreras, 2007), which can be leveraged for a wide variety of learning methods, such as feature-rich discriminative models (Laf- ferty et al., 2001; Collins, 2002; Taskar et al., 2003). These parsing algorithms share an impor- tant characteristic: they factor dependency trees into sets of parts that have limited interactions. By exploiting the additional constraints arising from the factorization, maximizations or summations over the set of possible dependency trees can be performed efficiently and exactly. A crucial limitation of factored parsing algo- rithms is that the associated parts are typically quite small, losing much of the contextual in- formation within the dependency tree. For the purposes of improving parsing performance, it is desirable to increase the size and variety of the parts used by the factorization.1 At the same time, the need for more expressive factorizations 1For examples of how performance varies with the degree of the parser’s factorization see, e.g., McDonald and Pereira (2006, Tables 1 and 2), Carreras (2007, Table 2), Koo et al. (2008, Tables 2 and 4), or Suzuki et al. (2009, Tables 3–6). must be balanced against any resulting increase in the computational cost of the parsing algorithm. Consequently, recent work in dependency pars- ing has been restricted to applications of second- order parsers, the most powerful of which (Car- reras, 2007) requires O(n4) time and O(n3) space, while being limited to second-order parts. In this paper, we present new third-order pars- ing algorithms that increase both the size and vari- ety of the parts participating in the factorization, while simultaneously maintaining computational requirements of O(n4) time and O(n3) space. We evaluate our parsers on the Penn WSJ Treebank (Marcus et al., 1993) and Prague Dependency Treebank (Hajiˇc et al., 2001), achieving unlabeled attachment scores of 93.04% and 87.38%. In sum- mary, we make three main contributions: 1. Efficient new third-order parsing algorithms. 2. Empirical evaluations of these parsers. 3. A free distribution of our implementation.2 The remainder of this paper is divided as follows: Sections 2 and 3 give background, Sections 4 and 5 describe our new parsing algorithms, Section 6 discusses related work, Section 7 presents our ex- …

Content truncated to 500 words