Boosting and Maximum Likelihood for Exponential Models

By Guy Lebanon, John D. Lafferty. 2001

192 citations recorded by the source corpus.

We derive an equivalence between AdaBoost and the dual of a convex optimization problem, showing that the only difference between minimizing the exponential loss used by AdaBoost and maximum likelihood for exponential models is that the latter requires the model to be normalized to form a conditional probability distribution over labels. In addition to establishing a simple and easily understood connection between the two methods, this framework enables us to derive new regularization procedures for boosting that directly correspond to penalized maximum likelihood. Experiments on UCI datasets support our theoretical analysis and give additional insight into the relationship between boosting and logistic regression.

Subfields: Artificial Intelligence, Statistics and Probability, Probabilistic & Bayesian Methods

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 Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

Adaptive Stochastic Dual Coordinate Ascent for Conditional Random Fields (2017, methodology): “Our proposed gap sampling strategy is similar to the one from Osokin et al. (2016) in the context of SDCA applied to the structured SVM objective, which reduces to the block-coordinate Frank-Wolfe (BCFW) algorithm (Lacoste-Julien et al.”
Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks (2008, methodology): “For both log-linear and max-margin models the dual problem corresponds to the minimization of a convex function Q subject to simplex constraints (Jaakkola and Haussler, 1999; Lebanon and Lafferty, 2002; Taskar et al., 2004a).”
Discriminative Reranking for Natural Language Parsing (2000, background): “…and criteria for training the parameters ¯ aa , but recent work (Friedman, Hastie, and Tibshirani 2000; Lafferty 1999; Duffy and Helmbold 1999; Mason, Bartlett, and Baxter 1999; Lebanon and Lafferty 2001; Collins, Schapire, and Singer 2002) has shown that the methods have strong similarities.”
Dual coordinate descent methods for logistic regression and maximum entropy models (2011, background): “Komarek and Moore (2005) and Lin et al. (2008) propose truncated Newton techniques.”
Robust parameter estimation with a small bias against heavy contamination (2008, background): “The Pythagorean relation is known in terms of the KL-divergence related to an exponential family and maximum likelihood estimation [1], the KL-divergence related to the predictive distribution [7], the extended KL-divergence related to AdaBoost [8], the Bregman divergence related to boosting [13], a”
Robust Boosting Algorithm Against Mislabeling in Multiclass Problems (2008, methodology): “It is pointed out that the original AdaBoost is derived from the minimization of the extended Kullback-Leibler divergence between the empirical distribution and the extended exponential model in M under the moment matching condition (see Lebanon & Lafferty, 2001).”
A Primal-Dual Message-Passing Algorithm for Approximated Large Scale Structured Prediction (2010, methodology): “Similarly to CRFs and structured SVMs [11, 16], one can use gradient methods to optimize structured prediction.”
Convexity, Classification, and Risk Bounds (2006, background): “…Vapnik 1995; Cristianini and Shawe-Taylor 2000; Schölkopf and Smola 2002), boosting (Freund and Schapire 1997; Collins, Schapire, and Singer 2002; Lebanon and Lafferty 2002), and variational inference for graphical models (Jordan, Ghahramani, Jaakkola, and Saul 1999) are all based directly on…”
Herding dynamical weights to learn (2009, background): “The dual of this problem is given by the maximum likelihood problem of a Markov random fleld model with indicator features fij;kl(xi;xj) = I[xi = k;xj = l] ( Lebanon & Lafierty, 2002 ).”
Information Divergence Geometry and the Application to Statistical Machine Learning (2009, background): “These loss functions lead to AdaBoost and LogitBoost algorithms, see [30] for the interesting understanding for the relation.”
Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models (2009, background): “As shown by Lebanon and Lafferty [13], in the case of two classes, these models are also closely related to AdaBoost, which can be viewed as solving precisely the same optimization problem with the same constraints, modulo a normalization constraint needed in the conditional maxent case to derive…”
An Introduction to Boosting and Leveraging (2002, methodology): “Additionally, we will briefly discuss relations to information geometry [24, 34, 110, 104, 39, 147, 111] and column generation techniques (cf.”
An evaluation of statistical spam filtering techniques (2004, result): “The work of [Lebanon and Lafferty, 2001] showed that AdaBoost and Maximum Likelihood of exponential models actually minimize the same Kullback-Leibler divergence objective function subject to identical feature constraints, and they typically yield identical results as the number of features increase”
Excess-Risk of Distributed Stochastic Learners (2013, background): “regularizer so that [50], [51]: Q(w,hk,i,yk(i)) = ρ 2 ‖w‖(2) + log ( 1 + e−yk(i)h T k,iw ) (93) and the excess-risk then has the interpretation of being the regularized KL divergence: DRKL ( p(yk(i)|hk,i;w) ‖ p(yk(i)|hk,i;w) )”
Learning from the Wisdom of Crowds by Minimax Entropy (2012, background): “As in the literature of regularized maximum entropy [14, 1, 9], we relax the optimization problem to prevent overfitting: min y max π,ξ,ζ − m ∑ i=1 n ∑ j=1 c ∑”
Blending Learning and Inference in Conditional Random Fields (2016, background): “Learning and inference of structured models drives much of the research in machine learning applications, from computer vision and natural language processing to computational biology.”