Dynamic Programming for Higher Order Parsing of Gap-Minding Trees

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 478–488, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Dynamic Programming for Higher Order Parsing of Gap-Minding Trees Emily Pitler, Sampath Kannan, Mitchell Marcus Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 epitler,kannan,mitch@seas.upenn.edu Abstract We introduce gap inheritance, a new struc- tural property on trees, which provides a way to quantify the degree to which intervals of de- scendants can be nested. Based on this prop- erty, two new classes of trees are derived that provide a closer approximation to the set of plausible natural language dependency trees than some alternative classes of trees: unlike projective trees, a word can have descendants in more than one interval; unlike spanning trees, these intervals cannot be nested in ar- bitrary ways. The 1-Inherit class of trees has exactly the same empirical coverage of natural language sentences as the class of mildly non- projective trees, yet the optimal scoring tree can be found in an order of magnitude less time. Gap-minding trees (the second class) have the property that all edges into an interval of descendants come from the same node, and thus an algorithm which uses only single in- tervals can produce trees in which a node has descendants in multiple intervals. 1 Introduction Dependency parsers vary in what space of possi- ble tree structures they search over when parsing a sentence. One commonly used space is the set of projective trees, in which every node’s descen- dants form a contiguous interval in the input sen- tence. Finding the optimal tree in the set of projec- tive trees can be done efficiently (Eisner, 2000), even when the score of a tree depends on higher order fac- tors (McDonald and Pereira, 2006; Carreras, 2007; Koo and Collins, 2010). However, the projectivity assumption is too strict for all natural language de- pendency trees; for example, only 63.6% of Dutch sentences from the CoNLL-X training set are pro- jective (Table 1). At the other end of the spectrum, some parsers search over all spanning trees, a class of structures much larger than the set of plausible linguistic struc- tures. The maximum scoring directed spanning tree can be found efficiently when the score of a tree de- pends only on edge-based factors (McDonald et al., 2005b). However, it is NP-hard to extend MST to in- clude sibling or grandparent factors (McDonald and Pereira, 2006; McDonald and Satta, 2007). MST- based non-projective parsers that use higher order factors (Martins et al., 2009; Koo et al., 2010), uti- lize different techniques than the basic MST algo- rithm. In addition, learning is done over a relaxation of the problem, so the inference procedures at train- ing and at test time are not identical. We propose two new classes of trees between pro- jective trees and the set of all spanning trees. These two classes provide a closer approximation to the set of plausible natural language …

Content truncated to 500 words