A Comparative Study of Parameter Estimation Methods for Statistical Natural Language Processing

Jianfeng Gao, Galen Andrew, Mark Johnson, Kristina ToutanovaACL 2007 · OpenReview

Abstract

This study evaluates five parameter estimation algorithms—Maximum Entropy (ME) with $L_2$ regularization, ME with $L_1$ regularization, the Averaged Perceptron (AP), Boosting, and BLasso—across four diverse Natural Language Processing (NLP) tasks. Our findings reveal a near statistical tie for top performance among ME/$L_1$, ME/$L_2$, and AP. Notably, $L_1$ regularization significantly reduces model size, and the Averaged Perceptron offers superior training efficiency.

Introduction

In Natural Language Processing, models often operate in high-dimensional spaces where features can number in the millions. This complexity necessitates robust parameter estimation methods to prevent overfitting. While $L_2$ regularization has long been the standard, this paper systematically compares it against $L_1$ regularization (Lasso), the Averaged Perceptron, and Boosting-based methods to identify the most effective strategies for large-scale NLP tasks.

Methodology

The study examines five algorithms:

  1. ME with $L_2$ Regularization: The standard approach that penalizes large weights to prevent overfitting.
  2. ME with $L_1$ Regularization: Encourages sparsity by driving irrelevant feature weights to zero, optimized using the novel Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) algorithm.
  3. Averaged Perceptron (AP): An iterative mistake-driven algorithm that averages weights over time to ensure stability.
  4. Boosting: An incremental feature selection method.
  5. BLasso: A hybrid of Boosting and $L_1$ regularization.

These were tested on four benchmarks: Parse Re-ranking (Penn Treebank), Language Model (LM) Adaptation (Japanese text), Chinese Word Segmentation (CWS), and Part-of-Speech (POS) Tagging.

Performance and Efficiency

The experimental results demonstrate that ME/$L_2$, ME/$L_1$, and AP are highly competitive in terms of accuracy. In the parse re-ranking task, the difference in F-scores between these three methods was negligible. However, the computational costs varied significantly.

Table 3: Performance comparison on the parse re-ranking task.

As shown in the table above, the Averaged Perceptron achieved competitive accuracy in just 2 minutes, whereas Boosting required nearly 8 hours. This highlights AP as a powerful choice for rapid prototyping and large-scale training.

The Advantage of Sparsity

One of the most significant findings is the efficiency of $L_1$ regularization in producing sparse models. By eliminating irrelevant features, $L_1$ methods create models that are often an order of magnitude smaller than their $L_2$ counterparts without sacrificing predictive power.

Table 5: Results for Chinese word segmentation showing model sparsity.

In the Chinese Word Segmentation task, ME/$L_1$ achieved an F1 score of 0.9713 using approximately 317,000 features, while ME/$L_2$ required over 8 million features to reach a similar score of 0.9719. This sparsity is critical for deploying models on memory-constrained hardware, such as mobile devices.

Conclusion

The choice of parameter estimation method involves a trade-off between accuracy, model size, and training speed. While $L_2$ regularization remains a reliable baseline, $L_1$ regularization via OWL-QN is superior for applications requiring compact models. For scenarios where training time is the primary constraint, the Averaged Perceptron provides a highly efficient and effective alternative.

Summary updated

Abstract

This paper presents a comparative study of five parameter estimation algorithms on four NLP tasks. Three of the five algorithms are well-known in the computational linguistics community: Maximum Entropy (ME) estimation with L2 regularization, the Averaged Perceptron (AP), and Boosting. We also investigate ME estimation with L1 regularization using a novel optimization algorithm, and BLasso, which is a version of Boosting with Lasso (L1) regularization. We first investigate all of our estimators on two re-ranking tasks: a parse selection task and a language model (LM) adaptation task. Then we apply the best of these estimators to two additional tasks involving conditional sequence models: a Conditional Markov Model (CMM) for part of speech tagging and a Conditional Random Field (CRF) for Chinese word segmentation. Our experiments show that across tasks, three of the estimators — ME estimation with L1 or L2 regularization, and AP — are in a near statistical tie for first place.
BibTeX
@inproceedings{gao2007comparative,
  author = {Jianfeng Gao and Galen Andrew and Mark Johnson and Kristina Toutanova},
  title = {{A Comparative Study of Parameter Estimation Methods for Statistical Natural Language Processing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=BkW9z2l_ZB},
}
Figure