Unsupervised Parsing with S - DIORA : Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders (2020)

Abstract: The deep inside-outside recursive autoencoder (DIORA; Drozdov et al. 2019) is a self-supervised neural model that learns to induce syntactic tree structures for input sentences *without access to labeled training data*. In this paper, we discover that while DIORA exhaustively encodes all possible binary trees of a sentence with a soft dynamic program, its vector averaging approach is locally greedy and cannot recover from errors when computing the highest scoring parse tree in bottom-up chart parsing. To fix this issue, we introduce S-DIORA, an improved variant of DIORA that encodes a single tree rather than a softly-weighted mixture of trees by employing a hard argmax operation and a beam at each cell in the chart. Our experiments show that through *fine-tuning* a pre-trained DIORA with our new algorithm, we improve the state of the art in *unsupervised* constituency parsing on the English WSJ Penn Treebank by 2.2-6% F1, depending on the data used for fine-tuning.

## introduction syntactic parse trees are valuable intermediate features for many nlp pipelines @xcite , as a soft constraint @xcite , a hard constraint @xcite , or in multi-task learning with syntactic scaffolds @xcite . syntactic inductive bias can also improve generalization of deep learning models @xcite . these results have motivated researchers to pursue unsupervised parsing, with the hope of training syntax-dependent models on large amounts of data without annotation @xcite @xcite @xcite . of these models, we focus on the deep insideoutside recursive autoencoder (diora; @xcite . diora encodes sentences in a optimal decisions. by assigning a low weight to a potentially important subtree when recursively computing the vector for a target tree, it is difficult or impossible to recover and the important subtree is washed out (represented in light gray). our method, s-diora (bottom row) can recover from errors, and the desired tree ends up at the top of the beam in the right-most column. diora is a strong unsupervised parser in spite of its locally greedy nature. diora works by encoding all subtrees covering a particular span as separate vectors, and then computing a weighted average of these vectors -diora uses this averaged vector later in the dynamic program to represent the entire forest of trees covering a span. diora computes a score for each subtree; intuitively, a subtree's score affects how strongly it is represented in the averaged vector. the representations are computed recursively, and when a tree that looks locally not important is given a weak score, as shown in figure 1 , it will be washed out. this weakness in local decision making is similar to the label bias problem @xcite in sequence prediction. in this paper, we extend diora so that it can easily recover from local errors ( §3). we replace the weight assignment used for vector averaging with a sparse operator equivalent to a one-hot argmax function, ensuring that each representation accurately encodes a single tree (hence, we call our method s-diora). in s-diora, it is not possible for a subtree to be washed out, although it is still possible to make an error by ignoring a potentially important subtree. fortunately, this can be alleviated by adding a beam to each cell of the chart, allowing multiple subtrees over any span to be considered. the key benefit of our modification is that error recovery is easily possible, where previously the vector serves as a bottleneck that makes error recovery difficult or impossible. we initialize an instance of s-diora using the previously released diora model, then finetune before evaluating on the target domain, constituency parse trees from the english wsj treebank (ptb, @xcite . in one experimental setting, we assume no access to the evaluation domain and use a subset of diora's training data, a concatenation of the snli @xcite and multi-nli @xcite corpora (hereinafter nli). in the other setting, we assume access to raw text in the target domain, parse tree labels excluded. in both cases, we see s-diora improves on the original diora performance by at least 4 f1, and training on the ptb raw text leads to more than 3 f1 over the previous state of the art in constituency parsing. in summary, the main contributions in this paper are: (a) an extension to diora called s-diora that allows for easy recovery from local errors; (b) new results in unsupervised constituency parsing, improving over the previous state of the art by 2.2 6% f1 depending on the data used for fine-tuning; and (c) thorough error analysis of the parse tree output revealing useful insights of why s-diora improves over baselines, for example, capturing marginally less prepositional phrases in the parse tree output yet making half the ppattachment errors. here is a sketch for how this approach works. consider the hypothetical sentence with tokens: for each span of token x i:j diora computes an inside vector h in i,j , summarizing the information in that span. additionally, diora computes an outside vector h out i,j representing the tokens not in x i:j . assume that x 2 is the target token to predict, then for the parse tree ⌧ the token x 1 is in the inside context for x 2 because x 1 is the immediate sibling of x 2 in the subtree capturing both tokens. the tokens x 0 and x 3 are not captured in this subtree and are considered to be in the outside context of x 2 . diora represents the inside context as h in 1,1 and the outside context as h out 1,2 to compute h out 2,2,k . the k in the subscript indicates that this is only one of many possible valid trees for the hypothetical sentence. diora assigns a weight to each valid tree s 2,2,k where higher weight values indicate the tree is more helpful for predicting the target token. the vector used to predict the target token is a weighted summation of all the tree representations h out 2,2 = p k q 2,2,k h out 2,2,k where q i,j,k is a weight diora assigns to each subtree. the rest of this section covers in more technical detail how to recursively compute the inside and outside vectors and weights for diora. the recursive computation is done efficiently using a chart data structure and dynamic program similar to the inside-outside algorithm @xcite . part of this computation involves a softly weighted summation, which is an efficient way to encode all valid trees, yet has some downsides ( §2.3). in the inside pass (left) diora composes two neighboring vectors. in the outside pass (right) diora computes the values for a target span (i, j) recursively from its sibling inside span (j +1, k) and outside spans (0, i 1) and (k + 1, n 1). the sibling span on the outside pass can appear to the left of the target span, in which case the indexing is adjusted. ## s-diora: single tree encoding we improve diora by making it more robust to local errors. diora is sensitive to errors because its vector averaging approach makes it difficult or impossible to recover when important subtrees have been washed out. the first modification we present prevents trees from being washed out by replacing the weights q with a sparse operator q 0 equivalent to a one-hot argmax. this effectively replaces vector averaging with selection of the highest scoring subtree for each span. this change alone is not sufficient. if using only a single highest-scoring tree, s-diora would remain as vulnerable, or more so, to local errors that are inevitable when using the context-free approach of the inside-outside algorithm. instead, at each cell in the chart we record up to values corresponding to the highest scoring subtrees. we refer to as beam-size, and our experiments demonstrate that using a beam-size of 2 already gives a great improvement in results, although any size of can be used at test time regardless what was used during training. in the popular k-means algorithm, each point minimizes its distance to only one centroid. using this as motivation, we train s-diora s.t. each sentence is only drawn towards one tree. we implement this change using a variant of the structured svm loss: j unsup tree (x) = min(0, s(y 1 ) s(y 0 ) + 1), where s(y i ) is the score for the i-th tree represented on the beam and s(y) = p (i,j,k)2y s in i,j,k . s-diora trains with this loss in addition to the reconstruction loss (the original diora objective): j s-@xmath0. to help train s-diora, we employed different tricks. during our unsupervised parsing experiments, we used gumbel-top-k @xcite for q 0 to ensure the model would sufficiently explore multiple parse trees. we also added regularization via mixout @xcite or l2 regularization for the initial parameters so that the model would not diverge drastically from its initialization and suffer catastrophic forgetting. empirically, we found that none of these additions were necessary, and that fine-tuning with the j s-diora objective was sufficient. one possible explanation for why this is so is that training @xmath1. ## experiments and results the model and approach in this paper are motivated mainly by wash out in diora with respect to its vector averaging. in this section we experimentally test the following hypotheses: although we expect training with s-diora to be helpful for unsupervised parsing, we expect an even bigger benefit when training on the same domain as used for evaluation. ## discussion and analysis in this section we examine the parse tree output of the models in our experimental setup with more fine-grained detail than parsing f1. given the prevalence of pre-trained language models in nlp tasks, we also include in our analysis recent results using transformers for unsupervised parsing. in addition, we present a new baseline demonstrating that pretrained language models are better at unsupervised parsing than previously known. ## conclusion we introduce s-diora, an extension to diora that enables for easy recovery from local errors and is not subject to wash out from vector averaging. our experiments in supervised parsing verify s-diora improves upon the representational power of diora. unsupervised fine-tuning with s-diora leads to new impressive results in unsupervised constituency parsing, improving upon the previous state of the art by 2.2 6% f1, depending on the data used.