coursera機器學習技法筆記(7-8)——blending and bagging & Adaptive Boosting

7 Blending and Bagging

7.1 Motivation of Affregation

　　之前都是通過特征轉換達到更好的分類目的，而有另一種思路就是将多個模型的分數線性組合起來以期得到更好的效果。它們的權重應為x的函數，這樣能包含投票、取最大等多種情況。

7.2 Uniform Blending

　　本節從理論上探讨了blend的可行性：

G(x)=1T∑Tt=1gt(x)

則：

avg((gt−f)2)=avg((gt−G2))+(G−f)2

可以看出，任選一個g_t其誤差期望是大于平均後的誤差期望的。另外，令 f=0 ：

avg(Eout(gt))=avg((gt−G)2)+Eout(G)

可以看出，blend做的事就是令前一項盡量小以得到更加穩定的結果。

7.3 Linear and Any Blending

　　在給定 gt 的情況下如何求解将它們線性組合起來的權重 αn 呢。即先計算每個 gt 的結果，并将 T 個結果作為特征，對它們進行二次線性訓練，其得到的權重即對應gt的 αt 。該方法即linear Blending。這裡需要注意的是， αt 可能為負，我們可以把它的符号給 gt ，這意味着 gt 起了反作用，我們将它反向使用。

　　另外，在選擇 gt 的時候應注意如果将資料集劃分為了訓練集和驗證集，最後計算得到 αt 後應當在完整資料集上重新訓練 gt 。

　　另外，如果在兩次訓練中不使用線性模型，而使用非線性模型，則該方法稱為Any Blending或是stacking。如果使用非線性模型，應當注意過拟合問題。

7.4 Bagging Booststrap Aggregation

　　如果 gt 之間差距很大，那麼它們組合起來效果越好。而之前提到過一種方法就是，通過同一個分布采樣出 N 個資料集，并在這N個資料集上跑出 N 個gt。這種思路的一種實作方法是在資料集中進行re-sample，即經過多次有放回采樣獲得 N 個資料集。

8 Adaptive Boosting

8.1 Motivation of Boosting

　　本節主要講述了boost算法的動機，即一個分類器沒有辦法很好的分類，但是當一個分類器犯錯之後加大犯錯樣本的權重，讓後來的分類器更重視這個樣本，最後把所有方法組合起來能得到一個好的分類器。

8.2 Diversity by Re-weighting

　　在bootstrap中我們通過對訓練集進行可重複采樣得到不同的訓練集，我們可以把這一過程看做是對不同樣本集進行了權重處理。是以，當我們使用多個分類器進行聚合的時候，我們希望不同的分類器通過對樣本進行不同權重的方法使他們表現的差別很大。具體的來說，就是在給定分類器gt所使用的樣本權重 u(t)n ，分類器 gt+1 所使用的樣本權重 u(t+1)n 的情況下， gt 在樣本權重 u(t+1)n 的條件下所得到的分類表現接近于 12 .

　　我們希望的是

ϵ=∑Nn=1u(t+1)nI[yn≠gt(xn)]∑Nn=1u(t+1)n=12

可以看到，分子是分類錯誤的權重，分母是分類正确與分類錯誤的權重和，而我們要做的是讓分類錯誤的權重和等于分類正确的權重和。是以，假設分類錯誤的權重和是1126，分類正确的權重和是6211，則在每個錯誤分類的權重上乘以6211，在每個正确分類的權重上乘以1126即可。注意的是，乘以的比例可以拉伸，是以将6211拉伸成正确率，将1126拉伸成錯誤率。

8.3 Adaptive Boosting Algorithm

　　接上節的思路，我們可以讓錯誤的樣本權重乘以 1−ϵϵ−−−√ ，而讓正确的樣本權重除以 1−ϵϵ−−−√ ，這樣的效果與上述一緻(可以兩者相除來進行驗證)。可以看到，當正确率大于0.5的時候，錯誤樣本權重上升而正确樣本權重下降。另外，為了使得 g1 在 Ein 上表現最好，我們令最開始的樣本權重為 1N 。

　　由此，我們得到了每一輪訓練之後的樣本權重變化方式，那麼還有個問題就在于算法如何組合起來。這裡可以排除投票法，因為不能讓一個在某些樣本上表現很差的 g 也和其他表現好的g有相同的權重，是以我們根據g的表現決定它們的權重，即 1−ϵϵ−−−√ 的函數。

　　這裡使用了 ln((1−ϵ)/ϵ−−−−−−−√) 作為權重的決定函數，因為當 ϵ=12 的時候，這個分類器接近于亂猜，就給他0的權重，當 ϵ 很小的時候，則權重無限大，說明我們很信賴這個分類器。

最後得到線性組合是：

f(x)=sign(∑Tt=1αtgt(x))

另外，從VC維的角度說，該算法的誤差上限是：

Eout(G)≤Ein(G)+O((O(dvc(H)TlogT)logNN)−−−−−−−−−−−−−−−−−−−√)

　　根據作者的相關證明，當每個分類器的錯誤率略大于一半時，經過 T=O(logN) 次疊代， Ein(G)=0 。同時由于 T 的複雜度是logN的，是以右邊 O(dvc(H)TlogT) 也會相應很小，故當 N 比較大時，這會是個好算法。

8.4 Adaptive Boosting in Action

　　在實際上經常應用于adaboost的算法是decision stump：

hs,i,θ(x)=s⋅sign(xi−θ)

這個分類器的意思是，在所有次元裡面選擇一個次元、一個門檻值以及一個方向，據此決定這個樣本的分類，例如當第三個向量大于2時為負。選擇它是因為實作簡單，隻需 O(d⋅NlogN) 的時間複雜度就可以訓練出來。