機器學習: Ensemble learning之Bagging、Boosting和AdaBoost
Bagging、Boosting和AdaBoost (Adaptive Boosting)都是Ensemble learning(集成學習)的方法(手法)。Ensemble learning在我念書的時後我比較喜歡稱為多重辨識器，名稱很直覺，就是有很多個辨識器。其概念就是「三個臭皮匠勝過一個諸葛亮」，如果單個分類器表現的很好，那麼為什麼不用多個分類器呢？
Ensemble Learning基本條件是:每個分類器之間應該要有差異，每個分類器準確率需大於0.5。
如果用的分類器沒有差異，那只是用很多個一樣的分類器來分類，結果合成起來是沒有差異的。如果分類器的精度p<0.5，隨著ensemble規模的增加，分類準確率不斷下降；如果精度大於p>0.5，那麼最終分類準確率可以趨向於1。
既然稱為多重辨識器或集成學習顧明思義就是要產生很多個分類器，所以目標要放在怎麼產生多個分類器，用不同手法就可以產生不同的分類器。
今天介紹的Bagging、Boosting和Adaboost都是產生多個分類器的手法。
Bagging
Bagging概念很簡單，從訓練資料中隨機抽取(取出後放回，n<N)樣本訓練多個分類器(要多少個分類器自己設定)，每個分類器的權重一致最後用投票方式(Majority vote)得到最終結果，而這種抽樣的方法在統計上稱為bootstrap。
Note: Bagging的精神在於從樣本中抽樣這件事情，如果模型不是分類問題而是預測的問題，分類器部份也可以改成regression，最後投票方式改成算平均數即可。如果是用Bagging會希望單一分類器能夠是一個效能比較好的分類器。
Bagging的優點在於原始訓練樣本中有噪聲資料(不好的資料)，透過Bagging抽樣就有機會不讓有噪聲資料被訓練到，所以可以降低模型的不穩定性。
Boosting
Boosting算法是將很多個弱的分類器(weak classifier)進行合成變成一個強分類器(Strong classifier)，和Bagging不同的是分類器之間是有關聯性的，是透過將舊分類器的錯誤資料權重提高，然後再訓練新的分類器，這樣新的分類器就會學習到錯誤分類資料(misclassified data)的特性，進而提升分類結果。
Boosting的概念很玄，我自己的解讀是舊的分類器在訓練有些資料落在confusion area，如果再用全部的data下去訓練，錯的資料永遠都會判錯，因此我們需要針對錯誤的資料去學習(將錯誤的資料權重加大)，那這樣新訓練出來的分類器才能針對這些錯誤判讀的資料得到好的結果。
Note: 由於Boosting將注意力集中在分類錯誤的資料上，因此Boosting對訓練資料的噪聲非常敏感，如果一筆訓練資料噪聲資料很多，那後面分類器都會集中在進行噪聲資料上分類，反而會影響最終的分類性能。
對於Boosting來說，有兩個關鍵，一是在如何改變訓練資料的權重；二是如何將多個弱分類器組合成一個強分類器。而且存在一個重大的缺陷：該分類算法要求預先知道弱分類器識別準確率的下限。
AdaBoost
AdaBoost算法，是一種改進的Boosting分類算法。方式是提高被前幾個分類器線性組合的分類錯誤樣本的權重，這樣做可以讓每次訓練新的分類器的時後都聚焦在容易分類錯誤的訓練樣本上。每個弱分類器使用加權投票機制取代平均投票機制，只的準確率較大的弱分類器有較大的權重，反之，準確率低的弱分類器權重較低。
Note: 這邊我有參考李宏毅老師的課程(ML Lecture 22: Ensemble)，如果想知道更多可以聽聽他的課程。
AdaBoost的手法: 讓判斷錯誤的train data提高權重，讓產生新的權重的training set讓舊的分類器f1(x) fail掉，但在新的分類器上就去加強學這些權重較大的training set。
第一個分類器為f1(x)，其在training data的錯誤率為ε1(公式如下)，假設ε1<0.5，在機器學習內，學習出來的分類器錯誤率不太可能會大於0.5，但如果分類器錯誤率真的>0.5怎麼辦，如果是二分類問題那就讓結果正的變負的，負的變正的，那錯誤率就<0.5。
δ為step function，wi_1為第i個training data的權重，yi_hat為第i個training data的預測結果。
那回到剛剛的問題，「要怎麼讓f1(x) fail掉?」
答案: Re-weighting training data讓錯誤率當好等於0.5，那f1(x)就是fail掉
那衍生出的問題是，要怎麼達成錯誤率等於0.5→那就把權重改掉(w2取代w1)就好了阿，
範例「要怎麼讓f1(x) fail掉」:
假設有5個樣本
我們現在用某一種演算法訓練出第一個分類器(f1)，因為是第一個分類器所以每個樣本的權重要先假設一樣(w1到w5都先初始化為1)。
f1(x)判讀結果: x1, x2, x3, x4都判對，x5判錯，此時錯誤率為0.2 (ε1=0.2)
因為x1, x2, x3, x4都判對所以權重要變小，這邊先假設w1,w2,w3,w4更新為1/2，然後因為x5判錯權重加大，變成2。當權重更變時，錯誤率會跟著變成 2/(1/2+1/2+1/2+1/2+2)=2/4=0.5。
所以更變權重，就可以達到讓舊的分類器的錯誤率變差。但新的分類器是看新的權重去訓練，所以ε2<0.5。
看完了範例可以知道怎麼re-weighting training data讓f1爛掉，在去訓練f2，方法為
其中d1>1。
d1要設為多少，才會讓錯誤率為0.5?
其中
d1一定大於1，所以平方根只找正數。
Recall: 這邊為了方程式方便我們會在d1上作個轉換
AdaBoost algorithm flow
初始化權重不用1，採用1/n其實用意一樣，但因為在權重我們喜歡用機率的概念，所以全機率為1，因此我們用1/n來做權重初始化。
最後我們會得到f1(x), f2(x), fL(x)個分類器。
我們需要把L個分類器的結果作weighted-sum合成。
和training data的權重不太一樣，錯誤率越低的分類器在最後結果的合成上要佔較大的權重，下面假設錯誤率分別為0.1, 0.2, 0.4下的權重變化：
εk=0.1, αk=0.5*ln(((1–0.1))/0.1)=1.0986
εk=0.2, αk=0.5*ln(((1–0.2))/0.2)=0.6931
εk=0.4, αk=0.5*ln(((1–0.4))/0.4)=0.2027
Note: 多重辨識器合成有很多種方法，有Majority Vote，sum-out，weighted-sum，或特殊的fuzzy fusion。
下圖為用AdaBoost的範例:
Bagging與Boosting的區別之處：
訓練樣本:
Bagging: 每一次的訓練集是隨機抽取(每個樣本權重一致)，抽出可放回，以獨立同分布選取的訓練樣本子集訓練弱分類器。
Boosting: 每一次的訓練集不變，訓練集之間的選擇不是獨立的，每一是選擇的訓練集都是依賴上一次學習得結果，根據錯誤率(給予訓練樣本不同的權重)取樣。
分類器:
Bagging: 每個分類器的權重相等。
Boosting: 每個弱分類器都有相應的權重，對於分類誤差小的分類器會有更大的權重。
每個分類器的取得:
Bagging: 每個分類器可以並行生成。
Boosting: 每個弱分類器只能依賴上一次的分類器順序生成。
Bagging和Boosting這兩種方法是比較常見的ensemble learning的方法，當然ensemble learning還有很多不同的方法，比如
1. 將不同的分類器進行合成提高單一分類器的效果例如SVM+k-NN+MLP+QDA+BNC等。
2. 很多個SVM合成，方式為每個SVM給不同的kernel function或是kernel參數。
3. Random subspace: 這個概念跟bagging很像，不同的是bagging是從訓練樣本去抽樣產生不同的訓練集來訓練分類器，但Random subspace是feature bagging，從特徵中去抽樣，然後訓練多個分類器做合成，通常用在非常高維度的資料中。當然也有衍生出來的feature Adaboosting。
但不論用哪種方式都是把多個分類器整合出一個結果，只是整合的方式不一樣，最終得到不一樣的效果。
Note: 因為Decision tree最近比較紅，所以提一下
1. Random Forest : Bagging + Decision tree
2. Boosting Tree : AdaBoost + Decision tree
3. GBDT : Gradient Boost + Decision tree
