On the Margin Explanation of Boosting Algorithms
Liwei Wang, Masashi Sugiyama, Masashi Sugiyama, Chen Yang, Zhi‐Hua Zhou, Jufu Feng · 2008
Much attention has been paid to the theo-retical explanation of the empirical success of AdaBoost. The most influential work is the margin theory, which is essentially an upper bound for the generalization error of any vot-ing classifier in terms of the margin distribu-tion over the training data. However, Breiman raised important questions about the margin explanation by developing a boosting algo-rithm arc-gv that provably generates a larger minimum margin than AdaBoost. He also gave a sharper bound in terms of the minimum mar-gin, and argued that the minimum margin gov-erns the generalization. In experiments how-ever, arc-gv usually performs worse than Ad-aBoost, putting the margin explanation into serious doubts. In this paper, we try to give a complete answer to Breiman’s critique by proving a bound in terms of a new margin measure called Equilibrium margin (Emargin). The Emargin bound is uniformly sharper than Breiman’s minimum margin bound. This re-sult suggests that the minimum margin is not crucial for the generalization error. We also show that a large Emargin implies good gener-alization. Experimental results on benchmark datasets demonstrate that AdaBoost usually has a larger Emargin and a smaller test error than arc-gv, which agrees well with our theory. 1