Title（标题）：The Margin Explanation of Boosting Algorithms: Right or Wrong

Speaker（汇报人）：王立威副教授，北大智能科学系

Time（功夫）：2010年9月23日（周四）下午2:00-4:00

Place（地址）：拉斯维加斯9888新楼217教室

Abstract（提要）：There have been a lot of arguments on why boosting has excellent

empirical performance and why it is often immune to overfitting. The most influential explanation 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, Breiman raised important questions about the margin explanation by developing a boosting algorithm arc-gv that provably generates a larger minimum margin than AdaBoost. He also gave a sharper bound in terms of the minimum margin, and argued that the minimum margin governs the generalization. In experiments however, arc-gv usually performs worse than AdaBoost, putting the margin explanation into serious doubts. In this talk, 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 result suggests that the minimum margin is not crucial for the generalization error. We also show that a large Emargin implies good generalization. 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.

About the speaker（汇报人介绍）：王立威副教授别离于1999和2002年在清华大学电子工程系获本科和硕士学位。2005年毕业于北京大学数学科学学院，获博士学位。同年进入北大智能科学系任讲师，2006年任副教授。在机械进建领域顶级会议及期刊NIPS、COLT、ICML、PAMI、CVPR等颁发论文三十篇。多篇论文获期刊最高引用奖和会议优良论文奖。2008年颁发于COLT的论文“On the margin explanation of boosting algorithms”是中国大陆学者在该会议上迄今为止唯逐一篇论文。