Annealing Structural Bias in Multilingual Weighted Grammar Induction

Noah A. Smith, Jason EisnerACL 2006 · OpenReview

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.

Effect of fixed locality bias ($\delta$) on parsing accuracy across six languages. Negative values indicate a preference for local 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.

Comprehensive comparison of F1 scores for EM, fixed bias, annealed bias, and Contrastive Estimation (CE) methods across six languages.

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

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.
BibTeX
@inproceedings{smith2006annealing,
  author = {Noah A. Smith and Jason Eisner},
  title = {{Annealing Structural Bias in Multilingual Weighted Grammar Induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=HyE4vhg_-H},
}
Figure