Title: SEMI-SUPERVISED AUTOENCODING PROJECTIVE DE-PENDENCY PARSING

Abstract: We describe two end-to-end autoencoding models for semi-supervised graphbased dependency parsing. The first model is a Local Autoencoding Parser (LAP) encoding the input using continuous latent variables in a sequential manner; The second model is a Global Autoencoding Parser (GAP) encoding the input into dependency trees as latent variables, with exact inference. Both models consist of two parts: an encoder enhanced by deep neural networks (DNN) that can utilize the contextual information to encode the input into latent variables, and a decoder which is a generative model able to reconstruct the input. Both LAP and GAP admit a unified structure with different loss functions for labeled and unlabeled data with shared parameters. We conducted experiments on WSJ and UD dependency parsing data sets, showing that our models can exploit the unlabeled data to boost the performance given a limited amount of labeled data.

1. INTRODUCTION:

Dependency parsing captures bi-lexical relationships by constructing directional arcs between words, defining a head-modifier syntactic structure for sentences, as shown in Figure 1 . Dependency trees are fundamental for many downstream tasks such as semantic parsing (Reddy et al., 2016; Marcheggiani & Titov, 2017) , machine translation (Bastings et al., 2017; Ding & Palmer, 2007) , information extraction (Culotta & Sorensen, 2004; Liu et al., 2015) and question answering (Cui et al., 2005) . As a result, efficient parsers (Kiperwasser & Goldberg, 2016; Dozat & Manning, 2017; Dozat et al., 2017; Ma et al., 2018) have been developed using various neural architectures. While supervised approaches have been very successful, they require large amounts of labeled data, particularly when neural architectures are used. Syntactic annotation is notoriously difficult and requires specialized linguistic expertise, posing a serious challenge for low-resource languages. Semisupervised parsing aims to alleviate this problem by combining a small amount of labeled data and a large amount of unlabeled data, to improve parsing performance over labeled data alone. Traditional semi-supervised parsers use unlabeled data to generate additional features, assisting the learning process (Koo et al., 2008) , together with different variants of self-training (Søgaard & Rishøj, 2010) . However, these approaches are usually pipe-lined and error-propagation may occur.

In this paper, we propose two end-to-end semi-supervised parsers based on probabilistic autoencoder models illustrated in Figure 3 , Locally Autoencoding Parser (LAP) and Globally Autoencoding Parser (GAP). In LAP, continuous latent variables are used to support tree inference by providing a better representation, while in GAP, the latent information forms a probability distribution over dependency trees corresponding to the input sentence. A similar idea has been proposed by Corro & Titov (2018) , but our GAP model differs fundamentally from their parser, as GAP does not sample from the posterior of the latent tree structure to approximate the Evidence Lower Bound (ELBO).

Instead it relies on a tractable algorithm to directly compute the posterior to calculate the ELBO.

We summarize our contributions as follows:

1. We proposed two autoencoding parsers for semi-supervised dependency parsing, with complementary strengths, trading off speed vs. accuracy; 2. We propose a tractable inference algorithm to compute the expectation and marginalization of the latent dependency tree posterior analytically for GAP, avoiding sampling from the posterior to approximate the expectation (Corro & Titov, 2018) ; 3. We show improved performance of both LAP and GAP with unlabeled data on WSJ and UD data sets empirically, and improved results of GAP comparing to a recently proposed semi-supervised parser (Corro & Titov, 2018) .

2. RELATED WORK:

Most dependency parsing studies fall into two major groups: graph-based and transition-based (Kubler et al., 2009) . Graph-based parsers (McDonald, 2006) regard parsing as a structured prediction problem to find the most probable tree, while transition-based parsers (Nivre, 2004; 2008) treat parsing as a sequence of actions at different stages leading to a dependency tree.

While earlier works relied on manual feature engineering, in recent years the hand-crafted features were replaced by embeddings and deep neural architectures, leading to improved performance in both graph-based parsing (Nivre, 2014; Pei et al., 2015) and transition-based parsing (Chen & Manning, 2014; Dyer et al., 2015; Weiss et al., 2015) . More recent works rely on neural architectures for learning a representation for scoring structural decisions Andor et al. (2016) ; Kiperwasser & Goldberg (2016) ; Wiseman & Rush (2016) .

The annotation difficulty for this task, has also motivated work on unsupervised (grammar induction) and semi-supervised approaches to parsing (Tu & Honavar, 2012; Jiang et al., 2016; Koo et al., 2008; Li et al., 2014; Kiperwasser & Goldberg, 2015; Cai et al., 2017; Corro & Titov, 2018) .

