AdaBoost详解

提升方法的思路

对于一个复杂任务，将多个决策进行适当的综合所得出的判断，要比其中任何一个决策更为准确.

对于分类问题，提升方法的就是从弱学习方法出发，反复学习，得到一系列弱分类器，然后组合这些弱分类器，构成一个强分类器，大多数提升方法都是通过改变训练数据的概率分布，(即通过对训练数据进行加权)，针对不同分布的数据调用弱学习方法学习一系列的弱分类器.

提升方法有两个关键所在：

• 在每一轮如果改变训练数据的权值或概率分布.
• 如何将弱分类器组合成一个强分类器.

强可学习和弱可学习

Kearns和Valiant提出了强可学习和弱可学习的概念. 在概率近似正确(probably approximately correct, PAC)学习的框架中，

一个概念如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的.

一个概念如果存在一个多项式的学习算法能够学习它，学习的正确率只比随机猜测略好，则称这个概念是弱可学习的.

Schapire后来证明强可学习和若可学习是等价的，即在PAC学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的.

PAC学习

很容易得知，除非对所有可能的数据进行训练，否则总会存在多个假设使得错误率不为0，也就是说学习器不能保证和目标函数完全一致，且由于样本是随机选择的，总存在一定的偶然性，使得学习器学习到的与真实分布不同。

因此我们只要求学习学习到一个近似正确的假设，即PAC学习.

一个可PAC学习的学习需要满足两个条件：

• 学习器必须以任意高的概率输出一个错误率任意低的假设.
• 学习的时间最多以多项式方式增长.

AdaBoost

对于提升方法的两个关键，AdaBoost采取的做法是，提高被前一轮弱分类器错误分类样本的权值，降低被正确分类样本的权值，这样分类器就会更加关注上一轮被错分类的数据；对于弱分类器的组合，AdaBoost采取加权多数表决的方法，对于分类误差率小的弱分类器取较大的权值，减小分类误差率大得弱分类器的权值.

AdaBosst算法

假设给定一个二类分类的训练数据集T=(x1,y1),(x2,y2)…(xN,yN)T={(x_1,y_1), (x_2, y_2)\dots(x_N, y_N)}T=(x1​,y1​),(x2​,y2​)…(xN​,yN​)，其中，每个样本点有实例和标记组成. 标记yi={−1,+1}y_i = \{-1, +1\}yi​={−1,+1}，AdaBoost利用以下算法，从训练数据中学习一系列弱分类器，然后将弱分类器线性组合成为一个强分类器.

算法(AdaBoost)

输入：训练数据集，弱学习算法.

输出：强分类器G(x)G(x)G(x)

1. 初始化训练数据的权值分布 D1=(w11,…,w1i,…,w1N), w1i=1N, i=1,2…,N D_1 = (w_{11},\dots,w_{1i},\dots,w_{1N}),\ w_{1i}=\frac{1}{N},\ i=1,2\dots,N D1​=(w11​,…,w1i​,…,w1N​), w1i​=N1​, i=1,2…,N
2. 对m=1,2,…,Mm=1,2,\dots,Mm=1,2,…,M
   1. 使用具有权值分布的DmD_mDm​的训练数据集学习，得到基本分类器Gm(x):x→{−1,+1}G_m(x):x\rightarrow\{-1,+1\}Gm​(x):x→{−1,+1}.
   2. 计算Gm(x)G_m(x)Gm​(x)在训练数据集上的分类误差率em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)e_m = P(G_m(x_i)\neq y_i) = \sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)em​=P(Gm​(xi​)̸​=yi​)=∑i=1N​wmi​I(Gm​(xi​)̸​=yi​).
   3. 计算Gm(x)G_m(x)Gm​(x)的系数αm=12log⁡1−emem\alpha_m = \frac{1}{2}\log \frac{1-e_m}{e_m}αm​=21​logem​1−em​​.
   4. 更新训练数据集的权值分布，这里的ZmZ_mZm​是规范化因子 Dm+1=(wm+1,1,…,wm+1,i,…,wm+1,N)Wm+1,i=wmiZmexp⁡(−αmyiGm(xi))，i=1,2…,NZm=∑i=1Nwmiexp⁡(−αmyiGm(xi)) D_{m+1} = (w_{m+1,1},\dots,w_{m+1,i},\dots,w_{m+1,N})\\ W_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i))，i=1,2\dots,N\\ Z_m = \sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i)) Dm+1​=(wm+1,1​,…,wm+1,i​,…,wm+1,N​)Wm+1,i​=Zm​wmi​​exp(−αm​yi​Gm​(xi​))，i=1,2…,NZm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​))
