Abstract
We first show how a structural locality bias can improve the accuracy of state-of-the-art dependency grammar induction models trained by EM from unannotated examples (Klein and Manning, 2004). Next, by annealing the free parameter that controls this bias, we achieve further improvements. We then describe an alternative kind of structural bias, toward "broken" hypotheses consisting of partial structures over segmented sentences, and show a similar pattern of improvement. We relate this approach to contrastive estimation (Smith and Eisner, 2005a), apply the latter to grammar induction in six languages, and show that our new approach improves accuracy by 1-17% (absolute) over CE (and 8-30% over EM), achieving to our knowledge the best results on this task to date. Our method, structural annealing, is a general technique with broad applicability to hidden-structure discovery problems.
Introduction
Inducing the underlying structure of language without explicit supervision—unsupervised parsing—remains a fundamental challenge in computational linguistics. The standard tool for this task, the Expectation-Maximization (EM) algorithm, often converges to linguistically implausible local optima because it lacks inherent knowledge of syntactic properties, such as the tendency for words to relate to nearby neighbors. This paper introduces structural annealing, a technique that guides the learning process by initially imposing a strong "locality bias" and gradually relaxing it, allowing the model to discover complex structures only after mastering simple ones.
Methodology
The researchers build upon the Dependency Model with Valence (DMV), introducing novel ways to steer the learner toward plausible syntactic structures:
Locality Bias ($\delta$)
Natural languages exhibit a strong preference for local dependencies. The authors formalize this by adding a penalty for long-distance links, controlled by a parameter $\delta$. When $\delta < 0$, the model is forced to prefer short-range dependencies.
Structural Annealing
The core contribution is the annealing of this bias. Instead of a fixed constraint, the model begins with a very strong locality bias and gradually relaxes it over several training epochs. This "coaxing" strategy prevents the model from getting stuck in poor local optima early in the search process.
Segmentation Bias and Contrastive Estimation
An alternative "Vine Parsing" bias is explored, where sentences are initially treated as sequences of independent fragments. The authors also combine these structural biases with Contrastive Estimation (CE), an alternative to EM that moves probability mass from "perturbed" versions of a sentence to the observed sentence.
Key Results
The approach was evaluated on six diverse languages: English, German, Bulgarian, Mandarin, Turkish, and Portuguese. Structural annealing consistently outperformed the standard EM baseline across all datasets.
As shown in the results, German accuracy jumped from a baseline of 54.4% (EM) to 70.0% using annealed locality bias. English reached 63.5% when combined with Contrastive Estimation, and Turkish saw a significant leap to 62.4%. At the time of publication, these results represented the best reported performance for unsupervised dependency induction on these benchmarks.
Discussion and Conclusion
The success of structural annealing highlights that in unsupervised learning, the optimization trajectory—the "path" the model takes—is as critical as the objective function itself. By starting with simple, local patterns, the model builds a foundation that allows it to eventually resolve long-distance relationships correctly. While the method requires careful hyperparameter tuning, it provides a general framework for any hidden-structure discovery problem where some structures are inherently simpler than others.
Summary updated