A Comparison of Algorithms for Maximum Entropy Parameter Estimation

A comparison of algorithms for maximum entropy parameter estimation Robert Malouf Alfa-Informatica Rijksuniversiteit Groningen Postbus 716 9700AS Groningen The Netherlands malouf@let.rug.nl Abstract Conditional maximum entropy (ME) models pro- vide 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 con- ceptually straightforward, in practice ME models for typical natural language tasks are very large, and may well contain many thousands of free parame- ters. In this paper, we consider a number of algo- rithms for estimating the parameters of ME mod- els, including iterative scaling, gradient ascent, con- jugate gradient, and variable metric methods. Sur- prisingly, the standardly used iterative scaling algo- rithms 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. 1 Introduction Maximum entropy (ME) models, variously known as log-linear, Gibbs, exponential, and multinomial logit models, provide a general purpose machine learning technique for classification and prediction which has been successfully applied to fields as di- verse as computer vision and econometrics. In natu- ral language processing, recent years have seen ME techniques used for sentence boundary detection, part of speech tagging, parse selection and ambigu- ity resolution, and stochastic attribute-value gram- mars, to name just a few applications (Abney, 1997; Berger et al., 1996; Ratnaparkhi, 1998; Johnson et al., 1999). A leading advantage of ME models is their flex- ibility: they allow stochastic rule systems to be augmented with additional syntactic, semantic, and pragmatic features. However, the richness of the representations is not without cost. Even mod- est ME models can require considerable computa- tional resources and very large quantities of anno- tated training data in order to accurately estimate the model’s parameters. While parameter estima- tion for ME models is conceptually straightforward, in practice ME models for typical natural language tasks are usually quite large, and frequently contain hundreds of thousands of free parameters. Estima- tion of such large models is not only expensive, but also, due to sparsely distributed features, sensitive to round-off errors. Thus, highly efficient, accurate, scalable methods are required for estimating the pa- rameters of practical models. In this paper, we consider a number of algorithms for estimating the parameters of ME models, in- cluding Generalized Iterative Scaling and Improved Iterative Scaling, as well as general purpose opti- mization techniques such as gradient ascent, conju- gate gradient, and variable metric methods. Sur- prisingly, the widely used iterative scaling algo- rithms perform quite poorly, and for all of the test problems, a limited memory variable metric algo- rithm outperformed the other choices. 2 Maximum likelihood estimation Suppose we are given a probability distribution p over a set of events X which are characterized by a d dimensional feature vector function f : X → Rd. …

Content truncated to 500 words