---
title: "A Comparison of Algorithms for Maximum Entropy — Malouf 2002"
description: "Conditional maximum entropy (ME, log-linear) models are widely used for NLP classification, but realistic models can have hundreds of thousands of…"
authors: ["Robert Malouf"]
year: 2002
venue: "COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002)"
source: "https://aclanthology.org/W02-2018/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/malouf-2002-comparison-algorithms-maximum-entropy-parameter/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/malouf-2002-comparison-algorithms-maximum-entropy-parameter/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2002](https://md.research.elamur.ai/free/papers/2002/) / A Comparison of Algorithms for Maximum Entropy Parameter Estimation

# A Comparison of Algorithms for Maximum Entropy Parameter Estimation

**Authors:** Robert Malouf · **Year:** 2002 · **Venue:** COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/W02-2018/) · [PDF](https://aclanthology.org/W02-2018.pdf) · [OpenAlex](https://openalex.org/W2102667697)

**Citations:** 655 citations (openalex-snapshot · 2026-10-14) · [97](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Conditional maximum entropy (ME, log-linear) models are widely used for NLP classification, but realistic models can have hundreds of thousands of parameters. Fitting them is costly and numerically delicate. Malouf asks which optimization algorithm should be used to fit them. He compares six estimators on four realistic NLP datasets: the two traditional ones, Generalized Iterative Scaling (GIS) and Improved Iterative Scaling (IIS), and four general-purpose methods, namely steepest ascent, two conjugate gradient variants (Fletcher-Reeves and Polak-Ribière-Positive) and a limited-memory variable metric (quasi-Newton) method. All six are implemented on the same PETSc sparse-matrix foundation.

The widely used iterative scaling methods perform poorly. Gradient-based methods, apart from steepest ascent, need far fewer evaluations and much less time. The limited-memory variable metric algorithm wins on every dataset. Prediction accuracy is largely the same across methods.

This matters because faster estimation makes larger ME models practical and enables broader model and feature selection. More generally, the paper shows that NLP benefits from reusing numerical libraries built for scientific computing.

## Key points
- Six estimators are compared: GIS, IIS, steepest ascent, CG (Fletcher-Reeves), CG (Polak-Ribière-Positive) and limited-memory variable metric (Benson and Moré, 2001).
- There are four test datasets. Two are stochastic attribute-value grammar sets ('rules', 'lex'), plus 'summary' and 'shallow'.
- Each method is evaluated on:
  - KL divergence at convergence,
  - accuracy,
  - number of iterations,
  - number of function evaluations,
  - elapsed time.
- The speed gaps are large:
  - On 'summary', limited-memory variable metric took 8.52 s versus 107.05 s for GIS and 188.54 s for IIS.
  - On 'shallow', it took about 2,420 s versus about 21,224 s for GIS and about 66,856 s for IIS.
- Accuracy is mostly similar across methods, with two exceptions:
  - GIS is slightly ahead on the SAVG sets.
  - On the sparse 'shallow' data, GIS (14.19) and IIS (5.42) fall far behind the gradient methods (roughly 24–27).
- The implementation uses PETSc. Experiments ran on a single 1700 MHz Pentium 4 CPU with 2 GB RAM, and timings exclude data loading.

## Interesting ideas
- **Iterative scaling is gradient computation in disguise.** The expected feature counts that GIS and IIS compute are essentially the log-likelihood gradient. Feeding them to a proper optimizer is nearly free, which is a reminder to check whether a "special-purpose" algorithm is just a weak use of quantities a general method could exploit better.
- **Limited-memory quasi-Newton updates.** The method approximates curvature from only the last few gradient and step pairs (3–10 suffice). This keeps memory usage manageable at huge dimensionality and fits any large, smooth, concave objective, such as log-linear taggers or classifiers.
- **Evaluate optimizers on real data, not synthetic data.** Random or small problems can misrepresent how algorithms behave on ill-conditioned, sparse NLP data. Benchmarks should therefore use realistic tasks at realistic scale.
- **Stopping criteria interact with the algorithm.** A fixed relative-improvement threshold stops different methods at very different precision levels: on 'summary', the final KL divergence varied by up to two orders of magnitude. Comparisons should therefore report the final objective value alongside time.
- **Gradient methods are more robust on sparse data.** When many features drift toward infinite negative weights, gradient methods held up better than iterative scaling. The paper notes that smoothing would likely help all methods, which is worth remembering for small or sparse corpora.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

## Cited by

Cited by

97 papers of our library cite it (of the 140673 whose bibliographies we read); 12 of them have a page here, 85 not yet.

- [Robust VPE Detection using Automatically Parsed Text](https://md.research.elamur.ai/free/papers/aclbulk-2004-nielsen-robust-vpe-detection-automatically-parsed/)
- [Verb Phrase Ellipsis detection using Automatically Parsed Text](https://md.research.elamur.ai/free/papers/aclbulk-2004-nielsen-verb-phrase-ellipsis-detection-automatically/)
- [Probabilistic Disambiguation Models for Wide-Coverage HPSG Parsing](https://md.research.elamur.ai/free/papers/aclbulk-2005-miyao-probabilistic-disambiguation-models-wide-coverage/)
- [Learning Recursive Segments for Discourse Parsing](https://md.research.elamur.ai/free/papers/afantenos-2010-learning-recursive-segments-discourse-parsing/)
- [An Expectation Maximization Approach to Pronoun Resolution](https://md.research.elamur.ai/free/papers/cherry-2005-expectation-maximization-approach-pronoun-resolution/)
- [Feature Forest Models for Probabilistic HPSG Parsing](https://md.research.elamur.ai/free/papers/cl-2008-miyao-feature-forest-models-probabilistic-hpsg/)
- [Discriminative Reranking for Natural Language Parsing](https://md.research.elamur.ai/free/papers/collins-2000-discriminative-reranking-natural-language-parsing/)
- [Joint Determination of Anaphoricity and Coreference Resolution using Integer Programming](https://md.research.elamur.ai/free/papers/denis-2007-joint-determination-anaphoricity-coreference-resolution/)
- [Specialized Models and Ranking for Coreference Resolution](https://md.research.elamur.ai/free/papers/denis-2008-specialized-models-ranking-coreference-resolution/)
- [Early results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons](https://md.research.elamur.ai/free/papers/mccallum-2003-early-results-named-entity-recognition/)
- [Improving Machine Translation Performance by Exploiting Non-Parallel Corpora](https://md.research.elamur.ai/free/papers/munteanu-2005-improving-machine-translation-performance-exploiting/)
- [Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models](https://md.research.elamur.ai/free/papers/nlpgap-2007-clark-wide-coverage-efficient-statistical-parsing/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{malouf2002comparison,
  title = {{A Comparison of Algorithms for Maximum Entropy Parameter Estimation}},
  author = {Malouf, Robert},
  booktitle = {COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002)},
  year = {2002},
  doi = {10.3115/1118853.1118871},
  url = {https://doi.org/10.3115/1118853.1118871}
}
```

- [next → A Comprehensive NLP System for Modern Standard Arabic and Modern Hebrew](https://md.research.elamur.ai/free/papers/aclbulk-2002-kamir-comprehensive-nlp-system-modern-standard/)
- [↑ back to papers of 2002](https://md.research.elamur.ai/free/papers/2002/)

## References

23 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Steven P. Abney. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23:597– 618. [find](https://scholar.google.com/scholar?q=Steven+P%2E+Abney%2E+1997%2E+Stochastic+attribute%2Dvalue+grammars%2E+Computational+Linguistics%2C+23%3A597%E2%80%93+618%2E)
2. Satish Balay, William D. Gropp, Lois Curfman McInnes, and Barry F. Smith. 1997. Efficienct management of parallelism in object oriented numerical software libraries. In E. Arge, A. M. Bruaset, and H. P. Langtangen, editors, Modern Software Tools in Scientific Computing, pages 163– 202. Birkhauser Pr… [find](https://scholar.google.com/scholar?q=Satish+Balay%2C+William+D%2E+Gropp%2C+Lois+Curfman+McInnes%2C+and+Barry+F%2E+Smith%2E+1997%2E+Efficienct+management+of+parallelism+in+object+oriented+numerical+software+libraries%2E+In+E%2E+Arge%2C+A%2E+M%2E+Bruaset%2C+and+H%2E+)
3. Satish Balay, Kris Buschelman, William D. Gropp, Dinesh Kaushik, Lois Curfman McInnes, and Barry F. Smith. 2001. PETSc home page. [http://www.mcs.anl.gov/petsc](http://www.mcs.anl.gov/petsc). [↗](http://www.mcs.anl.gov/petsc)
4. Satish Balay, William D. Gropp, Lois Curfman McInnes, and Barry F. Smith. 2002. PETSc users manual. Technical Report ANL-95/11–Revision 2.1.2, Argonne National Laboratory. [find](https://scholar.google.com/scholar?q=Satish+Balay%2C+William+D%2E+Gropp%2C+Lois+Curfman+McInnes%2C+and+Barry+F%2E+Smith%2E+2002%2E+PETSc+users+manual%2E+Technical+Report+ANL%2D95%2F11%E2%80%93Revision+2%2E1%2E2%2C+Argonne+National+Laboratory%2E)
5. Steven J. Benson and Jorge J. Moré. 2001. A limited memory variable metric method for bound constrained minimization. Preprint ANL/ACS-P909-0901, Argonne National Laboratory. [find](https://scholar.google.com/scholar?q=Steven+J%2E+Benson+and+Jorge+J%2E+More%CC%81%2E+2001%2E+A+limited+memory+variable+metric+method+for+bound+constrained+minimization%2E+Preprint+ANL%2FACS%2DP909%2D0901%2C+Argonne+National+Laboratory%2E)
6. Steven J. Benson, Lois Curfman McInnes, Jorge J. Moré, and Jason Sarich. 2002. TAO users manual. Technical Report ANL/MCS-TM-242– Revision 1.4, Argonne National Laboratory. [find](https://scholar.google.com/scholar?q=Steven+J%2E+Benson%2C+Lois+Curfman+McInnes%2C+Jorge+J%2E+More%CC%81%2C+and+Jason+Sarich%2E+2002%2E+TAO+users+manual%2E+Technical+Report+ANL%2FMCS%2DTM%2D242%E2%80%93+Revision+1%2E4%2C+Argonne+National+Laboratory%2E)
7. Adam Berger, Stephen Della Pietra, and Vincent Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22. [find](https://scholar.google.com/scholar?q=Adam+Berger%2C+Stephen+Della+Pietra%2C+and+Vincent+Della+Pietra%2E+1996%2E+A+maximum+entropy+approach+to+natural+language+processing%2E+Computational+Linguistics%2C+22%2E) [our card](https://md.research.elamur.ai/free/papers/berger-1996-maximum-entropy-approach-natural-language/)
8. Gosse Bouma, Gertjan van Noord, and Robert Malouf. 2001. Alpino: wide coverage computational analysis of Dutch. In W. Daelemans, K. Sima’an, J. Veenstra, and J. Zavrel, editors, Computational Linguistics in the Netherlands 2000, pages 45– 59. Rodolpi, Amsterdam. [find](https://scholar.google.com/scholar?q=Gosse+Bouma%2C+Gertjan+van+Noord%2C+and+Robert+Malouf%2E+2001%2E+Alpino%3A+wide+coverage+computational+analysis+of+Dutch%2E+In+W%2E+Daelemans%2C+K%2E+Sima%E2%80%99an%2C+J%2E+Veenstra%2C+and+J%2E+Zavrel%2C+editors%2C+Computational+Linguist)
9. Zhiyi Chi. 1998. Probability models for complex systems. Ph.D. thesis, Brown University. [find](https://scholar.google.com/scholar?q=Zhiyi+Chi%2E+1998%2E+Probability+models+for+complex+systems%2E+Ph%2ED%2E+thesis%2C+Brown+University%2E)
10. J. Darroch and D. Ratcliff. 1972. Generalized iterative scaling for log-linear models. Ann. Math. Statistics, 43:1470–1480. [find](https://scholar.google.com/scholar?q=J%2E+Darroch+and+D%2E+Ratcliff%2E+1972%2E+Generalized+iterative+scaling+for+log%2Dlinear+models%2E+Ann%2E+Math%2E+Statistics%2C+43%3A1470%E2%80%931480%2E)
11. Stephen Della Pietra, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:380–393. [find](https://scholar.google.com/scholar?q=Stephen+Della+Pietra%2C+Vincent+Della+Pietra%2C+and+John+Lafferty%2E+1997%2E+Inducing+features+of+random+fields%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+19%3A380%E2%80%93393%2E)
12. W.E. Deming and F.F. Stephan. 1940. On a least squares adjustment of a sampled frequency table when the expected marginals are known. Annals of Mathematical Statistics, 11:427–444. [find](https://scholar.google.com/scholar?q=W%2EE%2E+Deming+and+F%2EF%2E+Stephan%2E+1940%2E+On+a+least+squares+adjustment+of+a+sampled+frequency+table+when+the+expected+marginals+are+known%2E+Annals+of+Mathematical+Statistics%2C+11%3A427%E2%80%93444%2E)
13. Elizabeth D. Dolan and Jorge J. Moré. 2002. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201–213. [find](https://scholar.google.com/scholar?q=Elizabeth+D%2E+Dolan+and+Jorge+J%2E+More%CC%81%2E+2002%2E+Benchmarking+optimization+software+with+performance+profiles%2E+Mathematical+Programming%2C+91%3A201%E2%80%93213%2E)
14. Mark Johnson, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic “unification-based” grammars. In Proceedings of the 37th Annual Meeting of the ACL, pages 535–541, College Park, Maryland. [find](https://scholar.google.com/scholar?q=Mark+Johnson%2C+Stuart+Geman%2C+Stephen+Canon%2C+Zhiyi+Chi%2C+and+Stefan+Riezler%2E+1999%2E+Estimators+for+stochastic+%E2%80%9Cunification%2Dbased%E2%80%9D+grammars%2E+In+Proceedings+of+the+37th+Annual+Meeting+of+the+ACL%2C+pages+535%E2%80%93)
15. John Lafferty and Bernhard Suhm. 1996. Cluster expansions and iterative scaling for maximum entropy language models. In K. Hanson and R. Silver, editors, Maximum Entropy and Bayesian Methods. Kluwer. [find](https://scholar.google.com/scholar?q=John+Lafferty+and+Bernhard+Suhm%2E+1996%2E+Cluster+expansions+and+iterative+scaling+for+maximum+entropy+language+models%2E+In+K%2E+Hanson+and+R%2E+Silver%2C+editors%2C+Maximum+Entropy+and+Bayesian+Methods%2E+Kluwer%2E)
16. John Lafferty, Fernando Pereira, and Andrew Mc-Callum. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In International Conference on Machine Learning (ICML). [find](https://scholar.google.com/scholar?q=John+Lafferty%2C+Fernando+Pereira%2C+and+Andrew+Mc%2DCallum%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+International+Conference+on+Machine+Learning+)
17. Thomas P. Minka. 2001. Algorithms for maximum-likelihood logistic regression. Statistics Tech Report 758, CMU. [find](https://scholar.google.com/scholar?q=Thomas+P%2E+Minka%2E+2001%2E+Algorithms+for+maximum%2Dlikelihood+logistic+regression%2E+Statistics+Tech+Report+758%2C+CMU%2E)
18. Jorge Nocedal and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York. [find](https://scholar.google.com/scholar?q=Jorge+Nocedal+and+Stephen+J%2E+Wright%2E+1999%2E+Numerical+Optimization%2E+Springer%2C+New+York%2E)
19. Jorge Nocedal. 1997. Large scale unconstrained optimization. In A. Watson and I. Duff, editors, The State of the Art in Numerical Analysis, pages 311–338. Oxford University Press. [find](https://scholar.google.com/scholar?q=Jorge+Nocedal%2E+1997%2E+Large+scale+unconstrained+optimization%2E+In+A%2E+Watson+and+I%2E+Duff%2C+editors%2C+The+State+of+the+Art+in+Numerical+Analysis%2C+pages+311%E2%80%93338%2E+Oxford+University+Press%2E)
20. Miles Osborne. 2002. Shallow parsing using noisy and non-stationary training material. Journal of Machine Learning Research, 2:695–719. [find](https://scholar.google.com/scholar?q=Miles+Osborne%2E+2002%2E+Shallow+parsing+using+noisy+and+non%2Dstationary+training+material%2E+Journal+of+Machine+Learning+Research%2C+2%3A695%E2%80%93719%2E)
21. Miles Osborne. to appear. Using maximum entropy for sentence extraction. In Proceedings of the ACL 2002 Workshop on Automatic Summarization, Philadelphia. [find](https://scholar.google.com/scholar?q=Miles+Osborne%2E+to+appear%2E+Using+maximum+entropy+for+sentence+extraction%2E+In+Proceedings+of+the+ACL+2002+Workshop+on+Automatic+Summarization%2C+Philadelphia%2E)
22. Adwait Ratnaparkhi. 1998. Maximum entropy models for natural language ambiguity resolution. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Adwait+Ratnaparkhi%2E+1998%2E+Maximum+entropy+models+for+natural+language+ambiguity+resolution%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
23. Jun Wu and Sanjeev Khudanpur. 2000. Efficient training methods for maximum entropy language modelling. In Proceedings of ICSLP2000, volume 3, pages 114–117, Beijing. [find](https://scholar.google.com/scholar?q=Jun+Wu+and+Sanjeev+Khudanpur%2E+2000%2E+Efficient+training+methods+for+maximum+entropy+language+modelling%2E+In+Proceedings+of+ICSLP2000%2C+volume+3%2C+pages+114%E2%80%93117%2C+Beijing%2E)