On 12 Feb, Dr Chunhua Shen from NICTA will be presenting a talk on ‘A Duality View of Boosting Algorithms’:
Consideration of the primal and dual problems together leads to important new insights into the characteristics of boosting algorithms. 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.
Based on these new theoretical results, a new boosting algorithm is designed. We call it margin-distribution boosting (MDBoost). MDBoost directly maximizes the average margin and minimizes the margin variance simultaneously. Empirically we show it outperforms AdaBoost and LPBoost on the UCI machine learning data sets.