3. 构成基本分类器的线性组合 f(x)=∑m=1MαmGm(x)f(x)=\sum_{m=1}^M\alpha_mG_m(x)f(x)=∑m=1M​αm​Gm​(x)，得到最终分类器 G(x)=sign(f(x))=sing(∑m=1MαmGm(x))G(x) = sign(f(x)) = sing(\sum_{m=1}^M\alpha_mG_m(x))G(x)=sign(f(x))=sing(m=1∑M​αm​Gm​(x))

在计算Gm(x)G_m(x)Gm​(x)在训练数据集上的分类误差率eme_mem​，我们可以得到em=∑Gm(xi)≠yiwmie_m = \sum_{G_m(x_i)\neq y_i}w_{mi}em​=∑Gm​(xi​)̸​=yi​​wmi​，即分类误差率是被Gm(x)G_m(x)Gm​(x)五分类样本的权值之和.

当em≤12e_m\leq \frac{1}{2}em​≤21​时，αm≥0\alpha_m\geq 0αm​≥0，并且αm\alpha_mαm​随eme_mem​的减小而增大，所以分类误差率越小的弱分类器在最终分类器中的权值越大.

AdaBoost算法的训练误差分析

AdaBoost在学习过程中不断减少训练误差.

定理: AdaBoost算法最终分类器的训练误差界为 1N∑i=1NI(G(xi)≠yi)≤1N∑iexp⁡(−yif(xi))=∏mZm\frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i)\leq \frac{1}{N}\sum_i\exp(-y_if(x_i))=\prod_mZ_mN1​i=1∑N​I(G(xi​)̸​=yi​)≤N1​i∑​exp(−yi​f(xi​))=m∏​Zm​

证明： 显然式子第一部分的值小于等于1，而当G(xi)≠yiG(x_i)\neq y_iG(xi​)̸​=yi​时，yif(xi)&lt;0y_if(x_i)&lt;0yi​f(xi​)<0，因而有exp⁡(−yif(xi))≥1\exp(-y_if(x_i))\geq 1exp(−yi​f(xi​))≥1，所以左半部分成立.

1N∑iexp⁡(−yif(xi))=1N∑iexp⁡(−∑m=1MαmyiGm(xi))=∑iw1iexp⁡(−∑m=1MαmyiGm(xi))=∑iw1i∏m=1Mexp⁡(−αmyiGm(xi))=Z1∑iw2i∏m=2Mexp⁡(−αmyiGm(xi))=Z1Z2∑iw3i∏m=3Mexp⁡(−αmyiGm(xi))=…=Z1Z2…ZM−1∑iwMiexp⁡(−αMyiGM(xi))=∏m=1MZm \begin{aligned} \frac{1}{N}\sum_i\exp(-y_if(x_i)) &amp;=\frac{1}{N}\sum_i\exp\Big(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\Big)\\ &amp;=\sum_iw_{1i}\exp\Big(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\Big)\\ &amp;=\sum_iw_{1i}\prod_{m=1}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &amp;=Z_1\sum_iw_{2i}\prod_{m=2}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &amp;=Z_1Z_2\sum_iw_{3i}\prod_{m=3}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &amp;=\dots\\ &amp;=Z_1Z_2\dots Z_{M-1}\sum_iw_{Mi}\exp(-\alpha_My_iG_M(x_i))\\ &amp;=\prod_{m=1}^MZ_m \end{aligned} N1​i∑​exp(−yi​f(xi​))​=N1​i∑​exp(−m=1∑M​αm​yi​Gm​(xi​))=i∑​w1i​exp(−m=1∑M​αm​yi​Gm​(xi​))=i∑​w1i​m=1∏M​exp(−αm​yi​Gm​(xi​))=Z1​i∑​w2i​m=2∏M​exp(−αm​yi​Gm​(xi​))=Z1​Z2​i∑​w3i​m=3∏M​exp(−αm​yi​Gm​(xi​))=…=Z1​Z2​…ZM−1​i∑​wMi​exp(−αM​yi​GM​(xi​))=m=1∏M​Zm​​

