Generalized Higher-Order Dependency Parsing with Cube Pruning

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 320–331, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Generalized Higher-Order Dependency Parsing with Cube Pruning Hao Zhang Ryan McDonald Google, Inc. {haozhang,ryanmcd}@google.com Abstract State-of-the-art graph-based parsers use fea- tures over higher-order dependencies that rely on decoding algorithms that are slow and difficult to generalize. On the other hand, transition-based dependency parsers can eas- ily utilize such features without increasing the linear complexity of the shift-reduce system beyond a constant. In this paper, we attempt to address this imbalance for graph-based pars- ing by generalizing the Eisner (1996) algo- rithm to handle arbitrary features over higher- order dependencies. The generalization is at the cost of asymptotic efficiency. To account for this, cube pruning for decoding is utilized (Chiang, 2007). For the first time, label tuple and structural features such as valencies can be scored efficiently with third-order features in a graph-based parser. Our parser achieves the state-of-art unlabeled accuracy of 93.06% and labeled accuracy of 91.86% on the stan- dard test set for English, at a faster speed than a reimplementation of the third-ordermodel of Koo et al. (2010). 1 Introduction The trade-off between rich features and exact de- coding in dependency parsing has been well docu- mented (McDonald and Nivre, 2007; Nivre and Mc- Donald, 2008). Graph-based parsers typically trade- off rich feature scope for exact (or near exact) de- coding, whereas transition-based parsers make the opposite trade-off. Recent research on both parsing paradigms has attempted to address this. In the transition-based parsing literature, the fo- cus has been on increasing the search space of the system at decoding time, as expanding the feature scope is often trivial and in most cases only leads to a constant-time increase in parser complexity. The most common approach is to use beam search (Duan et al., 2007; Johansson and Nugues, 2007; Titov and Henderson, 2007; Zhang and Clark, 2008; Zhang and Nivre, 2011), but more principled dynamic pro- gramming solutions have been proposed (Huang and Sagae, 2010). In all cases inference remains approx- imate, though a larger search space is explored. In the graph-based parsing literature, the main thrust of research has been on extending the Eisner chart-parsing algorithm (Eisner, 1996) to incorpo- rate higher-order features (McDonald and Pereira, 2006; Carreras, 2007; Koo and Collins, 2010). A similar line of research investigated the use of inte- ger linear programming (ILP) formulations of pars- ing (Riedel and Clarke, 2006; Martins et al., 2009; Martins et al., 2010). Both solutions allow for exact inference with higher-order features, but typically at a high cost in terms of efficiency. Furthermore, spe- cialized algorithms are required that deeply exploit the structural properties of the given model. Upgrad- ing a parser to score new types of higher-order de- pendencies thus requires significant changes to the underlying decoding algorithm. This is in stark con- trast to transition-based systems, which simply re- quire the definition of new feature …

Content truncated to 500 words