Similar to other structured prediction tasks, directly optimizing the objective is difficult when the underlying probabilistic model requires marginalizing over the dependency trees. Variational approaches are a natural way for alleviating this problem, as they try to improve the lower bound of the original objective, and were applied in several recent NLP works (Stratos, 2019; Kim et al., 2019b; Chen et al., 2018; Kim et al., 2019b; a) . Variational Autoencoder (VAE) (Kingma & Welling, 2014) is particularly useful for latent representation learning, and is studied in semi-supervised context as the Conditional VAE (CVAE) (Sohn et al., 2015) .

The work mostly related to ours is (Corro & Titov, 2018) as they consider the dependency tree as the latent variable, but their work takes a second approximation to the variational lower bound by an extra step to sample from the latent dependency tree, without identifying a tractable inference. We show that with the given structure, exact inference on the lower bound is achievable without approximation by sampling, which tightens the lower bound.

3. GRAPH-BASED DEPENDENCY PARSING:

A dependency graph of a sentence can be regarded as a directed tree spanning all the words of the sentence, including a special "word"-the ROOT-to originate out. Assuming a sentence length of l, a dependency tree can be denoted as T = (< h 1 , m 1 >, . . . , < h l-1 , m l-1 >), where h t is the index in the sequence of the head word of the dependency connecting the tth word m t as a modifier.

Our graph-based parser is constructed by following the standard structured prediction paradigm (McDonald et al., 2005; Taskar et al., 2005) . In inference, based on the parameterized scoring function S Λ with parameter Λ, the parsing problem is formulated as finding the most probable directed spanning tree for a given sentence x: where T * is the highest scoring parse tree and T is the set of all valid trees for the sentence x.

T * = arg max T ∈T S Λ (x, T ),

It is common to factorize the score of the entire graph into the summation of its substructures: the individual arc scores (McDonald et al., 2005) :

S Λ (x, T ) = (h,m)∈ T s Λ (h, m) = l t=1 s Λ (h t , m t ),

where T represents the candidate parse tree, and s Λ is a function scoring each individual arc. s Λ (h, m) describes the likelihood of forming an arc from the head h to its modifier m in the tree. Through out this paper, the scoring is based on individual arcs, as we focus on first order parsing.

3.1. SCORING FUNCTION USING NEURAL ARCHITECTURE:

We used the same neural architecture as that in Kiperwasser & Goldberg (2016) 

r h-arc t = W h o t ; r m-arc t = W m o t , s Λ (h, m) = w (tanh(r h-arc h + r m-arc m + b)).

In this formulation, we first use two parameters to extract two different representations that carry two different types of information: a head seeking for its modifier (h-arc); as well as a modifier seeking for its head (m-arc). Then a nonlinear function maps them to an arc score.

For a single sentence, we can form a scoring matrix as shown in Figure 4 , by filling each entry in the matrix using the score we obtained. Therefore, the scoring matrix is used to represent the head-modifier arc score of all the possible arcs connecting words in a sentence (Zheng, 2017) .

Using the scoring arc matrix, we build graph-based parsers. Since exploring neural architectures for scoring is not our focus, we did not explore other architectures, however performance shall be further improved using advanced neural architectures (Dozat & Manning, 2017; Dozat et al., 2017) .

4. PRELIMINARIES: VARIATIONAL AUTO-ENCODER AND TREE CRF:

Variational Autoencoder (VAE). The typical VAE is a directed graphical model with Gaussian latent variables, denoted by z. A generative process first generates a set of z from the prior distribution π(z) and the data x is generated as P θ (x|z) parameterized by θ given input x, In our scenario, x is an input sequence and z is a sequence of latent variables corresponding to it.

The VAE framework seeks to maximize the complete log-likelihood log P (x) by marginalizing out the latent variable z. Since direct parameter estimation of log P (x) is usually intractable, a common solution is to maximize its Evidence Lower Bound (ELBO) by introducing an auxiliary posterior Q(x|z) distribution that encodes the input into the latent space.

Tree Conditional Random Field. Linear chain CRF models an input sequence x = (x 1 . . . x l ) of length l with labels y = (y 1 . . . y l ) with globally normalized probability

P (y|x) = exp S(x, y) ỹ∈Y exp S(x, ỹ)

, where Y is the set of all the possible label sequences, and S(x, y) the scoring function, usually decomposed as emission ( l i=1 s(x i , y i )) and transition ( l i=1 s(y i , y i+1 )) for first order models. Tree CRF models generalize linear chain CRF to trees. For dependency trees, if POS tags are given, the tree CRF model tries to resolve which node pairs should be connected with direction, such that the arcs form a tree. The potentials in the dependency tree take an exponential form, thus the conditional probability of a parse tree T , given the sequence, can be denoted as:

EQUATION

