集成學(xué)習(xí)-Boosting-Adaboost

0.Adaboost介紹

Adaboost是以
加法模型為模型，
前項分布算法為學(xué)習(xí)算法，
指數(shù)損失函數(shù)為損失函數(shù)的boosting集成學(xué)習(xí)算法。

所謂加法模型，即最終的強分類器是由多個弱分類器加權(quán)求和所得
所謂前項分布算法，即第k+1個強分類器是由第k個強分類器學(xué)成后，再學(xué)習(xí)一個弱分類器組合而得。
所謂指數(shù)損失函數(shù)，即
\sum_{i=1}^{m}\exp({-y_{i}f_{k}(x))}

好處是，指數(shù)中冪相加可以轉(zhuǎn)化為指數(shù)相乘，這樣，可以結(jié)合前項分布算法提取出固定的部分，從而簡化計算。
當(dāng)然，可以選擇其他損失函數(shù)，那就是其他類型的boosting算法了

1.流程：

訓(xùn)練集
T= \left \{ (x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...(x^{(m)},y^{(m)}) \right \}
此處　　y={-1 ,1}

訓(xùn)練集樣本的權(quán)重
W(k)=(w_{k1},w_{k2} ... w_{km}),w_{1i}=\frac{1}{m} ,i=1,2...m
注意，初始權(quán)重即1/m ，如有1000個樣本，初始權(quán)重即 w=1/1000

第k個弱分類器加權(quán)誤差：
e_{k}= \sum_{i=1}^{m}w_{ki}I(G_{k}(x_{i})\neq y_{i})
注意，這里分類加權(quán)誤差，即本次樣本集錯分樣本權(quán)重之和，是歸一化后的。

第k個弱分類器權(quán)重：
\alpha _{k} = \frac{1}{2}log(\frac{1-e_{k}}{e_{k}})
理論上，弱分類器誤差ek應(yīng)該是<0.5的，則alpha > 0
ek越小，alpha越大
即，弱分類器效果越好，則其權(quán)重越大。

第k+1個弱分類器分類時，樣本的權(quán)重：

\begin{alignedat}{} w_{k+1i}&=\frac{w_{ki}}{Z_{k}}exp(-\alpha _{k}y_{i}G_{k}(x_{i})) \\ Z_{k}&=\sum_{i=1}^{m}w_{ki}exp(-\alpha _{k}y_{i}G_{k}(x_{i})) \end{alignedat}

Z_{k}是個固定值，alpha默認(rèn)>0
所以，
如果樣本i分錯了，則exp(...)的值>1

  • 即相比于上一次的弱分類，樣本i的權(quán)重在本次弱分類中得到了提高。

如果樣本i分對了，則exp(...)的值<1

  • 即相比于上一次的弱分類，樣本i的權(quán)重在本次弱分類中得到了降低。

所以，adaboost的思想就通過數(shù)學(xué)公式表達(dá)了出來：

  1. 弱分類器錯誤率越低，則權(quán)重alpha越高

  2. 樣本越被分錯，則權(quán)重w越高（具體的上一次弱分類分錯的樣本，在下一次弱分類時權(quán)重會提高，而如何提高則會根據(jù)上一個弱分類器的權(quán)重alpha來確定。）

弱分類器集合策略：加法模型
\begin{alignedat}{2} f_{K}(x)&=\sum_{k=1}^{K}\alpha _{k}G_{k}(x))\\ \end{alignedat}

但會疑問，權(quán)重更新公式具體是怎么來的？為什么看著很復(fù)雜？

2.推導(dǎo)

adaboost的損失函數(shù)用的是指數(shù)損失函數(shù)
\sum_{i=1}^{m}\exp({-y_{i}f_{k}(x))}
這個損失是有道理的，
如果分錯，則損失>1，且相差越多，損失越大
如果分對，則損失<1，且相差越多，損失越大

則adaboost的損失函數(shù)

\begin{alignedat}{} L &= \sum_{i=1}^{m} exp(-f_{k}(x_{i})y_{i}) \\ &=\sum_{i=1}^{m} exp(-(f_{k-1}(x_{i})y_{i}+\alpha_{k}y_{i}G_{k}(x_{i}))) \\ &= \sum_{i=1}^{m} (exp(-f_{k-1}(x_{i})y_{i})exp(-\alpha_{k}y_{i}G_{k}(x_{i}))) \\ \end{alignedat}
令

