High-order Graph-based Neural Dependency Parsing

High-order Graph-based Neural Dependency Parsing Zhisong Zhang1,2 and Hai Zhao1,2,∗ † 1Center for Brain-Like Computing and Machine Intelligence, Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China 2Key Laboratory of Shanghai Education Commission for Intelligent Interaction and Cognitive Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China zzs2011@sjtu.edu.cn, zhaohai@cs.sjtu.edu.cn Abstract In this work, we present a novel way of using neural network for graph-based dependency parsing, which fits the neural network into a simple probabilistic model and can be further- more generalized to high-order parsing. In- stead of the sparse features used in traditional methods, we utilize distributed dense feature representations for neural network, which give better feature representations. The proposed parsers are evaluated on English and Chinese Penn Treebanks. Compared to existing work, our parsers give competitive performance with much more efficient inference. 1 Introduction There have been two classes of typical approaches for dependency parsing: transition-based parsing and graph-based parsing. The former parses sen- tences by making a series of shift-reduce decisions (Yamada and Matsumoto, 2003; Nivre, 2003), while the latter searches for a tree through graph algo- rithms by decomposing trees into factors. This paper will focus on graph-based methods, which are based ∗Correspondence author. †This work was partially supported by the National Nat- ural Science Foundation of China (No. 61170114, and No. 61272248), the National Basic Research Program of China (No. 2013CB329401), the Science and Technology Commis- sion of Shanghai Municipality (No. 13511500200), the Eu- ropean Union Seventh Framework Program (No. 247619), the Cai Yuanpei Program (CSC fund 201304490199 and 201304490171), and the art and science interdiscipline funds of Shanghai Jiao Tong University, No. 14X190040031, and the Key Project of National Society Science Foundation of China, No. 15-ZDA041. on dynamic programming strategies (Eisner, 1996; McDonald et al., 2005; McDonald and Pereira, 2006). In this recent decade, extensions have been made to use high-order factors (Carreras, 2007; Koo and Collins, 2010) in graph models and the high- est one considers fourth-order (Ma and Zhao, 2012). However, all those methods usually use sparse indi- cator features as inputs and linear models to get the scores for later inference process. They are easy to suffer from the problem of sparsity, and linear mod- els can be insufficient to effectively integrate all the sparse features in spite of various rich context that can be potentially exploited. Distributed representations and neural network provide a way to alleviate such a drawback (Bengio et al., 2003; Collobert et al., 2011). Instead of high- dimensional sparse indicator feature vectors, dis- tributed representations use low-dimensional dense vectors (also known as embeddings) to represent the features, and then they are usually used in a neu- ral network. For example, in the traditional meth- ods, a word is usually expressed by a one-hot vector; while distributed representations use a dense vector. By appropriate representation learning (usually by back-propagations in neural network), these embed- dings can replace traditional sparse features and per- form quite well together with neural network. In recent years, using distributed representations …

Content truncated to 500 words