Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Autoencoders

1 Introduction

• Supervised parsers depend on small, newswire-focused treebanks, which limits transfer to new domains and makes additional syntactic annotation expensive and time-consuming.This motivates an unsupervised alternative for parsing beyond the annotated training domain.Source: §1 · p. 1
• DIORA induces shallow or full syntactic trees automatically from any domain or language without labeled training data while learning constituent representations for downstream use.The model is designed to capture both noun-phrase-like spans and complete syntactic trees.Source: §1 · p. 1
• Earlier latent tree chart parsers represent all chart nodes but still require sentence-level supervision, typically from downstream natural-language-inference tasks.DIORA is presented to remove that annotation requirement.Source: §1 · p. 1
• Inside-outside dynamic programming represents all possible binary-tree constituents, adds outside context, and trains the model to reconstruct each word from completely unmasked context.The highest-scoring tree is recovered with CKY using constituent compatibility scores.Source: §1 · pp. 1–2
• 13.7%, 11.5%, and 7.8% absolute F1 improvements on WSJ, WSJ-40, and MultiNLI establish new state-of-the-art unsupervised constituency parsing results.The experiments also evaluate segment recall and phrase representations.Source: §1 · p. 2

2 DIORA: Deep Inside-Outside Recursive Autoencoders

• DIORA learns structure from raw text by hypothesizing that syntactic organization yields effective sentence compression.The model is intended to discover and exploit syntactic regularities without labeled training data.Source: §2 · p. 2

2.1 Filling the Chart with Inside-Outside

• Inside representations recursively compose child vectors upward, while an outside pass unfolds from a learned root representation to produce leaf representations for reconstruction.The inside pass summarizes subtrees; the outside pass supplies context from beyond each subtree.Source: §2 · p. 2, §2.1.2 · p. 3

2.1.1 Inside Pass

• Each span is scored and represented by soft weighting over all constituent pairs that fully cover it, enabling the chart to consider alternative binary decompositions.The inside compatibility score uses neighboring span vectors, learned parameters, and the component scores of the merged cells.Source: §2.1.1 · p. 3

2.1.2 Outside Pass

• Outside computation disambiguates possible contexts using a sibling inside cell and a parent outside cell, while producing a representation for the missing sibling.The outside compatibility function is normalized over constituent pairs for each span, with parameters generally shared with the inside computation.Source: §2.1.2 · p. 3

2.2 Training Objective

• The training objective reconstructs each input word from terminal outside vectors, using an autoencoder-like objective with sampled negative examples and optionally cross-entropy.Unlike a standard autoencoder, reconstruction is conditioned on multiple subtree roots rather than one sentence-level latent vector.Source: §2.2 · p. 4

2.3 DIORA CKY Parsing

• CKY extracts the maximum-scoring parse after DIORA fills inside and outside charts for the input sentence.The procedure uses the model’s single grammar rule to recover a binary constituency parse.Source: §2.3 · p. 4

3 Experiments

• The experiments cover full unlabeled constituency parsing, phrase-type recall, phrase representation similarity, and sensitivity to losses and composition functions.The implementation uses CKY decoding to recover a maximal-scoring tree from the chart.Source: §3 · p. 4, §3.1 · p. 4

3.1.1 Binarized WSJ and MultiNLI results

• DIORA+PP achieves the highest average and maximum F1 on full WSJ, with a mean F1 7 points above ON-LSTM and lower seed variance.The comparison uses five random restarts; +PP attaches trailing punctuation to the root.Source: §3.1.1 · p. 5, Table 1 · p. 5
• On MultiNLI, DIORA matches PRPN-UP without post-processing and greatly surpasses both PRPN variants with the +PP heuristic.The evaluation compares against CoreNLP-produced parses rather than gold-standard trees and includes non-newswire domains.Source: §3.1.1 · p. 5, Table 2 · p. 5

3.1.2 WSJ-10 and WSJ-40 results

• DIORA outperforms PRLG in max F1 on WSJ-40, but no latent tree parser improves on prior non-neural methods for WSJ-10.The WSJ-10 and WSJ-40 splits remove punctuation and use non-binarized target trees; DIORA extends better to longer sequences.Source: §3.1.2 · pp. 5–6, Table 3 · p. 6

3.2 Unsupervised Phrase Segmentation

• DIORA has the highest recall across most common constituent types and is the only model effective on verb phrases, but trails PRPN-LM on prepositional phrases.The reported scores are maximum span recall, an upper bound because tree-cutting methods are left for future work.Source: §3.2 · p. 6, Table 4 · p. 7

3.3 Phrase Similarity