w_{ki}^{'}=exp(-f_{k-1}(x_{i})y_{i})
則
\begin{alignedat}{2} L & = \sum_{i=1}^{m} (exp(-f_{k-1}(x_{i})y_{i})exp(-\alpha_{k}y_{i}G_{k}(x_{i}))) \\ & = \sum_{i=1}^{m} (w_{ki}^{'}exp(-\alpha_{k}y_{i}G_{k}(x_{i}))) \\ & = e^{\alpha} \sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}^{'} + e^{-\alpha} \sum_{y_{i}=G_{k}(x_{i})}w_{ki}^{'} \\ & = \sum_{i=1}^{m}w_{ki}^{'} (e^{\alpha} \frac{\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}^{'}}{\sum_{i=1}^{m}w_{ki}^{'}}+e^{-\alpha} \frac{\sum_{y_{i}=G_{k}(x_{i})}w_{ki}^{'}}{\sum_{i=1}^{m}w_{ki}^{'}}) \\ \end{alignedat}

令
err^{'}=\frac{\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}^{'}}{\sum_{i=1}^{m}w_{ki}^{'}}
則
\begin{alignedat}{2} L &=\sum_{i=1}^{m}w_{ki}^{'} (e^{\alpha}err^{'}+e^{-\alpha}(1-err^{'})) \\ &=\sum_{i=1}^{m}w_{ki}^{'} ((e^{\alpha}-e^{-\alpha})err^{'}+e^{-\alpha}) \end{alignedat}
為求alpha，令
\begin{alignedat}{2} \frac{\partial L}{\partial \alpha} &=0 \\ \frac{\partial L}{\partial \alpha} &= \sum w_{ki}^{'} ((e^{\alpha}+e^{-\alpha})err^{'}-e^{-\alpha}) \\\\ \Rightarrow \\ ((e^{\alpha}&+e^{-\alpha})err^{'}-e^{-\alpha}) =0 \\\\ \Rightarrow \\ \alpha &= \frac{1}{2}log(\frac{1-err_{'}}{err_{'}}) \end{alignedat}
可以看到，此處的alpha和上面流程中的弱分類器權(quán)重alpha形式一樣。只需證明
err｀=e即可

3.證明 err'=e

注意

\begin{alignedat}{} err^{'}&=\frac{\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}^{'}}{\sum_{i=1}^{m}w_{ki}^{'}} \\ w_{ki}^{'}&=exp(-f_{k-1}(x_{i})y_{i}) \end{alignedat}
可以看出err是一個類似于錯誤率的東西，表示w·總體中錯分的那部分w·
則關(guān)鍵在于，w·是否等價于樣本權(quán)重w

先來看樣本權(quán)重的更新：

\begin{alignedat}{} w_{k+1i}&=\frac{w_{ki}}{Z_{k}}exp(-\alpha _{k}y_{i}G_{k}(x_{i})) \\ Z_{k}&=\sum_{i=1}^{m}w_{ki}exp(-\alpha _{k}y_{i}G_{k}(x_{i})) \end{alignedat}
則有
\begin{alignedat}{2} w_{1i}&=\frac{1}{m} \\ w_{2i}&=\frac{w_{1i}}{Z_{1}}exp(-\alpha_{1} y_{i}G_{1}(x_{i})) \\ &= \frac{1}{m} \frac{1}{Z_{1}} exp(-\alpha_{1} y_{i}G_{1}(x_{i}))\\ &= \frac{1}{m} \frac{1}{Z_{1}} exp(-y_{i}f_{1}(x_{i}))\\ w_{3i}&=\frac{w_{2i}}{Z_{2}}exp(-\alpha_{2} y_{i}G_{2}(x_{i})) \\ &= \frac{1}{m} \frac{1}{Z_{1}} \frac{1}{Z_{2}} exp(-y_{i}f_{1}(x_{i}))exp(-\alpha_{2} y_{i}G_{2}(x_{i})) \\ &=\frac{1}{m} \frac{1}{Z_{1}} \frac{1}{Z_{2}} exp(-y_{i}f_{2}(x_{i}))\\ ...\\ w_{ki}&=\frac{1}{m} \prod_{j=1}^{k-1}\frac{1}{Z_{j}} exp(-y_{i}f_{k-1}(x_{i}))\\ \because\\ w_{ki}^{'}&=exp(-y_{i}f_{k-1}(x_{i})) \\\\ \therefore\\ w_{ki}&=\frac{1}{m} \prod_{j=1}^{k-1}\frac{1}{Z_{j}} w_{ki}^{'}\\ w_{ki}^{'}&=m\prod_{j=1}^{k-1}Z_{j}w_{ki}\\ err^{'}&=\frac{\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}^{'}}{\sum_{i=1}^{m}w_{ki}^{'}}\\ &=\frac{\sum_{y_{i}\neq G_{k}(x_{i})}(m\prod_{j=1}^{k-1}Z_{j}w_{ki})}{\sum_{i=1}^{m}(m\prod_{j=1}^{k-1}Z_{j}w_{ki})}\\ &=\frac{m\prod_{j=1}^{k-1}Z_{j} *\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}}{m\prod_{j=1}^{k-1}Z_{j}*\sum_{i=1}^{m}w_{ki}}\\ &=\frac{\sum_{y_{i}\neq G_{k}(x_{i})}w_{ki}}{\sum_{i=1}^{m}w_{ki}}\\ &=e \end{alignedat}

其實，從
w_{ki}^{'}=exp(-y_{i}f_{k-1}(x_{i}))
也可以看出樣本的分類損失直接決定了該樣本的新權(quán)重。損失越大，后續(xù)權(quán)重越大

未完待續(xù)
如有錯誤歡迎指正

參考：
劉建平博客-adaboost
統(tǒng)計學(xué)習(xí)方法-李航
adaboost推導(dǎo)
誤差限

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容