您的位置: 首页  >  文章  >  AdaBoost算法原理详细总结

AdaBoost算法原理详细总结

分类: 文章 • 2022-10-28 09:14:28

        在集成学习方法之Bagging，Boosting，Stacking篇章中，我们谈论boosting框架的原理，在boosting系列算法中，AdaBoost是著名的算法之一。AdaBoost是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。
        今天我们就来探讨下AdaBoost分类算法的原理，本篇我们先介绍AdaBoost算法；然后通过误差分析探讨AdaBoost为什么能提升模型的学习精度；并且从前向分步加法模型角度解释AdaBoost；最后对AdaBoost的算法优缺点进行一个总结。

1）从boosting到AdaBoost算法

        集成原理中，我们提到的boosting框架的思想是选择同质的基分类器，让基分类器之间按照顺序进行训练，并让每个基分类器都尝试去修正前面的分类。既然这样，怎样才能让同质的基分类器能够修正前面的分类？或者说怎样才能让同质的基分类器之间保持“互助”呢？
       AdaBoost的做法是，让前一个基分类器ft−1(x)f_{t-1}(x)在当前基分类器ft(x)f_t(x)的训练集上的效果很差（和我们随机瞎猜一样），这样ft(x)f_t(x)就能修正ft−1(x)f_{t-1}(x)的分类误差，ft(x)f_t(x)和ft−1(x)f_{t-1}(x)之间也就产生了“互助”。
       AdaBoost的具体做法是，通过提高被前一轮基分类器ft−1(x)f_{t-1}(x)分类错误的样本的权值，降低被正确分类样本的权值，使得上一个基分类器ft−1(x)f_{t-1}(x)在更新权值后的训练集上的错误率ϵt−1\epsilon_{t-1}增大到0.5。（再在更新权值后的训练集上训练基分类器ft(x)f_t(x)，那ft(x)f_t(x)必能和ft−1(x)f_{t-1}(x)产生互助。）

2）AdaBoost算法

       下面我们在二分类问题上介绍AdaBoost算法。假如给定训练数据集T={(xi,yi)}i=1nT=\left\{ (x^i,y^i) \right\}^n_{i=1}，xi∈Rdx^i\in R^d，yi∈{−1,1}y^i\in\left\{ -1,1\right\}