where Z(x) = T ∈T(x) exp S(x, T ) is the partition function that sums over all possible valid dependency trees in the set T(x) of the given sentence x.

5. LOCALLY AUTOENCODING PARSER (LAP):

We extend the original VAE model for sequence labeling (Chen et al., 2018) to dependency parsing by building a latent representation position-wise to form a sequential latent representation.

It has been shown that under the VAE framework the latent representation can reflect the desired properties of the raw input (Kingma & Welling, 2014) . This inspired us to use the continuous latent variable as neural representations for the dependency parsing task. Typically, each token in the sentence is represented by its latent variable z t , which is a high-dimensional Gaussian variable. This configuration on the one hand ensures the continuous latent variable retains the contextual information from lower-level neural models to assist finding its head or its modifier; on the other hand, it forces tokens of similar properties closer in the euclidean space. We adjust the original VAE setup in our semi-supervised task by considering examples with labels, similar to recent conditional variational formulations (Sohn et al., 2015; Miao & Blunsom, 2016; Zhou & Neubig, 2017) .

We propose a full probabilistic model for any certain sentence x, with the unified objective to maximize for supervised and unsupervised parsing as follows:

J = log P θ (x)P ω (T |x), = 1, if T exists, 0, otherwise.

This objective can be interpreted as follows: if the training example has a golden tree T with it, then the objective is the log joint probability P θ,ω (T , x); if the golden tree is missing, then the objective is the log marginal probability P θ (x). The probability of a certain tree is modeled by a tree-CRF in Eq. 1 with parameters ω as P ω (T |x). Given the assumed generative process P (x|z), directly optimizing this objective is intractable, we instead optimize its ELBO (We show the details in the appendix, proving J lap is the ELBO of J in Lemma A.1):

J lap = E z∼Q φ (z|x) [log P θ (x|z)] -KL(Q φ (z|x)||P θ (z)) + E z∼Q φ (z|x) [log P ω (T |z)] .

6. GLOBALLY AUTOENCODING PARSER (GAP):

Instead of autoencoding the input locally at the sequence level, we could alternatively directly regard the dependency tree as the structured latent variable to reconstruct the input sentence, by building a model containing both a discriminative component and a generative component. The discriminative component builds a neural CRF model for dependency tree construction, and the generative model reconstructs the sentence from the factor graph as a Bayesian network, by assuming a generative process in which each head generates its modifier. Concretely, the latent variable in this model is the dependency tree structure.

6.1. DISCRIMINATIVE COMPONENT: THE ENCODER:

We model the discriminative component in our model as P Φ (T |x) parameterized by Φ, taking the same form as in Eq. 1. Typically in our model, Φ are the parameters of the underlying neural networks, whose architecture is described in Sec. 3.1.

6.2. GENERATIVE COMPONENT: THE DECODER:

We use a set of conditional categorical distributions to construct our Bayesian network decoder. More specifically, using the head h and modifier m notation, each head reconstructs its modifier with the probability P (m t |h t ) for the tth word in the sentence (0th word is always the special "ROOT" word), which is parameterized by the set of parameters Θ. Given Θ as a matrix of |V| by |V|, where |V| is the vocabulary size, θ mh is the item on row m column h denoting the probability that the head word h would generate m. In addition, we have a simplex constraint m∈V θ mh = 1.

The probability of reconstructing the input x as modifiers m in the generative process is

P Θ (m|T ) = l t P (m t |h t ) = l t θ mtht ,

where l is the sentence length and P (m t |h t ) represents the probability a head generating its modifier.

6.3. A UNIFIED SUPERVISED AND UNSUPERVISED LEARNING FRAMEWORK:

With the design of the discriminative component and the generative component of the proposed model, we have a unified learning framework for sentences with or without golden parse tree.

The complete data likelihood of a given sentence, if the golden tree is given, is

P Θ,Φ (m, T |x) =P Θ (m|T )P Φ (T |x) = l t=1 P (m t |h t ) exp S Φ (x, T ) Z(x) = exp (h,m)∈T s Φ,Θ (h, m) Z(x) ,

where s Φ,Θ (h, m) = s Φ (h, m) + log θ mh , with m, x and T all observable.

For unlabeled sentences, the complete data likelihood can be obtained by marginalizing over all the possible parse trees in the set T(x):

P Θ,Φ (m|x) = T ∈T(x) P Θ,Φ (m, T |x) = U (x) Z(x) ,

where

U (x) = T ∈T(x) exp (h,m)∈T s Φ,Θ (h, m).

We adapted a variant of Eisner (1996) 's algorithm to marginalize over all possible trees to compute both Z and U , as U has the same structure as Z, assuming a projective tree.

We use log-likelihood as our objective function. The objective for a sentence with golden tree is:

