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

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 824–831, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics A Comparative Study of Parameter Estimation Methods for Statistical Natural Language Processing Jianfeng Gao*, Galen Andrew*, Mark Johnson*&, Kristina Toutanova* *Microsoft Research, Redmond WA 98052, {jfgao,galena,kristout}@microsoft.com &Brown University, Providence, RI 02912, mj@cs.brown.edu 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) estima- tion with L2 regularization, the Averaged Perceptron (AP), and Boosting. We also in- vestigate 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 sta- tistical tie for first place. 1 Introduction Parameter estimation is fundamental to many sta- tistical approaches to NLP. Because of the high-dimensional nature of natural language, it is often easy to generate an extremely large number of features. The challenge of parameter estimation is to find a combination of the typically noisy, re- dundant features that accurately predicts the target output variable and avoids overfitting. Intuitively, this can be achieved either by selecting a small number of highly-effective features and ignoring the others, or by averaging over a large number of weakly informative features. The first intuition motivates feature selection methods such as Boosting and BLasso (e.g., Collins 2000; Zhao and Yu, 2004), which usually work best when many features are completely irrelevant. L1 or Lasso regularization of linear models, introduced by Tibshirani (1996), embeds feature selection into regularization so that both an assessment of the reliability of a feature and the decision about whether to remove it are done in the same frame- work, and has generated a large amount of interest in the NLP community recently (e.g., Goodman 2003; Riezler and Vasserman 2004). If on the other hand most features are noisy but at least weakly correlated with the target, it may be reasonable to attempt to reduce noise by averaging over all of the features. ME estimators with L2 regularization, which have been widely used in NLP tasks (e.g., Chen and Rosenfeld 2000; Charniak and Johnson 2005; Johnson et al. 1999), tend to produce models that have this property. In addition, the perceptron algorithm and its variants, e.g., the voted or aver- aged perceptron, is becoming increasingly popular due to their competitive performance, simplicity in implementation and low computational cost in training (e.g., Collins 2002). While recent studies claim …

Content truncated to 500 words