样本权值为winw_i^n，误差率ϵi\epsilon_i。在训练数据集TT上训练第一个基分类器f1(x)f_1(x)，其错误率为ϵ1，ϵ1<0.5\epsilon_1，\epsilon_1 < 0.5（起码比瞎猜要好一些）
ϵ1=∑nw1nδ((f1(xn)≠y^n)Z1Z1=∑nw1n\epsilon_1=\frac{\sum_nw_1^n\delta((f_1(x^n)\neq {\hat y}^n)}{Z_1} \qquad Z_1 = \sum_nw_1^n
        更新样本的权值（权值为w2nw_2^n）后的训练集为T′{T}'，使得f1(x)f_1(x)在T′{T}'分类效果等同于随机瞎猜（ϵ=0.5\epsilon=0.5）。用数学语言表示即为
∑nw2nδ((f1(xn)≠y^n)Z2=0.5Z2=∑nw2n\frac{\sum_nw_2^n\delta((f_1(x^n)\neq {\hat y}^n)}{Z_2}=0.5 \qquad Z_2 = \sum_nw_2^n
        那么样本权重如何更新呢？AdaBoost具体做法是，减小f1(x)f_1(x)分类正确的样本的权值，权值除以一个常数dd，即w1nd1\frac{w_1^n}{d_1}；增大f1(x)f_1(x)分类错误的样本的权值，权值乘以一个常数dd，即w1nd1w_1^nd_1。用数学语言表示即为
{w2n=w1nd1if f1(xn)≠y^n)w2n=w1nd1if f1(xn)=y^n)\begin{cases} w_2^n = w_1^nd_1 \qquad if \ f_1(x^n)\neq {\hat y}^n)\\ w_2^n = \frac{w_1^n}{d_1} \qquad if \ f_1(x^n)= {\hat y}^n)\\ \end{cases}
        下面我们再回到下式中来，

∑nw2nδ((f1(xn)≠y^n)Z2=0.5\frac{\sum_nw_2^n\delta((f_1(x^n)\neq {\hat y}^n)}{Z_2}=0.5

其中，Z2=∑f1(xn)≠y^nw1nd1+∑f1(xn)=y^nw1nd1Z_2=\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n d_1+\sum_{f_1(x^n)= {\hat y}^n} \frac{w_1^n}{d_1}；当f1(xn)≠y^nf_1(x^n)\neq {\hat y}^n时，w2n=w1nd1w_2^n = w_1^nd_1。
        将上面两式带入得：

∑f1(xn)≠y^nw1nd1∑f1(xn)≠y^nw1nd1+∑f1(xn)=y^nw1nd1=0.5\frac{\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n d_1}{\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n d_1+\sum_{f_1(x^n)= {\hat y}^n} \frac{w_1^n}{d_1}}=0.5

∑f1(xn)=y^nw1nd1=∑f1(xn)≠y^nw1nd1\sum_{f_1(x^n)= {\hat y}^n} \frac{w_1^n}{d_1}=\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n d_1

又因为ϵ1=∑f1(xn)≠y^nw1nZ1⇒ϵ1Z1=∑f1(xn)≠y^nw1n\epsilon_1=\frac{\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n}{Z_1}\Rightarrow \epsilon_1Z_1=\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n
1−ϵ1=∑f1(xn)=y^nw1nZ1⇒(1−ϵ1)Z1=∑f1(xn)=y^nw1n1-\epsilon_1=\frac{\sum_{f_1(x^n)= {\hat y}^n} w_1^n}{Z_1}\Rightarrow (1-\epsilon_1)Z_1=\sum_{f_1(x^n)= {\hat y}^n} w_1^n
因此，
∑f1(xn)=y^nw1nd1=∑f1(xn)≠y^nw1nd1\sum_{f_1(x^n)= {\hat y}^n} \frac{w_1^n}{d_1}=\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n d_1
1d1∑f1(xn)=y^nw1n=d1∑f1(xn)≠y^nw1n\frac{1}{d_1}\sum_{f_1(x^n)= {\hat y}^n} {w_1^n}=d_1\sum_{f_1(x^n)\neq {\hat y}^n} w_1^n
1d1(1−ϵ1)Z1=d1ϵ1Z1\frac{1}{d_1}(1-\epsilon_1)Z_1=d_1\epsilon_1Z_1
d1=1−ϵ1ϵ1d_1=\sqrt{\frac{1-\epsilon_1 }{\epsilon_1}}
其中d1>1d_1>1（因为ϵ1<0.5\epsilon_1<0.5）。
        因此AdaBoost每次更新权值表达式为：
{wt+1n=wtn1−ϵtϵt=wtnexp(Ln(1−ϵtϵt))if ft(xn)≠y^n)wt+1n=wtn1−ϵtϵt=wtnexp(−Ln(1−ϵtϵt))if ft(xn)=y^n)\begin{cases} w_{t+1}^n = w_t^n\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}=w_t^nexp(Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})) \qquad if \ f_t(x^n)\neq {\hat y}^n)\\ w_{t+1}^n = \frac{w_t^n}{\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}}=w_t^nexp(-Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})) \qquad if \ f_t(x^n)= {\hat y}^n)\\ \end{cases}
令αt=Ln(1−ϵtϵt)\alpha_t= Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})，αt\alpha_t即为基分类器ft(x)f_t(x)的权重系数。当ϵt=0.1\epsilon_t =0.1时，αt=1.1\alpha_t=1.1，当ϵt=0.4\epsilon_t =0.4时，αt=0.2\alpha_t=0.2。这表明，当基分类器分类误差率越小时，基分类器的权重越大，在最终表决时起的作用也越大；当基分类器分类误差率越大时，基分类器的权重越小，在最终表决时起的作用也越小。将αt\alpha_t带入上式，样本权值更新表达式变成：
{wt+1n=wtn1−ϵtϵt=wtnexp(αt)if ft(xn)≠y^n)wt+1n=wtn1−ϵtϵt=wtnexp(−αt)if ft(xn)=y^n)\begin{cases} w_{t+1}^n = w_t^n\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}=w_t^nexp(\alpha_t) \qquad if \ f_t(x^n)\neq {\hat y}^n)\\ w_{t+1}^n = \frac{w_t^n}{\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}}=w_t^nexp(-\alpha_t) \qquad if \ f_t(x^n)= {\hat y}^n)\\ \end{cases}
为了方便表示，将上式两项合并成一项得，权值更新的表达式为：
wt+1n=wtnexp(−y^nft(xn)αt)w_{t+1}^n =w_t^nexp(-{\hat y}^nf_t(x^n)\alpha_t)
当ft(xn)=y^nf_t(x^n)= {\hat y}^n时，y^nft(xn){\hat y}^nf_t(x^n)为+1，当 ft(xn)≠y^n\ f_t(x^n)\neq {\hat y}^n时，y^nft(xn){\hat y}^nf_t(x^n)为-1，以上两式为等价变换。
       以上就是AdaBoost算法如何做样本权值更新的整个推导过程。

       
       下面对二元分类AdaBoost算法流程进行总结：
       输入：训练数据集T={(xi,yi)}i=1NT=\left\{ (x^i,y^i) \right\}^N_{i=1}，xi∈Rdx^i\in R^d，yi∈{−1,1}y^i\in\left\{ -1,1\right\}
       输出：最终的分类器H(x)H(x)
