Bagging和Boosting-有解無憂

集成學習

　　在集成學習中，我們會訓練多個模型（通常稱為「弱學習器」）解決相同的問題，并將它們結合起來以獲得更好的結果，最重要的假設是：當弱模型被正確組合時，我們可以得到更精確和/或更魯棒的模型，Baggging 和Boosting都屬于集成學習的方法，模型融合，將弱分類器融合之后形成一個強分類器，而且融合之后的效果會比最好的弱分類器更好，

bagging

　　Bagging演算法（英語：Bootstrap aggregating，引導聚集演算法），又稱裝袋演算法，Bagging演算法可與其他分類、回歸演算法結合，提高其準確率、穩定性的同時，通過降低結果的方差，避免過擬合的發生，

基本思想

　　1.給定一個弱學習演算法,和一個訓練集; 　　2.單個弱學習演算法準確率不高; 　　3.將該學習演算法使用多次,得出預測函式序列,進行投票; 　　4.最后結果準確率將得到提高.

演算法步驟

　　給定一個大小為n的訓練集D，Bagging演算法從中均勻、有放回地（即使用自助抽樣法）選出m個大小為n'的子集Di，作為新的訓練集（在訓練集中，有些樣本可能被多次抽取到，而有些樣本可能一次都沒有被抽中），在這m個訓練集上使用分類、回歸等演算法，則可得到m個模型，再通過取平均值、取多數票等方法，即可得到Bagging的結果，

Bagging演算法特性

　　1.Bagging通過降低基分類器的方差，改善了泛化誤差，　　2.其性能依賴于基分類器的穩定性；如果基分類器不穩定，bagging有助于降低訓練資料的隨機波動導致的誤差；如果穩定，則集成分類器的誤差主要由基分類器的偏倚引起，　　3.由于每個樣本被選中的概率相同，因此bagging并不側重于訓練資料集中的任何特定實體，

boosting

提升方法（Boosting），是一種可以用來減小監督式學習中偏差的機器學習演算法，弱學習者一般是指一個分類器，它的結果只比隨機分類好一點點；強學習者指分類器的結果非常接近真值，

　　大多數提升演算法使用弱學習分類器組成，并將其結果加入一個最終的成強學習分類器，加入的程序中，通常根據它們的分類準確率給予不同的權重，加和弱學習者之后，資料通常會被重新加權，來強化對之前分類錯誤資料點的分類，Boosting會減小在上一輪訓練正確的樣本的權重，增大錯誤樣本的權重，（對的殘差小，錯的殘差大）梯度提升的Boosting方式是使用代價函式對上一輪訓練出的模型函式f的偏導來擬合殘差，

經典Boosting方法

　　Boosting系列演算法最經典的包括AdaBoost演算法和GBDT演算法，

1.AdaBoost演算法

　　AdaBoost，是英文"Adaptive Boosting"（自適應增強）的縮寫，它的自適應在于：前一個基本分類器分錯的樣本會得到加強，加權后的全體樣本再次被用來訓練下一個基本分類器，同時，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率或達到預先指定的最大迭代次數，　　Adaboost 迭代演算法步驟： 　　（1）初始化訓練資料的權值分布，如果有N個樣本，則每一個訓練樣本最開始時都被賦予相同的權值：1/N，　　（2）訓練弱分類器，具體訓練程序中，如果某個樣本點已經被準確地分類，那么在構造下一個訓練集中，它的權值就被降低；相反，如果某個樣本點沒有被準確地分類，那么它的權值就得到提高，然后，權值更新過的樣本集被用于訓練下一個分類器，整個訓練程序如此迭代地進行下去，　　（3）將各個訓練得到的弱分類器組合成強分類器，各個弱分類器的訓練程序結束后，加大分類誤差率小的弱分類器的權重，使其在最終的分類函式中起著較大的決定作用，而降低分類誤差率大的弱分類器的權重，使其在最終的分類函式中起著較小的決定作用，換言之，誤差率低的弱分類器在最終分類器中占的權重較大，否則較小，

2.GBDT演算法

