Adaboost算法详解.pdfVIP

提升方法(boosting)详解 作者博客：@灵魂机器 /soulmachine 最后更新日期：2012-12-11 提升方法 （boosting ）是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过 改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。 本章首先介绍提升方法的思路和代表性的提升算法 AdaBoost ，然后通过训练误差分析探讨 AdaBoost 为什么能够提高学习精度，并且从前向分布加法模型的角度解释AdaBoost ，最后叙述提 升方法更具体的事例——提升术（boosting tree ）。AdaBoost 算法是1995 年由Freund 和Schapire 提 出的，提升树是2000 年由Friedman 等人提出的。 1 Adaboost 算法基本原理 1.1 提升方法的基本思路 提升方法是基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合 所得出的判断，要比其中任何一个专家单独的判断好。通俗点说，就是“三个臭皮匠顶个诸葛亮”。 Leslie Valiant 首先提出了 “强可学习（strongly learnable ）”和 “弱可学习（weakly learnable ）” 的概念，并且指出：在概率近似正确（probably approximately correct, PAC ）学习的框架中，一个概 念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念 是强可学习的，如果正确率不高，仅仅比随即猜测略好，那么就称这个概念是弱可学习的。2010 年的图灵奖给了L. Valiant ，以表彰他的PAC 理论。非常有趣的是Schapire 后来证明强可学习与弱 可学习是等价的，也就是说，在PAC 学习的框架下，一个概念是强可学习的充要条件是这个概念 是可学习的。 这样一来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升（boost ） 为 “强学习算法”。大家知道，发现弱学习算法通常比发现强学习算法容易得多。那么如何具体实 施提升，便成为开发提升方法时所要解决的问题。关于提升方法的研究很多，有很多算法被提出。 最具代表性的是AdaBoost 算法（Adaptive Boosting Algorithm ），可以说，AdaBoost 实现了PAC 的 理想。 对于分类问题而言，给定一个训练数据，求一个比较粗糙的分类器（即弱分类器）要比求一个 精确的分类器 （即强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列 弱分类器，然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的 概率分布（训练数据中的各个数据点的权值分布），调用弱学习算法得到一个弱分类器，再改变训 练数据的概率分布，再调用弱学习算法得到一个弱分类器，如此反复，得到一系列弱分类器。 这样，对于提升方法来说，有两个问题需要回答：一是在每一轮如何如何改变训练数据的概 率分布；而是如何将多个弱分类器组合成一个强分类器。 关于第一个问题，AdaBoost 的做法是，提高那些被前几轮弱分类器线性组成的分类器错误分 类的的样本的权值。这样一来，那些没有得到正确分类的数据，由于权值加大而受到后一轮的弱 分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第二个问题，AdaBoost 采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大 的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。 AdaBoost 的巧妙之处就在于它将这些想法自然而然且有效地实现在一种算法里。 1.2 AdaBoost 算法 n 输入：训练数据集T={(x ,y ),(x ,y ),…,(x ,y )} ，其中x ∈X⊆R ，表示输入数据，y ∈Y={-1,+1}， 1 1 2 2 N N i i 表示类