①初始化训练数据的权值（权值相等）
w1n=1w_1^n=1
②for t=1...T:for \ t=1...T:

  • 在权值为{wt1,wt2...wtN}\left\{ w_t^1,w_t^2...w_t^N\right\}的训练机上训练基分类器ft(x)f_t(x)

  • 计算ft(x)f_t(x)在训练数据集上的分类误差率ϵt\epsilon_t ϵt=P(ft(xn≠y^n))=∑nwtnδ(ft(xn≠y^n))\epsilon_t=P(f_t(x^n\neq {\hat y}^n))=\sum_nw_t^n\delta (f_t(x^n\neq {\hat y}^n))

  • 计算ft(x)f_t(x)的权值系数
    αt=Ln(1−ϵtϵt)\alpha_t= Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})

  • for n=1,2....N:for \ n=1,2....N:
           if xn被ft(x)分类错误：if \ x^n 被f_t(x)分类错误：
                   wt+1n=wtn1−ϵtϵt=wtnexp(αt)w_{t+1}^n= w_t^n\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}=w_t^nexp(\alpha_t)
           else xnelse \ x^n 被ft(x)f_t(x)分类正确：
                   wt+1n=wtn1−ϵtϵt=wtnexp(−αt)w_{t+1}^n = \frac{w_t^n}{\sqrt{\frac{1-\epsilon_t }{\epsilon_t}}}=w_t^nexp(-\alpha_t)
    ③构建基分类器线性组合
    f(x)=∑Tαtft(x)f(x)=\sum_T\alpha_tf_t(x)
    得到最终的分类器H(x)H(x)
    H(x)=sign(∑Tαtft(x))H(x)=sign(\sum_T\alpha_tf_t(x))

3）AdaBoost的训练误差分析

       AdaBoost最基本的性质是它能在学习的过程中不断减少训练误差，且训练误差以指数速率下降，且无限逼近于0。具体的数学表达式为：
ErrorRate=1N∑δ(y^ng(x)<0)≤1N∑nexp(−y^ng(x))=1NZT+1Error Rate=\frac{1}{N}\sum \delta (\hat y^n g(x)<0)\leq \frac{1}{N}\sum_nexp(-\hat y^n g(x))=\frac{1}{N}Z_{T+1}
1NZT+1=∏t=1T2ϵt(1−ϵt)=∏t=1T(1−4γt2)≤exp(−2∑t=1Tγt2)\frac{1}{N}Z_{T+1}=\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}=\prod _{t=1}^T\sqrt{(1-4\gamma _t^2)}\leq exp(-2\sum _{t=1}^T\gamma _t^2)
其中，γt=12−ϵt\gamma_t=\frac{1}{2}-\epsilon _t。

       下面我们就AdaBoost做二元分类的情况，对这一结论分步进行证明。证明过程会涉及较多的数学公式的推导，对证明不感兴趣的小伙伴可以直接跳到第5部分AdaBoost算法总结。
       首先我们证明：
