Efficient Inner-to-outer Greedy Algorithm for Higher-order Labeled Dependency Parsing

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1322–1328, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Efficient Inner-to-outer Greedy Algorithm for Higher-order Labeled Dependency Parsing Xuezhe Ma and Eduard Hovy Language Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA xuezhem@cs.cmu.edu, ehovy@andrew.cmu.edu Abstract Many NLP systems use dependency parsers as critical components. Jonit learn- ing parsers usually achieve better parsing accuracies than two-stage methods. How- ever, classical joint parsing algorithms significantly increase computational com- plexity, which makes joint learning im- practical. In this paper, we proposed an ef- ficient dependency parsing algorithm that is capable of capturing multiple edge-label features, while maintaining low computa- tional complexity. We evaluate our parser on 14 different languages. Our parser consistently obtains more accurate results than three baseline systems and three pop- ular, off-the-shelf parsers. 1 Introduction Natural language processing (NLP) systems, like machine translation (Xie et al., 2011), resource- low languages processing (McDonald et al., 2013; Ma and Xia, 2014), word sense disambigua- tion (Fauceglia et al., 2015) , and entity corefer- ence resolution (Durrett and Klein, 2013), are be- coming more sophisticated, in part because of uti- lizing syntacitc knowledges such as dependency parsing trees. Dependency parsers predict dependency struc- tures and dependency type labels on each edge. However, most graph-based dependency parsing algorithms only produce unlabeled dependency trees, particularly when higher-order factoriza- tions are used (Koo and Collins, 2010; Ma and Zhao, 2012b; Martins et al., 2013; Ma and Zhao, 2012a). A two-stage method (McDonald, 2006) is often used because the complexity of some joint learning models is unacceptably high. On the other hand, joint learning models can benefit from edge-label information that has proven to be im- portant to provide more accurate tree structures and labels (Nivre and Scholz, 2004). Previous studies explored the trade-off between computational costs and parsing performance. Some work (McDonald, 2006; Carreras, 2007) simplified labeled information to only single la- bel features. Other work (Johansson and Nugues, 2008; Bohnet, 2010) used richer label features but increased systems’ complexities significantly, while achieving better parsing accuracy. Yet, there are no previous work addressing the problem of good balance between parsing accuracy and com- putational costs for joint parsing models. In this paper, we propose a new dependency parsing algorithm that can utilize edge-label infor- mation of more than one edge, while simultane- ously maintaining low computational complexity. The component needed to solve this dilemma is an inner-to-outer greedy approximation to avoid an exhaustive search. The contributions of this work are (i) showing the effectiveness of edge-label in- formation on both UAS and LAS. (ii) proposing a joint learning parsing model which achieves both effectiveness and efficience. (iii) giving empiri- cal evaluations of this parser on different treebanks over 14 languages. 2 Joint Parsing Algorithm 2.1 Basic Notations In the following, x represents a generic input sen- tence, and y represents a generic dependency tree. Formally, for a sentence x, dependency parsing is the task of finding the dependency tree …

Content truncated to 500 words