文章目录
- 1. AdaBoost的思想
- 2. 数学定义和推导
- 2.1. 决策推理过程的输出表达式定义
- 2.2. 优化训练过程中的迭代表达式推导
- 2.3. 由迭代过程表达式得到的几个结论
- 2.3.1. 基学习器$G_M(x)$
- 2.3.3. 下一轮样本权重$w_i^{(M+1)}$
- 2.3.4. 各基学习器的系数$alpha_M$
- 3. Adaboost流程图
参考：
https://www.cnblogs.com/massquantity/p/9063033.html 1. AdaBoost的思想
回顾一下boosting的思想：将多个弱学习器“提升”为强学习器。AdaBoost也是基于此思想提出的，它的全称是Adaptive Boosting，即能够适应弱学习器的各自训练误差率。
它的流程可以概括为：先对每个样本赋予相同的初始权重，每一轮学习器训练后都会根据该学习器的表现对每个样本的权重进行调整，增加错分样本的权重，使得下一个学习器对错分样本有更多的关注度。最后对多个学习器进行加权求和。
以二分类为例，正类输出为+1，负类输出为-1.假设AdaBoost的学习过程得到了M个学习器
G
m
(
x
)
,
m
=
1
,
2
,
⋯
,
M
G_m(x),m=1,2,cdots,M
Gm(x),m=1,2,⋯,M,对于某个输入
x
x
x，对应的输出分别为
y
m
(
x
)
,
m
=
1
,
2
,
⋯
,
M
y_m(x),m=1,2,cdots,M
ym(x),m=1,2,⋯,M。则该算法的最终输出为：
Y
M
(
x
)
=
s
i
g
n
(
∑
m
=
1
M
α
m
y
m
(
x
)
)
(2-1)
Y_M(x)=sign(sum_{m=1}^{M}alpha_my_m(x))tag{2-1}
YM(x)=sign(m=1∑Mαmym(x))(2-1)
由上面的定义可以知道，AdaBoost算法得到的强学习器是多个弱学习期的线性组合：
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
(2-2)
f(x)=sum_{m=1}^{M}alpha_mG_m(x)tag{2-2}
f(x)=m=1∑MαmGm(x)(2-2)
记训练集为
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
⋯
,
(
x
N
,
y
N
)
(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)
(x1,y1),(x2,y2),⋯,(xN,yN).每一步的损失函数是固定的形式，记为
L
(
y
,
f
m
(
x
)
)
L(y,f_m(x))
L(y,fm(x))，则第M步时我们的优化目标是：
arg
min
(
α
m
,
G
m
)
∑
i
=
1
N
L
(
y
i
,
∑
m
=
1
M
α
m
G
m
(
x
)
)
(2-3)
argmin limits_{(alpha_m,G_m)}sum_{i=1}^NLleft(y_i,sum_{m=1}^Malpha_m G_m(x)right)tag{2-3}
arg(αm,Gm)mini=1∑NL(yi,m=1∑MαmGm(x))(2-3)
上式中需要优化的参数有M组（每一步的参数都要更新），实际求解比较复杂，我们可以简化一下，假设前M-1次迭代的系数
α
alpha
α和基学习器
G
(
x
)
G(x)
G(x)都是固定的，而
f
M
(
x
)
=
f
M
−
1
+
α
M
G
M
(
x
)
f_M(x)=f_{M-1}+alpha_MG_M(x)
fM(x)=fM−1+αMGM(x)，因此我们只需要优化
α
N
,
G
M
(
x
)
alpha_N,G_M(x)
αN,GM(x)即可。其实这里有点贪心算法的思想。
损失函数
L
(
y
,
f
m
(
x
)
)
L(y,f_m(x))
L(y,fm(x))的具体表达式一般采用指数损失函数：
L
(
y
,
f
m
(
x
)
)
=
e
−
y
f
(
x
)
(2-4)
L(y,f_m(x))=e^{-yf(x)}tag{2-4}
L(y,fm(x))=e−yf(x)(2-4)
因此优化目标为：
(
α
M
,
G
M
(
x
)
)
=
arg
min
(
α
,
G
)
∑
i
=
1
N
e
−
y
i
(
f
M
−
1
(
x
i
)
+
α
G
(
x
i
)
)
(2-5)
(alpha_M,G_M(x))=arg min limits_{(alpha,G)}sum_{i=1}^Ne^{-y_i(f_{M-1}(x_i)+alpha G(x_i))}tag{2-5}
(αM,GM(x))=arg(α,G)mini=1∑Ne−yi(fM−1(xi)+αG(xi))(2-5)
由于前M-1轮迭代的系数和基学习器与上述的
α
,
G
alpha,G
α,G无关，可以记
w
i
(
M
)
=
e
−
y
i
f
M
−
1
(
x
i
)
w_i^{(M)}=e^{-y_i f_{M-1}(x_i)}
wi(M)=e−yifM−1(xi),它代表了第M轮迭代前，每个样本被赋予的权重（其实是每个样本对应的损失函数的权重）。而且注意到，
w
i
(
M
)
w_i^{(M)}
wi(M)是会在每次迭代的时候更新的，第m次迭代的时候会更新第m+1次对应的权重。
于是乎，{2-5}中的目标函数可以化为：
∑
i
=
1
N
w
i
(
M
)
e
−
y
i
α
G
(
x
i
)
=
e
−
α
∑
y
i
=
G
(
x
i
)
w
i
(
M
)
+
e
α
∑
y
i
≠
G
(
x
i
)
w
i
(
M
)
=
(
e
α
−
e
−
α
)
∑
i
=
1
N
w
i
(
M
)
1
(
y
i
≠
G
(
x
i
)
)
+
e
−
α
∑
i
=
1
N
w
i
(
M
)
(2-6)
begin{aligned} sum_{i=1}^Nw_i^{(M)}e^{-y_ialpha G(x_i)}&=e^{-alpha}sum_{y_i=G(x_i)}w_i^{(M)}+e^{alpha}sum_{y_ineq G(x_i)}w_i^{(M)}\ &=(e^{alpha}-e^{-alpha})sum_{i=1}^Nw_i^{(M)}1_{(y_ineq G(x_i))}+e^{-alpha}sum_{i=1}^Nw_i^{(M)}\ tag{2-6} end{aligned}
i=1∑Nwi(M)e−yiαG(xi)=e−αyi=G(xi)∑wi(M)+eαyi=G(xi)∑wi(M)=(eα−e−α)i=1∑Nwi(M)1(yi=G(xi))+e−αi=1∑Nwi(M)(2-6)
由上一小节可以知道几个重要推论
2.3.1. 基学习器 G M ( x ) G_M(x) GM(x)使{2-6}最小化的 G ( x ) G(x) G(x)等价于使 ( e α − e − α ) ∑ i = 1 N w i ( M ) 1 ( y i ≠ G ( x i ) ) (e^{alpha}-e^{-alpha})sum_{i=1}^Nw_i^{(M)}1_{(y_ineq G(x_i))} (eα−e−α)∑i=1Nwi(M)1(yi=G(xi))最小化的 G ( x ) G(x) G(x)，也即每一轮的基学习器是通过最小化的带权重误差得到。
2.3.3. 下一轮样本权重 w i ( M + 1 ) w_i^{(M+1)} wi(M+1)w i ( M + 1 ) = e − y i f M ( x i ) = e − y i ( f M − 1 ( x i ) + α M G M ( x i ) ) = w i ( M ) e − y i α M G M ( x i ) w_i^{(M+1)}=e^{-y_i f_{M}(x_i)}=e^{-y_i (f_{M-1}(x_i)+alpha_MG_M(x_i))}=w_i^{(M)}e^{-y_ialpha_MG_M(x_i)} wi(M+1)=e−yifM(xi)=e−yi(fM−1(xi)+αMGM(xi))=wi(M)e−yiαMGM(xi)。可以看到，若 α M > 0 alpha_M>0 αM>0，则对于第M轮分正确的样本，下一轮的权重会减小；对于第M轮分错误的样本，下一轮的权重会增大。
2.3.4. 各基学习器的系数 α M alpha_M αM
G
M
(
x
)
G_M(x)
GM(x)在训练集上的加权误差率
ϵ
M
=
∑
i
=
1
N
w
i
(
M
)
1
(
y
i
≠
G
(
x
i
)
)
∑
i
=
1
N
w
i
(
M
)
epsilon_M=frac{sum_{i=1}^Nw_i^{(M)}1_{(y_ineq G(x_i))}}{sum_{i=1}^Nw_i^{(M)}}
ϵM=∑i=1Nwi(M)∑i=1Nwi(M)1(yi=G(xi)).而如果我们对{2-6}中的
α
alpha
α求偏导使其等于0，则有
−
e
−
α
∑
y
i
=
G
(
x
i
)
w
i
(
M
)
+
e
α
∑
y
i
≠
G
(
x
i
)
w
i
(
M
)
=
0
-e^{-alpha}sum_{y_i=G(x_i)}w_i^{(M)}+e^{alpha}sum_{y_ineq G(x_i)}w_i^{(M)}=0
−e−α∑yi=G(xi)wi(M)+eα∑yi=G(xi)wi(M)=0,两边乘
e
α
e^{alpha}
eα,得：
e
2
α
=
∑
y
i
=
G
(
x
i
)
w
i
(
M
)
∑
y
i
≠
G
(
x
i
)
w
i
(
M
)
=
1
−
ϵ
M
ϵ
M
e^{2alpha}=frac{sum_{y_i=G(x_i)}w_i^{(M)}}{sum_{y_ineq G(x_i)}w_i^{(M)}}=frac{1-epsilon_M}{epsilon_M}
e2α=∑yi=G(xi)wi(M)∑yi=G(xi)wi(M)=ϵM1−ϵM，从而有
α
M
=
1
2
l
n
1
−
ϵ
M
ϵ
M
alpha_M=frac{1}{2}lnfrac{1-epsilon_M}{epsilon_M}
αM=21lnϵM1−ϵM.
因此，准确率越高的基学习器会有越大的权重。
