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.
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:
- The Encoder: Takes a sentence and predicts a latent representation. Here, the latent representation is the dependency tree itself.
- The Decoder: Takes that predicted tree and tries to regenerate the original sentence.
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
argmaxinside 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