A Neural Probabilistic Structured-Prediction Model for Transition-Based Dependency Parsing

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1213–1222, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics A Neural Probabilistic Structured-Prediction Model for Transition-Based Dependency Parsing Hao Zhou†∗ Yue Zhang‡ Shujian Huang† Jiajun Chen† †State Key Laboratory for Novel Software Technology, Nanjing University, China ‡Singapore University of Technology and Design, Singapore {zhouh, huangsj, chenjj}@nlp.nju.edu.cn, yue zhang@sutd.edu.sg Abstract Neural probabilistic parsers are attrac- tive for their capability of automatic fea- ture combination and small data sizes. A transition-based greedy neural parser has given better accuracies over its lin- ear counterpart. We propose a neural probabilistic structured-prediction model for transition-based dependency parsing, which integrates search and learning. Beam search is used for decoding, and contrastive learning is performed for max- imizing the sentence-level log-likelihood. In standard Penn Treebank experiments, the structured neural parser achieves a 1.8% accuracy improvement upon a com- petitive greedy neural parser baseline, giv- ing performance comparable to the best linear parser. 1 Introduction Transition-based methods have given competitive accuracies and efficiencies for dependency pars- ing (Yamada and Matsumoto, 2003; Nivre and Scholz, 2004; Zhang and Clark, 2008; Huang and Sagae, 2010; Zhang and Nivre, 2011; Goldberg and Nivre, 2013). These parsers construct depen- dency trees by using a sequence of transition ac- tions, such as SHIFT and REDUCE, over input sen- tences. High accuracies are achieved by using a linear model and millions of binary indicator fea- tures. Recently, Chen and Manning (2014) pro- pose an alternative dependency parser using a neu- ral network, which represents atomic features as dense vectors, and obtains feature combination au- tomatically other than devising high-order features manually. The greedy neural parser of Chen and Man- ning (2014) gives higher accuracies compared to ∗Work done while the first author was visiting SUTD. the greedy linear MaltParser (Nivre and Scholz, 2004), but lags behind state-of-the-art linear sys- tems with sparse features (Zhang and Nivre, 2011), which adopt global learning and beam search decoding (Zhang and Nivre, 2012). The key difference is that Chen and Manning (2014) is a local classifier that greedily optimizes each ac- tion. In contrast, Zhang and Nivre (2011) leverage a structured-prediction model to optimize whole sequences of actions, which correspond to tree structures. In this paper, we propose a novel framework for structured neural probabilistic dependency pars- ing, which maximizes the likelihood of action se- quences instead of individual actions. Follow- ing Zhang and Clark (2011), beam search is ap- plied to decoding, and global structured learn- ing is integrated with beam search using early- update (Collins and Roark, 2004). Designing such a framework is challenging for two main reasons: First, applying global structured learning to transition-based neural parsing is non-trivial. A direct adaptation of the framework of Zhang and Clark (2011) under the neural probabilistic model setting does not yield good results. The main rea- son is that the parameter space of a neural network is much denser compared to that of …

Content truncated to 500 words