J l = log P Θ,Φ (m, T |x) = (h,m)∈T s Φ,Θ (h, m) -log Z(x)

Algorithm 1 Learning Algorithm for GAP 1: Initialize the parameter Θ in the decoder with the labeled data set {x, T } l . 2: Initialize Λ in the encoder randomly.

3: for t in epochs do 4:

for sentence x l i with golden parse tree T l i in the labeled data set {x, T } l do 5:

Stochastically update the parameter Λ in the encoder using Adam while fixing the decoder. Compute the posterior Q(T ) in an arc factored manner for x u i tractably.

10:

Compute the expectation of all possible (h(head) → m(modif ier)) occurrence in the sentence x based on Q(T ).

11::

Update buffer B using the expectation to the power for 1 1-σ of all possible (h → m).

12:

end for 13:

Obtain Θ globally and analytically based on the buffer B and renew the decoder. 14: end for If the input sentence does not have an annotated golden tree, then the objective is:

J u = log P Θ,Φ (m|x) = log U (x) -log Z(x).

(2) Thus, during training, the objective function with shared parameters is chosen based on whether the sentence in the corpus has golden parse tree or not.

6.4. LEARNING:

Directly optimizing the loss in Eq.2 is difficult for the unlabeled data, and may lead to undesirable shallow local optima without any constraints. Instead, we derive the evidence lower bound (ELBO) of log P Θ,Φ (m|x) as follows, by denoting Q(T ) = P Θ,Φ (T |m, x) as the posterior:

log P Θ,Φ (m|x) = log T Q(T ) P Θ,Φ (m, T |x) Q(T ) = log E T ∼Q(T ) P Θ,Φ (m, T |x) Q(T ) ≥ E T ∼Q(T ) log P Θ,Φ (m, T |x) Q(T ) = E T ∼Q(T ) [log P Θ (m|T )] -KL [Q(T )||P Φ (T |x)] .

Instead of maximizing the log-likelihood directly, we alternatively maximize the ELBO, so our new objective function for unlabeled data becomes max

Θ,Φ i E T ∼Q(T ) [log P Θ (m|T )] -KL [Q(T )||P Φ (T |x)] .

In addition, to account for the unambiguity in the posterior, we incorporate entropy regularization (Tu & Honavar, 2012) when applying our algorithm, by adding an entropy term -T Q(T ) log Q(T ) with a non-negative factor σ when the input sentence does not have a golden tree. Adding this regularization term is equivalent as raising the expectation of Q(T ) to the power of 1 1-σ . We annealed σ from 1 to 0.3 from the beginning of training to the end, as in the beginning, the generative model is well initialized by sentences with golden trees that resolve disambiguity.

In practice, we found the model benefits more by fixing the parameter Φ when the data is unlabeled and optimizing the ELBO w.r.t. the parameter Θ. We attribute this to the strict convexity of the ELBO w.r.t. Θ, by sketching the proof in the appendix. The details of training are shown in Alg. 1.

6.5. TRACTABLE INFERENCE:

The common approach to approximate the expectation of the latent variables from the posterior distribution Q(T ) is via sampling in VAE-type models (Kingma & Welling, 2014) . In a significant contrast to that, we argue in this model the expectation of the latent variable (which is the dependency tree structure) is analytically tractable by designing a variant of the inside-outside algorithm (Eisner, 1996; Paskin, 2001) in an arc decomposed manner. We leave the detailed derivation in the appendix. A high-level explanation is that assuming the dependency tree is projective, specialized belief propagation algorithm exists to compute not only the marginalization but also the expectation analytically, making inference tractable.

7. EXPERIMENTS:



7.1. EXPERIMENTAL SETTINGS:

Data sets First we compared our models' performance with strong baselines on the WSJ data set, which is the Stanford Dependency conversion (De Marneffe & Manning, 2008) of the Penn Treebank (Marcus et al., 1993) using the standard section split: 2-21 for training, 22 for development and 23 for testing. Second we evaluated our models on multiple languages, using data sets from UD (Universal Dependency) 2.3 (Mcdonald et al., 2013) . Since semi-supervised learning is particularly useful for low-resource languages, we believe those languages in UD can benefit from our approach.The statistics of the data used in our experiments are described in Table 3 in appendix.

To simulate the low-resource language environment, we used 10% of the whole training set as the annotated, and the rest 90% as the unlabeled.

Input Representation and Architecture Since we use the same neural architecture in all of our models, we specify the details of the architecture once, as follows: The internal word embeddings have dimension 100 and the POS embeddings have dimension 25. The hidden layer of the bi-LSTM layer is of dimension 125. The nonlinear layers used to form the head and the modifier representation both have 100 dimension. For LAP, we use separate bi-LSTMs for words and POSs. In GAP, using "POS to POS" decoder only yield the satisfactory performance. This echos the finding that complicated decoders may cause "posterior collapse" (van den Oord et al., 2017; Kim et al., 2018) .

