Neural Probabilistic Model for Non-projective MST Parsing

Proceedings of the The 8th International Joint Conference on Natural Language Processing, pages 59–69, Taipei, Taiwan, November 27 – December 1, 2017 c⃝2017 AFNLP Neural Probabilistic Model for Non-projective MST Parsing Xuezhe Ma and Eduard Hovy Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA xuezhem@cs.cmu.edu, hovy@cmu.edu Abstract In this paper, we propose a probabilistic parsing model that defines a proper con- ditional probability distribution over non- projective dependency trees for a given sentence, using neural representations as inputs. The neural network architec- ture is based on bi-directional LSTM- CNNs, which automatically benefits from both word- and character-level represen- tations, by using a combination of bidi- rectional LSTMs and CNNs. On top of the neural network, we introduce a probabilistic structured layer, defining a conditional log-linear model over non- projective trees. By exploiting Kirchhoff’s Matrix-Tree Theorem (Tutte, 1984), the partition functions and marginals can be computed efficiently, leading to a straight- forward end-to-end model training pro- cedure via back-propagation. We eval- uate our model on 17 different datasets, across 14 different languages. Our parser achieves state-of-the-art parsing perfor- mance on nine datasets. 1 Introduction Dependency parsing is one of the first stages in deep language understanding and has gained in- terest in the natural language processing (NLP) community, due to its usefulness in a wide range of applications. Many NLP systems, such as ma- chine translation (Xie et al., 2011), entity coref- erence resolution (Ng, 2010; Durrett and Klein, 2013; Ma et al., 2016), low-resource languages processing (McDonald et al., 2013; Ma and Xia, 2014), and word sense disambiguation (Fauceglia et al., 2015), are becoming more sophisticated, in part because of utilizing syntactic knowledge such as dependency parsing trees. Dependency trees represent syntactic relation- ships through labeled directed edges between heads and their dependents (modifiers). In the past few years, several dependency parsing algo- rithms (Nivre and Scholz, 2004; McDonald et al., 2005b; Koo and Collins, 2010; Ma and Zhao, 2012a,b) have been proposed, whose high perfor- mance heavily rely on hand-crafted features and task-specific resources that are costly to develop, making dependency parsing models difficult to adapt to new languages or new domains. Recently, non-linear neural networks, such as recurrent neural networks (RNNs) with long-short term memory (LSTM) and convolution neural net- works (CNNs), with as input distributed word representations, also known as word embeddings, have been broadly applied, with great success, to NLP problems like part-of-speech (POS) tag- ging (Collobert et al., 2011) and named entity recognition (NER) (Chiu and Nichols, 2016). By utilizing distributed representations as inputs, these systems are capable of learning hidden in- formation representations directly from data in- stead of manually designing hand-crafted features, yielding end-to-end models (Ma and Hovy, 2016). Previous studies explored the applicability of neu- ral representations to traditional graph-based pars- ing models. Some work (Kiperwasser and Gold- berg, 2016; Wang and Chang, 2016) replaced the linear scoring function of each arc in tradi- tional models with neural networks and used a margin-based objective (McDonald et al., 2005a) for model …

Content truncated to 500 words