Bootstrapping Feature-Rich Dependency Parsers with Entropic Priors

David A. Smith, Jason EisnerEMNLP 2007 · OpenReview

Abstract

One may need to build a statistical parser for a new language, using only a very small labeled treebank together with raw text. We argue that bootstrapping a parser is most promising when the model uses a rich set of redundant features, as in recent models for scoring dependency parses (McDonald et al., 2005). Drawing on Abney’s (2004) analysis of the Yarowsky algorithm, we perform bootstrapping by entropy regularization: we maximize a linear combination of conditional likelihood on labeled data and confidence (negative Rényi entropy) on unlabeled data. In initial experiments, this surpassed EM for training a simple feature-poor generative model, and also improved the performance of a feature-rich, conditionally estimated model where EM could not easily have been applied. For our models and training sets, more peaked measures of confidence performed better.

Introduction

In Natural Language Processing, dependency parsing—the task of identifying grammatical "head-modifier" relationships—is essential for downstream applications. However, state-of-the-art statistical parsers typically require massive treebanks of manually annotated sentences. For low-resource languages or niche domains, such resources are often unavailable. This paper investigates bootstrapping: a semi-supervised approach that leverages a tiny "seed" set of labeled data alongside vast quantities of raw, unlabeled text to build robust parsing models.

Methodology: Entropy Regularization

The authors utilize a feature-rich parsing framework that represents edges in a parse tree using millions of overlapping, redundant features. Their core innovation is a training objective that combines supervised likelihood on the seed set with entropy regularization on unlabeled data.

By minimizing the Rényi entropy of the model's predictions on raw text, the model is encouraged to be "confident" in its own parses. The Rényi entropy parameter $\alpha$ allows for tuning the "peakedness" of the resulting probability distributions.

Comparison of probability distributions over parses for supervised and bootstrapping methods. Note how bootstrapping with $R_\infty$ (Viterbi) results in the most peaked distribution.

The researchers evaluated this approach on non-projective dependency treebanks from the CoNLL 2006 shared task (German, Spanish, and Czech), simulating low-resource scenarios with seed sets as small as 100 trees.

Key Insights

  • Redundancy as a Virtue: Traditional bootstrapping often fails due to model uncertainty. However, feature-rich models are "overdetermined"; when multiple redundant features (e.g., word identity, POS tags, and distance) converge on the same grammatical link, the model gains sufficient confidence to learn effectively from its own predictions.
  • The Power of Peakedness: The authors found that "peaked" measures of confidence ($\alpha \to \infty$, essentially Viterbi training) consistently outperformed smoother measures. The model learns best when forced to commit strongly to its best guess.
  • Computational Efficiency: While calculating Shannon entropy for non-projective parsing is computationally expensive ($O(n^4)$), using Rényi entropy reduces the complexity to $O(n^3)$, making bootstrapping feasible for complex sentence structures.

Results and Performance

The entropy-based approach significantly outperformed standard Expectation-Maximization (EM), which is prone to "drifting" during unsupervised learning. For a German parser trained on a 100-tree seed, bootstrapping with the most peaked entropy measure ($\alpha = \infty$) improved accuracy from 60.9% to 65.3%.

Precision-Recall curves comparing supervised baselines with bootstrapping methods using different entropy measures ($R_2$ and $R_\infty$).

Across all three languages, increasing the confidence requirement (higher $\alpha$) led to consistent improvements in parsing accuracy compared to the supervised baseline.

Conclusion

This work demonstrates that feature-rich models can effectively "pull themselves up by their bootstraps" using entropic priors. While a performance gap remains compared to fully supervised models, this approach offers a viable path for developing parsers in low-resource settings. Future research will explore scaling to massive corpora and incorporating cross-lingual "soft projections" to further guide the bootstrapping process.

Summary updated

Abstract

One may need to build a statistical parser for a new language, using only a very small labeled treebank together with raw text. We argue that bootstrapping a parser is most promising when the model uses a rich set of redundant features, as in recent models for scoring dependency parses (McDonald et al., 2005). Drawing on Abney’s (2004) analysis of the Yarowsky algorithm, we perform bootstrapping by entropy regularization: we maximize a linear combination of conditional likelihood on labeled data and confidence (negative R´ enyi entropy) on unlabeled data. In initial experiments, this surpassed EM for training a simple feature-poor generative model, and also improved the performance of a feature-rich, conditionally estimated model where EM could not easily have been applied. For our models and training sets, more peaked measures of con
BibTeX
@inproceedings{smith2007bootstrapping,
  author = {David A. Smith and Jason Eisner},
  title = {{Bootstrapping Feature-Rich Dependency Parsers with Entropic Priors}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
  url = {https://openreview.net/forum?id=H1bxjzfdZH},
}
Figure