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”是中国大陆学者在该聚会上迄今为止唯逐一篇论文。