We introduce deep inside-outside recursive autoencoders (DIORA), a fully-unsupervised method for discovering syntax that simultaneously learns representations for constituents within the induced tree. Our approach predicts each word in an input sentence conditioned on the rest of the sentence and uses inside-outside dynamic programming to consider all possible binary trees over the sentence. At test time the CKY algorithm extracts the highest scoring parse. DIORA achieves a new state-of-the-art F1 in unsupervised binary constituency parsing (unlabeled) in two benchmark datasets, WSJ and MultiNLI. Syntactic parse trees are useful for downstream tasks such as relation extraction (Gamallo et al., 2012), semantic role labeling (Sutton and McCallum, 2005; He et al., 2018), machine translation (Aharoni and Goldberg, 2017; Eriguchi et al., 2017; Zaremoodi and Haffari, 2018), and text classification (Li and Roth, 2006; Tai et al., 2015). Traditionally, supervised parsers trained on datasets such as the Penn Treebank (Marcus et al., 1993) are used to obtain syntactic trees. However, the treebanks used to train these supervised parsers are typically small and restricted to the newswire domain. Unfortunately, models trained on newswire treebanks tend to perform considerably worse when applied to new types of data, and creating new domain specific treebanks with syntactic annotations is expensive and time-consuming. Motivated by the desire to address the limitations of supervised parsing and by the success of large-scale unsupervised modeling such as ELMo and BERT (Peters et al., 2018a; Devlin et al.,  Equal contribution, randomly ordered. Under the current circumstances he says their scenario no longer seems unrealistic Figure 1: An unlabeled binary constituency parse from DIORA matching the ground truth. 2019), we propose a new deep learning method of unsupervised parser training that can extract both shallow parses (i.e., noun phrases or entities) and full syntactic trees from any domain or language automatically without requiring any labeled training data . In addition to producing parses, our model simultaneously builds representations for internal constituents that reflect syntactic and semantic regularities which can be leveraged by downstream tasks. Our model builds on existing work developing latent tree chart parsers (Socher et al., 2011b; Le and Zuidema, 2015; Yogatama et al., 2017; Mail-lard et al., 2017; Choi et al., 2018). These methods produce representations for all internal nodes in the tree (cells in the chart), each generated as a soft weighting over all possible sub-trees (  2). Unfortunately, they still require sentence-level annotations during training, as they are all trained to optimize a downstream task, typically natural language inference. To address these limitations, we present deep inside-outside recursive autoencoders (DIORA) which enable unsupervised discovery and representation of constituents without requiring any supervised training data. DIORA incorporates the inside-outside algorithm (Baker, 1979; Lari and Young, 1990) into a latent tree chart parser. The bottom-up inside step calculates a representation for all possible constituents within a binary tree over the input sentence. This step is equivalent to the forward-pass of previous latent tree chart parsers (Maillard et al., 2017). These inside representations only encode the current subtree, ignor-0.7  + 0.3  The cat drinks The cat drinks ing all outside context. Thus, we perform an additional top-down outside calculation for each node in the tree, providing external context into the subtree representations in each chart cell. The model is then trained with the objective that the outside representations of the leaf cells should reconstruct the corresponding leaf input word, analogous to masked language model (Devlin et al., 2019) pretraining, except by using dynamic programming we predict every word from a completely unmasked context. The single most likely tree can be recovered using the CKY algorithm and compatibility scores between constituents. Previous work either predict trees that are not well aligned with known treebanks (Yogatama et al., 2017; Choi et al., 2018), or has no mechanism for explicitly modeling phrases, requiring a complex procedure to extract syntactic structures (Shen et al., 2018). To probe different properties of our model, we run experiments on unsupervised parsing, segment recall, and phrase representations. DIORA achieves multiple new state-of-the-art results for unsupervised constituency parsing (absolute improvements of 13.7% , 11.5% , and 7.8% on WSJ, WSJ-40, and MultiNLI), has a greater recall on more constituent types than a strong baseline, and produces meaningful phrase representations. Our goal is to design a model and unsupervised training procedure that learns structure from raw text. The design of DIORA is based on our hypothesis is that the most effective compression of a sentence will be derived from following the true syntactic structure of the underlying input. Our approach builds on previous latent tree chart parsers which are augmented with the inside-outside algorithm ( Baker, 1979; Lari and Young, 1990) and trained to reproduce each input word from its outside context. Based on our hypothesis, loosely inspired by the linguistic substitution principle (Frege, 1960), the model will best reconstruct the input by discovering and exploiting syntactic regularities of the text. The inside pass of our method recursively compresses the input sequence, at each step inputting the vector representations of the two children into a composition function (  2.1.1) that outputs an inside vector representation of the parent. This process continues up to the root of the tree, eventually yielding a single vector representing the entire sentence (Figure 2a). This is loosely analogous to the compression step of an autoencoder and equivalent to existing latent tree chart parsers forward pass (Maillard et al., 2017). Following this, we initiate the outside pass of our algorithm with a generic (root) representation that is learned as a separate parameter. As the outside step of the inside-outside algorithm (Figure 2b), we unfold until finally producing representations of the leaf nodes. These leaves are then optimized to reconstruct the input sentence as done in an autoencoder-based deep neural network. Each inside representation is the root of a particularly sub-tree, and that representation is generated by considering only the descendant constituents within that sub-tree, ignoring any outside context. After the inside representations are calculated, we perform a top-down outside pass to compute outside representations. The outside representations are encoded by looking at only the context of a given sub-tree. Once the chart is filled, each constituent k (cell in the chart) is associated with an inside vector  a ( k ) , an outside vector  b ( k ) , inside compatibility score  e ( k ) and outside compatibility score  f ( k ) . The input to our model is a sentence x made up of T tokens, x 0 , x 1 , ..., x T  1 . Each token x i has a corresponding pre-trained embedded vector v i . For each pair of neighboring constituents i and j 1 , we compute a compatibility score and a composition vector. The score and vector that represent a particular span k are computed using a soft weighting over all possible pairs of constituents, that together fully cover the span (we refer to this set of constituent pairs as { k } ). Vectors for spans of length 1 are initialized as a non-linear transformation 2 of the embedded input v i , and the scores associated with these spans are set to 0 :   x o u   =     tanh   ( U  v k + b )  a ( k ) = o + tanh( x  u )  e ( k ) = 0 Higher levels of the chart are computed as a weighted summation of constituent pairs:  a ( k ) = X i,j { k } e ( i, j ) a ( i, j )  e ( k ) = X i,j { k } e ( i, j )  e ( i, j ) The compatibility function  e is meant to produce a score for how likely a pair of neighboring cells are to be merged. We implement this as a bilinear function of the vectors from neighboring spans, using a learned parameter matrix S . We additionally add the individual scores from each two merging cells. Intuitively, these individual scores correspond to how likely each of the cells would 1 The symbols i , j , and k are identifiers of spans from the input x . exist in the final binary tree independently. The formula for the compatibility function (and its normalized form e ) is defined as follows: e ( i, j ) = exp( e ( i, j )) P  i,  j { k } exp( e ( i,  j ))  e ( i, j ) =  ( a ( i ) ,  a ( j ); S  ) +  e ( i ) +  e ( j ) Where the bilinear projection  is defined as:  ( u, v ; W ) = u  W v For the composition function a we used either a TreeLSTM (Tai et al., 2015) or a 2-layer MLP (see Appendix A.2 for more precise definitions on both methods). In order for the remainder of equations to remain agnostic to the choice of composition function, we refer to the function as Compose , which produces a hidden state vector h and, in the case of TreeLSTM , a cell state vector c , resulting in: a ( i, j ) = Compose  ( a ( i ) ,  a ( j )) 2.1.2 Outside Pass The outside computation is similar to the inside pass (depicted in Figure 2b). The root node of the outside chart is learned as a bias. Descendant cells are predicted using a disambiguation over the possible outside contexts. Each component of the context consists of a sibling cell from the inside chart and a parent cell from the outside chart. The function f is analogous to the function e . It is normalized over constituent pairs i, j for the span k , and is used to disambiguate among the many outside contexts. The function b generates a phrase representation for the missing sibling cell. Equations for the outside computation follow:  b ( k ) = X i,j { k } f ( i, j ) b ( i, j )  f ( k ) = X i,j { k } f ( i, j )  f ( i, j ) b ( i, j ) = Compose  ( a ( i ) ,  b ( j ))  f ( i, j ) =  ( a ( i ) ,  b ( j ); S  ) +  e ( i ) +  f ( j ) In the majority of our experiments, the Compose used in b shares parameters with a used in the inside pass, as do the compatibility functions  e and  f (see  3.4 for results on the effects of parameter sharing). To train our model we use an autoencoder-like language modeling objective. In a standard autoencoder, the entire input x is compressed into a single lower dimensional representation. This representation, z , is then decompressed and trained to reconstruct x . In our model, we never condition the reconstruction of x on a single z because the root's outside representation is initialized with a bias rather than the root's own inside vector. Instead, we reconstruct x conditioned on the many sub-tree roots, each of which is only a compression of a subset of the input. To approximate this reconstruction we use a max-margin loss considering a set { x  } of N negative examples that are sampled according to their frequency from the vocabulary (further details in Appendix A.1). The terminal outside vector  b ( i ) is trained to predict its original input v i . The per-instance loss function is described in Equation 1: L x = T  1 X i =0 N  1 X i  =0 max(0 , 1   b ( i )   a ( i ) +  b ( i )   a ( i  )) (1) The max-margin loss does not provide a gradient if the predicted vector is closer to its ground truth than the negative example by a margin greater than 1 . For that reason, we also experimented with an objective based on cross-entropy, described in Equation 2: Z  = N  1 X i  =0 exp( b ( i )   a ( i  )) L x =  T  1 X i =0 log exp( b ( i )   a ( i )) exp(  b ( i )   a ( i )) + Z  (2) 2.3 DIORA CKY Parsing To obtain a parse with DIORA, we populate an inside and outside chart using the input sentence. We can extract the maximum scoring parse based on our single grammar rule using the CKY procedure (Kasami, 1966; Younger, 1967). The steps for this procedure are described in Algorithm 1 and its runtime complexity in Appendix A.4. vised segment recall, and phrase similarity. The model has been implemented in PyTorch (Team, 2018) and the code is published online. 3 For training details, see Appendix A.1. We first evaluate how well our model predicts a full unlabeled constituency parse. We look at two data sets used in prior work (Htut et al., 2018), The Wall Street Journal (WSJ) section of Penn Treebank (Marcus et al., 1993), and the automatic parses from MultiNLI (Williams et al., 2018b). WSJ has gold human-annotated parses and MultiNLI contains automatic parses derived from a supervised parser (Manning et al., 2014). In addition to PRPN (Shen et al., 2018), 4 we compare our model to deterministically constructed left branching, right branching, balanced, and random trees. We also compare to ON-LSTM (Shen et al., 2019), an extension of the PRPN model, RL-SPINN (Yogatama et al., 2017), an unsupervised shift-reduce parser, and ST-Gumbel (Choi et al., 2018), an unsupervised chart parser. The latter two of these models are trained to predict the downstream task of natural language inference (NLI). For the full WSJ test set and MultiNLI datasets we follow the experimental setup of previous work (Williams et al., 2018a). We binarize target trees using Stanford CoreNLP (Manning et al., 2014) and do not remove punctuation (experiments in  3.1.2 do remove punctuation). Latent tree models have been shown to perform particularly poorly on attachments at the beginning and end of the sequence (Williams et al., 2018a). To address this, we incorporate a postprocessing heuristic (denoted as +PP in result tables) 5 . This heuristic simply attaches trailing punctuation to the root of the tree, regardless of its predicted attachment. In Table 1, we see that DIORA +PP achieves the highest average and maximum F1 from five random restarts. This model achieves a mean F1 7 points higher than ON-LSTM and an increase of over 6.5 max F1 points. We also see that DIORA exhibits much less variance between random seeds than ON-LSTM. Additionally, we find that PRPN-UP and DIORA benefit much more from the +PP heuristic than PRPN-LM. This is consistent with qualitative analysis showing that DIORA and PRPN-UP incorrectly attach trailing punctuation much more often than PRPN-LM. On the MultiNLI dataset, PRPN-LM is the top performing model without using the +PP heuristic while DIORA matches PRPN-UP (Table 2. Using the heuristic, DIORA greatly surpasses both variants of PRPN. However, it is worth noting that this is not a gold standard evaluation and instead evaluates a model's ability to replicate the output of a trained parser (Manning et al., 2014). A second caveat is that SNLI (Bowman et al., 2015) and MultiNLI contain several non-newswire domains. Syntactic parsers often suffer significant performance drops when predicting outside of the newswire domain that the models were trained on. We also compare our models to two subsets of the WSJ dataset that were used in previous unsupervised parsing evaluations. WSJ-10 and WSJ-40 contain sentences up to length 10 and 40 respectively after punctuation removal. We do not binarize either of these two splits in order to compare to previous work (see Appendix A.3 for more 5 We did not have access to predictions or an implementation of the concurrent ON-LSTM model and therefore could not apply the +PP heuristic. details on WSJ split differences). Not binarizing the target trees sets an upper-bound on the performance of our models, denoted as UB in Table 3. We compare against previous notable models for this task: CCM ( Klein and Manning, 2002) uses the EM algorithm to learn probable nested bracketings over a sentence using gold or induced part-of-speech tags, and PRLG (Ponvert et al., 2011) performs constituent parsing through consecutive rounds of sentence chunking. In Table 3, we see that DIORA outperforms the previous state of the art for WSJ-40, PRLG, in max F1. The WSJ-10 split has been difficult for latent tree parsers such as DIORA, PRPN, and ON-LSTM, none of which (including our model) are able to improve upon previous non-neural methods. However, when we compare trends between WSJ-10 and WSJ-40, we see that DIORA does a better job at extending to longer sequences. In many scenarios, one is only concerned with extracting particular constituent phrases rather than a full parse. Common use cases would be identifying entities, noun phrases, or verb phrases for downstream analysis. To get an idea of how well our model can perform on phrase segmentation, we consider the maximum recall of spans in our predicted parse tree. We leave methods for cutting the tree to future work and instead consider the maximum recall of our model which serves as an upper bound on its performance. Recall here is the percentage of labeled constituents that appear in our predicted tree relative to the total number of constituents in the gold tree. These scores are separated by type and presented in Table 4. In Table 4 we see the breakdown of constituent recall across the 10 most common types. DIORA achieves the highest recall across the most types and is the only model to perform effectively on verb-phrases. Interestingly, DIORA performs worse than PRPN-LM at prepositional phrases. One of the goals of DIORA is to learn meaningful representations for spans of text. Most language modeling methods focus only on explicitly modeling token representations and rely on ad-hoc postprocessing to generate representations for longer spans, typically relying on simple arithmetic functions of the individual tokens. To evaluate our model's learned phrase representations, we look at the similarity between spans of the same type within labeled phrase datasets. We look at two datasets. CoNLL 2000 (Tjong Kim Sang and Buchholz , 2000) is a shallow parsing dataset containing spans of noun phrases, verb phrases, etc. CoNLL 2012 ( Pradhan et al., 2012) WSJ-10 WSJ-40 Model F1  F1 max F1  F1 max UB 87.8 87.8 85.7 85.7 LB 28.7 28.7 12.0 12.0 RB 61.7 61.7 40.7 40.7 CCM  -63.2 -CCM gold  -71.9 -33.7 PRLG  -72.1 -54.6 PRPNNLI 66.3  0 . For each of the labeled spans with length greater than one, we first generate its phrase representation. We then calculate its cosine similarity to all other labeled spans. We then calculate if the label for that query span matches the labels for each of the K most similar other spans in the dataset. In Table 5 we report precision@ K for both datasets and various values of K . The first baseline we compare against produces phrase representations from averaging context-insensitive (CI) ELMo vectors of individual tokens with the span. The second uses sentence-insensitive (SI) ELMo vectors, running the full ELMo over only the relevant tokens and ignoring the rest of the sentence. We also look at ELMo's output when given the entire sentence. When analyzing our baselines that run the full ELMo, we follow the procedure described in (Pe-ters et al., 2018b) and represent phrases as a function of its first and last hidden state. We extract these states from the final ELMo layer (3rd BiL-STM) as these consistently gave the best performance among other options. For DIORA, we use the concatenation of the inside and outside representations ( [ a ; b ] ). This demonstrates DIORA's ability to capture and represent syntactic information within phrases. For CoNLL 2012, we find that DIORA outperforms both ELMo CI and ELMo SI while ELMo performs best overall. ELMo CI is surprisingly effective on this dataset even though it performed more poorly on CoNLL 2000. These results indicate that DIORA is capturing syntax quite well, but still has room to improve on more fine-grained semantic representations. To test the impact of our modeling choices, we compared the performance of two different losses and four different composition functions on the full WSJ validation set. The losses were covered in Equations 1 (Margin) and 2 (Softmax). The two primary methods of composition we considered were TreeLSTM (Tai et al., 2015) and MLP (a 2-hidden layer neural network). In addition, we experimented with a simple kernel of the MLP input [ x ; y ; x  y ; x  y ] and with a setting where both the inside and outside parameters are shared . The results are shown in Table 6. We see that MLP composition consistently performs better than with TreeLSTM, that MLP benefits from the Softmax loss, and that the best performance comes from sharing parameters. All other experimental results use this highly performant setting unless otherwise specified. All examples of DIORA parses are already binary. Some punctuation has been removed for easier readability. Looking at our model's output, we see that some trees are an exact replication of the binarized ground truth (Fig. 3), or very close (Fig. 4). For future work we intend to explore common patterns in DIORA's learned structure, although some patterns are already recognizable, such as the affinity to group particles and verbs (Fig. 5). Latent Tree Learning A brief survey of neural latent tree learning models was covered in (Williams et al., 2018a). The first positive result for neural latent tree parsing was shown in (Htut et al., 2018), which used a language modeling objective. The model in (Liu et al., 2018) uses an inside chart and an outside procedure to calculate marginal probabilities in order to align spans between sentences in entailment. Neural Inside-Outside Parsers The Inside-Outside Recursive Neural Network (IORNN) (Le and Zuidema, 2014) is closest to ours. It is a graph-based dependency parser that uses beam search and can reliably find accurate parses when retaining a k -best list. In contrast, our model produces the most likely parse given the learned compatibility of the constituents. The Neural CRF Parser (Durrett and Klein, 2015), similar to DIORA, performs exact inference on the structure of a sentence, although requires a set of grammar rules and labeled parse trees during training. DIORA, like Liu et al. (2018), has a single grammar rule that applies to any pair of constituents and does not use structural supervision. Learning from Raw Text Unsupervised learning of syntactic structure has been an active research area (Brill et al., 1990), including for unsupervised segmentation (Ando and Lee, 2000; Goldwater et al., 2009; Ponvert et al., 2011) and unsupervised dependency parsing (Spitkovsky et al., 2013). Some models exploit the availability of parallel corpora in multiple languages (Das and Petrov, 2011; Cohen et al., 2011). Others have shown that dependency parsing can be used for unsupervised constituency parsing (Spitkovsky et al., 2013; Klein and Manning, 2004), or that it's effective to prune a random subset of possible trees (Bod, 2006). These approaches aren't necessarily orthogonal to DIORA. For instance, our model may benefit when combined with an unsupervised dependency parser. In this work we presented DIORA, an unsupervised method for inducing syntactic trees and representations of constituent spans. We showed inside-outside representations constructed with a latent tree chart parser and trained with an autoencoder language modeling objective learns syntactic structure of language effectively. In experiments on unsupervised parsing, chunking, and phrase representations we show our model is comparable to or outperforms previous methods, achieving the state-of-the-art performance on unsupervised unlabeled constituency parsing for the full WSJ (with punctuation), WSJ-40, and NLI datasets. We also show our model obtains higher segment recall than a comparable model and outperforms strong baselines on phrase representations on a chunking dataset. While the current model seems to focus primarily on syntax, future work can improve the model's ability to capture fine-grained semantics. Potential avenues include training larger models over much larger corpora, extra unsupervised or weakly-supervised phrase classification objectives, and other modeling enhancements. We are also eager to apply DIORA to other domains and languages which do not have rich linguistically annotated training sets. We are grateful to Carolyn Anderson, Adina Williams, Phu Mon Htut, and our colleagues at UMass for help and advice, and to the UMass NLP reading group and the anonymous reviewers for feedback on drafts of this work. This work was supported in part by the Center for Intelligent Information Retrieval, in part by the National Science Foundation (NSF) grant numbers DMR-1534431, IIS-1514053 and CNS-0958392. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.
abstain method abstain abstain other abstain abstain abstain other method abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain objective method objective abstain abstain abstain abstain method method abstain abstain method abstain abstain abstain abstain method method other method method abstain abstain other other abstain abstain abstain abstain abstain abstain other abstain abstain abstain method abstain method abstain other other method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain result result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method objective result result abstain abstain method other other other