Boosting理论与算法的研究

Boosting是模式识别、机器学习领域最重要的研究成果之一。虽然在算法方面取得了突出的效果，但关于boosting的两个核心问题- - 1）Boosting为何具备优异的性能；2）Boosting为何会具有较强的抗过拟合能力- - 至今没有令人满意的理论解释。本项目将研究并建立完整的理论体系以回答上述两个核心问题，进而在理论指导下设计更高性能的全新boosting算法。计划建立boosting分类器基于Emargin的泛化错误率上界、匹配下界、以及大样本相合性。设计以优化Emargin为目标的boosting算法。此外，还预计将新算法应用到人脸检测与识别系统。本项目预期在国际权威学术期刊、会议上发表论文8-10篇，并培养3-5名研究生。

Boosting是机器学习领域性能最好的算法之一，已经被广泛用于多个应用领域。Boosting中最具代表性的算法是adaboost。该算法利用一个给定的基本分类算法，通过对训练数据集相继赋予不同的权重分布，学习出一系列基本分类器，而后将这些基本分类器组合起来作为最终的分类器。关于adaboost有两个核心问题：1）为什么adaboost会有如此优异的性能？ 2）实验中观察到adaboost在很多情况下不发生过拟和,这似乎与Occam剃刀原则完全相悖，理论上如何解释？ ..本项目针对上述两个boosting基本问题进行了较为系统的理论研究。在Schapire, Breiman等人工作的基础上，提出了Equilibrium margin理论。项目核心成果在于，我们证明了一个组合分类器的margin上界。该上界中的核心量是我们定义的一个新的概念，称作Equilibrium-margin，简称Emargin。我们证明了Emargin理论一致优于Breiman的最小margin理论和Schapire的margin distribution理论。这一结果对margin理论的争论给出了解释。此外，我们根据Emargin理论，设计了新的boosting算法，取得了较好的效果。..在上述工作基础上，我们对一般线性分类器的margin理论进行了深入的分析。由Vapnik等人给出的经典margin理论一直认为学习结果的泛化能力只与分类器的margin有关，与数据所在空间维数无关。我们证明了一个新的margin上界，该上界不仅与margin有关，而且与空间维数有关。我们同时证明，新的维数相关margin上界一致优于经典的维数无关上界。新结论说明泛化能力随着空间维数增加变差，并非与维数无关。..此外我们还研究了主动学习理论、排序学习和基于学习的算法博弈论。并将以上理论和算法成果应用于计算机视觉领域的具体问题中，取得了较好的效果。..本项目在包括JMLR, NIPS, COLT, IJCAI等机器学习领域权威学术刊物、会议上发表高水平论文10篇。项目负责人在CCML2013做大会特邀报告。本项目还培养6名研究生。