ErrorRate=1N∑δ(y^ng(x)<0)≤1Nexp(−y^ng(x))Error Rate=\frac{1}{N}\sum \delta (\hat y^n g(x)<0)\leq \frac{1}{N}exp(-\hat y^n g(x))

       从上一部分内容可知，训练数据集T={(xi,yi)}i=1nT=\left\{ (x^i,y^i) \right\}^n_{i=1}，xi∈Rdx^i\in R^d，yi∈{−1,1}y^i\in\left\{ -1,1\right\}，最终的分类器H(x),αtH(x),\alpha_t的表达式为
H(x)=sign(∑t=1Tαtft(x))αt=Ln(1−ϵtϵt)H(x)=sign(\sum_{t=1}^T\alpha_tf_t(x)) \qquad \alpha_t = Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})
       分类器H(x)H(x)的分类误差率为ErrorRateError Rate等于分类错误的样本所占总样本的比例，用数学语言表达即为，
ErrorRate=1N∑δ(H(xn)≠(y^)n)Error Rate=\frac{1}{N}\sum \delta (H(x^n)\neq (\hat y)^n)
其中，H(xn)≠(y^)nH(x^n)\neq (\hat y)^n表示模型的预测值和真实值异号，因此，
ErrorRate=1N∑δ(y^n∑t=1Tαtft(x)<0)Error Rate=\frac{1}{N}\sum \delta (\hat y^n \sum_{t=1}^T\alpha_tf_t(x)<0)
令g(x)=∑t=1Tαtft(x)g(x)=\sum_{t=1}^T\alpha_tf_t(x)，因此，
ErrorRate=1N∑δ(y^ng(x)<0)Error Rate=\frac{1}{N}\sum \delta (\hat y^n g(x)<0)
下面我们开始证明：
ErrorRate=1N∑δ(y^ng(x)<0)≤1Nexp(−y^ng(x))Error Rate =\frac{1}{N}\sum \delta (\hat y^n g(x)<0)\leq \frac{1}{N}exp(-\hat y^n g(x))
其中δ(y^ng(x)<0)\delta (\hat y^n g(x)<0)为01损失函数，exp(−y^ng(x))exp(-\hat y^n g(x))为指数损失函数。画出函数图像很容易发现上式不等式成立：AdaBoost算法原理详细总结
       下面我们证明
ErrorRate≤1N∑nexp(−y^ng(x))=1NZT+1Error Rate\leq \frac{1}{N}\sum_nexp(-\hat y^n g(x))=\frac{1}{N}Z_{T+1}
       已知g(x)=∑t=1Tαtft(x)g(x)=\sum_{t=1}^T\alpha_tf_t(x)（上面我们定义的等式）。且Zt+1Z_{t+1}为基分类器ft+1(x)f_{t+1}(x)所有训练样本的权重之和，用数学语言表示，
       Zt+1=∑nwT+1nZ_{t+1}=\sum _nw_{T+1}^n

                =∑nwTnexp(−y^nft(xn)αt)=\sum _nw_{T}^nexp(-\hat y^nf_t(x^n)\alpha_t)（权值更新公式）
                =∑n∏t=1Texp(−y^nft(xn)αt)=\sum _n\prod _{t=1}^Texp(-\hat y^nf_t(x^n)\alpha_t)
                =∑nexp(−y^n∑t=1Tft(xn)αt)=\sum _nexp(-\hat y^n\sum _{t=1}^Tf_t(x^n)\alpha_t)（连乘符号∏\prod，放到指数expexp中变成求和∑\sum）
                =∑nexp(−y^ng(xn))=\sum _nexp(-\hat y^ng(x^n))
       因此，ErrorRate≤1N∑nexp(−y^ng(x))=1NZT+1Error Rate\leq \frac{1}{N}\sum_nexp(-\hat y^n g(x))=\frac{1}{N}Z_{T+1}
       已知αt=Ln(1−ϵtϵt)\alpha_t = Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})，下面我们证明
