Syntax is a powerful abstraction for language understanding. Many downstream tasks require segmenting input text into meaningful constituent chunks (e.g., noun phrases or entities); more generally, models for learning semantic representations of text benefit from integrating syntax in the form of parse trees (e.g., tree-LSTMs). Supervised parsers have traditionally been used to obtain these trees, but lately interest has increased in unsupervised methods that induce syntactic representations directly from unlabeled text. To this end, we propose the deep inside-outside recursive autoencoder (DIORA), a fully-unsupervised method for discovering syntax that simultaneously learns representations for constituents within the induced tree. Unlike many prior approaches, DIORA does not rely on supervision from auxiliary downstream tasks and is thus not constrained to particular domains. Furthermore, competing approaches do not learn explicit phrase representations along with tree structures, which limits their applicability to phrase-based tasks. Extensive experiments on unsupervised parsing, segmentation, and phrase clustering demonstrate the efficacy of our method. DIORA achieves the state of the art in unsupervised parsing (46.9 F1) on the benchmark WSJ dataset. Syntax in the form of parse trees is an essential component of many natural language processing tasks. Constituent spans taken from a parse tree are useful for tasks such as relation extraction BID0 and semantic role labeling BID1 , while the full parse itself can be used to build higher-quality systems for machine translation BID2 ) and text classification BID3 . Supervised parsers trained on datasets such as the Penn Treebank BID4 are traditionally used to obtain these trees; however, these datasets are generally small and restricted to the newswire domain. For out-of-domain applications, it is generally infeasible to create new treebanks, as syntactic annotation is expensive and time-consuming. Motivated by these limitations, we propose a method that extracts both shallow parses (i.e., noun phrases or entities) and full syntactic trees from any domain or language automatically without any training data. In addition to just producing the parse, we want our model to build representations for internal constituents that obey syntactic and semantic regularities, as we can then easily inject these representations into downstream tasks. Our model extends existing work on latent tree chart parsers BID5 BID6 BID7 BID8 , which build up representations for all internal nodes in the tree (cells in the chart) generated by a soft weighting over all possible sub-trees (Section 2).In previous work, the representation at the root node is used as a sentence encoding and trained to optimize some downstream task, typically natural language inference. Unfortunately, this method requires sentence level annotations to train the model. Worse still, analysis on the trees learned by these models show that they are actually quite poor at capturing syntax that in any way resembles linguistic theory BID9 . To address these issues, we incorporate the inside-outside algorithm BID10 BID11 ) into a latent tree chart parser. The bottom-up inside step is equivalent to the forward-pass of previous latent tree chart parsers BID7 . However, these inside representations are encoded by looking only within the current subtree, completely ignoring outside context. Thus, we perform an additional top-down outside calculation for each node in the tree incorporating external context into sub-tree representations. Finally, we train This news raised hopes for further interest-rate cuts .This news raised hopes for further interest-rate cuts .Figure 1: Example parse trees. Top PRPN-LM prediction, bottom DIORA prediction. DIORA correctly chunks the span 'raised hopes for further interest-rate cuts'. the outside representations of leaves to reconstruct the initial input, which results in a completely unsupervised autoencoder-like objective. Recently, BID12 proposed Parsing-Reading-Predict Networks (PRPN), an RNN based language model with an additional module for inferring syntactic distance. After training, this syntax module can be decomposed to recover a parse BID13 ) via a complex mechanism that involves modeling a distribution over possible syntactic structures with a stick-breaking process. Like DIORA, this model can be trained in a completely unsupervised manner. However, it has no mechanism of explicitly modeling phrases, and span representations can only be generated by post-hoc heuristics. Additionally, finding the most probable tree in DIORA is much simpler than in PRPN, as we can just run the CKY algorithm. To probe different properties of our model, we run experiments on unsupervised parsing, segmentation, and phrase representations. DIORA sets the state-of-the-art for unsupervised parsing on the WSJ dataset, has a greater recall on a more constituent types than PRPN, and demonstrates strong clustering of phrase representations. Our goal is to build an unsupervised model which can automatically discover syntactic structure from raw text. The hypothesis that our model follows is that the most efficient compression of a sentence will be derived from following the true syntactic structure of the underlying input. Our model is an extension of latent tree chart parsers augmented with the inside-outside algorithm BID10 BID11 and trained as an auto-encoder. Based on our hypothesis, the auto-encoder will best reconstruct the input by discovering and exploiting syntactic regularities of the text. The inside phase of our method recursively compresses the input sequence into a single vector representing the sentence (Section 2.1.1). This is analogous to the compression step of an autoencoder and equivalent to existing latent tree chart parsers forward pass. Following this, we initiate the outside phase of our algorithm there a generic sentence (root) representation which is trained as a part of the model parameter. As an outside step of the inside-outside algorithm (Section 2.1.2), we expand outward until finally producing reconstructed representations of the leaf nodes. These reconstructed leaves are then optimized to reconstruct the input sentence as done in an auto-encoder based deep neural network (Section 2.2). Each inside representation of a given sub-tree is built considering only the children constituents of that sub-tree, independent of any outside context. After the inside representations are calculated, we do a top-down outside pass to compute outside representations. The outside representations are encoded by looking at the context of a given sub-tree. In the end, each cell in the chart will contain an inside vector, inside compatibility score, outside vector, and outside compatibility score. Once the chart is filled, each constituent k (cell in the chart) is associated with an inside vector α Assuming that the input to our model is a sentence X made up of T tokens, x 0 , x 1 , ..., x T , we describe inside and outside phases of our algorithm in the following Sections 2.1.1 and 2.1.2. Also, each token x i has a corresponding pre-trained d dimensional embedding vector v i . For each pair of neighboring constituents i and j, we compute a compatibility score α score k and a composition vector α vec k . The score and vector that represents a particular span k are computed using a soft weighting over all possible pairs of constituents that together covers the span entirely (we refer to this set of constituent pairs as {k}):Vectors for spans of length 1 are initialized using a linear transformation of the embedded input v i . Scores associated with these spans are set to 0. DISPLAYFORM0 For higher levels of the chart we use: DISPLAYFORM1 The compatibility function compat is a bilinear function of the vectors from neighboring spans, adding their scores: DISPLAYFORM2 And the composition function compose is a TreeLSTM BID3 which produces a hidden state vector h and cell state vector c.: DISPLAYFORM3 Where the T reeLST M is defined as follows: DISPLAYFORM4 The constant ω is set to 1 for the inside phase and 0 for the outside phase. The parameters U and b are not shared between the inside phase and outside phase. The outside computation is similar to the inside,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. DISPLAYFORM0 DISPLAYFORM1 To train our model we use an auto-encoder-like language modeling objective. In a standard autoencoder, the input X is compressed into a single lower dimensional representation Y . Y is then decompressed and trained to predict X. In our model, we never condition the reconstruction of X on a single Y 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, none of which is a single compression of the entire X, but rather a subset. Each generated outside vector β vec ifor constituents of length 1 are trained to predict their original input v i . We approximate a reconstruction loss with a max-margin across N negative samples. For each x i , we sample N negative x n i uniformly at random from the vocabulary. The training objective of our model over a batch B = {X i T i , i = 1, ..., B} is computed identically for all tokens (which are also all spans with length 1) within the batch and averaged to get the overall loss for the entire batch. Precisely, the loss function for each token (span k) is described in Equation 14. DISPLAYFORM0 In equation 14, α for each k ∈ chart | size(k) = 1 doInitialize terminal values.3: DISPLAYFORM1 for each k ∈ chart do 5: DISPLAYFORM2 Calculate a maximum score for each span.6: DISPLAYFORM3 Record a backpointer. procedure FOLLOW-BACKPOINTERS(k) 8:if size(k) = 1 then 9:return k 10: DISPLAYFORM0 return (i, j)13:return FOLLOW-BACKPOINTERS(k = root) Backtrack to get the maximal tree. To obtain a parse with DIORA, we populate an inside and outside chart using the input sentence. Then, we can extract the most likely parse based on our single grammar rule using the CKY procedure BID14 BID15 ).It's true that using CKY produces the most likely parse given a set of grammar rules, although in the case of DIORA, the single grammar rule is only a weak abstraction for a PCFG. For this reason, including context during CKY might inform our parser to make different decision. We include context by adding the scalar value of the outside cell to each inside cell. To evaluate the effectiveness of DIORA, we run experiments on unsupervised parsing, unsupervised segmentation, and phrase similarities. The model has been implemented in PyTorch (Team, 2018) and the code is published online 1 . For implementation details, see the Appendix A.1Our main baseline is the current state-of-the-art unsupervised parser PRPN BID12 . We compare our model against two size variants of this model which were used in BID13 .Comparison of the number of parameters and maximum training sentence length are shown in 1. We first evaluate how well our model is able to predict a full unlabeled syntactic parse. We look at two data sets which have been used in prior work BID13 , The Wall Street Journal(WSJ) section of Penn Tree Bank BID4 , and the automatic parses from MultiNLI BID17 . WSJ has gold human annotated parses and MultiNLI contains automatic parses derived from the Stanford CoreNLP parser . We compare our model to left/right branching and balanced trees which are deterministically constructed. RL-SPINN BID6 and ST-Gumbel BID8 are chart parsing models trained to predict the downstream task of NLI. Latent tree models have been shown to perform particularly poorly on attachments at the beginning and end of the sequence BID9 . To address this, we incorporate a post-processing heuristic (+PP in Table 2 ). We see that PRPN-UP and DIORA benefit much more than PRPN-LM from this heuristic. This is consistent with qualitative analysis showing that DIORA and PRPN-UP incorrectly attach trailing punctuation much more than PRPN-LM. This heuristic simply attaches trailing punctuation to the root of the tree, regardless of its predicted attachment. We find this to be extremely effective, increasing our state-of-the-art WSJ parsing results by by over 3 absolute F1 points. On the MultiNLI dataset, PRPN-LM is the top performing model without using the PP heuristic and DIORA outperforms PRPN-UP. Afterwards, PRPN-UP surpasses DIORA. However, it is worth noting that this is not actually a gold standard evaluation and instead evaluates the ability to replicate the output of a trained parser . Table 2 : Unsupervised Parsing. † indicates trained to optimize NLI task. We use the max unlabeled binary F1 across runs for PRPN-UP 2 , PRPN-LM, and DIORA. F1 was calculated using the parse trees provided by BID13 and all results in the upper portion of the table were copied from BID13 . +PP refers to post-processing heuristic to remove trailing punctuation explained in Section 3.1. In many scenarios, rather than a full parse, one is only concerned with extracting particular constituent phrases, such as entities, to be used for downstream analysis. In order 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. We calculate recall as the percentage of labeled constituents that appear in our predicted tree relative the total number of constituents in the gold tree. We separate these scores by type which are presented in Table 3 . In Table 2 we see the breakdown of constituent recall across the 10 most common types. We see that PRPN-UP has the highest recall for the most common type noun-phrase, but drops in every other category. DIORA achieves the highest recall across the most types and is the only model to perform effectively on verb-phrases. However, DIORA performs poorly relative to PRPN at prepositional phrases. Table 3 : Segment recall from WSJ seperated by phrase type. The 10 most frequent phrase types are shown. Highest value in each row is bolded. 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 post-processing 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 is a shallow parsing dataset containing spans of noun phrases, verb phrases, etc. CoNLL 2012 is a named entity dataset containing 19 different entity types. For each of the labeled spans (greater than length 1) in the datasets, we generate a phrase representation and similarities are based on cosine distance. We report three numerical evaluations for both datasets precision@K, mean average precision (MAP), and dendogram purity (DP). We run a hierarchical clustering algorithm over the representations and computeDP BID19 . Given any two points with the same gold label, the clustering tree is cut to form the minimal cluster containing both points. DP then calculates how pure that cluster is. The first baseline we compare against produces phrase representations from averaging Glove vectors of the individual tokens within the span. The second uses ELMo BID20 , a method for obtaining powerful, context dependent word embeddings that has led to many recent state-of-the-art results in NLP. We obtain phrases following the procedure described in BID21 and represent phrases as a function of its first and last hidden state. We look at two variants of ELMo 3 . ELMo-L1 produces token hidden states by only taking the bottom LSTM layer outputs, ELMo-Avg takes a flat average over all of the LSTM hidden state layers 4 . On the CoNLL 2000 dataset, we find that our model outperforms Glove and is competitive with ELMo. For CoNLL 2012, an named entity dataset, we find Glove to actually be the top performer under some metrics while our model is far behind. These results indicate that DIORA is capturing syntax quite well, but is currently missing semantics. We show example trees from PRPN-LM and DIORA in 3. Latent Tree Learning A brief survey of neural latent tree learning models was covered in BID9 . The first positive result for latent tree was shown in BID13 , which used a language modeling objective. The model in BID22 uses an inside chart and an outside procedure to calculate marginal probabilities use to align spans between sentences in entailment. Neural Inside-Outside Parsers The Inside-Outside Recursive Neural Network (IORNN) in BID23 is closest to ours and is a graph-based dependency parser that produces a k-best list of parses, in contrast, DIORA produces the most likely parse given the learned the potential functions of the constituents. The Neural CRF Parser BID24 , 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 BID22 , has a single grammar rule that applies to any pair of constituents and does not use structural supervision. Unsupervised Parsing and Segmentation Unsupervised segmentation (also called chunking) from raw text dates back to BID25 . Another paper by the same authors BID26 only looked at parsing certain low-level constituents. Earlier grammar induction models were evaluated against a subset of the WSJ treebank filtered to sentences of length 10 after removing punctuation BID27 BID28 while DIORA is evaluated against two much larger datasets for unsupervised parsing, including the full WSJ treebank. Unsupervised segmentation with across parallel corpora was performed in BID29 . The source language had segment labels, the target language did not, but there are mapped translations between the two languages. BID30 achieved unsupervised segmentation for parallel corpora without using mapped translations. In this work we presented DIORA, a completely unsupervised method for inducing syntactic trees and segmentations over text. We showed that an auto encoder language modeling objective on top of inside-outside representations of latent tree chart parsers allows us to effectively learn syntactic Third-quarter shipments slipped 7 % from the year-ago period and 17 % from this year 's second quarter Third-quarter shipments slipped 7 % from the year-ago period and 17 % from this year 's second quarter Mr. Hoelzer did n't return phone calls seeking comment on the judge 's decision Mr. Hoelzer did n't return phone calls seeking comment on the judge 's decisionThe earthquake caused many streets to buckle and crack making them impassibleThe earthquake caused many streets to buckle and crack making them impassible Figure 3 : Pairs of example parses for the same sentence from two different models. For each pair, the top is the output of PRPN-LM and bottom was produced by DIORA. Bolden token pairs or spans indicate a parse error by PRPN that was correctly attached by DIORA. Some punctuation was removed for clarity of printed trees. structure of language. In experiments on unsupervised parsing, chunking, and phrase representations we show our model is comparable to or outperforms current baselines, achieving the state-of-the-art performance on unsupervised parsing for the WSJ dataset. .Future work can improve the current method by training larger models over much larger corpora including other domains and languages. While the current model seems to focus primarily on syntax, extra unsupervised objectives or light supervision could be injected into the learning procedure to encourage a more thorough capturing of semantics.
In this work we propose deep inside-outside recursive auto-encoders(DIORA)  a  fully  unsupervised  method  of  discovering  syntax  while  simultaneously learning representations for discovered constituents.  A neural latent tree model trained with an auto-encoding objective that achieves state of the art on unsupervised constituency parsing and captures syntactic structure better than other latent tree models. The paper proposes a model for unsupervised dependency parsing (latent tree induction) that is based on a combination of the inside-outside algorithm with neural modeling (recursive auto-encoders). 