A Comparison of Algorithms for Maximum Entropy Parameter Estimation

By Robert Malouf. Conference on Computational Natural Language Learning, 2002

789 citations recorded by the source corpus.

Conditional maximum entropy (ME) models provide a general purpose machine learning technique which has been successfully applied to fields as diverse as computer vision and econometrics, and which is used for a wide variety of classification problems in natural language processing. However, the flexibility of ME models is not without cost. While parameter estimation for ME models is conceptually straightforward, in practice ME models for typical natural language tasks are very large, and may well contain many thousands of free parameters. In this paper, we consider a number of algorithms for estimating the parameters of ME models, including iterative scaling, gradient ascent, conjugate gradient, and variable metric methods. Sur-prisingly, the standardly used iterative scaling algorithms perform quite poorly in comparison to the others, and for all of the test problems, a limited-memory variable metric algorithm outperformed the other choices.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/878783964ab23c97052ea82685368099d85c500d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress (2018, methodology): “When input (demonstration) data is structured accordingly, these algorithms make the evaluation of partition function efficient [58].”
Label Distribution Learning (2013, methodology): “(18) Thus it performs much more efficiently than the standard line search Newton method, and based on previous studies [18], it stands a good chance of outperforming the IIS-based algorit hm IIS-LLD.”
Calibration of Confidence Measures in Speech Recognition (2011, methodology): “We evaluate the proposed techniques on several datasets in Section VI and conclude the paper in Section VII.”
Accurate Information Extraction from Research Papers using Conditional Random Fields (2004, positive): “Traditional maximum entropy learning algorithms, such as GIS and IIS (Pietra et al., 1995), can be used to train CRFs, however, it has been found that a quasi-Newton gradient-climber, BFGS, converges much faster (Malouf, 2002; Sha and Pereira, 2003).”
Generalized Expectation Criteria for Semi-Supervised Learning with Weakly Labeled Data (2010, methodology): “This can be done by gradient methods (Malouf, 2002), where the gradient of the likelihood is ∂ ∂θk O(θ”
Chinese Segmentation and New Word Detection using Conditional Random Fields (2004, positive): “However, our implementation uses a quasi-Newton gradient-climber BFGS for optimization, which has been shown to converge much faster (Malouf, 2002; Sha and Pereira, 2003).”
Hybrid Deterministic-Stochastic Methods for Data Fitting (2011, methodology): “Several comparison studies indicate that these type of limited-memory quasi-Newton methods are among the most eﬃcient deterministic methods available for solving large-scale logistic regression and conditional random ﬁeld problems [19, 36, 21, 32].”
Shallow Parsing with Conditional Random Fields (2003, methodology): “An earlier study indicates that L-BFGS performs well in maximum-entropy classi(cid:2)er training (Malouf, 2002).”
Efficiently Inducing Features of Conditional Random Fields (2002, methodology): “…scaling is the traditional method of train ing these maximum-entropy models (Darroch et al., 1980; Della Pietra et al., 1997), however it has recently been shown that quasi-Newton methods, such as L-BFGS, are significantly more efficient (Byrd et a!., 1994; Malouf, 2002; Sha & Pereira, 2003).”
Book Reviews: Data-Intensive Text Processing with MapReduce by Jimmy Lin and Chris Dyer (2010, methodology): “Gradient-based optimization techniques can be quite effectively used to learn the parameters of probabilistic models with a log-linear parameterization [71].”
Learning objective functions for manipulation (2013, methodology): “It has been shown that for maximum entropy modeling tasks, gradientbased methods outperform all variants of iterative scaling [19].”
Building a Sentiment Summarizer for Local Service Reviews (2008, methodology): “We then trained a maximum entropy classifier (with a gaussian prior over the weights) [2, 11] to predict these ratings based on a small number of local and global contextual features for a sentence xi occurring in the review r = (x1, x2, .”
Discriminative Reranking for Natural Language Parsing (2000, methodology): “…defined as There are many methods in the literature for minimizing LogLoss(¯ aa ) with respect to ¯ aa , for example, generalized or improved iterative scaling (Berger, Della Pietra, and Della Pietra 1996; Della Pietra, Della Pietra, and Lafferty 1997), or conjugate gradient methods (Malouf 2002).”
Structured Embedding via Pairwise Relations and Long-Range Interactions in Knowledge Base (2015, background): “0001; (iv) the length of each path is no longer than 4 (L = 4) and the maximum number of long-range interactions for each pairwise relation is K = 10; (v) minibatched Limited-memory BFGS (L-BFGS) (Malouf 2002; Andrew and Gao 2007) is used for optimizing non-convex object function and the number of t”
A Maximum Entropy Model of Phonotactics and Phonotactic Learning (2008, background): “Table 4 (continued) Constraint Weight Comment Examples ?stw vs. skw,2.06 In effect: only [r] may occur after 20.”
Simple, robust, scalable semi-supervised learning via expectation regularization (2007, methodology): “; D) =log p.(y(d)|x(d)). d This can be done by gradient methods (Malouf, 2002), where the gradient of the likelihood is (d) (d) .”
Efficient Training of Conditional Random Fields (2002, methodology): “To investigate whether there is any computational advantage to using iterative scaling algorithms when training conditional maximum entropy models, Malouf [32] compared the performance of a number of algorithms for estimat-”
Scalable training of L1-regularized log-linear models (2007, methodology): “…objective function cannot be minimized with generalpurpose gradient-based optimization algorithms such as the l-bfgs quasi-Newton method (Nocedal & Wright, 1999), which has been shown to be superior at training large-scale L2-regularized log-linear models by Malouf (2002) and Minka (2003).”
Speech Recognition Using Augmented Conditional Random Fields (2009, methodology): “In the case of maximum entropy modeling for natural language processing, Malouf [69] demonstrated that gradient-based optimization is considerably more efficient than approaches based on iterative scaling.”