Human annotation for syntactic parsing is expensive, and large resources are available only for a  fraction of languages. A question we ask is whether one can leverage abundant unlabeled texts to improve syntactic parsers, beyond just using the texts to obtain more generalisable lexical features (i.e. beyond word embeddings). To this end, we propose a novel latent-variable generative model for semi-supervised syntactic dependency parsing. As exact inference is intractable, we introduce a differentiable relaxation to obtain approximate samples and compute gradients with respect to the parser parameters. Our method (Differentiable Perturb-and-Parse) relies on differentiable dynamic programming over stochastically perturbed edge scores. We demonstrate effectiveness of our approach with experiments on English, French and Swedish. A dependency tree is a lightweight syntactic structure exposing (possibly labeled) bi-lexical relations between words BID77 BID24 , see Figure 1 . This representation has been widely studied by the NLP community leading to very efficient state-of-the-art parsers BID30 BID12 BID43 , motivated by the fact that dependency trees are useful in downstream tasks such as semantic parsing BID66 , machine translation BID11 BID4 , information extraction BID9 BID42 , question answering BID8 and even as a filtering method for constituency parsing BID34 , among others.Unfortunately, syntactic annotation is a tedious and expensive task, requiring highly-skilled human annotators. Consequently, even though syntactic annotation is now available for many languages, the datasets are often small. For example, 31 languages in the Universal Dependency Treebank, 1 the largest dependency annotation resource, have fewer than 5,000 sentences, including such major languages as Vietnamese and Telugu. This makes the idea of using unlabeled texts as an additional source of supervision especially attractive.In previous work, before the rise of deep learning, the semi-supervised parsing setting has been mainly tackled with two-step algorithms. On the one hand, feature extraction methods first learn an intermediate representation using an unlabeled dataset which is then used as input to train a supervised parser BID35 BID83 BID7 BID73 . On the other hand, the self-training and co-training methods start by learning a supervised parser that is then used to label extra data. Then, the parser is retrained with this additional annotation BID68 BID25 BID50 . Nowadays, unsupervised feature extraction is achieved in neural parsers by the means of word embeddings BID55 BID65 . The natural question to ask is whether one can exploit unlabeled data in neural parsers beyond only inducing generalizable word representations. Figure 1: Dependency tree example: each arc represents a labeled relation between the head word (the source of the arc) and the modifier word (the destination of the arc). The first token is a fake root word. Our method can be regarded as semi-supervised Variational Auto-Encoder (VAE, Kingma et al., 2014) . Specifically, we introduce a probabilistic model (Section 3) parametrized with a neural network (Section 4). The model assumes that a sentence is generated conditioned on a latent dependency tree. Dependency parsing corresponds to approximating the posterior distribution over the latent trees within this model, achieved by the encoder component of VAE, see Figure 2a . The parameters of the generative model and the parser (i.e. the encoder) are estimated by maximizing the likelihood of unlabeled sentences. In order to ensure that the latent representation is consistent with treebank annotation, we combine the above objective with maximizing the likelihood of gold parse trees in the labeled data.Training a VAE via backpropagation requires marginalization over the latent variables, which is intractable for dependency trees. In this case, previous work proposed approximate training methods, mainly differentiable Monte-Carlo estimation BID27 BID67 and score function estimation, e.g. REINFORCE BID80 . However, REINFORCE is known to suffer from high variance BID56 . Therefore, we propose an approximate differentiable Monte-Carlo approach that we call Differentiable Perturb-and-Parse (Section 5). The key idea is that we can obtain a differentiable relaxation of an approximate sample by (1) perturbing weights of candidate dependencies and (2) performing structured argmax inference with differentiable dynamic programming, relying on the perturbed scores. In this way we bring together ideas of perturb-and-map inference BID62 BID45 and continuous relaxation for dynamic programming BID53 . Our model differs from previous works on latent structured models which compute marginal probabilities of individual edges BID26 ; BID41 . Instead, we sample a single tree from the distribution that is represented with a soft selection of arcs. Therefore, we preserve higher-order statistics, which can then inform the decoder. Computing marginals would correspond to making strong independence assumptions. We evaluate our semi-supervised parser on English, French and Swedish and show improvement over a comparable supervised baseline (Section 6).Our main contributions can be summarized as follows: (1) we introduce a variational autoencoder for semi-supervised dependency parsing; (2) we propose the Differentiable Perturb-and-Parse method for its estimation; (3) we demonstrate the effectiveness of the approach on three different languages. In short, we introduce a novel generative model for learning latent syntactic structures. The fact that T is a soft selection of arcs, and not a combinatorial structure, does not impact the decoder. Indeed, a GCN can be run over weighted graphs, the message passed between nodes is simply multiplied by the continuous weights. This is one of motivations for using GCNs rather than a Recursive LSTMs BID74 in the decoder. On the one hand, running a GCN with a matrix that represents a soft selection of arcs (i.e. with real values) has the same computational cost than using a standard adjacency matrix (i.e. with binary elements) if we use matrix multiplication on GPU. 13 On the other hand, a recursive network over a soft selection of arcs requires to build a O(n 2 ) set of RNN-cells that follow the dynamic programming chart where the possible inputs of a cell are multiplied by their corresponding weight in T, which is expensive and not GPU-friendly. We presented a novel generative learning approach for semi-supervised dependency parsing. We model the dependency structure of a sentence as a latent variable and build a VAE. We hope to motivate investigation of latent syntactic structures via differentiable dynamic programming in neural networks. Future work includes research for an informative prior for the dependency tree distribution, for example by introducing linguistic knowledge BID57 BID61 or with an adversarial training criterion BID46 . This work could also be extended to the unsupervised scenario.where z is the sample. As such, e ∼ N (0, 1) is an input of the neural network for which we do not need to compute partial derivatives. This technique is called the reparametrization trick BID27 BID67 .
Differentiable dynamic programming over perturbed input weights with application to semi-supervised VAE
{"src": "scitldr-AIC_train", "paper_id": "BJlgNh0qKQ"}