Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder

Caio Corro, Ivan Titov

Syntactic parsing—the process of determining the grammatical structure of a sentence—is a cornerstone of natural language processing. However, training these models usually requires massive amounts of human-annotated data. This data is expensive to produce and unavailable for the vast majority of the world's languages.

Example of a syntactic dependency tree.

In their ICLR 2019 paper, Caio Corro and Ivan Titov propose a way to bridge this gap. They introduce a method to leverage abundant unlabeled text to improve parsers using a Structured Variational Autoencoder (VAE) and a novel technique called Differentiable Perturb-and-Parse.

Executive Summary

The authors develop a semi-supervised dependency parser that treats the grammatical structure of a sentence as a hidden (latent) variable. By making the discrete parsing process differentiable, they allow the model to learn from unlabeled text through a "reconstruction" task, leading to significant accuracy gains in low-resource settings.

The Challenge of Low-Resource Parsing

Most modern parsers are "supervised," meaning they learn strictly from sentences where humans have already drawn the "arcs" between words (e.g., identifying that "walk" is the head of "dog"). For many languages, we have fewer than 5,000 such annotated sentences.

While we have nearly infinite unlabeled text, it is difficult to use for parsing. Previous attempts often used a two-step process (like pre-training word embeddings) or "self-training" (where a model labels its own data). This paper seeks a more integrated approach: a generative model that "imagines" a tree structure for an unlabeled sentence and checks if that structure helps it "understand" or reconstruct the sentence.

A Generative Approach: Structured VAEs and Differentiable Parsing

The core of the paper is a Structured Variational Autoencoder (VAE). A VAE typically consists of two parts:

  1. The Encoder: Takes a sentence and predicts a latent representation. Here, the latent representation is the dependency tree itself.
  2. The Decoder: Takes that predicted tree and tries to regenerate the original sentence.
Overview of the probabilistic model, computation graph, and decoder architecture.

The Discrete Bottleneck

Standard deep learning relies on "backpropagation," which requires every step of the model to be differentiable (smooth). Parsing algorithms like Eisner’s algorithm are discrete—they use a "hard" argmax to pick the best tree. This "breaks" the gradient, making it impossible for the decoder's errors to tell the encoder how to pick better trees.

The Solution: Differentiable Perturb-and-Parse

The authors overcome this bottleneck with two clever tricks:

  • Perturbation: They add random noise (Gumbel noise) to the predicted weights of the arcs. This allows the model to "sample" different possible trees rather than always picking the single best one.
  • Relaxation: They replace the hard argmax inside the parsing algorithm with a "peaked-softmax" operator. This turns the discrete choice into a "soft selection" of arcs, making the entire parsing process differentiable.

For the decoder, they use a Graph Convolutional Network (GCN). This allows the model to pass information along the arcs of the predicted tree, forcing the model to actually use the syntax to reconstruct the words.

Datasets and Key Results

The authors evaluated their method on three languages to test its versatility: English (using a simulated low-resource setting of 10% labeled data), French, and Swedish (which had a particularly small amount of unlabeled data).

The "Differentiable Perturb-and-Parse" method consistently outperformed the supervised baseline across all tested languages:

  • English: The Unlabeled Attachment Score (UAS) rose from 88.79% (supervised) to 89.50% (semi-supervised).
  • Swedish: Even with very limited unlabeled data, the model saw an improvement from 86.59% to 86.97% UAS.

Key Insights

  • Syntax as a Useful Latent Feature: Because the decoder is a GCN that follows the arcs, the model is incentivized to find trees that reflect real-world linguistic dependencies to minimize reconstruction error.
  • End-to-End Training: Unlike previous semi-supervised methods, this model learns the parser and the reconstruction task simultaneously.
  • Long-Distance Gains: The semi-supervised model became much better at identifying long-distance relationships (arcs spanning more than 7 words) compared to the supervised baseline. It also made significantly fewer mistakes on "root" attachments.

Limitations and Future Work

While highly effective, the approach has a few limitations. The current algorithm only supports "projective" trees (trees where arcs don't cross), which are less common in languages like Czech or German. Additionally, training a VAE with a structured decoder is computationally expensive, taking about 2.3x longer than the supervised baseline. Finally, the model currently assumes a "uniform" prior (all trees are equally likely at the start); incorporating basic linguistic rules as a prior could further boost performance in extremely low-resource scenarios.

Summary updated

Abstract

Human annotation for syntactic parsing is expensive, and large resources are available only for a fraction of languages. A question we ask is whether one can leverage abundant unlabeled texts to improve syntactic parsers, beyond just using the texts to obtain more generalisable lexical features (i.e. beyond word embeddings). To this end, we propose a novel latent-variable generative model for semi-supervised syntactic dependency parsing. As exact inference is intractable, we introduce a differentiable relaxation to obtain approximate samples and compute gradients with respect to the parser parameters. Our method (Differentiable Perturb-and-Parse) relies on differentiable dynamic programming over stochastically perturbed edge scores. We demonstrate effectiveness of our approach with experiments on English, French and Swedish.
BibTeX
@inproceedings{corro2019differentiable,
  author = {Caio Corro and Ivan Titov},
  title = {{Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=-YK6zgx5TTj},
}
Figure