Second-Order Unsupervised Neural Dependency Parsing (2020)

Abstract: Most of the unsupervised dependency parsers are based on first-order probabilistic generative models that only consider local parent-child information. Inspired by second-order supervised dependency parsing, we proposed a second-order extension of unsupervised neural dependency models that incorporate grandparent-child or sibling information. We also propose a novel design of the neural parameterization and optimization methods of the dependency models. In second-order models, the number of grammar rules grows cubically with the increase of vocabulary size, making it difficult to train lexicalized models that may contain thousands of words. To circumvent this problem while still benefiting from both second-order parsing and lexicalization, we use the agreement-based learning framework to jointly train a second-order unlexicalized model and a first-order lexicalized model. Experiments on multiple datasets show the effectiveness of our second-order models compared with recent state-of-the-art methods. Our joint model achieves a 10% improvement over the previous state-of-the-art parser on the full WSJ test set.

## introduction dependency parsing is a classical task in natural language processing. the head-dependent relations produced by dependency parsing can provide an approximation to the semantic relationship between words, which is useful in many downstream nlp tasks such as machine translation, information extraction and question answering. nowadays, supervised dependency parsers can reach a very high accuracy @xcite . unfortunately, supervised parsing requires treebanks (annotated parse trees) for training, which are very expensive and time-consuming to build. on the other hand, unsupervised dependency parsing requires only unannotated corpora for training, though the accuracy of unsupervised parsing still lags far behind that of supervised parsing. we focus on unsupervised dependency parsing in this paper. most methods in the literature of unsupervised dependency parsing are based on the dependency model with valence (dmv) @xcite , which is a probabilistic generative model. a main disadvantage of dmv and many of its extensions is that they lack expressiveness. the generation of a dependent token is only conditioned on its parent, the relative direction of the token to its parent, and whether its parent has already generated any child in this direction, hence ignoring other contextual information. to improve model expressiveness, researchers often turn to discriminative methods, which can incorporate more contextual information into the scoring or prediction of dependency arcs. for example, @xcite uses the idea of disrciminative clustering, @xcite uses a discriminative parser in the crf-autoencoder framework, and @xcite uses an encoder-decoder framework that contains a discriminative transitioned-based parser. for dmv, @xcite proposes the discriminative neural dmv which uses a global sentence embedding to introduce contextual information into the calculation of grammar rule probabilities. in the literature of supervised graph-based dependency parsing, however, there exists another technique for incorporating contextual information and increasing expressiveness, namely high-order parsing @xcite . a first-order parser, such as the dmv, only considers local parent-children information. in comparison, a high-order parser takes into account the interaction between multiple dependency arcs. in this work, we propose the second-order neural dmv model, which incorporates second-order information (e.g., sibling or grandparent) into the original (neural) dmv model. to achieve better learning accuracy, we design a new neural architecture for rule probability computation and promote direct marginal likelihood optimization @xcite over the widely used expectationmaximization algorithm for training. one particular challenge faced by second-order neural dmvs is that the number of grammar rules grows cubically to the vocabulary size, making it difficult to store and train a lexicalized model containing thousands of words. therefore, instead of learning a second-order lexicalized model, we propose to jointly learn a second-order unlexicalized model (whose vocabulary consists of pos tags instead of words) and a first-order lexicalized model based on the agreement-based learning framework @xcite . the jointly learned models have a manageable number of grammar rules while still benefiting from both second-order parsing and lexicalization. we conduct experiments on the wall street journal (wsj) dataset and seven languages on the universal dependencies (ud) dataset. the experimental results demonstrate that our models achieve state-ofthe-art accuracies on unsupervised dependency parsing. ## conclusion we propose second-order ndmv models, which incorporate sibling or grandparent information. we find that sibling information is very useful in unsupervised dependency parsing. we use agreement-based learning to combine the benefits of second-order parsing and lexicalization, achieving state-of-the-art results on the wsj dataset. we also show the effectiveness of our neural parameterization architecture with skip-connections and the direct marginal likelihood optimization method. algorithm 1: inside algorithm for grand-ndmv notation @xmath0, @xmath1, @xmath2, @xmath3, g c g,0 i,i,0 = d[i, g, 0, 0, 0] c g,1 i,i,0 = d[i, g, 0, 1, 0] c g,0 i,i,1 = d[i, g, 1, 0, 0] c g,1 i,i,1 = d[i, g, 1, 1, 0] for @xmath4...(n -1) for @xmath5...(n -w) @xmath6,0 i,j,0 = logsumexp @xmath7,1 i,r,1 + c g,0 r+1,j,0 + d[j, g, 0, 0, 1] + s[j, i, g, 0, 0] i g,1 i,j,0 = logsumexp @xmath8,1 i,r,1 + c g,0 r+1,j,0 + d[j, g, 0, 1, 1] + s[j, i, g, 0, 1] i g,0 i,j,1 = logsumexp @xmath9,0 i,r,1 + c i,1 r+1,j,0 + d[i, g, 1, 0, 1] + s[i, j, g, 1, 0] i g,1 i,j,1 = logsumexp @xmath10,0 i,r,1 + c i,1 r+1,j,0 + d[i, g, 1, 1, 1] + s[i, j, g, 1, 1] c g,0 i,j,0 = logsumexp @xmath11,1 i,r,0 + i g,0 r,j,0 c g,1 i,j,0 = logsumexp @xmath12,1 i,r,0 + i g,1 r,j,0 for the ud dataset, we use a more expressive mlp to get the final hidden representation h since we find that the ud dataset is more difficult to train. for decision rules, we introduce two embedding x stop and x continue . we feed x stop and x continue to a fully connected layer w dec to get e stop and e continue . we use the same neural network to get hidden representation h stop and h continue . for root rules, we introduce x root . we feed x root to a fully connected layer w root to get e root . also, we use the same neural network to get hidden representation h root . we use different decomposed trilinear function parameters for different types of rules. the calculation of the decision rule probability and root rule probability is similar to that of the child rule probability.