Incremental Graph-based Neural Dependency Parsing

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1655–1665 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Incremental Graph-based Neural Dependency Parsing Xiaoqing Zheng School of Computer Science, Fudan University, Shanghai, China Shanghai Key Laboratory of Intelligent Information Processing zhengxq@fudan.edu.cn Abstract Very recently, some studies on neural de- pendency parsers have shown advantage over the traditional ones on a wide va- riety of languages. However, for graph- based neural dependency parsing systems, they either count on the long-term mem- ory and attention mechanism to implicitly capture the high-order features or give up the global exhaustive inference algorithms in order to harness the features over a rich history of parsing decisions. The former might miss out the important features for specific headword predictions without the help of the explicit structural information, and the latter may suffer from the error propagation as false early structural con- straints are used to create features when making future predictions. We explore the feasibility of explicitly taking high-order features into account while remaining the main advantage of global inference and learning for graph-based parsing. The pro- posed parser first forms an initial parse tree by head-modifier predictions based on the first-order factorization. High-order fea- tures (such as grandparent, sibling, and un- cle) then can be defined over the initial tree, and used to refine the parse tree in an iterative fashion. Experimental result- s showed that our model (called INDP) archived competitive performance to ex- isting benchmark parsers on both English and Chinese datasets. 1 Introduction and Motivation The rise of machine learning methods in natural language processing (NLP) coupled with the avail- ability of treebanks (Buchholz and Marsi, 2006) for a wide variety of languages has led to a rapid increase in research on data-driven dependency parsing. Two predominant paradigms for the data- driven dependency parsing are often called graph- based and transition-based dependency parsing (McDonald and Nivre, 2007, 2011). The first cat- egory learns the parameters to score correct de- pendency subgraphs over incorrect ones, typically by factoring the graphs into their component di- rected arcs, and performs parsing by searching the highest-scoring graph for a given sentence. The second category of parsing systems instead learns to predict one transition from one parse state to the next given a parse history, and performs parsing by taking the predicted transitions at each parse state until a complete dependency graph is derived. Empirical studies show that the graph-based and transition-based models exhibit no statistical- ly significant difference in accuracy on a variety of languages, although they are very different the- oretically (McDonald and Nivre, 2011). Graph- based models are usually trained by maximizing the difference in score between the entire correct dependency graph and all incorrect ones for ev- ery training sentence. However, exhaustive infer- ence is generally NP-hard when the score is fac- tored over any extended scope of the dependency subgraph beyond a single arc (McDonald and Sat- ta, 2007), which is the primary shortcoming of the …

Content truncated to 500 words