Training In the training phase, we use Adam (Kingma & Ba, 2014) to update all the parameters in both LAP and GAP, except the parameters in the decoder in GAP, which are updated by using their global optima in each epoch. We did not take efforts to tune models' hyper-parameters and they remained the same across all the experiments.

7.2. SEMI-SUPERVISED DEPENDENCY PARSING ON WSJ DATA SET:

We first evaluate our models on the WSJ data set and compared the model performance with other semi-supervised parsing models, including CRFAE (Cai et al., 2017) , which is originally designed for dependency grammar induction but can be modified for semi-supervised parsing, and "differentiable Perturb-and-Parse" parser (DPPP) (Corro & Titov, 2018) . To contextualize the results, we also experiment with the supervised neural margin-based parser (NMP) (Kiperwasser & Goldberg, 2016) , neural tree-CRF parser (NTP) and the supervised version of LAP and GAP, with only the labeled data. To ensure a fair comparison, our experimental set up on the WSJ is identical as that in DPPP and we use the same 100 dimension skip-gram word embeddings employed in an earlier transition-based system (Dyer et al., 2015) . We show our experimental results in Table 1 .

As shown in this table, both of our LAP and GAP model are able to utilize the unlabeled data to increase the overall performance comparing with only using labeled data. Our LAP model performs slightly worse than the NMP model, which we attribute to the increased model complexity by incorporating extra encoder and decoders to deal with the latent variable. However, our LAP model achieved comparable results on semi-supervised parsing as the DPPP model, while our LAP model is simple and straightforward without additional inference procedure. Instead, the DPPP model has to sample from the posterior of the structure by using a "GUMBEL-MAX trick" to approximate the categorical distribution at each step, which is intensively computationally expensive. Further, our GAP model achieved the best results among all these methods, by successfully leveraging the the unlabeled data in an appropriate manner. We owe this success to such a fact: GAP is able to calculate the exact expectation of the arc-decomposed latent variable, the dependency tree structure, in the ELBO for the complete data likelihood when the data is unlabeled, rather than using sampling Model UAS DPPP (Corro & Titov, 2018)(L) 88.79 DPPP (Corro & Titov, 2018)(L+U) 89.50 CRFAE (Cai et al., 2017)(L+U) 82.34 NMP (Kiperwasser & Goldberg, 2016) Table 2 : In this table we compare different models on multiple languages from UD. Models were trained in a fully supervised fashion with labeled data only (noted as "L") or semi-supervised (notes as "L+U"). "ST" stands for self-training. to approximate the true expectation. Self-training using NMP with both labeled and unlabeled data is also included as a base-line, where the performance is deteriorated without appropriately using the unlabeled data.

7.3. SEMI-SUPERVISED DEPENDENCY PARSING ON THE UD DATA SET:

We also evaluated our models on multiple languages from the UD data and compared the model performance with the semi-supervised version of CRFAE and the fully supervised NMP and NTP.

To fully simulate the low-resource scenario, no external word embeddings were used.

We summarize the results in Table 2 . First, when using labeled data only, LAP and GAP have similar performance as NMP and NTP. Second, we note that our LAP and GAP models do benefit from the unlabeled data, compared to using labeled data only. Both our LAP and GAP model are able to exploit the hidden information in the unlabeled data to improve the performance. Comparing between LAP and GAP, we notice GAP in general has better performance than LAP, and can better leverage the information in the unlabeled data to boost the performance. These results validate that GAP is especially useful for low-resource languages with few annotations. We also experimented using self-training on the labeled and unlabeled data with the NMP model. As results show, selftraining deteriorate the performance especially when the size of the training data is small.

8. CONCLUSION:

In this paper, we present two semi-supervised parsers, which are locally autoencoding parser (LAP) and globally autoencoding parser (GAP). Both of them are end-to-end learning systems enhanced with neural architecture, capable of utilizing the latent information within the unlabeled data together with labeled data to improve the parsing performance, without using external resources. More importantly, our GAP model outperforms the previous published (Corro & Titov, 2018) semisupervised parsing system on the WSJ data set. We attribute this success to two reasons: First, our GAP model consists both a discriminative component and a generative component. These two components are constraining and supplementing each other such that final parsing choices are made in a checked-and-balanced manner to avoid over-fitting. Second, instead of sampling from posterior of the latent variable (the dependency tree) (Corro & Titov, 2018) , our model analytically computes the expectation and marginalization of the latent variable, such that the global optima can be found for the decoder, which leads to an improved performance.

A APPENDIX

