Transition-based Dependency Parsing with Selectional Branching

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1052–1062, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Transition-based Dependency Parsing with Selectional Branching Jinho D. Choi Department of Computer Science University of Massachusetts Amherst Amherst, MA, 01003, USA jdchoi@cs.umass.edu Andrew McCallum Department of Computer Science University of Massachusetts Amherst Amherst, MA, 01003, USA mccallum@cs.umass.edu Abstract We present a novel approach, called selec- tional branching, which uses confidence es- timates to decide when to employ a beam, providing the accuracy of beam search at speeds close to a greedy transition-based dependency parsing approach. Selectional branching is guaranteed to perform a fewer number of transitions than beam search yet performs as accurately. We also present a new transition-based dependency parsing algorithm that gives a complexity of O(n) for projective parsing and an expected lin- ear time speed for non-projective parsing. With the standard setup, our parser shows an unlabeled attachment score of 92.96% and a parsing speed of 9 milliseconds per sentence, which is faster and more accurate than the current state-of-the-art transition- based parser that uses beam search. 1 Introduction Transition-based dependency parsing has gained considerable interest because it runs fast and per- forms accurately. Transition-based parsing gives complexities as low as O(n) and O(n2) for projec- tive and non-projective parsing, respectively (Nivre, 2008).1 The complexity is lower for projective pars- ing because a parser can deterministically skip to- kens violating projectivity, while this property is not assumed for non-projective parsing. Nonethe- less, it is possible to perform non-projective parsing in expected linear time because the amount of non- projective dependencies is notably smaller (Nivre and Nilsson, 2005) so a parser can assume projec- tivity for most cases while recognizing ones for which projectivity should not be assumed (Nivre, 2009; Choi and Palmer, 2011). 1We refer parsing approaches that produce only projective dependency trees as projective parsing and both projective and non-projective dependency trees as non-projective parsing. Greedy transition-based dependency parsing has been widely deployed because of its speed (Cer et al., 2010); however, state-of-the-art accuracies have been achieved by globally optimized parsers using beam search (Zhang and Clark, 2008; Huang and Sagae, 2010; Zhang and Nivre, 2011; Bohnet and Nivre, 2012). These approaches generate multiple transition sequences given a sentence, and pick one with the highest confidence. Coupled with dynamic programming, transition-based dependency parsing with beam search can be done very efficiently and gives significant improvement to parsing accuracy. One downside of beam search is that it always uses a fixed size of beam even when a smaller size of beam is sufficient for good results. In our exper- iments, a greedy parser performs as accurately as a parser that uses beam search for about 64% of time. Thus, it is preferred if the beam size is not fixed but proportional to the number of low confidence pre- dictions that a greedy parser makes, in which case, fewer transition sequences need to be explored to produce the same or similar parse output. We …

Content truncated to 500 words