对于一个复杂任务,将多个决策进行适当的综合所得出的判断,要比其中任何一个决策更为准确.
对于分类问题,提升方法的就是从弱学习方法出发,反复学习,得到一系列弱分类器,然后组合这些弱分类器,构成一个强分类器,大多数提升方法都是通过改变训练数据的概率分布,(即通过对训练数据进行加权),针对不同分布的数据调用弱学习方法学习一系列的弱分类器.
提升方法有两个关键所在:
Kearns和Valiant提出了强可学习和弱可学习的概念. 在概率近似正确(probably approximately correct, PAC)学习的框架中,
一个概念如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么就称这个概念是强可学习的.
一个概念如果存在一个多项式的学习算法能够学习它,学习的正确率只比随机猜测略好,则称这个概念是弱可学习的.
Schapire后来证明强可学习和若可学习是等价的,即在PAC学习框架下,一个概念是强可学习的充分必要条件是这个概念是弱可学习的.
很容易得知,除非对所有可能的数据进行训练,否则总会存在多个假设使得错误率不为0,也就是说学习器不能保证和目标函数完全一致,且由于样本是随机选择的,总存在一定的偶然性,使得学习器学习到的与真实分布不同。
因此我们只要求学习学习到一个近似正确的假设,即PAC学习.
一个可PAC学习的学习需要满足两个条件:
对于提升方法的两个关键,AdaBoost采取的做法是,提高被前一轮弱分类器错误分类样本的权值,降低被正确分类样本的权值,这样分类器就会更加关注上一轮被错分类的数据;对于弱分类器的组合,AdaBoost采取加权多数表决的方法,对于分类误差率小的弱分类器取较大的权值,减小分类误差率大得弱分类器的权值.
假设给定一个二类分类的训练数据集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)
在计算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)̸=yiwmi,即分类误差率是被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算法最终分类器的训练误差界为 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_mN1i=1∑NI(G(xi)̸=yi)≤N1i∑exp(−yif(xi))=m∏Zm
证明: 显然式子第一部分的值小于等于1,而当G(xi)≠yiG(x_i)\neq y_iG(xi)̸=yi时,yif(xi)<0y_if(x_i)<0yif(xi)<0,因而有exp(−yif(xi))≥1\exp(-y_if(x_i))\geq 1exp(−yif(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)) &=\frac{1}{N}\sum_i\exp\Big(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\Big)\\ &=\sum_iw_{1i}\exp\Big(-\sum_{m=1}^M\alpha_my_iG_m(x_i)\Big)\\ &=\sum_iw_{1i}\prod_{m=1}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &=Z_1\sum_iw_{2i}\prod_{m=2}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &=Z_1Z_2\sum_iw_{3i}\prod_{m=3}^M\exp\Big(-\alpha_my_iG_m(x_i)\Big)\\ &=\dots\\ &=Z_1Z_2\dots Z_{M-1}\sum_iw_{Mi}\exp(-\alpha_My_iG_M(x_i))\\ &=\prod_{m=1}^MZ_m \end{aligned} N1i∑exp(−yif(xi))=N1i∑exp(−m=1∑MαmyiGm(xi))=i∑w1iexp(−m=1∑MαmyiGm(xi))=i∑w1im=1∏Mexp(−αmyiGm(xi))=Z1i∑w2im=2∏Mexp(−αmyiGm(xi))=Z1Z2i∑w3im=3∏Mexp(−αmyiGm(xi))=…=Z1Z2…ZM−1i∑wMiexp(−αMyiGM(xi))=m=1∏MZm
在每一轮过程中我们总可以选取合适的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∏MZm=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 &= \sum_{i=1}^N w_{mi}\exp(-\alpha_my_iG(x_i))\\ &=\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}\\ &=(1-e_m)e^{-\alpha_m} + e_me^{\alpha}\\ &=2\sqrt{e_m(1-e_m)}=\sqrt{1-4\gamma_m^2} \end{aligned} Zm=i=1∑Nwmiexp(−αmyiG(xi))=yi=Gm(xi)∑wmie−αm+yi̸=Gm(xi)∑wmieαm=(1−em)e−αm+emeα=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).
推论 如果存在γ>0\gamma>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) N1i=1∑NI(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βmb(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,γmmini=1∑NL(yi,m=1∑Mβmb(xi;γm)) 前向分步算法求解这一优化问题的想法是:从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数,就可以简化优化的复杂度,每一步只需要优化如下损失函数: minβ,γ∑i=1NL(yi,βb(xi;γ))\min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma))β,γmini=1∑NL(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)
这样就将同时求解从m=1m=1m=1到M所有参数βm,γm\beta_m,\gamma_mβm,γm的优化问题简化为逐次求解各个βm,γm\beta_m,\gamma_mβm,γm的优化问题.
定理 AdaBoost算法是前向分步算法的特例,模型是由基本分类器促成的加法模型,损失函数是指数函数.
证明
现证明使上述代价函数最小的α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),对于任意α>0\alpha>0α>0,使得上式最小的G(x)G(x)G(x)由下式得到: Gm∗(x)=argminG∑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)=argGmini=1∑NwˉmiI(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))&=\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}\\ &=(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∑Nwˉmiexp(−yiαG(xi))=yi=Gm(xi)∑wˉmie−α+yi̸=Gm(xi)∑wˉmieα=(eα−e−α)i=1∑NwˉmiI(yi̸=G(xi))+e−αi=1∑Nwˉmi 将Gm∗(x)G_m^*(x)Gm∗(x)代入上式,对α\alphaα求导等于0,即可得到使损失函数最小的α\alphaα αm∗=12log1−emem \alpha_m^* = \frac{1}{2}\log \frac{1-e_m}{e_m} αm∗=21logem1−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)+αmGm(x)wˉmi=exp(−yifm−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,iexp(−yiαmGm(x))
李航-统计学习方法