DETAILS OF THE LAP MODEL ELBO OF LAP'S ORIGINAL OJECTIVE:

Lemma A.1. J lap is the ELBO (evidence lower bound) of the original objective J , with an input sequence x.

Denote the encoder Q is a distribution used to approximate the true posterior distribution P φ (z|x), parameterized by φ such that Q encoding the input into the latent space z.

Proof. log P θ (x)P ω (T |x) = log P θ (x)

U + log P ω (T |x) L U = log z Q φ (z|x) P θ (x) Q φ (z|x) d z ≥ E z∼Q φ (z|x) [log P θ (x|z)] - E z∼Q φ (z|x) log Q φ (z|x) P θ (x) = E z∼Q φ (z|x) [log P θ (x|z)] -KL (Q φ (z|x)||P θ (z)) , (ELBO of traditional VAE) L = log P ω (T |x) = log z P ω (T |z)Q φ (z|x)d z = log E z∼Q φ (z|x) [P ω (T |z)] ≥ E z∼Q φ (z|x)

[log P ω (T |z)] .

Combining U and L leads to the fact:

U + L ≥ E z∼Q φ (z|x) [log P θ (x|z)] -KL(Q φ (z|x)||P θ (z)) + E z∼Q φ (z|x) [log P ω (T |z)] = J lap

In practice, similar as VAE-style models, E z∼Q φ (z|x)

[log P θ (x|z)] is approximated by

1 N N j=1 log P θ (x|z j ) and E z∼Q φ (z|x)

[log P ω (T |z)] by 1 N N j=1 log P ω (T |z j ), where z j is the jthe sample of N samples sampled from Q φ (z|x). At prediction stage, we simply use µ z rather than sampling z.

MEAN FIELD APPROXIMATION AND ANNEALING:

Here we used a mean field approximation (Tanaka, 1999) together with the conditional independence assumption by assuming P θ (z|x) ≈ l t=1 Q φ (z t |x t ). The generative model P θ (x|z) acting as decoder parameterized by θ tries to regenerate the specific input x t at time step t from the latent space z t , as we assume conditional independence in the generative process among P θ (x t |z t ). The encoder and the decoder are trained jointly in the classical variational autoencoder framework, by minimizing the KL divergence between the approximated posterior and the true posterior.

We describe the encoder and decoder formulation. We parameterize the encoder Q φ (z t |x t ) in such a way: First a bi-LSTM is used to obtain a non-linear transformation h t of the original x t ; then two separate MLPs are used to compute the mean µ zt and the variance σ 2 zt . The generative story P θ (x t |z t ) follows such parameterization: we used a MLP of two hidden layers in-between to take z t as the input, and then predict the word (or POS tag) over the vocabulary, such that the reconstruction probability can be measured.

Following traditional VAE training paradigms, we also apply the "re-parameterization" trick (Kingma & Welling, 2014) to circumvent the non-differentiable sampling procedure to sample z t from the Q φ (z t |x t ). Instead of directly sample from N (µ zt , σ 2 zt ), we form z t = µ zt + σ 2 zt by sampling ∼ N (0, I). In addition, to avoid hindering learning during the initial training phases, following previous works (Chen et al., 2018; Bowman et al., 2016) , we anneal the temperature on the KL divergence term from a small value to 1.

EMPIRICAL BAYESIAN TREATMENT:

From an empirical Bayesian perspective, rather than fixing the prior using some certain distributions, it is beneficial to estimate the prior distribution directly from the data by treating prior's parameters part of the model parameters. Similar to the approach used in the previous study (Chen et al., 2018) , LAP also learns the priors from the data by updating them iteratively. We initialize the priors from a standard Gaussian distribution N (0, I), where I is an identity matrix. During the training, the current priors are updated using the last optimized posterior, following the rule:

π k θ (z) = x Q k-1 φ (z|x)P (x),

where P (x) represents the empirical data distribution, and k the iteration step. Empirical Bayesian is also named as "maximum marginal likelihood", such that our approach here is to marginalize over the missing observation as a random variable.

INCORPORATING POS AND EXTERNAL EMBEDDINGS:

In previous studies (Chen & Manning, 2014; Dozat & Manning, 2017; Dozat et al., 2017; Kiperwasser & Goldberg, 2016) exploring parsing using neural architectures, POS tags and external embeddings have been shown to contain important information characterizing the dependency relationship between a head and a child. Therefore, in addition to the variational autoencoding framework taking as input the randomly initialized word embeddings, optionally we can build the same structure for POS to reconstruct tags and for external embeddings to reconstruct words as well, whose variational objectives are U p and U e respectively. Hence, the final variational objective can be a combination of three: U = U w (The original U in Lemma A.1) + U p + U e (or just U = U w + U p if external embeddings are not used).