• On CoNLL 2000, DIORA outperforms all baselines at every reported K, while on CoNLL 2012 it beats ELMoCI and ELMoSI but not ELMo overall.These results support syntactic phrase information in the representations while leaving room for finer-grained semantic representation.Source: §3.3 · pp. 6–7

3.4 Impact of Modeling Choices

• MLP composition consistently outperforms TreeLSTM, benefits from the Softmax loss, and performs best when inside and outside parameters are shared.This shared-parameter setting is used for subsequent experiments unless otherwise specified.Source: §3.4 · p. 7

3.5 Qualitative Results

• Qualitative examples show that DIORA sometimes exactly replicates or closely approximates binarized ground truth, while other cases exhibit contrary attachments and errors.The model also shows a recognizable affinity for grouping verbs and particles.Source: Figure 3 · p. 7, Figure 4 · p. 7, Figure 5 · p. 7

Neural Inside-Outside Parsers

• DIORA uses one grammar rule for any pair of constituents and avoids structural supervision, unlike neural CRF parsing, which requires grammar rules and labeled trees.Source: §4 · p. 8
• The related-work comparison includes exact-inference systems and beam-search parsers, with DIORA recovering the most likely parse from learned constituent compatibility.Source: §4 · p. 8

Learning from Raw Text

• Unsupervised parsing research also includes segmentation, dependency parsing, multilingual corpora, and pruning strategies that could potentially complement DIORA.Source: §4 · p. 8

• DIORA reaches state-of-the-art unlabeled constituency parsing on full WSJ, WSJ-40, and NLI datasets.Source: §5 · p. 9
• The model combines latent-chart inside-outside representations with an autoencoder language-modeling objective to learn syntactic structure.Source: §5 · p. 9
• The current model focuses primarily on syntax, while future work targets fine-grained semantics, larger corpora, additional objectives, and broader domains and languages.Source: §5 · p. 9

Composition

• The TreeLSTM maps two child vectors to a hidden state and cell state for recursive composition.Source: §A.1 · p. 12
• The inside calculation sets ω to 1 and the outside calculation sets ω to 0, while U and b are learned parameters.Source: §A.1 · p. 12
• The MLP provides a deep nonlinear composition function for combining constituent representations.Source: §A.1 · p. 12
• The MLPKernel enriches concatenation with elementwise products and differences between the two input vectors.Source: §A.1 · p. 12

Training Details

• Training uses sentences of length ≤20 from SNLI and MultiNLI, with Adam optimization, normalized cells, and gradients clipped to L2-norm 5.Source: §A.2 · p. 12
• The model uses an open-vocabulary setup with pretrained character embeddings from ELMo and batches sentences of uniform length.Source: §A.2 · p. 12
• Hyperparameters are selected by grid search over cell dimensions {400D, 800D} and learning rates {2, 4, 8, 10, 20} · 10^-4.Source: §A.2 · p. 12
• All experiments sample N = 100 negatives per batch and run for 1M parameter updates, taking 3 days on 4x Nvidia 1080ti.Source: §A.2 · p. 12

• Parallel computation can theoretically achieve linear complexity under suitable batch size, input length, and core-count conditions, though practical performance may be super-linear.Source: §A.3 · p. 12
• Both inside and outside passes have an O(n^3) upper bound, but the outside pass performs more operations for sentences longer than one word.Source: §A.3 · p. 12
• 5 minutes 30 seconds are required to compute the loss over the entire WSJ corpus at 3,500 words per second using a single GPU.Source: §A.3 · p. 12
• DIORA’s runtime complexity is tabulated by sentence length n, negative examples per token N, and serial versus parallel constituent computation.Source: Table 7 · p. 12

• WSJ evaluation splits may use only section 23 or all training, validation, and test data, with optional punctuation removal and sentence-length filtering.Source: §A.4 · p. 12
• PARSEVAL computes bracketing F1 over all spans, although some prior work excludes trivially correct whole-sentence spans.Source: §A.4 · p. 12
• Evaluation compares predicted trees with either full annotated parses or binarized parses using unlabeled binary bracketing settings summarized in Table 8.Source: §A.4 · p. 12, Table 8 · p. 13

• The parse-tree examples derive from compatibility scores, and some punctuation is removed for readability.Source: §A.5 · p. 13
• DIORA achieves 100% accuracy on the binarized ground truth in the examples shown in Figure 6.Source: Figure 6 · p. 13
• Figure 7 shows cases with 100% recall against raw n-ary ground truth but less than 100% accuracy against binarized ground truth.Source: Figure 7 · p. 13
• DIORA can produce parses close to the ground truth even for long sentences, as illustrated with n-ary ground-truth trees in Figure 8.Source: Figure 8 · p. 14