Transition-Based Dependency Parsing with Heuristic Backtracking

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2313–2318, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Transition-Based Dependency Parsing with Heuristic Backtracking Jacob Buckman♣ Miguel Ballesteros♦ Chris Dyer♠♣ ♣School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA ♦NLP Group, Pompeu Fabra University, Barcelona, Spain ♠Google DeepMind, London, UK jacobbuckman@cmu.edu, miguel.ballesteros@upf.edu, cdyer@google.com Abstract We introduce a novel approach to the decoding problem in transition-based parsing: heuris- tic backtracking. This algorithm uses a se- ries of partial parses on the sentence to locate the best candidate parse, using confidence es- timates of transition decisions as a heuristic to guide the starting points of the search. This allows us to achieve a parse accuracy compa- rable to beam search, despite using fewer tran- sitions. When used to augment a Stack-LSTM transition-based parser, the parser shows an unlabeled attachment score of up to 93.30% for English and 87.61% for Chinese. 1 Introduction Transition-based parsing, one of the most prominent dependency parsing techniques, constructs a depen- dency structure by reading words sequentially from the sentence, and making a series of local decisions (called transitions) which incrementally build the structure. Transition-based parsing has been shown to be both fast and accurate; the number of transi- tions required to fully parse the sentence is linear relative to the number of words in the sentence. In recent years, the field has seen dramatic im- provements in the ability to correctly predict tran- sitions. Recent models include the greedy Stack- LSTM model of Dyer et al. (2015) and the globally normalized feed-forward networks of Andor et al. (2016). These models output a local decision at each transition point, so searching the space of possible paths to the predicted tree is an important compo- nent of high-accuracy parsers. One common search technique is beam search. (Zhang and Clark, 2008; Zhang and Nivre, 2011; Bohnet and Nivre, 2012; Zhou et al., 2015; Weiss et al., 2015; Yazdani and Henderson, 2015) In beam- search, a fixed number of candidate transition se- quences are generated, and the highest-scoring se- quence is chosen as the answer. One downside to beam search is that it often results in a significant amount of wasted predictions. A constant number of beams are explored at all points throughout the sentence, leading to some unnecessary exploration towards the beginning of the sentence, and poten- tially insufficient exploration towards the end. One way that this problem can be mitigated is by using a dynamically-sized beam (Mejia-Lavalle and Ramos, 2013). When using this technique, at each step, prune all beams whose scores are below some value s, where s is calculated based upon the distri- bution of scores of available beams. Common meth- ods for pruning are removing all beams below some percentile, or any beams which scored below some constant percentage of the highest-scoring beam. Another approach to solving this issue is given by Choi and McCallum (2013). They introduced se- lectional branching, which involves performing an initial greedy parse, and …

Content truncated to 500 words