AdaBoost

Boosting

Boosting 是指，仅通过训练精度比随机猜想（50%）稍高的学习器，通过集成的方式过建出强学习器。

其中boosting中最有名的是AdaBoost算法。AdaBoost是英文"Adaptive Boosting"（自适应增强）的缩写，它的自适应在于：前一个基本分类器被错误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数才确定最终的强分类器。

AdaBoost 推导

设存在数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } T=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots,\left(x_N,y_N\right)\right\} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)} ，其中 x i ∈ X ⊆ R n , y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , ⋯   , N ; x_i\in\mathcal{X}\subseteq R^n,y_i\in\mathcal{Y}=\left\{+1,-1\right\},i=1,2,\cdots,N\text{;} xi​∈X⊆Rn,yi​∈Y={+1,−1},i=1,2,⋯,N;

考虑二分类问题

因为AdaBoost算法最终得到的学习器是由多个弱学习器集成而来的，由此设
F ( x ) = ∑ k = 1 K α k ϕ ( x ; θ k ) ϕ ( x ; θ k ) ∈ { − 1 , 1 } F(\boldsymbol{x})=\sum_{k=1}^{K}\alpha_{k}\phi(\boldsymbol{x};\boldsymbol{\theta}_{k})\\ \phi(\boldsymbol{x};\boldsymbol{\theta}_{k})\in\{-1,1\} F(x)=k=1∑K​αk​ϕ(x;θk​)ϕ(x;θk​)∈{−1,1}
其中 ${\theta }_k$为参数向量，代表第k个学习器的参数， ${\alpha }_k$为第k个学习器的权重，表示在最终学习器中第k个学习器在其中的权重。

其中最终决策为
f ( x ) = s i g n { F ( x ) } f(\boldsymbol{x})=sign\{F(x)\} f(x)=sign{F(x)}
当正确分类时，存在 $y_{i}F(x_i)>0,-y_{i}F(x_i)<0$

当错误分类时，存在 $y_{i}F(x_i)<0,-y_{i}F(x_i)>0$

其中AdaBoost分类的目标就是尽可能的正确分类，即最大限度时，错分的样本数目最少，由此构建目标函数
$$\arg \underset{{\alpha }_k,{\theta }_k,k:\mathrm{1...},K}{\min }\sum _{i=1}^N\exp (-y_{i}F(x_i))$$
其中在AdaBoost推导过程中，设 $F_m(x)$为前m个分类器的集成结果，即
$$F_m(x)=\sum _{k=1}^m{\alpha }_k\varphi (x;{\theta }_k),m=1,2,...,K$$
若写为增量表示，则为
$$F_m(x)=F_{m-1}(x)+{\alpha }_m\varphi (x;{\theta }_m)$$
即前m个分类器集成的结果为前m-1个分类器集成的结果加上第m个分类器的结果 $\times$ 权重

由此前m个分类器的目标函数为
$$\begin{array}{rl}& J(\alpha ,\theta )=\sum _{i=1}^N\exp (-y_i(F_{m-1}(x)+\alpha \varphi (x;\theta )))\\ & \\ & ({\alpha }_m,{\theta }_m)=\arg \underset{\alpha ,\theta }{\min }J(\alpha ,\theta )\end{array}$$
令 $w_i^{(m)}$为前$m-1$个分类器对$x_i$对错分指数，易知这与第m个分类器的 $\alpha ,\theta$无关。即
$$w_i^{(m)}\equiv \exp (-y_i{F}_{m-1}(x_i))$$
所以前m个分类器的目标函数可以写为
$$J(\alpha ,\mathbf{\theta })=\sum _{i=1}^N{w}_i^{(m)}\exp (-y_i\alpha \varphi (\mathbf{x};\mathbf{\theta }))$$
由此我们选择的参数 ${\theta }_m$ 应是使得目标函数最小的，即错分的样本最少
$$\begin{array}{rl}{\mathbf{\theta }}_m& =\arg \underset{\theta }{\min }\sum _{i=1}^N{w}_i^{(m)}\exp (-y_i\alpha \varphi (x;\theta ))\\ {\mathbf{\theta }}_m& =\arg \underset{\theta }{\min }\left\{P_m=\sum _{i=1}^N{w}_i^{(m)}I(1-y_i\varphi (\mathbf{x};\mathbf{\theta }))\right\}\end{array}$$
其中：