DETAILS OF THE GAP MODEL MARGINALIZATION AND EXPECTATION OF LATENT PARSE TREES:

Assuming the sentence is of length l, and we have obtained a arc decomposed scoring matrix S of size l ×l, and an entry S[i, j] i =j,j =0 stands for the arc score where ith word is the head and jth word the modifier. We first describe the inside algorithm to compute the marginalization of all possible projective trees in Algo.2.

We then describe the outside algorithm to compute the outside tables in Algo. 3. In this algorithm, stands for the logaddexp operation.

Finally, with the inside table α, outside table β and the marginalization Z of all possible latent trees, we can compute the expectation of latent tree in an arc-decomposed manner. Algo. 4 describes the procedure. It results the matrix P containing the expectation of all individual arcs by marginalize over all other arcs except itself.

Light modification is needed in our study to calculate the expectation w.r.t. the posterior distribution Q(T ) = P Θ,Φ (T |m, x), as we have CONVEXITY OF ELBO W.R.T. Θ

Algorithm 2 Inside Algorithm Input: S Output: α, Z 1: α ← -∞ 2: for s ∈ 0 . . . l -1 do 3: if s > 0 then 4: α[s, s, L, C] ← 0 5: end if 6: α[s, s, R, C] ← 0 7: end for 8: for k ∈ 1 . . . l -1 do 9: for s ∈ 0 . . . l -k do 10: t = s + k 11: if s > 0 then 12: α[s, t, L, I] ← log u∈[s,t] exp (α[s, u, L, C] + α[u, t, L, C]) + S[t, s] 13: end if 14: α[s, t, R, I] ← log u∈[s,t] exp (α[s, u, L, C] + α[u, t, L, C]) + S[s, t]

In this section we derive the strict convexity of ELBO w.r.t. Θ. Since we only care about the term containing Θ, the KL divergence term degenerates to a constant. For sentence i, Q(T i ) has been derived in the previous section as matrix P and 1 is the indication function.

max Θ i E Ti∼Q(Ti) [log P Θ (m i |T i )] -KL [Q(T i )||P Φ (T i |x i )] max Θ i Ti∈T(x i ) Q(T i ) log P Θ (m i |T i ) + Const max Θ (h→m) log θ mh E (h→m)∼Q 1(h → m) max Θ (h→m) Q(1(h → m)) log θ mh Q(1(h → m)

) is a Bernoulli distribution, indicating whether the arc (h → m) exists.

s.t.:

m θ mh = 1 ∀h.

(3)

DATA SET STATISTICS:

We show the details of the statistics of the WSJ data set, which is the Stanford Dependency conversion (De Marneffe & Manning, 2008) of the Penn Treebank (Marcus et al., 1993) and the statistics of the languaes we used in UD (Universal Dependency) 2.3 (Mcdonald et al., 2013) here.

:



Figures and Tables:

Figure 1: A dependency tree: directional arcs represent head-modifier relation between words.

Figure 3: Illustration of two different parsers. (a) LAP uses continuous latent variable to form the dependency tree (b) GAP treats the dependency tree as the latent variable.

unlabeled sentence x u i in the unlabeled data set {x} u do 9:

, t, L, C] ← log u∈[s,t-1] exp (α[s, u, L, C] + α[u, t, L, C]) , t, R, C] ← log u∈[s+1,t] exp (α[s, u, R, I] + α[u, t, R, I]) 19:end for 20: end for21: Z ← α[0, l -1, R, C] Algorithm 3 Outside Algorithm Input: S, α Output: β 1: β ← -∞ 2: β[0, l -1, R, C] ← 0 3: for k ∈ l -1 . . . 1 do 4:for s ∈ 0 . . . l -k do 5:

[s, t] ← exp(α[s, t, R, I] + β[s, t, R, I] -Z) [t, s] ← exp(α[s, t, L, I] + β[s, t, L, I] -Z) for P Θ,Φ (T |m, x) = P Θ,Φ (T , m|x) P Θ,Φ (m|x) s Φ,Θ (h, m)is the real marginal we need to calculate using the transformed scoring matrix S as input in the inside algorithm. Each entry in this transformed scoring matrix is defined in the text as s Φ,Θ (h, m).

's study. We first use a bi-LSTM model to take as input u t = [p t ; e t ] at position t to incorporate contextual information, by feeding the word embedding e t concatenated with the POS (part of speech) tag embeddings p t of each word. The bi-LSTM then projects u t as o t .Subsequently a nonlinear transformation is applied on these projections. Suppose the hidden states generated by the bi-LSTM are [o root , o 1 , o 2 , . . . , o t , . . . , o l ], for a sentence of length l, we compute the arc scores by introducing parameters W h , W m , w and b, and transform them as follows:

