A Refined Margin Analysis for Boosting Algorithms via Equilibrium Margin
A Refined Margin Analysis for Boosting Algorithms via Equilibrium Margin
复制标题
通过均衡保证金提升算法的精细保证金分析
DOI：
10.5555/1953048.2021058
复制
发表时间：
2011-02
影响因子：
6
通讯作者：
Feng, Jufu
中科院分区：
文献类型：
--
作者：
Wang, Liwei;Sugiyama, Masashi;Jing, Zhaoxiang;Yang, Cheng;Zhou, Zhi-Hua;Feng, Jufu
AdaBoost的实证成功的理论解释一直受到关注。最有影响力的工作是边际理论，它本质上是任何投票分类器在训练数据上的边际分布方面的泛化误差的上限。但是，有人对差值的解释提出了重要问题。Breiman（1999）证明了一个最小边际的界，它比边际分布界更精确。他认为，最小边际在预测泛化误差方面会更好。格罗夫和Schuurmans（1998）开发了一种称为LP-AdaBoost的算法，该算法在保持所有其他因素与AdaBoost相同的情况下最大化最小裕度。然而，在实验中，LP-AdaBoost通常比AdaBoost表现得更差，这使得边际解释受到严重质疑。本文对边际理论进行了精细化分析。我们证明了一个新的保证金措施称为均衡保证金（Emargin）的约束。Emargin界比Breiman的最小margin界一致更尖锐。因此，我们的研究结果表明，最小间隔可能不是至关重要的泛化误差。我们还表明，一个大的Emargin和一个小的经验误差Emargin意味着一个较小的范围内的推广误差。在基准数据集上的实验结果表明，AdaBoost通常比LP-AdaBoost具有更大的Emargin和更小的测试误差，这与我们的理论是一致的。
Much attention has been paid to the theoretical 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 voting classifier in terms of the margin distribution over the training data. However, important questions were raised about the margin explanation. Breiman (1999) proved a bound in terms of the minimum margin, which is sharper than the margin distribution bound. He argued that the minimum margin would be better in predicting the generalization error. Grove and Schuurmans (1998) developed an algorithm called LP-AdaBoost which maximizes the minimum margin while keeping all other factors the same as AdaBoost. In experiments however, LP-AdaBoost usually performs worse than AdaBoost, putting the margin explanation into serious doubt. In this paper, we make a refined analysis of the margin theory. We prove a bound in terms of a new margin measure called the Equilibrium margin (Emargin). The Emargin bound is uniformly sharper than Breiman's minimum margin bound. Thus our result suggests that the minimum margin may be not crucial for the generalization error. We also show that a large Emargin and a small empirical error at Emargin imply a smaller bound of the generalization error. Experimental results on benchmark data sets demonstrate that AdaBoost usually has a larger Emargin and a smaller test error than LP-AdaBoost, which agrees well with our theory.
登录
查看更多内容
影响因子：
1.6
作者：
L. Devroye
通讯作者：
L. Devroye
DOI：
10.5555/1390681.1390687
发表时间：
2008-06
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
David Mease;A. Wyner
通讯作者：
David Mease;A. Wyner
DOI：
10.5555/1005332.1044712
发表时间：
2004-12
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
C. Rudin;I. Daubechies;R. Schapire
通讯作者：
C. Rudin;I. Daubechies;R. Schapire
DOI：
10.1198/016214505000000907
发表时间：
2006-03-01
影响因子：
3.7
作者：
Bartlett, PL;Jordan, MI;McAuliffe, JD
通讯作者：
McAuliffe, JD
影响因子：
7.5
作者：
Dietterich, TG
通讯作者：
Dietterich, TG