$I(1-y_i\varphi (\mathbf{x};\mathbf{\theta }))$是一个非0即1的函数，当 $1-y_i\varphi (\mathbf{x};\mathbf{\theta })=0$是函数 $I(1-y_i\varphi (\mathbf{x};\mathbf{\theta }))=0$，即正确分类时，函数 $I(1-y_i\varphi (\mathbf{x};\mathbf{\theta }))$为0，当错误分类时，函数 $I(1-y_i\varphi (\mathbf{x};\mathbf{\theta })=1$；

$P_m$为第m个分类器错误识别样本的平均权重。求 $\theta$通常在选择第m个分类器时候,选择阈值 $P_m<0.5$

所以优化目标可以改为：优化第m个分类器，使得错分样本对应的平均权重最小，即在第m个分类器的正确分类样本，尽可能时前m-1个分类器中错分指数大的样本即 $w_i^{(m)}$ 大，求 ${\theta }_m$。即可认为在集成过程中使得对 $x_i$分类错误的学习器的$w_i^{(m)}$小，使得最终的学习器受到错分的影响最小。
$$J(\alpha ,\theta )=\sum _{i=1}^N{w}_i^{(m)}\exp (-y_i\alpha \varphi (x;\theta ))$$
因为
$$\begin{array}{rl}\sum _{y_i\varphi (x_i;{\theta }_m)<0}{w}_i^{(m)}=& P_m,y_i\varphi (x_i;{\theta }_m)=-1\\ \sum _{y_i\varphi (x_i;{\theta }_m)>0}{w}_i^{(m)}=& 1-P_m,y_i\varphi (x_i;{\theta }_m)=1\end{array}$$
所以
α m = arg ⁡ min ⁡ α { exp ⁡ ( − α ) ( 1 − P m ) + exp ⁡ ( α ) P m } \alpha_{m}=\arg\min_{\alpha}\{\exp(-\alpha)(1-P_{m})+\exp(\alpha)P_{m}\} αm​=argαmin​{exp(−α)(1−Pm​)+exp(α)Pm​}
由此设存在函数：
$$f(a)=\exp (-\alpha )(1-P_m)+\exp (\alpha )P_m$$
对其求导数得到
$$\begin{array}{r}{f}^{\prime }(\alpha )=P_m\exp (\alpha )-(1-P_m)\exp (-\alpha )\end{array}$$
令 $f^{\prime }(\alpha )=0$得到 $f(\alpha )$的取最小值时的 $\alpha$ 即 ${\alpha }_m$
$${\alpha }_m=\frac{1}{2}\ln \frac{1-P_m}{P_m}$$
由此更新权重
$$w_i^{(m+1)}\equiv \exp (-y_i{F}_m({\mathbf{x}}_i))=w_i^{(m)}\exp (-y_i{\alpha }_m\varphi ({\mathbf{x}}_i;{\mathbf{\theta }}_m))$$
将 ${\alpha }_m=\frac{1}{2}\ln \frac{1-P_m}{P_m}$代入可得:

被第m个分类器正确分类的样本权值为：
$$y_i\varphi (x_i;{\theta }_m)=1,w_i^{(m+1)}=w_i^{(m)}\exp \left(-{\alpha }_m\right)=w_i^{(m)}\sqrt{\frac{P_m}{1-P_m}}$$
被第m个分类器错误分类的样本权值为：
$$\begin{array}{rl}{y}_i\varphi (x_i;{\theta }_m)=& -1,u_i^{(m+1)}=w_i^{(m)}\exp \left({\alpha }_m\right)=w_i^{(m)}\sqrt{\frac{1-P_m}{P_m}}\end{array}$$
归一化：
$$w_i^{(m+1)}=w_i^{(m+1)}/\sum _{i=1}^N{w}_i^{(m+1)}$$

示例

当存在10个样本如图所示

首先初始化各分类器的权重
$$D_1=\left(w_{11},w_{12},\cdots ,w_{1N}\right),w_{1i}=\frac{1}{N},i=1,2,\cdots ,N$$
可得：$\text{аll }{x}_i\text{,}{w}_{\mathrm{i}}^{(0)}=0.1$

然后对其使用 $h_1$分类器，分类结果如图所示

易知有三个样本被错误分类

其中正确分类的样本权值不变，错误分类的样本权值为：

$$w_i^{(m+1)}=w_i^{(m)}\frac{1-P_m}{P_m}$$
其中
$$P_m=\sum _{i=1}^N{w}_i^{(m)}I(1-y_i\varphi (\mathbf{x};\mathbf{\theta }))$$
即被错分的样本乘上平均错分权重
$${\alpha }_m=\frac{1}{2}\ln \frac{1-P_m}{P_m}$$
得到
$$\begin{array}{rl}{P}_1& =N_F{w}^{(0)}=0.3\\ 1-P_1& =0.7\\ {\alpha }_1& =\frac{1}{2}\ln (\frac{1-P_1}{P_1})=\frac{1}{2}\ln (\frac{1-0.3}{0.3})=0.42\\ w_i^{(1)}& =w^{(0)}=0.1\text{正确分类不变 }\\ w_i^{(1)}& =w^{(0)}\frac{1-P_1}{P_1}=0.233\text{错误分类}\end{array}$$
对其$w^{(1)}$进行归一化处理
$$\begin{array}{r}{w}_i^{(1)}=\frac{0.1}{0.1\ast 7+0.233\ast 3}\text{1被正确分类}\\ w_i^{(1)}=\frac{0.233}{0.1\ast 7+0.233\ast 3}\text{1被错误分类}\end{array}$$
对其使用 $h_2$分类器，分类结果如图所示

易知有三个样本被错误分类
$$\begin{array}{rl}{P}_2& =N_F{w}_i^{(1)}=3\ast \frac{0.1}{0.1\ast 7+0.233\ast 3}=0.2144\\ {\alpha }_2& =\frac{1}{2}\ln (\frac{1-P_2}{P_2})=\frac{1}{2}\ln \left(\frac{1-0.2144}{0.2144}\right)=0.6493\\ w_i^{(2)}& =w_i^{(1)}\text{正确分类不变 }\\ w_i^{(2)}& =w_i^{(1)}\frac{1-P_2}{P_2}=0.3644\text{错误分类}\end{array}$$
对$w_i^{(2)}$进行归一化
$$\begin{array}{rl}{w}_i^{(1)}& =\frac{0.1}{0.1\ast 4+0.233\ast 3+0.3644\ast 3}\text{1、2都被正确分类}\\ w_i^{(1)}& =\frac{0.233}{0.1\ast 4+0.233\ast 3+0.3644\ast 3}\text{1被错误分类，2被正确分类}\\ w_i^{(1)}& =\frac{0.3644}{0.1\ast 4+0.233\ast 3+0.3644\ast 3}\text{2被错误分类，1被正确分类}\end{array}$$

对其使用 $h_3$分类器，分类结果如图所示

易知有一个样本被错误分类
$$\begin{array}{rl}{P}_2& =N_F{w}_i^{(1)}=1\ast \frac{0.1}{0.1\ast 4+0.233\ast 3+0.3644\ast 3}=0.1356\\ {\alpha }_2& =\frac{1}{2}\ln (\frac{1-P_3}{P_3})=\frac{1}{2}\ln \left(\frac{1-0.1356}{0.1356}\right)=0.9223\\ w_i^{(2)}& =w_i^{(1)}\text{正确分类不变 }\\ w_i^{(2)}& =w_i^{(1)}\frac{1-P_3}{P_3}=0.6326\text{错误分类}\end{array}$$
综上所述