在每一轮过程中我们总可以选取合适的GmG_mGm​使得ZmZ_mZm​最小，从而使训练误差下降最快.

定理：二分类问题AdaBoost的训练误差界

∏m=1MZm=∏m=1M(2em(1−em))=∏m=1M(1−4γm2)≤exp⁡(−2∑m=1Mγm2)\prod_{m=1}^MZ_m = \prod_{m=1}^M(2\sqrt{e_m(1-e_m)})=\prod_{m=1}^M\sqrt{(1-4\gamma_m^2)}\leq \exp\big(-2\sum_{m=1}^M\gamma_m^2\big)m=1∏M​Zm​=m=1∏M​(2em​(1−em​)​)=m=1∏M​(1−4γm2​)​≤exp(−2m=1∑M​γm2​) 这里γm=12−em\gamma_m=\frac{1}{2}-e_mγm​=21​−em​

证明 Zm=∑i=1Nwmiexp⁡(−αmyiG(xi))=∑yi=Gm(xi)wmie−αm+∑yi≠Gm(xi)wmieαm=(1−em)e−αm+emeα=2em(1−em)=1−4γm2 \begin{aligned} Z_m &amp;= \sum_{i=1}^N w_{mi}\exp(-\alpha_my_iG(x_i))\\ &amp;=\sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha_m} + \sum_{y_i\neq G_m(x_i)}w_{mi}e^{\alpha_m}\\ &amp;=(1-e_m)e^{-\alpha_m} + e_me^{\alpha}\\ &amp;=2\sqrt{e_m(1-e_m)}=\sqrt{1-4\gamma_m^2} \end{aligned} Zm​​=i=1∑N​wmi​exp(−αm​yi​G(xi​))=yi​=Gm​(xi​)∑​wmi​e−αm​+yi​̸​=Gm​(xi​)∑​wmi​eαm​=(1−em​)e−αm​+em​eα=2em​(1−em​)​=1−4γm2​​​ 利用泰勒公式将exe^xex和1−x\sqrt{1-x}1−x​在x=0x=0x=0处展开可以推出1−4γm2≤exp⁡(−2γm2)\sqrt{1-4\gamma_m^2}\leq \exp(-2\gamma_m^2)1−4γm2​​≤exp(−2γm2​).

推论 如果存在γ&gt;0\gamma&gt;0γ>0，对所有mmm有γm≥γ\gamma_m\geq \gammaγm​≥γ，则 1N∑i=1NI(G(xi)≠yi)≤exp⁡(−2Mγ2) \frac{1}{N}\sum_{i=1}^NI(G(x_i)\neq y_i)\leq \exp(-2M\gamma^2) N1​i=1∑N​I(G(xi​)̸​=yi​)≤exp(−2Mγ2)

由此可以看出AdaBoost训练误差其上界是以指数速率下降的.

前向分步算法

AdaBoost可以看作是模型为加法模型、损失函数为指数函数的前向分步算法.

