A convex and feature-rich discriminative approach to dependency grammar induction

Edouard Grave, Noémie ElhadadACL 2015 · OpenReview

Unsupervised dependency parsing—the task of uncovering the syntactic structure of sentences without labeled training data—has long been considered a "holy grail" of computational linguistics. Traditionally, this problem has been dominated by generative models like the Dependency Model with Valence (DMV). However, these models rely on non-convex optimization (Expectation-Maximization), making them notoriously sensitive to initialization and prone to local minima.

This paper, presented at ACL 2015, introduces a novel framework that shifts the paradigm from generative modeling to a discriminative, convex optimization approach. By formulating grammar induction as a convex quadratic program, the authors provide a method that is robust to initialization, computationally efficient, and capable of handling complex linguistic structures like non-projectivity.

The Problem with Generative Baselines

Generative models attempt to model how a sentence is produced. While theoretically sound, they face two major practical hurdles:

  1. Non-Convexity: Training requires finding parameters that maximize data likelihood. Because the objective function is non-convex, researchers often rely on "initialization magic"—highly specific heuristics—to avoid poor local optima.
  2. Feature Limitations: It is difficult to incorporate rich, overlapping features (like trigram context) or handle non-projective dependencies (where dependency arcs cross) within a standard probabilistic generative framework.

A Discriminative, Convex Alternative

The authors propose a discriminative clustering approach. Instead of modeling sentence generation, the goal is to find a dependency tree $y$ and a parameter vector $w$ such that the tree can be efficiently predicted by a discriminative parser.

Optimization via Frank-Wolfe

To make this tractable, the authors relax the discrete set of valid dependency trees into a "tree polytope" (the convex hull of all valid trees). They then employ the Frank-Wolfe algorithm to solve the resulting convex objective.

Geometric illustration of the Frank-Wolfe algorithm on the tree polytope $\mathcal{D}$.

The choice of Frank-Wolfe is particularly strategic. Each iteration requires solving a linear subproblem, which in this context is equivalent to finding a Minimum Weight Spanning Tree (MST). This can be solved rapidly using standard algorithms like Chu-Liu/Edmonds, which naturally support non-projective structures.

Key Insights and Features

  • Universal Priors: To guide the model without labeled data, the authors incorporate "syntactic universals"—a small set of language-independent rules (e.g., "Adjectives usually depend on Nouns")—as constraints within the optimization.
  • Non-Projectivity by Default: Unlike many generative models that struggle with crossing dependencies, this method treats parsing as an MST problem. This allows it to handle non-projective edges, which are common in many world languages, more efficiently than projective ones.
An example of a non-projective dependency tree where edges cross, a structure handled naturally by the proposed MST-based approach.
  • Feature Flexibility: As a discriminative model, it easily integrates rich features. An ablation study revealed that "Distance" features (the signed distance between a head and its dependent) were the most critical for success.

Experimental Results

The model was evaluated on the Universal Treebanks (v2.0) across ten languages from four different families (Germanic, Romance, and others like Korean and Japanese).

  1. Accuracy: The proposed method outperformed the standard DMV baseline and other state-of-the-art systems on 7 out of 10 languages. On sentences of length $\le 10$, it achieved an average directed dependency accuracy of 64.8%, significantly higher than the DMV's 40.2%.
  2. Efficiency: The computational gains were stark. For the English treebank, the authors' method trained in just 2 minutes, whereas the previous state-of-the-art baseline required 15 hours.

Conclusion and Future Directions

By moving to a convex formulation, the authors have eliminated the "initialization lottery" inherent in unsupervised parsing. While the current model lacks a notion of "valency" (the number of arguments a head takes) and relies on part-of-speech tags, it provides a powerful, fast, and theoretically grounded foundation for future work in unsupervised syntax. Future iterations may explore higher-order parsing and lexicalization through word embeddings to further improve performance on longer, more complex sentences.

Summary updated

Abstract

In this paper, we introduce a new method for the problem of unsupervised dependency parsing. Most current approaches are based on generative models. Learning the parameters of such models relies on solving a non-convex optimization problem, thus making them sensitive to initialization. We propose a new convex formulation to the task of dependency grammar induction. Our approach is discriminative, allowing the use of different kinds of features. We describe an efficient optimization algorithm to learn the parameters of our model, based on the Frank-Wolfe algorithm. Our method can easily be generalized to other unsupervised learning problems. We evaluate our approach on ten languages belonging to four different families, showing that our method is competitive with other state-of-the-art methods.
BibTeX
@inproceedings{grave2015convex,
  author = {Edouard Grave and Noémie Elhadad},
  title = {{A convex and feature-rich discriminative approach to dependency grammar induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2015},
  url = {https://openreview.net/forum?id=Hkb4ZhxOWB},
}
Figure