Semi-Supervised Dependency Parsing with Arc-Factored Variational Autoencoding (2020)

Abstract: Mannual annotation for dependency parsing is both labourious and time costly, resulting in the difficulty to learn practical dependency parsers for many languages due to the lack of labelled training corpora. To compensate for the scarcity of labelled data, semi-supervised dependency parsing methods are developed to utilize unlabelled data in the training procedure of dependency parsers. In previous work, the autoencoder framework is a prevalent approach for the utilization of unlabelled data. In this framework, training sentences are reconstructed from a decoder conditioned on dependency trees predicted by an encoder. The tree structure requirement brings challenges for both the encoder and the decoder. Sophisticated techniques are employed to tackle these challenges at the expense of model complexity and approximations in encoding and decoding. In this paper, we propose a model based on the variational autoencoder framework. By relaxing the tree constraint in both the encoder and the decoder during training, we make the learning of our model fully arc-factored and thus circumvent the challenges brought by the tree constraint. We evaluate our model on datasets across several languages and the results demonstrate the advantage of our model over previous approaches in both parsing accuracy and speed.

## introduction dependency parsing is the task of finding syntactic dependency relations between words in sentences @xcite . for each sentence, the dependency arcs between words are constrained to form a tree structure. a main bottleneck for learning a practical dependency parser is the lack of adequate training corpora as labelling raw text with dependency trees is both labourious and time costly. semisupervised dependency parsing utilizes unlabelled data to compensate the scarcity of labelled data in training dependency parsers @xcite @xcite . in previous work, the autoencoder framework is a prevalent approach for the utilization of unlabelled data @xcite . when this framework is applied to dependency parsing, training sentences are reconstructed from a decoder conditioned on dependency trees predicted by an encoder. concretely, the autoencoder approaches to dependency parsing are mainly divided into two categories: the conditional random field (crf) autoencoder @xcite and the variational autoencoder (vae) @xcite . the crf autoencoder predicts the dependency structure with the encoder and tries to reconstruct the input sentence based on the predicted structure. the variational autoencoder assumes the decoder is a generative model which generates the observed sentence from a group of latent variables containing information of the dependency tree, while the encoder tries to infer the posterior of the latent variables from the observed sentence. the tree structure constraint of the dependency parsing brings challenges to approaches of both categories. for the crf autoencoder, the encoder predicts the dependency tree structure using dynamic programming with the time complexity of o(n 3 ) @xcite , which is quite time-consuming in practice. for the vae, the learning objective function contains an expectation over the posterior of the parse tree modeled by the encoder and sophisticated sampling techniques have to be applied to approximate it in previous work. another problem in previous approaches is related to the incorporation of contextual information in the decoding procedure. the decoder of the crf autoencoder of @xcite independently generates each word of the sentence using only information from its dependency head, which is linguistically unrealistic. the decoder in the vae approaches uses complicated models such as long short-term memory (lstm) network @xcite and graph convolutional network (gcn) @xcite to leverage context information, but only part of the context can be used as the generation is constrained to follow the left-to-right order. in this work, to handle the challenges mentioned above, we propose our method based on the vae framework with the following features. we relax the tree constraint in both encoding and decoding during training and make the learning of our model fully arc-factored. for the encoder, the relaxation of the tree restriction transforms the task of finding the most probable tree to head selection for each token, hence eliminating the need for the time-consuming dynamic programming parsing algorithms as well as the need to sample tree structures when computing the expectation in vae training. this makes training faster and stabler. the decoder is also arc-factored similar to that used by the crf autoencoder, but an important difference is that we introduce a continuous latent variable for each head word representing its contextual information from both left and right to influence the generation of each child word. we evaluate our model on datasets of several languages and the experiment results demonstrate that our model is effective in utilizing unlabelled data and achieves better parsing accuracy and faster speed than previous work. ## related work dependency parsing is a classic research topic in the natural language processing (nlp) community. because of the difficulty in obtaining dependency annotations, approaches to dependency parsing with scarce or even no labelled training data have been widely studied. most of such approaches @xcite @xcite are extended from dependency model with valence (dmv) proposed by @xcite , a generative model adapting the expectation-maximization (em) algorithm for its parameter optimization. limited by strong contextfree assumption, dmv and its variants fail to capture useful contextual information in the sentence when scoring dependency parses. there are attempts made to incorporate discriminative information with dmv to remedy this problem @xcite , leading to models similar to autoencoders. another line of research is to incorporate traditional machine learning methods for unlabelled data utilization, such as self-training and tri-training @xcite @xcite . a third line of research is to utilize the autoencoder framework, as discussed in section 1. previous work has already broadly applied the autoencoder framework in many nlp tasks other than dependency parsing such as part-of-speech (pos) tagging @xcite and sentence generation @xcite . among them, vae has been proved to be a useful tool in modelling problems with latent representations. however, compared with the crf autoencoder, it is more difficult to use vae in tasks involving latent structures. the main reason is that vae requires marginalizing all latent variables (approximated by monte carlo sampling in implementation), which is intractable when both continuous and structural latent variables are present. @xcite alleviate the problem by first dividing the latent variables into two parts: the discrete ones containing structural information and the continuous ones containing sentence content information. then they develop a sophisticated sampling method to the approximately marginalize the structural latent variables and employ the gumbel-softmax trick @xcite to facilitate backpropagation in the training process of the structural variables while the continuous variables are treated with traditional vae procedures. in the area of transition-based dependency parsing and semantic parsing, the reinforce algorithm is introduced to vae-based models for the marginalization of structural latent variables @xcite . ## model inspired by the previous work mentioned in section 2, we propose our semi-supervised dependency parsing model based on the vae framework. following the classic vae setting, our model assumes that all the observed data are generated from a generative model based on a set of latent variables. the generative model forms the decoder part of vae while the encoder part tries to infer the posterior of the latent variables. formally, for an observed sentence represented by a sequence of tokens @xmath0:t , we assume it is generated from a sequence of continuous latent vectors @xmath1:t according to a latent dependency tree structure y. y and z are assumed to be independent. the tree structure y is also represented as a sequence by defining @xmath2:t , where y i is the index of the dependency head for x i . we generate each token x i conditioned on the latent vector z y i that corresponds to the dependency head of x i . we use y @xmath3, the probability of generating the whole sentence is the product of arc-wise generation probabilities: p (x|z, y) = t @xmath4. note that although we follow @xcite to divide the latent variables into discrete y and continuous z, an important difference is that we define z as a sequence of continuous vectors respectively assigned to each token in the sentence, while @xcite define a single continuous vector representing the whole sentence. our definition of z is intended to make arc-factored autoencoding possible. maximizing the log likelihood of the observed sentence log p θ (x) with distribution parameter θ requires marginalizing all the latent variables, which is intractable with the presence of continuous latent variables. therefore, vae seeks to instead maximize the lower bound of the likelihood by introducing an auxiliary variational distribution q φ (z, y|x) that is parameterized by φ. we assume that q φ is also arcfactored: q(z, y|x) = q(z|x)q(y|x) = t @xmath5. note that by assuming arc-factorization with respect to y, we can no longer enforce that y represents a valid tree structure. this relaxation, however, leads to tractable computation. we illustrate the graphical model representation of x,y,z in fig. 1 . the derivation of the lower bound, formally known as the evidence lower bound objective (elbo), follows that of the vanilla vae with the additional discrete latent variable y: the prior for z and y are set to be the standard normal distribution and uniform distribution respectively, so closed-form computation for the kullback-leibler (kl) divergence can be achieved. ## evaluation settings we evaluate the parsing performance of our model on datasets across 7 languages: english, french, german, italian, spanish, swedish and hindi. to make our evaluation comparable with that of @xcite , for english and french we choose corpora from stanford dependency conversion @xcite of the penn treebank @xcite and the french treebank distributed for the spmrl 2013 shared task @xcite . the corpora for the rest five languages are all from the universal dependencies (ud) v2.0 @xcite we adopt the default split of training, development and test sets for the spmrl and ud corpora and the commonly used split for the penn treebank corpus (section 2-22 for training, section 22 for development and section 23 for test). following @xcite , we split the training set of each dataset into a labelled set and an unlabelled set with the ratio of 1:9 and choose a sentence as labelled one if its index modulo 10 equals zero. the dimensions for the word embeddings and pos tag embeddings are set to 100 and 25. the dimensions in lstms and mlps are uniformly set to 200 except for the layer before word generation, whose dimension is set to 100 in order to fit the word embedding size. the word embeddings used in the encoder part and the decoder part share the same initialization. pre-trained word embeddings are used for all the datasets. for english, we use the 100 dimensions version of glove embedding @xcite . for all the other languages, the embeddings released for the 2017 conll shared task on universal dependency parsing are used. the network parameters are optimized by @xcite with the setting of learning rate 0.002, β 1 = 0.9, and β 2 = 0.9. the hyperparameter α varies for different datasets: α = 0.2 for english and french, α = 0.9 for spanish and α = 0.8 for the other corpora. the number of epochs taken to train the parser until convergence also varies in different datasets, but none of them is above 150 epochs. all the hyperparameters are tuned on the development set for each treebank. ## analysis in this section we conduct a series of analysis on the english penn treebank corpus to shed more insights into our model and reveal where its advantage lies compared with other models. ## conclusion in this paper, we presented a semi-supervised dependency parsing model based on the vae framework. we tackle the main challenges brought by the tree structure constraint of dependency parsing by relaxing the tree constraint during training and making the learning of our model fully arc-factored. the experiments show that the simplicity of the model does not hinder its performance and it achieves better parsing accuracy and faster speed than previous work. in future work we plan to extend our model to other tasks such as semantic dependency parsing and apply it to fully unsupervised scenarios.