集成学习（二）：Adaboost

Adaboost 是 Boosting 族算法的代表。这篇文章将介绍一下 Adaboost 算法。

• 训练数据 T=(x1,y1),(x2,y2),⋯,(xN,yN)T=(x1,y1),(x2,y2),⋯,(xN,yN)
• 假设 χχ 是实例空间
• 假设 γγ 是标记集合
• xi∈χ⊆Rnxi∈χ⊆Rn
• yi∈γ=−1,+1yi∈γ=−1,+1

Adaboost 算法执行过程归纳

1. 初始化训练集中每个样本的权重值为 1N1N
2. 迭代 M 次，每次迭代都会生成一个基学习器，首先要检查当前生成的基学习器是否满足基本条件（基学习器在训练数据集上的加权错误率是否小于 0.5）
   (1)如果不满足上述基本条件，则当前基学习器被抛弃且学习过程停止。
   (2)如果满足上述基本条件，那么根据当前基分类器的加权错误率调整训练数据集中样本的权值分布（增加分类错误的样本的权重，减少分类正确的样本的权重）。
3. 将所有的基学习器加权组合得到最终的分类器。

展开描述算法执行过程

假设算法共计迭代 MM 次，当前迭代次数为第 mm 次，对于 m=1,2,⋯,Mm=1,2,⋯,M，使用 DmDm 代表第 mm 次迭代的训练集的权值分布，使用 Gm(x)Gm(x) 代表第 mm 次迭代得到的基分类器。
训练集初始的权值分布为：
D1=(w11,⋯,w1i,⋯,w1N),,w1i=1N,,i=1,2,3,⋯,ND1=(w11,⋯,w1i,⋯,w1N),,w1i=1N,,i=1,2,3,⋯,N
第 mm 次迭代的错误率计算方式如下，其中 wmiwmi 是第 mm 次迭代中，第 ii 个样本的权重，I(⋅)I(⋅) 为指示函数，可以看出这里计算的错误率实际上是对被分错的样本的一个加权错误率：
em=P(Gm(xi)≠yi)=N∑i=1wmiI(Gm(xi)≠yi)em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)
第 mm 次迭代为 Gm(x)Gm(x) 分配的权重为：
αm=12log1−ememαm=12log1−emem
这里我们可以发现当 em=12em=12 时，αm=0αm=0，也就相当于这个基分类器被抛弃了，所以当发生这种情况时，当前基分类器被抛弃并且整个训练过程停止。当 em<12em<12 的情况与此类似。另外，αmαm 同样是第 mm 个分类器的权重，描述了第 mm 个分类器在最终分类器中的作用有多大。
当 em>12em>12 时，更新第 m+1m+1 次迭代时对应的数据集的权重分布：
Dm+1=(wm+1,1,wm+1,w,⋯,wm+1,N) wm+1,i=wm,iZmexp(−αmyiGm(xi)) Zm=N∑i=1wmiexp(−αmyiGm(xi))Dm+1=(wm+1,1,wm+1,w,⋯,wm+1,N)wm+1,i=wm,iZmexp(−αmyiGm(xi))Zm=∑i=1Nwmiexp(−αmyiGm(xi))
其中 ZmZm 的作用就是让 Dm+1Dm+1 所有元素的和为 1。并且容易看出来当 Gm(xi)≠yiGm(xi)≠yi 时，也就是当前基分类器分类错误的时候，yiGm(xi)=−1yiGm(xi)=−1，此时：
wm+1,i=wm,iZmexp(αm)wm+1,i=wm,iZmexp(αm)
可以发现，被分错的样本的权重会增大，同理可以推出被分错的样本的权重会减小。
最后，我们就可以将各个分类器进行线性组合得到最终的分类器了：
f(x)=M∑m=1αmGm(x) G(x)=sign(f(x))=sign(M∑m=1αmGm(x))f(x)=∑m=1MαmGm(x)G(x)=sign(f(x))=sign(∑m=1MαmGm(x))

Adaboost 的训练过程是一个加权训练的过程。因为其选择当前最优基分类器时，选择的是加权错误率最低的模型。从偏差-方差分解的角度看，Boosting 主要关注降低偏差。

1. 《机器学习》 —— 周志华
2. 《统计学习方法》 —— 李航

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]