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))

参考文献

李航-统计学习方法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 三摄正普及,四摄在路上?谷歌逆天AI算法,只做单摄虚化

    想要提高拍照效果,想必对于多数手机厂商而言,给手机塞进更多的摄像头似乎成了当前主流做法,例如“普通摄像头+景深摄像头”、“黑白+彩色摄像头”、“广角+长焦摄像头...

    AI科技大本营
  • Gartner六大安全趋势 | 数据安全是关乎企业生死存亡的核心要素

    近日,Gartner研究团队副总裁Peter Firstbrook在美国佛罗里达州举办的顶级安全趋势大会上表示,数据安全是关乎企业生死存亡的核心要素之一。

    FB客服
  • 机器学习重大挑战:坏数据和坏算法正在毁掉你的项目

    简单来说,由于你的主要任务是选择一种学习算法,并对某些数据进行训练,所以最可能出现的两个问题不外乎是坏算法和坏数据。

    华章科技
  • NeurIPS 2018首日:阿里霸气演示全中文Demo,谷歌发布“找新娘”图片识别竞赛

    两年前的2016年,依然被称为NIPS大会的该活动有5,000名注册参与者。去年,参会者人数达到8,000。到了今年,首批2,000张门票在放出12分钟内即售罄...

    大数据文摘
  • 亚马逊推出AI芯片、定制CPU:入局芯片军备竞赛

    「Inferentia 将会是一款超高吞吐量、低延迟、性能强大,且功耗比极佳的处理器,」AWS 首席执行官 Andy Jassy 在发布中介绍道。

    机器之心
  • 轻松玩转 Scikit-Learn 系列 —— 你居然不知道 PCA ?

    PCA 的全称是 Principal Component Analysis,翻译过来就是主成分分析法,是数据分析中常用的数据降维方法,亦是一种学习数据表示的无监...

    小小詹同学
  • 2019 互联网校招薪酬及就职要求曝光 !

    链接:https://mp.weixin.qq.com/s/aUKV5rCCSlT-NBcgy1zohg

    小小詹同学
  • iOS开发者的出路在哪里?从Swift到机器学习

    内容来源:2018 年 9 月 15 日,iOS职业开发者王巍在“2018@swift 第三届 Swift 开发者大会”进行《从Swift到机器学习》演讲分享。...

    IT大咖说
  • 四大机器学习编程语言对比:R、Python、MATLAB、Octave

    人工智能(AI)是近几年来最热的话题之一,不管是医疗界、互联网界、服务界,还是制造业、工业等等,不和AI挂个边都不好意思出来和人打招呼(比如咱们运维界也有AIO...

    嘉为科技
  • 干货 | 机器学习概念的深度解析(入门必看)

    在进入正题前,我想读者心中可能会有一个疑惑:机器学习有什么重要性,以至于要阅读完这篇非常长的文章呢?

    用户2769421

扫码关注云+社区

领取腾讯云代金券