对于加法模型 f(x)=∑m=1Mβmb(x;γm)f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)f(x)=m=1∑M​βm​b(x;γm​) 其中b(x;γm)b(x;\gamma_m)b(x;γm​)为基函数，γm\gamma_mγm​为基函数的参数，βm\beta_mβm​为基函数的系数. 在给定训练数据及损失函数的条件下，学习加法模型f(x)f(x)f(x)程维经验风险极小化即损失函数极小化问题. min⁡βm,γm∑i=1NL(yi,∑m=1Mβmb(xi;γm))\min_{\beta_m,\gamma_m}\sum_{i=1}^NL\Big(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))βm​,γm​min​i=1∑N​L(yi​,m=1∑M​βm​b(xi​;γm​)) 前向分步算法求解这一优化问题的想法是：从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，就可以简化优化的复杂度，每一步只需要优化如下损失函数： min⁡β,γ∑i=1NL(yi,βb(xi;γ))\min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma))β,γmin​i=1∑N​L(yi​,βb(xi​;γ)) 算法

输入： 训练数据集T,损失函数L(y,f(x))L(y,f(x))L(y,f(x))，基函数集{b(x;γ)}\{b(x;\gamma)\}{b(x;γ)}

输出： 加法模型f(x)f(x)f(x)

1. 初始化f0(x)=0f_0(x)=0f0​(x)=0.
2. 对m=1,2…,Mm=1,2\dots,Mm=1,2…,M
   1. 极小化损失函数 (βm,γm)=argmin⁡β,γ∑i=1NL(yi,fm−1(xi)+βb(xi;γ)) (\beta_m,\gamma_m)=arg \min_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma)) (βm​,γm​)=argβ,γmin​i=1∑N​L(yi​,fm−1​(xi​)+βb(xi​;γ)) 得到其参数βm,γm\beta_m,\gamma_mβm​,γm​
   2. 更新 fm(x)=fm−1(x)+βmb(x;γm)f_m(x) = f_{m-1}(x) + \beta_mb(x;\gamma_m)fm​(x)=fm−1​(x)+βm​b(x;γm​)
3. 得到加法模型 f(x)=fM(x)=∑m=1Mβmb(x;γm)f(x) = f_M(x) = \sum_{m=1}^M\beta_mb(x;\gamma_m)f(x)=fM​(x)=m=1∑M​βm​b(x;γm​)

这样就将同时求解从m=1m=1m=1到M所有参数βm,γm\beta_m,\gamma_mβm​,γm​的优化问题简化为逐次求解各个βm,γm\beta_m,\gamma_mβm​,γm​的优化问题.

前向分步算法和AdaBoost

定理 AdaBoost算法是前向分步算法的特例，模型是由基本分类器促成的加法模型，损失函数是指数函数.

证明

1. 显然，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器 f(x)=∑m=1MαmGm(x)f(x) = \sum_{m=1}^M\alpha_mG_m(x)f(x)=m=1∑M​αm​Gm​(x)
2. 证明AdaBoost的损失函数为指数损失函数. L(y,f(x))=exp⁡(−yf(x))L(y,f(x)) = \exp(-yf(x))L(y,f(x))=exp(−yf(x)) 假设已经经过m−1m-1m−1次迭代，得到了fm−1(x)f_{m-1}(x)fm−1​(x): fm−1(x)=fm−2(x)+αm−1Gm−1(x)=α1G1(x)+⋯+αm−1Gm−1(x)f_{m-1}(x) = f_{m-2}(x) + \alpha_{m-1}G_{m-1}(x)=\alpha_1G_1(x) + \dots+\alpha_{m-1}G_{m-1}(x)fm−1​(x)=fm−2​(x)+αm−1​Gm−1​(x)=α1​G1​(x)+⋯+αm−1​Gm−1​(x) 第mmm轮迭代目标是获得αm,Gm(x),fm(x)\alpha_m,G_m(x),f_m(x)αm​,Gm​(x),fm​(x)， fm(x)=fm−1(x)+αmGm−1(x)f_m(x) = f_{m-1}(x) + \alpha_mG_{m-1}(x)fm​(x)=fm−1​(x)+αm​Gm−1​(x) 目标是使fm(x)f_m(x)fm​(x)在训练数据集上的指数损失函数最小 (αm,Gm(x))=argmin⁡α,G∑i=1Nexp⁡(−yi(fm−1(xi)+αG(xi)))=argmin⁡α,G∑i=1Nwˉmiexp⁡(−yiαG(xi)) \begin{aligned} (\alpha_m,G_m(x)) &amp;= arg \min_{\alpha,G}\sum_{i=1}^N\exp(-y_i(f_{m-1}(x_i)+ \alpha G(x_i)))\\ &amp;= arg \min_{\alpha,G}\sum_{i=1}^N\bar{w}_{mi}\exp(-y_i\alpha G(x_i)) \end{aligned} (αm​,Gm​(x))​=argα,Gmin​i=1∑N​exp(−yi​(fm−1​(xi​)+αG(xi​)))=argα,Gmin​i=1∑N​wˉmi​exp(−yi​αG(xi​))​ 其中wˉmi=exp⁡(−yifm−1(xi))\bar{w}_{mi}=\exp(-y_if_{m-1}(x_i))wˉmi​=exp(−yi​fm−1​(xi​))，wˉmi\bar{w}_{mi}wˉmi​与αm,Gm\alpha_m,G_mαm​,Gm​都无关，所以与最小化无关.

