论文部分内容阅读
Boosting是一类著名的主流机器学习方法,长期以来一直受到国际机器学习界的高度关注。Boosting方面的研究产生了很多影响力甚至超越机器学习领域的研究成果,例如理论计算机科学界的2003年度哥德尔奖、计算机视觉与模式识别领域的2011年度Longuet-Higgins奖,都颁给了 Boosting方面的工作。本文对Boosting所涉及的若干重要理论问题进行了研究,主要取得了以下成果:(1)理论上给出了 Boosting的间隔分布泛化界,结束了 15年来关于Boost-ing 间隔 理论的 争论。 Boosting 的理论 研究中 最重要 的问题 是理解 AdaBoost为何不易陷入过拟合,为此,哥德尔奖得主Schapire等人在1998年提出间隔理论,然而权威统计学家Breiman在1999年对其质疑,此后15年间,关于间隔理论是否成立一直存在争论。本文通过证明新的经验Bernstein界,给出Boosting的间隔分布泛化界,从而有效支撑了 Boosting间隔理论。(2)提出了近似稳定性(approximation stability)这一理论概念,证明了Boosting的泛化性可通过近似稳定性有效刻画。稳定性可以有效刻画一般学习算法的泛化性,然而,传统的L1稳定性对Boosting失效。本文在理论上提出了近似稳定性,可用于刻画具有无穷VC维的学习模型,不仅解决了 Boosting难通过稳定性刻画的问题,还使稳定性理论框架得以发展,可用于更多类型的机器学习算法分析。(3)理论上给出了多标记学习一致性充要条件,揭示出Boosting对常见多标记准则不具有一致性,设计出具有一致性的替代函数。Boosting被认为是进行多标记学习的有效途径;然而,学习算法优化结果是否与真相一致,一直缺乏理论研究。本文证明了多标记学习一致性的充要条件,填补了理论研究的空白,在此基础上揭示出Boosting对常用多标记准则不具有一致性这个令人惊讶的事实。本文给出了具有一致性的替代函数,为设计新算法提供指导。(4)理论上给出了优化AUC学习一致性的必要条件和充分条件,在此基础上,证明了 RankBoost具有一致性并在一定条件下与AdaBoost等价。AUC是一种广为使用的机器学习评价准则,但优化AUC学习一致性尚缺理论研究。本文首先给出了优化AUC学习一致性的必要条件和充分条件,在此基础上,证明了 RankBoost对优化AUC具有一致性,以及RankBoost在合适的阈值下与AdaBoost 等价。(5)基于AUC一致性理论的启发,提出了 OPAUC算法,仅扫描一遍数据且只需常数级存储,即可进行AUC优化学习。AUC涉及正负样本间的两两比较,以往优化AUC学习方法需对数据进行多遍扫描、存储数据全集,这不适于大数据环境。本文提出了 OPAUC算法,只需扫描数据一遍且存储开销与数据量无关。实验结果表明,OPAUC算法在性能上明显优于在线AUC学习算法且效率更高,甚至与多遍扫描并存储数据全集的批学习算法性能相当。