ErrorRate≤1NZT+1=∏t=1T2ϵt(1−ϵt)Error Rate\leq \frac{1}{N}Z_{T+1}=\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}
       Zt+1Z_{t+1}为基分类器ft+1(x)f_{t+1}(x)所有训练样本的权重之和，它是由上一轮权值ZtZ_{t}更新而来的，被分类错误的样本权值增大，被分类正确的样本权值减小。
       且Z1=NZ_1=N，因此，

       ZT+1=Ztϵtexp(αt)+Zt(1−ϵt)exp(−αt)Z_{T+1}=Z_t \epsilon _{t}exp(\alpha _{t})+Z_t(1-\epsilon _{t})exp(-\alpha _{t})
                       =Ztϵt1−ϵtϵt+Zt(1−ϵt)ϵt1−ϵt=Z_t \epsilon _{t}\sqrt{\frac{1-\epsilon _{t}}{\epsilon _{t}}}+Z_t(1-\epsilon _{t})\sqrt{\frac{\epsilon _{t}}{1-\epsilon _{t}}}
                       =2Ztϵt(1−ϵt)=2Z_t\sqrt{\epsilon _{t}(1-\epsilon _{t})}
                       =N∏t=1T2ϵt(1−ϵt)=N\prod _{t=1}^T2\sqrt{\epsilon _{t}(1-\epsilon _{t})}
       因此，
ErrorRate≤1NZT+1=∏t=1T2ϵt(1−ϵt)Error Rate\leq \frac{1}{N}Z_{T+1}=\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}
       由于ϵt<0.5\epsilon _t<0.5，因此2ϵt(1−ϵt)≤12\sqrt{\epsilon _t(1-\epsilon _t)}\leq 1，所以AdaBoost的分类误差率是不断的再减小的。
       下面我们证明
∏t=1T2ϵt(1−ϵt)=∏t=1T(1−4γt2)≤exp(−2∑t=1Tγt2)\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}=\prod _{t=1}^T\sqrt{(1-4\gamma _t^2)}\leq exp(-2\sum _{t=1}^T\gamma _t^2)
       ∏t=1T2ϵt(1−ϵt)\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}
       =∏t=1T2(12−(12−ϵt))(12+12−ϵt)=\prod _{t=1}^T2\sqrt{(\frac{1}{2}-(\frac{1}{2}-\epsilon _t))(\frac{1}{2}+\frac{1}{2}-\epsilon _t)}
令γt=12−ϵt\gamma_t=\frac{1}{2}-\epsilon _t，γt>0\gamma_t >0得，
       ∏t=1T2ϵt(1−ϵt)\prod _{t=1}^T2\sqrt{\epsilon _t(1-\epsilon _t)}
       =∏t=1T2(12−(12−ϵt))(12+12−ϵt)=\prod _{t=1}^T2\sqrt{(\frac{1}{2}-(\frac{1}{2}-\epsilon _t))(\frac{1}{2}+\frac{1}{2}-\epsilon _t)}
       =∏t=1T214−γt2=\prod _{t=1}^T2\sqrt{\frac{1}{4}-\gamma _t^2}
       =∏t=1T1−4γt2=\prod _{t=1}^T\sqrt{1-4\gamma _t^2}
       最后我们证明，
∏t=1T(1−4γt2)≤exp(−2∑t=1Tγt2)\prod _{t=1}^T\sqrt{(1-4\gamma _t^2)}\leq exp(-2\sum _{t=1}^T\gamma _t^2)
       首先我们构造一个函数f(x)=e−x+x−1f(x)=e^{-x}+x-1，由于f′′(x)=e−x>0f''(x)=e^{-x}>0，因此f(x)f(x)为凸函数，且minf(x)=f(0)=0minf(x)=f(0)=0，所以f(x)≥0f(x) \geq 0。下面我们进入正式证明：
       f(x)=e−x+x−1≥0f(x)=e^{-x}+x-1 \geq 0
       ⇒e−x≥1−x\Rightarrow e^{-x}\geq 1-x，令x=4γ2x=4\gamma^2，得
       ⇒e−4γ2≥1−4γ2\Rightarrow e^{-4\gamma^2}\geq 1-4\gamma^2
       ⇒e−2γ2≥1−4γ2\Rightarrow e^{-2\gamma^2}\geq \sqrt{1-4\gamma^2}
