1 Adaboost

adaboost屬於linearly blending（線性混合），既有數據權重也有分類器權重。Adaboost屬於boosting的一種。Boosting是集成學習的一種思路，通過多輪迭代（全部數據），每一輪產生一個弱分類器，將弱分類器預測結果相加，得到強分類器的最終結果。

2 adaboost具體描述

對樣本賦予權重，採用迭代的方式來構造每一步的弱分類器，最終通過linear blending的方式得到強的分類器，可用如下公式描述：

如何迭代產生若干互不相同的g(x)？

通過賦予樣本不同的權重獲得不同的g(x)。基分類器g(x)大多使用decision-stump（樹樁）。

這裡是由於adaboost一般是分兩層。我們通過修改數據的權重，使得本次訓練的弱分類器在上一次弱分類器做的不好的地方進行訓練。

什麼是權重正確率？

什麼是權重錯誤率？

也就是說，每條數據前面都有一個權重（也就是重要性指標），權重正確率就是正確的權重的綜合與總權重和。

分裂條件是什麼？

以權重正確率大小作為分裂條件。

具體迭代思想：

設第一代的數據權重為1，我們的目的是讓對的降低，錯的升高，這樣讓下一代分類器著重考慮。數據權重用 U_{n} 來表示，更新數據權重，獲得的分類器會隨之改變。

由 U_{n}^{1} 得到 g_{1}left( x ight) ，然後得到 U_{n}^{2} ，此時帶入 g_{1}left( x ight) ，其權重正確率會改變。

U_{n}^{2} 決定 g_{2}left( x ight) ，目的是讓之前的 g_{1}left( x ight) 分類器做的不好的地方做的更好。

怎麼讓 g_{1}left( x ight) 做到不好呢？

讓 g_{1}left( x ight) 分類器的權重正確率達到0.5，即為不好。

找到一個 U_{n}^{2} 求得一個 g_{1}left( x ight) 使其權重正確率達到0.5，通過 U_{n}^{2} 得到一個 g_{2}left( x ight) 先判斷哪一個權重正確率高（也就是看哪一個判斷準則的權重正確率高），然後用誰做 g_{1}left( x ight) ，然後找 U_{n}^{2} 使得 g_{1}left( x ight) 的權重正確率為0.5，然後再訓練 g_{2}left( x ight) 。

根據上圖可計算權重正確率和錯誤率。

修改 U_{n}^{2} 使得 g_{1}left( x ight) 的權重正確率為0.5，切記 g_{1}left( x ight) 是沒有發生變化的。

Adaboost 中的數據權重 U_{n} 迭代：

1 在訓練集中的每個數據背後都標註一個權重，初始權重為 frac{1}{N} ，此時的數據錯誤率等於權重錯誤率。

2 每一輪訓練一個當前權重下錯誤率最低的 gleft( x ight)

3 迭代生成下一輪的權重

如何得到下一輪的權重：

上式表示把這下一代的數據權重放到上一代的權重錯誤率最小。

也即下一輪權重放到上一輪的分類器得到的權重錯誤率為0.5時，可以訓練處更好的 g_{2}left( x ight) 。

上式中 W_{t+1} ， R_{t+1} ，分別表示下一輪的權重放到上一輪的分類器中的正確權重和和錯誤權重和。

eg：假設上一輪的錯誤權重和是1126，正確權重和是6211

如果上一輪的錯誤權重和乘以6211，正確權重和乘以1126，這樣一來，上一輪的錯誤權重和與上一輪的正確權重和相等。但此時，數據量大，我們做一下調整。

讓上一輪的錯誤權重和乘以 frac{1126}{7337} ，讓其為a，上一輪的正確權重和乘以 frac{6211}{7337} ,讓其為b。

此時我們若a作為下一輪的錯誤權重和，b作為下一輪的正確權重和，此時就可以滿足，下一輪的權重和放到上一輪的分類器中得到的權重錯誤率為0.5。

設 varepsilon_{t} 代表 t 輪的權重錯誤率。其公式可表示如下：

正確的權重和乘以 varepsilon_{t} ，每個錯誤的權重和乘以 left( 1-varepsilon_{t} ight) 。

定義如下式子：

設A為正確的總權重和，B為錯誤的總權重和。則此時， frac{A}{ heta} 作為下一輪的正確權重和, B imes heta 作為下一輪錯誤權重和，此時才能使得下一輪的權重放到上一輪的分類器中權重錯誤率為0.5。也即將 U_{n}^{t+1} 放入 gleft( t ight) 中使得得到權 gleft( t ight) 錯誤率為0.5的分類器。

公式(7)的來源為：

更新過程如下：

但是其中的α如何計算呢？

可用如下公式：

以上就是adaboost的整個迭代過程。

接下來思考幾個問題

為什麼我們需要弱一些的樹？

完全長成的樹優缺點？

優點； varepsilon_{t}=0 權重錯誤和為0；缺點：容易產生過擬合。

如果用一顆深的樹去構造adaboost，會發生什麼事情呢？

根據公式 alpha_{t}=ln heta=lnsqrt{frac{1-varepsilon_{{t}}}{varepsilon_{t}}} ，當 varepsilon_{t}=0 時，會出現獨裁現象，也即會出現過擬合的問題。

因此完成長成的樹不能用。

決策樁概念：被剪枝過的pruned decision tree

之前講的決策樹為什麼不以acc為分裂結果，而以純度呢？

答：在大於兩層的決策樹中效果不好。

推薦閱讀：

相关文章