Table content: <table/>

Comparing model performance on WSJ data set with 10% labeled data. "L" means only 10% labeled data is used, while "L+U" means both 10% labeled and 90% unlabeled data are used.

Table content: <table><tr><td>(L) 89.64</td></tr></table>

[s + 1 : t + 1, t, R, C] ← (β[s + 1 : t + 1, t, R, C], β[s, t, R, C] + α[s, s + 1 : t + 1, R, I]) [s, s : t, L, C] ← (β[s, s : t, L, C], β[s, t, R, C] + α[s : t, t, L, I]) : t, t, L, I] ← (β[s : t, t, L, I], β[s, t, L, C] + α[s, s : t, L, C]) [s, s : t, R, C] ← (β[s, s : t, R, C], β[s, t, R, I] + α[s + 1 : t + 1, t, L, C] + S[s, t]) + 1 : t + 1, t, L, C] ← (β[s + 1 : t + 1, t, L, C], β[s, t, R, I] + α[s, s : t, R, C] + S[s, t]) [s, s : t, R, C] ← (β[s, s : t, R, C], β[s, t, L, I] + α[s + 1 : t + 1, t, L, C] + S[t, s]) Arc Decomposed Expectation Input: α, β, Z Output: P 1: P ← 0 2: for s ∈ 0 . . . l -2 do 3: for t ∈ s + 1 . . . l -1 do

Table content: <table><tr><td colspan="2">Algorithm 4</td></tr><tr><td>8:</td><td>if s &gt; 0 then</td></tr><tr><td>9:</td><td/></tr><tr><td colspan="2">10: β[s 11: end if</td></tr><tr><td>12:</td><td/></tr><tr><td colspan="2">13: β[s 14: if s &gt; 0 then</td></tr><tr><td>15:</td><td/></tr><tr><td>16:</td><td/></tr><tr><td>17:</td><td>end if</td></tr><tr><td>18:</td><td>end for</td></tr><tr><td colspan="2">19: end for</td></tr></table>

Peer review (iclr2020):
The paper contains two semi-supervised dependency parsing algorithms. The two are end-to-end autoencoding models. For one the latent variables are sequences and for the other the latent variables are dependency trees. Experimental results are given showing that unlabeled data help to slightly improve performance. One main contribution is to improve over the algorithm by Corro and Titov at ICLR last year. For this, the paper contains a tractable algorithm for computing the optimal dependency tree structure. The paper is not easy to read. A number of important details are not given, either omitted or to be found in references. My main concern is that the main contribution is left in Appendix and that the Appendix does not help much to understand why the assertion stands. Also, using the Eisner algorithm has the drawback that the GAP method is no more end to end. Therefore I am inclined to reject the paper. Detailed comments and questions. * First contribution. The paper said that the two methods provide a trade-off speed vs accuracy. But the paper does not consider this question. It should be nice to compare the complexity, both theoretically and experimentally, of the two methods. * Second contribution. As said before here is my main concern. The tractable inference is the topic of Section 6.5. But the few lines do not help and refer to the Appendix. The appendix does not help much. It seems that you use a variant of the Eisner algorithm but what are the differences? Also, it is not clear how is computed the transformed scoring matrix ? And why this transformed matrix allows to compute the optimal dependency tree for unlabeled data? The GAP model is no more end-to-end because of using the (a variant of the) Eisner algorithm. * Second contribution. It should be nice (in relation to the first item) to give the complexity of the algorithm. The paper should compare time efficiency for the GAP algorithm and the Corro and Titov*s algorithm. * Related work. Kim et al 2019b is cited two times. You should discuss this paper and recent new developments in unsupervised parsing. * Section 3.1. It is not clear whether you use pre-trained word embeddings. For instance, in the Kiperwasser and Goldberg*s paper, the distinction between using internal word embeddings and pre-trained word embeddings is made clear with improved performance for the latter. Also, the use of POS tag embeddings is not done in other systems. Please explain why the method uses such embeddings and discuss whether they improve performance. I do not understand the last paragraph of Section 3.1. * Section 6.5. Should be an important part of the paper. * Section 7. The paper should made explicit the hyperparameters and their default value. It is not clear whether the development set was used. * Section 7.1. I do not understand the sentence *in GAP using POS to POS decoder only yield the satisfactory performance*. * Section 7.2. As said before a comparison between the computation time of GAP and Corro and Titov*s algorithm should be given. * The paper does not consider recent improvements for word embeddings such as ELMo (Peters et al 2018) and BERT (Devlin et al 2018). I wonder whether using such word embeddings would improve greatly dependency parsing algorithms. Typos. * Section 3, l2, a special root token * Section 3, l2, length of