Parse, Price and Cut—Delayed Column and Row Generation for Graph Based Parsers

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 732–743, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Parse, Price and Cut—Delayed Column and Row Generation for Graph Based Parsers Sebastian Riedel David Smith Andrew McCallum Department of Computer Science University of Massachusetts, Amherst {riedel,dasmith,mccallum}@cs.umass.edu Abstract Graph-based dependency parsers suffer from the sheer number of higher order edges they need to (a) score and (b) consider during opti- mization. Here we show that when working with LP relaxations, large fractions of these edges can be pruned before they are fully scored—without any loss of optimality guar- antees and, hence, accuracy. This is achieved by iteratively parsing with a subset of higher- order edges, adding higher-order edges that may improve the score of the current solu- tion, and adding higher-order edges that are implied by the current best first order edges. This amounts to delayed column and row gen- eration in the LP relaxation and is guaranteed to provide the optimal LP solution. For second order grandparent models, our method consid- ers, or scores, no more than 6–13% of the sec- ond order edges of the full model. This yields up to an eightfold parsing speedup, while pro- viding the same empirical accuracy and cer- tificates of optimality as working with the full LP relaxation. We also provide a tighter LP formulation for grandparent models that leads to a smaller integrality gap and higher speed. 1 Introduction Many problems in NLP, and structured prediction in general, can be cast as finding high-scoring struc- tures based on a large set of candidate parts. For example, in second order graph-based dependency parsing (Kübler et al., 2009) we have to choose a quadratic number of first order and a cubic number of second order edges such that the graph is both high-scoring and a tree. In coreference, we have to select high-scoring clusters of mentions from an exponential number of candidate clusters, such that each mention is in exactly one cluster (Culotta et al., 2007). In segmentation of citation strings, we need to consider a quadratic number of possible seg- ments such that every token is part of exactly one segment (Poon and Domingos, 2007). What makes such problems challenging is the large number of possible parts to consider. This number not only affects the cost of search or opti- mization but also slows down the process of scor- ing parts before they enter the optimization prob- lem. For example, the cubic grandparent edges in second-order dependency parsing slow down dy- namic programs (McDonald and Pereira, 2006), be- lief propagation (Smith and Eisner, 2008) and LP solvers (Martins et al., 2009), since there are more value functions to evaluate, more messages to pass, or more variables to consider. But to even calculate the score for each part we need a cubic number of operations that usually involve expensive feature ex- traction. This step often becomes a major bottleneck in parsing, and …

Content truncated to 500 words