Elamur Research⌕
☰
home / papers / 2002 / A Comparison of Algorithms for Maximum Entropy Parameter Estimation

A Comparison of Algorithms for Maximum Entropy Parameter Estimation

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

  • I1. 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.
  • I2. 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.
  • I3. 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.
  • I4. 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.
  • I5. 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

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.

Cite

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

@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}
}

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
  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
  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. ↗
  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
  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
  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
  7. Adam Berger, Stephen Della Pietra, and Vincent Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22. find our card
  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
  9. Zhiyi Chi. 1998. Probability models for complex systems. Ph.D. thesis, Brown University. find
  10. J. Darroch and D. Ratcliff. 1972. Generalized iterative scaling for log-linear models. Ann. Math. Statistics, 43:1470–1480. find
  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
  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
  13. Elizabeth D. Dolan and Jorge J. Moré. 2002. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201–213. find
  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
  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
  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
  17. Thomas P. Minka. 2001. Algorithms for maximum-likelihood logistic regression. Statistics Tech Report 758, CMU. find
  18. Jorge Nocedal and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York. find
  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
  20. Miles Osborne. 2002. Shallow parsing using noisy and non-stationary training material. Journal of Machine Learning Research, 2:695–719. find
  21. Miles Osborne. to appear. Using maximum entropy for sentence extraction. In Proceedings of the ACL 2002 Workshop on Automatic Summarization, Philadelphia. find
  22. Adwait Ratnaparkhi. 1998. Maximum entropy models for natural language ambiguity resolution. Ph.D. thesis, University of Pennsylvania. find
  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

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/malouf-2002-comparison-algorithms-maximum-entropy-parameter/