AdaBoost详解
本博客内容摘自李航老师的《统计学习方法》,加以一些整理。
相关概念
提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。
对于分类问题而言,给定一个训练集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多。提升(booting)方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
所以对于提升方法而言,有两个问题需要解决:一是在每一轮如何改变训练数据的权值或者概率分布;二是如何将弱分类器组合成一个强分类器。
对于第一个问题,AdaBoost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而受到后一轮的弱分类器的更大关注。于是,分类问题被一系列的弱分类器”分而治之”。
对于第二个问题,即弱分类器的组合,AdaBoost采取加权多数表决的方法。具体地,加大分类错误率小的弱分类器的权重,使其在表决中起较大的作用,减少分类误差率大的弱分类器的权值,使其在表决中起较小的作用。
AdaBoost算法
假定给定一个二分类的训练数据集:
其中,每个样本点由实力和标记组成。实例(表示实数),标记,即有两种标签的数据,用来表示这两种类别;是实例空间,是标记集合。AdaBoost算法利用以下算法,从训练数据中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成一个强分类器。
AdaBoost描述:
输入:训练数据集,其中;得到弱学习算法;
输出:最终分类器
算法步骤:
(1)初始化训练数据的权值分布
D是用来描述各样本的权值分布的。
(2)对,表示迭代的次数
(a)使用具有权值分布的训练数据集学习,得到基本分类器:
(b)计算在训练数据集上的分类误差率
其中,当分类正确时,等于0;分类错误时,等于1;表示第轮得到的弱分类器对第个样本的分类结果,表示第个样本的真实类别。注意计算误差率是用到了权重分布中的。
(c) 计算的系数
这里的对数是自然对数。可以发现,当错误率越大时,越小。这个参数将会用在集成阶段。
(d)更新训练数据集的权值分布
这里,是规范化因子,使得总的值和为1.
它使得成为一个概率分布。
(3)构建基本分类器的线性组合
错误率越低的弱分类器对应的值越大,使其在表决中起较大的作用。
得到最终的分类器
对AdaBoost算法作如下说明:
步骤(1)假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类器的学习中作用相同,这一假设保证第1步能够在原始数据上学习基本分类器.
步骤(2)AdaBoost反复学习基本分类器,在每一轮顺次地执行下列操作:
(a)使用当前分布加权的训练数据集,学习基本分类器.
(b)计算基本分类器在加权训练数据集上的分类错误率:
这里,表示第轮中第个实例的权值,.这表明,在加权的训练数据集上的分类错误率是被误分类样本的权值之和,由此可以看出数据权值分布与基本分类器的分类错误率的关系。
(c)计算基本分类器的系数表示在最终的分类器中的重要性。由式子(2.3)可知,当时,,并且伴随着的减小而增大,所以分类误差率越小的基本分类器在最终分类器中的作用越大。
(d)更新训练数据的权值分布,为下一轮作准备。式子(2.5)可以写成:
由此可知,被基本分类器误分类样本的权值得以扩大,而被正确分类样本的权值却得以缩小。二者比较,误分类样本的权值被放大倍.因此,误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据,而不断改变训练数据的权值分布,使得训练数据在基本分类器的学习中起不同的作用,这是AdaBoost的一个特点。
步骤(3)线性组合实现了个基本分类器的加权表决。系数表示了基本分类器的重要性,这里,所有之和并不为1.的符号决定实例的类,的绝对值表示分类的确信度,利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。
参考例子
注意,权值分布是在计算错误率时起作用,公式(2.2)中。