论文部分内容阅读
集成分类器算法(Boosting)是当今机器学习领域最成功的分类算法之一。Boosting算法在大部分标准测试集上的表现出了良好的分类性能,因此吸引了很多学者对其拥有如此良好的泛化能力进行理论研究。而Boosting算法的Margin理论解释.是其中最有影响力的工作之一。Margin理论是由一系列的关于集成分类器(voting classifier)的泛化错误率上界组成。由于其中用到了训练集合上的margin(详见第二章),故此得名。最近,[Wang et al.,2008,2011]提出了Equilibrium margin(Emargin)上界,紧于以前提出的所有上界。Emargin理论的主要结论是:集成分类器在训练样本上的margin分布的好坏对其泛化能力具有重要影响。Emargin的提出部分上解决了学习领域关于Boosting算法的margin理论之争。(详见第二章)。本文的主要工作在于通过实验方法,利用直接优化Emargin上界的算法——EEM——验证Emargin理论的准确性。EEM对已有集成分类算法(如Ada,Boost)得到的组合分类器的系数进行优化,使得生成的组合分类器的Emargin上界小于原有集成分类器Emargin上界,并比较二者的测试错误率,如果后者的错误率优于前者,则可以从实验上证明Emargin理论是对Boosting算法的合理解释。本文对当前主流的三种集成分类器算法AdaBoost,LogitBoost和Bagging进行了测试,并在17(12个大数据集,5个小数据集)个UCI标准测试数据集[Asuncion and Newman,2007]上进行广泛的实验。利用决策树桩(Decision Stump)和四层决策树作为基本分类器的实验结果表明Emargin理论与实验结果项符合,初步验证了Emargin理论。但是由于决策树函数集的复杂度难以控制,组合的基本分类器往往具有不同的复杂度,而Emargin理论的一个应用前提就是组合分类器的每个基本分类器具有相同的复杂度,从而削弱了我们的结论。因此,我们采用较好控制复杂度的弱分类器——Stump Product——作为基本分类器,并针对不同的集成分类器算法设计了新的迭代优化算法生成基本分类器。然后,再次在17个数据集上进行比较实验,实验结果依然符合Emargin理论的预测结果,从而进一步验证了Emargin理论。