　　GBDT也是集成學習Boosting家族的成員，但是卻和傳統的Adaboost有很大的不同，回顧下Adaboost，我們是利用前一輪迭代弱學習器的誤差率來更新訓練集的權重，這樣一輪輪的迭代下去，GBDT也是迭代，使用了前向分布演算法，但是弱學習器限定了只能使用CART回歸樹模型，同時迭代思路和Adaboost也有所不同，　　在GBDT的迭代中，假設我們前一輪迭代得到的強學習器是ft?1(x)ft?1(x), 損失函式是L(y,ft?1(x))L(y,ft?1(x)), 我們本輪迭代的目標是找到一個CART回歸樹模型的弱學習器ht(x)ht(x)，讓本輪的損失函式L(y,ft(x)=L(y,ft?1(x)+ht(x))L(y,ft(x)=L(y,ft?1(x)+ht(x))最小，也就是說，本輪迭代找到決策樹，要讓樣本的損失盡量變得更小，　　GBDT的思想可以用一個通俗的例子解釋，假如有個人30歲，我們首先用20歲去擬合，發現損失有10歲，這時我們用6歲去擬合剩下的損失，發現差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有一歲了，如果我們的迭代輪數還沒有完，可以繼續迭代下面，每一輪迭代，擬合的歲數誤差都會減小，

Bagging，Boosting二者之間的區別

1）樣本選擇：

Bagging：訓練集是在原始集中有放回選取的，從原始集中選出的各輪訓練集之間是獨立的，

Boosting：每一輪的訓練集不變，只是訓練集中每個樣例在分類器中的權重發生變化，而權值是根據上一輪的分類結果進行調整，

2）樣例權重：

Bagging：使用均勻取樣，每個樣例的權重相等

Boosting：根據錯誤率不斷調整樣例的權值，錯誤率越大則權重越大，

3）預測函式：

Bagging：所有預測函式的權重相等，

Boosting：每個弱分類器都有相應的權重，對于分類誤差小的分類器會有更大的權重，

4）并行計算：

Bagging：各個預測函式可以并行生成

Boosting：各個預測函式只能順序生成，因為后一個模型引數需要前一輪模型的結果，

為什么說bagging是減少variance，而boosting是減少bias？

　　Bagging對樣本重采樣，對每一重采樣得到的子樣本集訓練一個模型，最后取平均，由于子樣本集的相似性以及使用的是同種模型，因此各模型有近似相等的bias和variance（事實上，各模型的分布也近似相同，但不獨立），由于 $E[\frac{\sum X_i}{n}]=E[X_i]$ 所以bagging后的bias和單個子模型的接近，一般來說不能顯著降低bias，另一方面，若各子模型獨立，則有 $Var(\frac{\sum X_i}{n})=\frac{Var(X_i)}{n}$ ，此時可以顯著降低variance，若各子模型完全相同，則 $Var(\frac{\sum X_i}{n})=Var(X_i)$ ，此時不會降低variance，bagging方法得到的各子模型是有一定相關性的，屬于上面兩個極端狀況的中間態，因此可以一定程度降低variance，為了進一步降低variance，Random forest通過隨機選取變數子集做擬合的方式de-correlated了各子模型（樹），使得variance進一步降低，（用公式可以一目了然：設有i.d.的n個隨機變數，方差記為 $\sigma^2$ ，兩兩變數之間的相關性為 $\rho$ ，則 $\frac{\sum X_i}{n}$ 的方差為 $\rho*\sigma^2+(1-\rho)*\sigma^2/n$ ，bagging降低的是第二項，random forest是同時降低兩項，詳見ESL p588公式15.1），boosting從優化角度來看，是用forward-stagewise這種貪心法去最小化損失函式 $L(y, \sum_i a_i f_i(x))$ ，例如，常見的AdaBoost即等價于用這種方法最小化exponential loss： $L(y,f(x))=exp(-yf(x))$ ，所謂forward-stagewise，就是在迭代的第n步，求解新的子模型f(x)及步長a（或者叫組合系數），來最小化 $L(y,f_{n-1}(x)+af(x))$ ，這里 $f_{n-1}(x)$ 是前n-1步得到的子模型的和，因此boosting是在sequential地最小化損失函式，其bias自然逐步下降，但由于是采取這種sequential、adaptive的策略，各子模型之間是強相關的，于是子模型之和并不能顯著降低variance，所以說boosting主要還是靠降低bias來提升預測精度，