因此对于t=1,2...Tt=1,2...T，都有{e−2γ12≥1−4γ12e−2γ22≥1−4γ22...e−2γt2≥1−4γt2\begin{cases} e^{-2\gamma_1^2}\geq \sqrt{1-4\gamma_1^2}\\ e^{-2\gamma_2^2}\geq \sqrt{1-4\gamma_2^2}\\ ...\\ e^{-2\gamma_t^2}\geq \sqrt{1-4\gamma_t^2}\\ \end{cases}
       将上式连乘得：
⇒∏t=1Texp(−2γt2)≥∏t=1T1−4γt2\Rightarrow\prod _{t=1}^Texp(-2\gamma_t^2) \geq \prod _{t=1}^T \sqrt{1-4\gamma_t^2}
       ⇒∏t=1T1−4γt2≤∏t=1Texp(−2γt2)\Rightarrow\prod _{t=1}^T \sqrt{1-4\gamma_t^2}\leq \prod _{t=1}^Texp(-2\gamma_t^2)
       ⇒∏t=1T1−4γt2≤exp(−2∑t=1Tγt2)\Rightarrow \prod _{t=1}^T \sqrt{1-4\gamma_t^2}\leq exp(-2\sum _{t=1}^T\gamma_t^2)

       因此，证明得到下式成立：
ErrorRate=1N∑δ(y^ng(x)<0)≤exp(−2∑t=1Tγt2)Error Rate=\frac{1}{N}\sum \delta (\hat y^n g(x)<0)\leq exp(-2\sum _{t=1}^T\gamma_t^2)
       上不等式表明，AdaBoost的训练误差是以指数速率下降且无限逼近于0。（γ>0,−2∑t=1Tγt2<0\gamma >0,-2\sum _{t=1}^T\gamma_t^2<0，小于0的数求指数小于1，小于1的数无限连乘，将无限逼近与0）

4）前向分步加法模型解释AdaBoost

       AdaBoost的另外一种解释，认为AdaBoost是加法模型、损失函数为指数函数、学习算法为前向分步算法的分类学习算法。
       加法模型比较好理解，最终的分类器是有若干个基分类器加权平均得到。即
H(x)=∑Tαtft(x)H(x)=\sum_T\alpha_tf_t(x)
其中，ft(x)f_t(x)为基分类器，αt\alpha_t为基分类器的权值。
       前向分步学习算法，即利用前一个基分类器的结果更新后一个基分类器的训练权重。
       假定第t−1t-1轮后分类器为：
gt−1(x)=∑t=1t−1αtft(x)g_{t-1}(x)= \sum_{t=1}^{t-1}\alpha_tf_t(x)
       而第tt轮后分类器为为：
gt(x)=∑t=1tαtft(x)g_{t}(x)= \sum_{t=1}^{t}\alpha_tf_t(x)
       有上两式可以得：
gt(x)=gt−1(x)+αtft(x)g_t(x)=g_{t-1}(x)+\alpha_tf_t(x)
       因此，最终的分类器是通过前向学习算法得到的。
       AdaBoost的损失函数为，
argmin⏟α,f∑nexp(−y^ngt(x))\underbrace{argmin}_{\alpha,f}\sum_nexp(-\hat y^n g_t(x))
       利用前向分步学习算法可以得到损失函数为：
(αt,ft(x))=argmin⏟α,f∑nexp(−y^n(gt−1(x)+αtft(x))(\alpha_t,f_t(x))= \underbrace{argmin}_{\alpha,f}\sum_nexp(-\hat y^n (g_{t-1}(x)+\alpha_tf_t(x))
       令wt′n=exp(−y^ngt−1(x))w'^n_t=exp(-\hat y^n g_{t-1}(x))，它的值不依赖αt,ft(x)\alpha_t,f_t(x)，因此与最小化无关，仅仅依赖于gt−1(x)g_{t-1}(x)，随着每一轮迭代而改变。将上式子代入损失函数，得
(αt,ft(x))=argmin⏟α,f∑nwt′nexp(−y^αtft(x))(\alpha_t,f_t(x))= \underbrace{argmin}_{\alpha,f}\sum_n w'^n_texp(-\hat y \alpha_tf_t(x))
       我们先求ft∗(x)f^*_t(x)，对于任意的αt>0\alpha_t>0，使得上式最小的ft(x)f_t(x)由下式得到：
ft∗(x)=argmin⏟fwt′nδ(y^n≠ft(xn))f^*_t(x)=\underbrace{argmin}_fw_t'^n\delta (\hat y^n \neq f_t(x^n))
       其中，wt′n=exp(−y^ngt−1(x))w'^n_t=exp(-\hat y^n g_{t-1}(x))。

       基分类器ft∗(x)f^*_t(x)即为AdaBoost算法的基分类器ft(x)f_t(x)，因为它是让第tt轮加权训练数据分类误差率最小的基分类器。将ft∗(x)f^*_t(x)带入损失函数，对αt\alpha_t求导，使其等于0，得
αt=12Ln1−ϵtϵt\alpha_t = \frac{1}{2}Ln\frac{1-\epsilon _t}{\epsilon _t}
       其中ϵt\epsilon _t为分类误差率：
ϵt=∑nwt′nδ(y^n≠ft(xn))∑nwt′n=∑nwtnδ(y^n≠ft(xn))\epsilon _t=\frac{\sum _nw'^n_t\delta (\hat y^n \neq f_t(x^n))}{\sum_n w'^n_t}=\sum _nw_t^n\delta (\hat y^n \neq f_t(x^n))
       这与我们在第二部分讨论的一致（见下式）。上式的wtnw^n_t为权值率，下式中的wtnw^n_t为权值，除以Z1Z_1等价于权值率。
ϵ1=∑nw1nδ((f1(xn)≠y^n)Z1Z1=∑nw1n\epsilon_1=\frac{\sum_nw_1^n\delta((f_1(x^n)\neq {\hat y}^n)}{Z_1} \qquad Z_1 = \sum_nw_1^n
αt=Ln(1−ϵtϵt)\alpha_t= Ln(\sqrt{\frac{1-\epsilon_t }{\epsilon_t}})
       最后我们来看下每一轮权值的更新，利用以下两式
gt(x)=gt−1(x)+αtft(x)g_t(x)=g_{t-1}(x)+\alpha_tf_t(x)
wt′n=exp(−y^ngt−1(x))w'^n_t=exp(-\hat y^n g_{t-1}(x))
       可得到权值更新公式为：
wt+1n=wtnexp(−y^nft(xn)αt)w_{t+1}^n =w_t^nexp(-{\hat y}^nf_t(x^n)\alpha_t)
       这与我们在第一部分讨论的权值更新公式也一致。因此，AdaBoost也可以从加法模型、指数损失函数、前向分步学习算法角度来解释。
       需要注意的是，是先有了AdaBoost算法之后，人们才发现，通过加法模型、指数损失函数、前向分步学习算法的方式可以解释AdaBoost算法的过程。

5）AdaBoost算法总结

       下面我们对AdaBoost算法的优缺点进行总结。
优点：

  • 既可以处理分类任务，又可以处理回归任务；
  • 不易过拟合；
  • AdaBoost训练的分类器，分类精度高；
  • 支持各种分类器做基分类器，如逻辑回归，SVM；
    缺点：
  • 对异常值敏感，异常值的权重在模型训练的过程中可能会越来越大，最终影响整个模型的性能；

       终于写完了，这篇写的有点长，涉及的数学推导比较多，我也尽量往详细写了，大家需要一些耐心慢慢看。如果看到数学推导就头晕的小伙伴，可以只看第二部分AdaBoost算法原理部分。本篇涉及的数学公式较多，我也多检查了两遍，尽量减少数学上的表述错误。如果小伙伴发现还有错误，还望指正！
       下篇我们探讨Scikit learn中的AdaBoost算法库类，并进行实践。
       
（欢迎大家在评论区探讨交流，也欢迎大家转载，转载请注明出处！)
上篇：Scikit-learn随机森林算法库总结与调参实践
下篇：持续更新中，敬请关注

相关推荐