Graph-based Dependency Parsing with Bidirectional LSTM

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 2306–2315, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Graph-based Dependency Parsing with Bidirectional LSTM Wenhui Wang Baobao Chang Key Laboratory of Computational Linguistics, Ministry of Education. School of Electronics Engineering and Computer Science, Peking University, No.5 Yiheyuan Road, Haidian District, Beijing, 100871, China Collaborative Innovation Center for Language Ability, Xuzhou, 221009, China. {wangwenhui,chbb}@pku.edu.cn Abstract In this paper, we propose a neural network model for graph-based dependency pars- ing which utilizes Bidirectional LSTM (BLSTM) to capture richer contextual in- formation instead of using high-order fac- torization, and enable our model to use much fewer features than previous work. In addition, we propose an effective way to learn sentence segment embedding on sentence-level based on an extra forward LSTM network. Although our model uses only first-order factorization, experiments on English Peen Treebank and Chinese Penn Treebank show that our model could be competitive with previous higher-order graph-based dependency parsing models and state-of-the-art models. 1 Introduction Dependency parsing is a fundamental task for lan- guage processing which has been investigated for decades. It has been applied in a wide range of ap- plications such as information extraction and ma- chine translation. Among a variety of dependency parsing models, graph-based models are attractive for their ability of scoring the parsing decisions on a whole-tree basis. Typical graph-based mod- els factor the dependency tree into subgraphs, in- cluding single arcs (McDonald et al., 2005), sib- ling or grandparent arcs (McDonald and Pereira, 2006; Carreras, 2007) or higher-order substruc- tures (Koo and Collins, 2010; Ma and Zhao, 2012) and then score the whole tree by summing scores of the subgraphs. In these models, subgraphs are usually represented as high-dimensional feature vectors which are then fed into a linear model to learn the feature weights. However, conventional graph-based models heavily rely on feature engineering and their per- formance is restricted by the design of features. In addition, standard decoding algorithm (Eisner, 2000) only works for the first-order model which limits the scope of feature selection. To incor- porate high-order features, Eisner algorithm must be somehow extended or modified, which is usu- ally done at high cost in terms of efficiency. The fourth-order graph-based model (Ma and Zhao, 2012), which seems the highest-order model so far to our knowledge, requires O(n5) time and O(n4) space. Due to the high computational cost, high- order models are normally restricted to produc- ing only unlabeled parses to avoid extra cost in- troduced by inclusion of arc-labels into the parse trees. To alleviate the burden of feature engineering, Pei et al. (2015) presented an effective neural net- work model for graph-based dependency parsing. They only use atomic features such as word uni- grams and POS tag unigrams and leave the model to automatically learn the feature combinations. However, their model requires many atomic fea- tures and still relies on high-order factorization strategy to further improve the accuracy. Different from previous work, we propose an LSTM-based dependency …

Content truncated to 500 words