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

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

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

Place（地点）：成人直播-成人直播室 新楼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”是中国大陆学者在该会议上迄今为止唯一一篇论文。