Adaboost 算法简介
集成学习（ensemble learning）通过构建并结合多个学习器（learner）来完成学习任务，通常可获得比单一学习器更良好的泛化性能，特别是在集成弱学习器（weak learner）时。
集成学习两大类:
- 以bagging、Random Forest等算法为代表的，各个学习器之间相互独立、可同时生成的并行化方法；
- 以boosting、Adaboost等算法为代表的，个体学习器是串行序列化生成的、具有依赖关系，它试图不断增强单个学习器的学习能力。
算法详解
Adaboost步骤概览
- 初始化训练样本的权值分布，每个训练样本的权值相等（如果一共有N个样本，则每个样本的权值为1/N）
- 依次构造训练集并训练弱分类器。如果一个样本被准确分类，那么它的权值在下一个训练集中农会降低；相反，如果它分类错误，那么它在下一个训练集中的权值会提高。权值更新过后的训练集会用于训练下一个分类器。
- 训练好的弱分类器集成为一个强分类器集，误差率小的弱分类器会在最终的强分类器里占据更大的权重，否则较小。
Adaboost 算法流程
给定一个样本数量为m的数据集
T
=
{
(
x
1
,
y
1
)
,
…
,
(
x
m
,
y
m
)
}
T=\left \{\left(x_{1}, y_{1}\right), \ldots,\left(x_{m}, y_{m}\right) \right \}
T={(x1,y1),…,(xm,ym)}yi 属于标记集合{-1,+1}。
训练集的在第k个弱学习器的输出权重为
D
(
k
)
=
(
w
k
1
,
w
k
2
,
…
w
k
m
)
;
w
1
i
=
1
m
;
i
=
1
,
2
…
m
D(k)=\left(w_{k 1}, w_{k 2}, \ldots w_{k m}\right) ; \quad w_{1 i}=\frac{1}{m} ; i=1,2 \ldots m
D(k)=(wk1,wk2,…wkm);w1i=m1;i=1,2…m
① 初始化训练样本的权值分布，每个训练样本的权值相同：
D
(
1
)
=
(
w
11
,
w
12
,
…
w
1
m
)
;
w
1
i
=
1
m
;
i
=
1
,
2
…
m
D(1)=\left(w_{1 1}, w_{1 2}, \ldots w_{1 m}\right) ; \quad w_{1 i}=\frac{1}{m} ; i=1,2 \ldots m
D(1)=(w11,w12,…w1m);w1i=m1;i=1,2…m
② 进行多轮迭代，产生T个弱分类器。
for t = 1, … , T :
a. 使用权值分布 D(t) 的训练集进行训练，得到一个弱分类器
G
t
(
x
)
:
χ
→
{
−
1
,
+
1
}
G_{t}(x) : \quad \chi \rightarrow\{-1,+1\}
Gt(x):χ→{−1,+1} b. 计算 Gt(x) 在训练数据集上的分类误差率（其实就是被 Gt(x) 误分类样本的权值之和）:
e
t
=
P
(
G
t
(
x
i
)
≠
y
i
)
=
∑
i
=
1
m
w
t
i
I
(
G
t
(
x
i
)
≠
y
i
)
e_{t}=P\left(G_{t}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{m} w_{t i} I\left(G_{t}\left(x_{i}\right) \neq y_{i}\right)
et=P(Gt(xi)̸=yi)=i=1∑mwtiI(Gt(xi)̸=yi)
c. 计算弱分类器 Gt(x) 在最终分类器中的系数(即所占权重)
α
t
=
1
2
ln
1
−
e
t
e
t
\alpha_{t}=\frac{1}{2} \ln \frac{1-e_{t}}{e_{t}}
αt=21lnet1−et d. 更新训练数据集的权值分布，用于下一轮（t+1）迭代
D
(
t
+
1
)
=
(
w
t
+
1
,
1
,
w
t
+
1
,
2
,
⋯
w
t
+
1
,
i
⋯
 
,
w
t
+
1
,
m
)
D(t+1)=\left(w_{t+1,1} ,w_{t+1,2} ,\cdots w_{t+1, i} \cdots, w_{t+1, m}\right)
D(t+1)=(wt+1,1,wt+1,2,⋯wt+1,i⋯,wt+1,m)
for i = 1, … , m :
w
t
+
1
,
i
=
w
t
,
i
Z
t
×
{
e
−
α
t
（
i
f
G
t
(
x
i
)
=
y
i
）
e
α
t
（
i
f
G
t
(
x
i
)
≠
y
i
）
=
w
t
,
i
Z
t
exp
(
−
α
t
y
i
G
t
(
x
i
)
)
w_{t+1,i}=\frac{w_{t,i}}{Z_{t}} \times \left\{\begin{array}{ll}{e^{-\alpha_{t}}} & {\text （{ if } G_{t}\left(x_{i}\right)=y_{i}}） \\ {e^{\alpha_{t}}} & {\text （{ if } G_{t}\left(x_{i}\right) \neq y_{i}}）\end{array}\right. = \frac{w_{t,i}}{Z_{t}} \exp \left(-\alpha_{t} y_{i} G_{t}\left(x_{i}\right)\right)
wt+1,i=Ztwt,i×{e−αteαt（ifGt(xi)=yi）（ifGt(xi)̸=yi）=Ztwt,iexp(−αtyiGt(xi))
其中 Zt是规范化因子，使得D(t+1)成为一个概率分布（和为1）
Z
t
=
∑
j
=
1
m
w
t
,
i
exp
(
−
α
t
y
i
G
t
(
x
i
)
)
Z_{t}=\sum_{j=1}^{m} w_{t,i} \exp \left(-\alpha_{t} y_{i} G_{t}\left(x_{i}\right)\right)
Zt=j=1∑mwt,iexp(−αtyiGt(xi))
③ 集成T个弱分类器为1个最终的强分类器：
G
(
x
)
=
sign
(
∑
t
=
1
T
α
t
G
t
(
x
)
)
G(x)=\operatorname{sign}\left(\sum_{t=1}^{T} \alpha_{t} G_{t}(x)\right)
G(x)=sign(t=1∑TαtGt(x))
算法十问
1.Adaboost分类模型的学习器的权重系数
α
\alpha
α怎么计算的？
Adaboost是前向分步加法算法的特例，分类问题的时候认为损失函数指数函数.
- 当基函数是分类器时，Adaboost的最终分类器是：
f
(
x
)
=
∑
m
−
1
M
α
m
G
m
(
x
)
=
f
m
−
1
(
x
)
+
α
m
G
m
(
x
)
f(x)=\sum_{m-1}^{M}{\alpha_mG_m(x)}=f_{m-1}(x)+{\alpha_mG_m(x)}
f(x)=m−1∑MαmGm(x)=fm−1(x)+αmGm(x)
- 目标是使前向分步算法得到的
α
\alpha
α和
G
m
(
x
)
G_m(x)
Gm(x)使
f
m
(
x
)
f_m(x)
fm(x)在训练数据集T上的指数损失函数最小，即
(
α
,
G
m
(
x
)
)
=
a
r
g
m
i
n
α
,
G
∑
i
=
1
N
e
x
p
[
−
y
i
(
f
m
−
1
(
x
i
)
+
α
G
(
x
i
)
)
]
(\alpha, G_m(x))=arg min_{\alpha, G}\sum_{i=1}^{N}exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))]
(α,Gm(x))=argminα,Gi=1∑Nexp[−yi(fm−1(xi)+αG(xi))] 其中，
w
^
m
i
=
e
x
p
[
−
y
i
f
m
−
1
(
x
i
)
]
.
\hat{w}{mi}=exp[-y_i f{m-1}(x_i)].
w^mi=exp[−yifm−1(xi)].为了求上式的最小化，首先计算
G
m
(
x
)
G_m(x)
Gm(x),对于任意的
α
>
0
\alpha>0
α>0,可以转化为下式：
G
m
=
a
r
g
m
i
n
G
∑
i
=
1
N
w
^
m
i
I
(
y
i
≠
G
(
x
i
)
)
G_{m}=argmin_{G}\sum_{i=1}^{N}\hat{w}{mi}I(y_i \neq G(x_i))
Gm=argminGi=1∑Nw^miI(yi̸=G(xi)) 之后求
α
m
∗
\alpha_m^*
αm∗,将上述式子化简，得到
∑
i
=
1
N
w
^
m
i
e
x
p
[
−
y
i
α
G
(
x
i
)
]
=
∑
y
i
=
G
m
(
x
i
)
w
^
m
i
e
−
α
+
∑
y
i
≠
G
m
(
x
i
)
w
^
m
i
e
α
=
(
e
α
−
e
−
α
)
∑
i
=
1
N
w
^
m
i
I
(
y
i
≠
G
(
x
i
)
)
+
e
−
α
∑
i
=
1
N
w
^
m
i
\sum{i=1}^{N}\hat{w}{mi}exp[-y_i \alpha G(x_i)] = \sum{y_i =G_m(x_i)}\hat{w}{mi}e^{-\alpha}+\sum{y_i \neq G_m(x_i)}{\hat{w}{mi}e^{\alpha}} = (e^{\alpha} - e^{- \alpha})\sum{i=1}^{N}\hat{w}{mi}I(y_i \neq G(x_i)) + e^{- \alpha}\sum{i=1}^{N}\hat{w}{mi}
∑i=1Nw^miexp[−yiαG(xi)]=∑yi=Gm(xi)w^mie−α+∑yi̸=Gm(xi)w^mieα=(eα−e−α)∑i=1Nw^miI(yi̸=G(xi))+e−α∑i=1Nw^mi 将已经求得的
G
m
(
x
)
G_m(x)
Gm(x)带入上式面，对
α
\alpha
α求导并等于0，得到最优的
α
\alpha
α.
a
m
=
1
2
l
o
g
1
−
e
m
e
m
a_m=\frac{1}{2} log{\frac{1-e_m}{e_m}}
am=21logem1−em 其中
e
m
e_m
em是分类误差率:
e
m
=
∑
i
=
1
N
w
^
m
i
I
(
y
i
≠
G
m
(
x
i
)
)
∑
i
=
1
N
w
^
m
i
=
∑
i
=
1
N
w
^
m
i
I
(
y
i
≠
G
m
(
x
i
)
)
e_m=\frac{\sum{i=1}^{N}\hat{w}{mi}I(y_i \neq G_m(x_i))}{\sum{i=1}^{N}\hat{w}{mi}}=\sum{i=1}^{N}\hat{w}_{mi}I(y_i \neq G_m(x_i))
em=∑i=1Nw^mi∑i=1Nw^miI(yi̸=Gm(xi))=∑i=1Nw^miI(yi̸=Gm(xi))
2.Adaboost能否做回归问题？
Adaboost也能够应用到回归问题，相应的算法如下: 输入:
T
=
(
x
i
,
y
1
)
,
(
x
i
,
y
1
)
,
.
.
.
,
(
x
N
,
y
N
)
T={(x_i, y_1),(x_i, y_1),...,(x_N, y_N)}
T=(xi,y1),(xi,y1),...,(xN,yN), 弱学习器迭代次数M。 输出：强分类器f(x).
- 初始化权重，
D
(
1
)
=
w
11
,
w
12
,
.
.
.
,
w
1
N
;
w
1
i
=
1
N
;
i
=
1
,
2
,
.
.
,
N
D(1)={w_{11},w_{12},...,w_{1N}}; w_{1i}=\frac{1}{N}; i=1,2,..,N
D(1)=w11,w12,...,w1N;w1i=N1;i=1,2,..,N
- 根据m=1,2,…,M;
- 学习得到
G
m
(
x
)
G_m(x)
Gm(x)
- 计算训练集上最大误差
E
m
=
m
a
x
∣
y
i
−
G
m
(
x
i
)
∣
,
i
=
1
,
2
,
.
.
,
N
E_m=max|y_i-G_m(x_i)|, i=1,2,..,N
Em=max∣yi−Gm(xi)∣,i=1,2,..,N
- 计算样本的相对平方误差:
e
m
i
=
(
y
i
−
G
m
(
x
i
)
)
2
E
m
2
e_{mi}=\frac{(y_i-G_m(x_i))^2}{E_m^2}
emi=Em2(yi−Gm(xi))2
- 计算回归误差率:
e
m
=
∑
i
=
1
N
w
m
i
e
m
i
e_m=\sum_{i=1}^{N}w_{mi}e_{mi}
em=∑i=1Nwmiemi
- 计算若学习器系数:
α
m
=
e
m
1
−
e
m
\alpha_m=\frac{e_m}{1-e_m}
αm=1−emem
- 更新样本权重：
w
m
+
1
,
i
=
w
m
i
Z
m
α
m
1
−
e
m
,
i
w_{m+1,i}=\frac{w_{mi}}{Z_m}{\alpha_{m}^{1-e^{m,i}}}
wm+1,i=Zmwmiαm1−em,i 其中
Z
m
Z_m
Zm是规范化因子，
Z
m
=
∑
i
=
1
m
w
m
i
α
m
1
−
e
m
,
i
Z_m=\sum_{i=1}^{m}w_{mi}{\alpha_{m}^{1-e^{m,i}}}
Zm=i=1∑mwmiαm1−em,i
- 得到强学习器：
f
(
x
)
=
∑
m
=
1
M
G
m
∗
(
x
)
f(x)=\sum_{m=1}{M}G_{m}^*(x)
f(x)=m=1∑MGm∗(x)
注: 不管是分类问题还是回归问题，根据误差改变权重就是Adaboost的本质，可以基于这个构建相应的强学习器。
3.boosting和bagging之间的区别,从偏差-方差的角度解释Adaboost？
集成学习提高学习精度，降低模型误差，模型的误差来自于方差和偏差，其中bagging方式是降低模型方差，一般选择多个相差较大的模型进行bagging。boosting是主要是通过降低模型的偏差来降低模型的误差。其中Adaboost每一轮通过误差来改变数据的分布，使偏差减小。
4.为什么Adaboost方式能够提高整体模型的学习精度？
根据前向分布加法模型，Adaboost算法每一次都会降低整体的误差，虽然单个模型误差会有波动，但是整体的误差却在降低，整体模型复杂度在提高。
5.Adaboost算法如何加入正则项?
f
m
(
x
)
=
f
m
−
1
(
x
)
+
η
α
m
G
m
(
x
)
f_m(x)=f_{m-1}(x)+\eta \alpha_{m}G_{m}(x)
fm(x)=fm−1(x)+ηαmGm(x)
6.Adaboost使用m个基学习器和加权平均使用m个学习器之间有什么不同？
Adaboost的m个基学习器是有顺序关系的，第k个基学习器根据前k-1个学习器得到的误差更新数据分布，再进行学习，每一次的数据分布都不同，是使用同一个学习器在不同的数据分布上进行学习。加权平均的m个学习器是可以并行处理的，在同一个数据分布上，学习得到m个不同的学习器进行加权。
7.adabosot和gbdt之间的区别和相同？
Adaboost和gbdt都是通过减低偏差提高模型精度，都是前项分布加法模型的一种，不同的是，Adaboost每一个根据前m-1个模型的误差更新当前数据集的权重，学习第m个学习器；gbdt是根据前m-1个的学习剩下的label的偏差，修改当前数据的label进行学习第m个学习器，一般使用梯度的负方向替代偏差进行计算。
8.adaboost的迭代次数(基学习器的个数)如何控制？
一般使用earlystopping进行控制迭代次数。
9.adaboost算法中基学习器是否很重要，应该怎么选择基学习器？
sklearn中的adaboost接口给出的是使用决策树作为基分类器，一般认为决策树表现良好，其实可以根据数据的分布选择对应的分类器，比如选择简单的逻辑回归，或者对于回归问题选择线性回归。
10.MultiBoosting算法将Adaboost作为Bagging的基学习器，Iterative Bagging将Bagging作为Adaboost的基学习器。比较两者的优缺点？
两个模型都是降低方差和偏差。主要的不同的是顺序不同。MultiBosoting先减低模型的偏差再减低模型的方差，这样的方式 MultiBoosting由于集合了Bagging Wagging， AdaBoost，可以有效的降低误差和方差，特别是误差。但是训练成本和预测成本都会显著增加。 Iterative Bagging相比Bagging会降低误差，但是方差上升。由于Bagging本身就是一种降低方差的算法，所以Iterative Bagging相当于Bagging与单分类器的折中。
面试真题
1.分类器的权重系数α实际上是通过最小化指数损失函数的得到的，如果想了解 α 的 推导过程可以参考 Schapire 论文原文或者周志华《机器学习》8.2节内容。
2.对于无法接受带权样本的基学习算法，可以通过重采样resampling来产生训练集，这也是为什么之前说Adaboost可以理解为基于概率分布来选取样本。拿上面的例子来说，详细做法是：10个样本中每个样本被抽中的概率是Pi（i=1,…,10），现在按抽取概率连续做10次可放回的样本抽取，得到训练集即可训练出一个分类器。
3.adaboost的灵魂在于其样本权重更新（样本权重模拟了概率分布）的方法 以及 弱分类器加权组合。
4.Adaboost 的权值更新方法。
参考上面的算法介绍。
5.训练过程中，每轮训练一直存在分类错误的问题，整个Adaboost却能快速收敛，为何？
每轮训练结束后，AdaBoost 会对样本的权重进行调整，调整的结果是越到后面被错误分类的样本权重会越高。而后面的分类器为了达到较低的带权分类误差，会把样本权重高的样本分类正确。这样造成的结果是，虽然每个弱分类器可能都有分错的样本，然而整个 AdaBoost 却能保证对每个样本进行正确分类，从而实现快速收敛。
6.Adaboost 的优缺点？
优点：能够基于泛化性能相当弱的的学习器构建出很强的集成，不容易发生过拟合。
缺点：对异常样本比较敏感，异常样本在迭代过程中会获得较高的权值，影响最终学习器的性能表现。
7.AdaBoost 与 GBDT 对比有什么不同？
区别在于两者boosting的策略：Adaboost通过不断修改权重、不断加入弱分类器进行boosting；GBDT通过不断在负梯度方向上加入新的树进行boosting。
参考资料
- 台湾清华大学李端兴教授2017年秋机器学习概论课程(CS 4602)PPT
- 周志华 《机器学习》第8章 集成学习
- July的博客
- http://fornlp.com/周志华-《机器学习》-答案整理
