Making Dependency Labeling Simple, Fast and Accurate

Proceedings of NAACL-HLT 2016, pages 1089–1094, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Making Dependency Labeling Simple, Fast and Accurate Tianxiao Shen1 Tao Lei2 Regina Barzilay2 1The Institute for Theoretical Computer Science (ITCS) Institute for Interdisciplinary Information Sciences Tsinghua University 2MIT CSAIL 1shentianxiao0831@gmail.com 2{taolei, regina}@csail.mit.edu Abstract This work addresses the task of dependency labeling—assigning labels to an (unlabeled) dependency tree. We employ and extend a feature representation learning approach, op- timizing it for both high speed and accu- racy. We apply our labeling model on top of state-of-the-art parsers and evaluate its perfor- mance on standard benchmarks including the CoNLL-2009 and the English PTB datasets. Our model processes over 1,700 English sen- tences per second, which is 30 times faster than the sparse-feature method. It improves labeling accuracy over the outputs of top parsers, achieving the best LAS on 5 out of 7 datasets1. 1 Introduction Traditionally in dependency parsing, the tasks of finding the tree structure and labeling the de- pendency arcs are coupled in a joint achitecture. While it has potential to eliminate errors propogated through a separated procedure, joint decoding intro- duces other sources of issues that can also lead to non-optimal labeling assignments. One of the issues arises from inexact algorithms adopted in order to solve the hard joint search problem. For instance, many parsers (Nivre et al., 2007; Titov and Hender- son, 2007; Zhang et al., 2013; Dyer et al., 2015; Weiss et al., 2015) adopt greedy decoding such as beam search, which may prune away the correct la- beling hypothesis in an early decoding stage. An- other issue is caused by the absence of rich label 1Our code is available at https://github.com/ shentianxiao/RBGParser/tree/labeling. features. Adding dependency labels to the combina- torial space significantly slows down the search pro- cedure. As a trade-off, many parsers such as MST- Parser, TurboParser and RBGParser (McDonald et al., 2005; Martins et al., 2010; Zhang et al., 2014) incorporate only single-arc label features to reduce the processing time. This restriction greatly limits the labeling accuracy. In this work, we explore an alternative approach where the dependency labeling is applied as a sep- arate procedure, alleviating the issues described above. The potential of this approach has been ex- plored in early work. For instance, McDonald et al. (2006) applied a separate labeling step on top of the first-order MSTParser. The benefit of such approach is two-fold. First, finding the optimal labeling as- signment (once the tree structure is produced) can be solved via an exact dynamic programming algo- rithm. Second, it becomes relatively cheap to add rich label features given a fixed tree, and the ex- act algorithm still applies when high-order label fea- tures are included. However, due to performance is- sues, such approach has not been adopted by the top performing parsers. In this work, we show that the labeling procedure, when optimized with recent ad- vanced techniques in parsing, can achieve very high speed and accuracy. Specifically, our approach employs the recent distributional …

Content truncated to 500 words