现证明使上述代价函数最小的αm∗,Gm∗(x)\alpha_m^*,G_m^*(x)αm∗​,Gm∗​(x)就是AdaBoost算法所得到的αm\alpha_mαm​和Gm(x)G_m(x)Gm​(x).

求解可分为两步：

先求解Gm∗(x)G_m^*(x)Gm∗​(x)，对于任意α&gt;0\alpha&gt;0α>0，使得上式最小的G(x)G(x)G(x)由下式得到： Gm∗(x)=argmin⁡G∑i=1NwˉmiI(yi≠G(xi))G_m^*(x)=arg \min_G\sum_{i=1}^N\bar{w}_{mi}I(y_i\neq G(x_i))Gm∗​(x)=argGmin​i=1∑N​wˉmi​I(yi​̸​=G(xi​)) 此分类器即为AdaBoost算法的基本分类器Gm(x)G_m(x)Gm​(x)，因为其使第m轮加权训练数据分类误差率最小.

再求解αm∗\alpha_m^*αm∗​， ∑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 \begin{aligned} \sum_{i=1}^N\bar{w}_{mi}\exp(-y_i\alpha G(x_i))&amp;=\sum_{y_i=G_m(x_i)}\bar{w}_{mi}e^{-\alpha} + \sum_{y_i\neq G_m(x_i)}\bar{w}_{mi}e^{\alpha}\\ &amp;=(e^{\alpha}- e^{-\alpha})\sum_{i=1}^N\bar{w}_{mi}I(y_i\neq G(x_i))+e^{-\alpha}\sum_{i=1}^N\bar{w}_mi \end{aligned} i=1∑N​wˉmi​exp(−yi​αG(xi​))​=yi​=Gm​(xi​)∑​wˉmi​e−α+yi​̸​=Gm​(xi​)∑​wˉmi​eα=(eα−e−α)i=1∑N​wˉmi​I(yi​̸​=G(xi​))+e−αi=1∑N​wˉm​i​ 将Gm∗(x)G_m^*(x)Gm∗​(x)代入上式，对α\alphaα求导等于0，即可得到使损失函数最小的α\alphaα αm∗=12log⁡1−emem \alpha_m^* = \frac{1}{2}\log \frac{1-e_m}{e_m} αm∗​=21​logem​1−em​​ 其中eme_mem​是分类误差率.

最后再看每一轮样本权值的更新， fm(x)=fm−1(x)+αmGm(x)wˉmi=exp⁡(−yifm−1(xi)) f_m(x) = f_{m-1}(x) + \alpha_mG_m(x)\\ \bar{w}_{mi} = \exp(-y_if_{m-1}(x_i)) fm​(x)=fm−1​(x)+αm​Gm​(x)wˉmi​=exp(−yi​fm−1​(xi​)) 可得 wˉm+1,i=wˉm,iexp⁡(−yiαmGm(x)) \bar{w}_{m+1,i} = \bar{w}_{m,i}\exp(-y_i\alpha_mG_m(x)) wˉm+1,i​=wˉm,i​exp(−yi​αm​Gm​(x))

参考文献

李航-统计学习方法