提升方法AdaBoost
提升(boosting)方法是一种可以将弱学习器提升为强学习器的算法。在分类问题中，它通过改变训练样本的权重，使得先前学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器，并将这些分类器进行过线性组合，提高分类的性能。
提升方法AdaBoost算法
- 在每一轮如何改变训练数据的权值或概率分布
AdaBoost 提高那些被前一轮弱分类器错误分类的样本的权值，而降低那些被正确分类样本的权值。 - 如何将弱分类器组合成一个强分类器
AdaBoost采取加权多数表决的方法。加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。
AdaBoost算法
算法AdaBoost
输入：训练数据集T， <nobr> y∈(−1,1) </nobr>；弱学习算法
输出：最终分类器 <nobr> G(x) </nobr>
1. 初始化训练数据的权值分布
<nobr> D1=(w11,...,w1N),w1i=1N,i=1,...,N </nobr>
2. 对m=1，2，…,M
（a）使用具有权值分布 <nobr> Dm </nobr>的训练数据学习，得到基本分类器
<nobr> Gm(x):x→(−1,1) </nobr>
（b）计算 <nobr> Gm(x) </nobr>在训练集上的分类误差率
<nobr> em=∑i=1NP(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi) </nobr>
（c）计算 <nobr> Gm(x) </nobr>的系数
<nobr> am=12log1−emem(8.2) </nobr>
这里的对数是自然对数
（d）更新训练集的权值分布
这里， <nobr> Zm </nobr> 是规范化因子
<nobr> Zm=∑i=1Nwmiexp(−amyiGm(xi))(8.5) </nobr>
它使 <nobr> Dm+1 </nobr> 成为一个概率分布
3. 构建基分类器的线性组合
<nobr> f(x)=∑m=1NamGm(x) </nobr>
得到最终分类器
<nobr> G(x)=sign(f(x))=sign(∑m=1NamGm(x)) </nobr>
算法说明
<nobr> Gm(x) </nobr>在加权的训练数据集上的分类误差率是被 <nobr> Gm(x) </nobr>误分类样本的权值之和，由此可以看出数据权值分布 <nobr> Dm </nobr>与基本分类器 <nobr> Gm(x) </nobr>的分类误差率的关系。
由式(8.2)知，当 <nobr> em≤12 </nobr>时， <nobr> am≥0 </nobr>，并且 <nobr> am </nobr>随着 <nobr> em </nobr>的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
式(8.4)可以写成:
由此可知，被基分类器误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大 <nobr> e2am=1−emem </nobr> 倍。误分类样本在下一轮学习中起更大的作用。
不改变训练数据，不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。
最后线性组合 <nobr> f(x) </nobr> 实现了M个基分类器的加权表决。系数 <nobr> am </nobr> 之和并不为1。 <nobr> f(x) </nobr> 的符号决定实例x的类， <nobr> f(x) </nobr> 的绝对值表示分类的确信度。
利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。
AdaBoost算法的训练误差分析
定理8.1后半部分推导过程中第2个等号后出现的 <nobr> w1i </nobr>是因为在第一轮训练时，各个样本的权重均为 <nobr> 1N </nobr>。
上述定理说明，可以在每一轮选取适当的 <nobr> Gm </nobr>使得 <nobr> Zm </nobr>最小，从而使得训练误差下降最快。对二类分类问题，有如下结果。
最后一个不等式使用了 <nobr> 1−x≤e−x </nobr>
<nobr> Zm=(1−4γ2m)12≤(e−4γ2m)12=e−2γ2m </nobr>
所以
<nobr> ∏Mm=1Zm≤e−2∑Mm=1γ2m </nobr>
AdaBoost算法的解释
AdaBoost算法是模型为加法模型，损失函数为指数函数，学习算法为前向分布算法时的二类分类学习算法。
前向分步算法
考虑加法模型(additive model)
<nobr> f(x)=∑m=1Mβmb(x;γm) </nobr>
在给定训练数据和损失函数 <nobr> L(y,f(x)) </nobr>的条件下，学习加法模型 <nobr> f(x) </nobr>成为经验风险最小化及损失函数最小化问题:
<nobr> minβm,γm∑i=1NL(yi,∑m=1Mβmb(xi;γm)) </nobr>
前向分步算法(forward stagewise algorithm)求解这一优化问题的想法是：因为学习是加法模型，如果能够从前向后，每一步只学习一个 基函数及其系数，逐步逼近优化目标函数式(8.14)那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
<nobr> minβ,γ∑i=1NL(yi,βb(xi;γ)) </nobr>
前向分步算法与AdaBoost
参考资料
《统计学习方法》第8章
百威成长空间 50人发布
