Learning Latent Trees with Stochastic Perturbations and Differentiable Dynamic Programming

Caio Corro, Ivan Titov

Abstract

We treat projective dependency trees as latent variables in our probabilistic model and induce them in such a way as to be beneficial for a downstream task, without relying on any direct tree supervision. Our approach relies on Gumbel perturbations and differentiable dynamic programming. Unlike previous approaches to latent tree learning, we stochastically sample global structures and our parser is fully differentiable. We illustrate its effectiveness on sentiment analysis and natural language inference tasks. We also study its properties on a synthetic structure induction task. Ablation studies emphasize the importance of both stochasticity and constraining latent structures to be projective trees.

Introduction

Hierarchical structure is a fundamental property of natural language. While traditional NLP pipelines rely on pre-trained parsers to provide syntactic trees, these structures are often optimized for linguistic theory rather than specific downstream tasks. Furthermore, high-quality treebanks are expensive to produce and unavailable for many languages. Latent tree learning aims to discover task-specific structures automatically. However, the discrete nature of tree selection makes optimization difficult, often requiring high-variance reinforcement learning or structured attention mechanisms that may not yield a single coherent global structure.

Methodology

We propose a fully end-to-end trainable framework that treats dependency trees as latent variables. The model consists of two primary components:

Perturb-and-MAP Sampling

To encourage exploration of the structural space, we employ a "Perturb-and-MAP" approach. We add random noise sampled from a Gumbel distribution to the predicted scores for all potential word-to-word arcs. We then identify the Maximum A Posteriori (MAP) tree—the highest-scoring projective tree given these noisy scores. This stochasticity acts as a form of exploration that prevents the model from getting stuck in poor local optima.

Differentiable Dynamic Programming

The core of our structural induction is a differentiable version of the Eisner algorithm. By replacing the standard "hard" max operations with a smoothed version (using a softmax or log-sum-exp), we enable gradients to flow from the final task loss back to the arc scoring parameters. Once a tree is sampled, it is processed by a Graph Convolutional Network (GCN) to produce a sentence representation for classification.

Experimental Evaluation

We evaluated our approach on synthetic and real-world benchmarks, utilizing an optimized C++ implementation to maintain efficiency despite the $O(n^3)$ complexity of the dynamic programming algorithm.

Synthetic Structure Induction: ListOps

The ListOps dataset involves computing the result of nested mathematical operations (e.g., max[3, 4, med[9, 3]]). This task serves as a "sanity check" for hierarchical models. Our model successfully recovered the underlying grammar with near-perfect accuracy (99.7% attachment score), whereas many previous latent models failed this task.

Visualization of the hierarchical structure induced for a ListOps sequence.

Natural Language Tasks

On the MultiNLI dataset, our latent tree model achieved 73.0% accuracy, a 4.9% improvement over structure-agnostic baselines. Performance on the Stanford Sentiment Treebank (SST) was also competitive, though the gains were more modest, suggesting that the choice of the "consumer" network (the GCN) might be as critical as the tree structure itself.

Analysis of Induced Structures

A key finding is that the induced trees often deviate from standard linguistic conventions. The model tends to favor structures that optimize information flow for the downstream GCN rather than mimicking human-annotated syntax, often preferring long chains of left-dependencies.

Examples of latent trees induced by the model on natural language sentences.

Our ablation studies highlighted two critical factors for success:

  1. Stochasticity: Sampling different trees during training is superior to deterministic "best-tree" selection.
  2. Projectivity Constraints: Forcing the latent structure to be a projective tree (where arcs do not cross when drawn above the text) provides a powerful inductive bias that significantly outperforms unconstrained graph models.

Conclusion

By combining Gumbel perturbations with differentiable dynamic programming, we provide a robust method for latent tree induction. Our approach demonstrates that task-specific "grammars" can be learned effectively without direct supervision, offering a scalable path toward more structurally-aware neural models in NLP. Future work will explore extending this framework to constituency-based structures and more complex neural architectures.

Summary updated

Abstract

We treat projective dependency trees as latent variables in our probabilistic model and induce them in such a way as to be beneficial for a downstream task, without relying on any direct tree supervision. Our approach relies on Gumbel perturbations and differentiable dynamic programming. Unlike previous approaches to latent tree learning, we stochastically sample global structures and our parser is fully differentiable. We illustrate its effectiveness on sentiment analysis and natural language inference tasks. We also study its properties on a synthetic structure induction task. Ablation studies emphasize the importance of both stochasticity and constraining latent structures to be projective trees.
BibTeX
@inproceedings{corro2019learning,
  author = {Caio Corro and Ivan Titov},
  title = {{Learning Latent Trees with Stochastic Perturbations and Differentiable Dynamic Programming}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=HGTlOOm8iFm},
}
Figure