On the Dual Formulation of Boosting Algorithms

Abstract

We study boosting algorithms from a new perspective. We show that the Lagrange dual problems of AdaBoost, LogitBoost and soft-margin LPBoost with generalized hinge loss are all entropy maximization problems. By looking at the dual problems of these boosting algorithms, we show that the success of boosting algorithms can be understood in terms of maintaining a better margin distribution by maximizing margins and at the same time controlling the margin variance.We also theoretically prove that, approximately, AdaBoost maximizes the average margin, instead of the minimum margin. The duality formulation also enables us to develop column generation based optimization algorithms, which are totally corrective. We show that they exhibit almost identical classification results to that of standard stage-wise additive boosting algorithms but with much faster convergence rates. Therefore fewer weak classifiers are needed to build the ensemble using our proposed optimization technique.

Fixed typos. 16 pages. Published in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), Dec. 2010

References in corpus (1)

• Analysis of boosting algorithms using the smooth margin function

Cited by in corpus (27)

• On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning
• Guaranteed bounds on the Kullback-Leibler divergence of univariate mixtures using piecewise log-sum-exp inequalities
• Effective Pedestrian Detection Using Center-symmetric Local Binary/Trinary Patterns
• Incremental Training of a Detector Using Online Sparse Eigen-decomposition
• Parallel coordinate descent for the Adaboost problem
• StructBoost: Boosting Methods for Predicting Structured Output Variables
• On Tilted Losses in Machine Learning: Theory and Applications
• Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs
• A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
• Optimizing Ranking Measures for Compact Binary Code Learning
• Totally Corrective Boosting with Cardinality Penalization
• Parameterized Convex Universal Approximators for Decision-Making Problems
• Tilted Empirical Risk Minimization
• Totally Corrective Boosting for Regularized Risk Minimization
• A Direct Approach to Multi-class Boosting and Extensions
• Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables
• Optimally Training a Cascade Classifier
• Face Recognition using Optimal Representation Ensemble
• Asymmetric Totally-corrective Boosting for Real-time Object Detection
• Margin Maximization as Lossless Maximal Compression
• Boosting through Optimization of Margin Distributions
• RandomBoost: Simplified Multi-class Boosting through Randomization
• Margin Distribution Controlled Boosting
• Boosting with Lexicographic Programming: Addressing Class Imbalance without Cost Tuning
• Structured Learning of Binary Codes with Column Generation
• From Kernel Machines to Ensemble Learning
• Totally Corrective Multiclass Boosting with Binary Weak Learners