|
关于Adaboost，我以前推荐的是Ensemble Based Systems in Decision Making，在这个wiki中AdaBoost词条下的external links中就有，它没有给出为什么AdaBoost的推导，不过它本身是一篇很好的介绍，下面是Pattern Recognition and Machine Learning第14.3节中的介绍。 Boosting是一个将多个基分类器结合产生一个committee形式分类器的方法，它的分类效果会比任何单个基分类器要好的多。这里我们描述一个广泛使用的boosting算法AdaBoost，它是’adaptive boosting’的缩写(不能用汉语拼音的方法去读，其实这是一个很可怕的习惯)。Boosting可以在基分类器就比随机乱猜好一点的情况下，得到一个好的分类效果，所以有时基分类器被称为弱分类器(weak learners)。 Boosting与committee方法相比，比如bagging，主要区别在于，Boosting是基分类器是顺序学习的，并且每一个基分类器所训练的数据集样本是加权的，样本权重是由前面分类器的在该样本上的分类效果所决定的。特别是，被一个基分类器所分类错误的点会给更高的权重。当所有的分类器都训练好了，它们的预测是通过加权投票的方式结合起来，如图14.1所示。
考虑一个二分类问题，训练数据集由输入向量x1,…,x?N组成，每一个向量对应一个二值的目标值t1,…,tN。其中tN属于{-1, 1}。每个数据点给定一个相应的权重wn，所有的样本权重被初始化为1/N。假设我们有一个方法可以通过加权数据学习一个给定的函数y(x)，y(x)属于{-1,1}，训练一个基分类器。在算法的每一步，AdaBoost学习一个新的分类器，这个分类器通过上一次训练的分类器加权后的数据进行学习，加权是将错误的样本赋以更高的权重的过程。最后，当适合个数的基分类器被训练后，它们通过不同基分类器加以不同的权重的方法结合起来进行预测。AdaBoost的标准形式如下：
我们看到第一个基分类器y1(x)是通过全部相等的权重wn(1)训练的，它采用的是训练一个单分类器的标准过程。从14.18中我们可以看到随后的迭代中，对于分类错误的数据点增加权重系数w?n(m)，分类正确的数据点权重减小。随后的分类器所以被迫更关注于以前分类器分类错误的样本，随后分类器再分类错误的样本会被赋以更高的权重。量epsilonm表示每个基分类器错误率的一个度量方法。所以我们看到权重系数由14.17定义的alpham会对分类更准确的分类器赋以更高的权重，最后通过14.19将输出结果结合起来。 Adaboost算法示例在图14.2中，一个30个数据点的toy子数据集做为例子。这个简单的分类器对应决策树的一种形式称之为’decision stumps’，比如，一个决策树只有一个结点。所以每个基分类器分类一个与其对应的特征，当特征值超过了某个阈值，就把它分类成某个类别。也就是分类器只关心一个维，即与坐标轴平等的维。
下面是图14.2图注的翻译：boosting算法的一个例子，每一个基分类器包含x轴或是y轴坐标的阈值。每一幅图显示了当前有多少个基分类器已经训练了，还显示了最新训练的基分类器的决策边界(黑色的点线)和ensemble结合的决策边界。每一数据点由一个圈描述，它的半径表示当训练最新基分类器时，这个数据点的权重。所以，例如，我们看到由m=1基分类器分类错误的数据点在m=2基分类器学习时赋予更高的权重。
|
|
|
