台灣大學機器學習：Ensemble 隨堂筆記

05-13

本筆記中的所有取自課件的多媒體版權屬於台灣大學。

Ensemble的架構就是，假設現在有一組分類器，現在把這組分類器組合起來使其比原來每個單獨的分類器的性能要好，一般是希望每個分類器都有不同的屬性。

首先是Bagging這種Ensemble的方法。先回顧一下，在機器學習中會有Bias和Variance的trade-off，如果現在模型比較簡單，Bias會比較大而Variance會比較小，反過來模型比較複雜，則Bias會比較小而Variance會比較大。從下圖中可以看到隨著模型的複雜度上升，Bias的error會不斷下降而Variance的error的會不斷上升。

Bagging就是創造不同的數據集，再不同的數據集訓練一個複雜的模型，這時雖然單個模型的Variance會很大，但是當將這些複雜的模型集合起來，Variance相對就不會那麼大。具體地說，假設現在有 $N$ 個訓練樣例，然後有放回地抽取 $N$ 個訓練樣例，例如如下所示用該方法創建了4個不同的數據集。接著分別用4個複雜的模型對其進行訓練學習。

然後在測試階段把測試數據分別放入這4個訓練好的模型中，最後對4組輸出結果進行平均（回歸問題）或者投票（分類問題）操作，這時最後的結果是robust的。一般當模型（例如，決策樹）非常複雜，容易出現過擬合時，可以考慮使用Bagging。

實際上決策樹是很容易過擬合的，使用單個決策樹的模型的泛化能力可能會較差。所以對決策樹作Bagging就是隨機森林，在每一次要產生決策樹分支的時候，要隨機地決定哪一些特徵是不能用的，從而使生成的每一課決策樹的差異化更大。隨機森林一般大概有33%的數據是out of bag的，這就可以不用劃分驗證集，直接在訓練集上訓練並觀察訓練結果。

下面是含有100顆決策樹的隨機森林在不同樹深度下的語義分割的結果，可以看到Bagging在樹深度為5，即是模型比較簡單的時候不能提高表現性能，只是降低Variance，使得決策邊界更加的平滑。

與Bagging是用在很複雜的單個模型上不同，Boosting是用在很弱很簡單的模型上。假設現在有一個分類演算法在訓練集上有超過50%的錯誤率，Boosting可以保證在最後使得演算法的錯誤率降低到接近於0%。Boosting的架構是，首先得到一個弱分類器 $f_{1}(x)$ ，然後找到另一個分類器 $f_{2}(x)$ 去幫助 $f_{1}(x)$ 。這裡要注意的是 $f_{1}(x)$ 和 $f_{2}(x)$ 不能夠太相似，否則不能起到幫助作用。得到第二個分類器 $f_{2}(x)$ 後不斷重複以上步驟，最後將得到的所有分類器全部結合起來。

接下的要討論的是如何得到不同的分類器。這裡可以使用Re-sampling的方從訓練數據集得到新的數據集從而得到不同的訓練數據集。還可以對訓練數據集進行Re-weighting的方法來形成一個新的數據集，做法是對每一個訓練樣例一個權值，例如下面的例子中用u來代表每個訓練樣例的權值，且將u都初始化為1，現在將權值改為 $u_{1}=0.4,u_{2}=2.1,u_{3}=0.7$ ，這就相當於製造了一個新的數據集。對訓練集改變其權值是不會影響訓練，因為訓練的目標函數為 $L(f)=sum_{n}l(f(x_{n}),widehat{y}^{n})$ ，訓練的目標是最小化目標值和預測值的誤差，現在對這個目標函數加上權值u，變為 $L(f)=sum_{n}u^{n}l(f(x_{n}),widehat{y}^{n})$ ，所以如果訓練樣例的u比較大，那麼這個訓練樣例在優化的過程就會被更多的考慮。

接著介紹Adaboost，其做法是先訓練好一個分類器 $f_{1}(x)$ ，接著Re-weighting訓練數據集在 $f_{1}(x)$ 中得到很差的結果，然後再用一個 $f_{2}(x)$ 在這組訓練集上進行訓練。那現在的問題是如何找到讓$f_{1}(x)$失效的訓練數據集。首先看 $f_{1}(x)$ 在訓練集上的錯誤率的計算， $epsilon_{1}=frac{sum_{n}u_{1}^{n}delta(f_{1}(x^{n}) eq widehat{y}^{n})}{Z_{1}}$ ，其中 $Z_{1}=sum_{n}u_{1}^{n}$ 。然後將樣例權值從 $u_{1}^{n}$ 變為 $u_2^{n}$ ，使得 $frac{sum_{n}u_{2}^{n}delta(f_{1}(x^{n}) eq widehat{y}^{n})}{Z_{2}}=0.5$ ，接著使用 $f_{2}(x)$ 訓練樣例權值為 $u_2^{n}$ 的訓練集。

下面是一個具體的例子，假設現在有4個訓練數據，這個4個訓練數據的u都為1，用這4個訓練數據去訓練一個分類器 $f_{1}(x)$ ，這時 $f_{1}(x)$ 可以對其中三個訓練數據正確分類，這時的 $epsilon_{1}=0.25$ 。接著改變u，對 $f_{1}(x)$ 分類的正確的數據的u變小，分類不正確的u變大，在Re-weighting訓練數據集上 $f_{1}(x)$ 的錯誤率為0.5。在Re-weighting訓練數據集上用 $f_{2}(x)$ 進行訓練，因為它對根據新數據學習的，所以 $epsilon_2 < 0.5$ 。

接下來是講述如何進行Re-weighting操作，如果 $x^{n}$ 被 $f_{1}$ 誤分類，則將 $u_{1}^{n}$ 乘以 $d_{1}$ 提高權值得到 $u_{2}^{n}$ ；如果 $x^{n}$ 被 $f_{1}$ 正確分類，則將 $u_{1}^{n}$ 除以 $d_{1}$ 降低權值得到 $u_{2}^{n}$ ，其中 $d_{1}>1$ 。

下面是具體的數學推導。

AdaBoost的具體演算法如下所示。

得到一組分類器後，可以直接將其相加，但這不是最好的做法，因為這裡面的分類器有好有壞，更好的做法是給每一個分類器一個權值 $alpha_{t}$ 並全部加起來再取正負號，其中 $alpha_{t}$ 是改變訓練數據權值的參數。把不同的錯誤率 $epsilon$ 代入 $alpha_{t}=lnsqrt{(1-epsilon_{t})/epsilon_{t}}$ ，可以看到錯誤率 $epsilon_{t}$ 越低， $alpha_{t}$ 的值越大，反之亦然。

下面有一個AdaBoost的簡單的例子，首先將所有的訓練數據的權值設為1，當 $t=1$ 時使用 $f_{1}(x)$ 劃分數據集，藍色區域是表示正例，粉紅色區域是表示負例，現在可以看到有3個數據是劃分錯誤的，這時 $epsilon_{1}=0.30,d_{1}=1.53,alpha_{1}=0.42$ ，因此分類正確的數據的權值變小為0.65，分類錯誤的數據的權值變大為1.53。

現在有了一組新的權值，當 $t=2$ 時使用 $f_{2}(x)$ 劃分數據集，可以看到有3個數據是劃分錯誤的，這時 $epsilon_{2}=0.21,d_{2}=1.94,alpha_{2}=0.66$ ，將分類正確的數據的權值變小，分類錯誤的數據的權值變大。

現在有了一組新的權值，當 $t=3$ 時使用 $f_{3}(x)$ 劃分數據集，可以看到有3個數據是劃分錯誤的，這時 $epsilon_{3}=0.13,d_{3}=2.59,alpha_{3}=0.95$ ，將分類正確的數據的權值變小，分類錯誤的數據的權值變大。

假設現在只進行3次迭代就結束的訓練，最後將每個分類器與對應的 $alpha_{t}$ 相乘再取正負號得到最終的分類器。左上角的區域，三個分類器都認為是藍色，所以為藍色，左中的區域第一個分類器認為是紅色，第二、三個分類器認為是藍色，因為二、三相加的結果比一大，所以認為是藍色，剩下的四個區域按照相應的方法確定區域的顏色。

下面是證明如果有更多的 $f_{t}$ （更多的迭代次數T）， $H(x)$ 可以在訓練集上得到越來越小的錯誤率，這也是證明增加越多的弱分類器，可以增加最後的分類器的表現。

接下來是AdaBoost的一個神秘的現象，在下圖中橫軸是訓練迭代的次數，縱軸是錯誤率，下面的曲線是在訓練數據上的錯誤率，上面的曲線是在測試數據上的錯誤率，神奇的地方在於訓練集上的錯誤率大概在5次迭代後就變為0，但在根據AdaBoost的演算法中錯誤率是無法為0的。雖然訓練集的錯誤率已經為0，但是在測試集中的誤差仍然在下降。

現在來分析一下當中的原因，定義最後的分類器 $H(x)=signig(sum_{t=1}^{T}alpha_{t}f_{t}(x)ig)$ ，其中 $g(x)=sum_{t=1}^{T}alpha_{t}f_{t}(x)$ ， $Margin=widehat{y}g(x)$ ，這裡 $Margin>0$ 為分類正確，同時希望 $Margin$ 越大越好。從下圖的圖像中的曲線可以看到當 $widehat{y}$ 和 $g(x)$ 同號並越來越大時，AdaBoost的目標函數曲線（紅色曲線）只是越來越接近於零，這時測試誤差仍在下降的原因。

下面是用不同數量的弱分類器的AdaBoost的語義分割的實驗對比。

Gradient Boosting是AdaBoost更一般化的版本，這是在T次迭代中，每一次都要找 $f_{t}(x),alpha_{t}$ 來提升 $g_{t-1}(x)$ ，其中 $g_{t-1}(x)$ 將前 $T-1$ 次迭代中得到的弱分類器加權求和的結果，接著將 $f_{t}(x),alpha_{t}$ 和 $g_{t-1}(x)$ 互補得到 $g_{t}(x)$ ，最後經過 $T$ 次迭代後得到最終的 $H(x)$ 。現在的問題是如何學習目標 $g(x)$ ，做法是定義目標函數 $L(g)=sum_{n}lig(widehat{y}^{n},g(x^{n})ig)$ ，然後調整參數來優化目標函數，這裡 $L(g)=sum_{n}exp(-widehat{y}^{n}g(x^{n}))$ 並希望 $widehat{y}^{n}$ 和 $g(x^{n})$ 盡量同號和同號相乘的結果越大越好。

接下來就是要最小化 $L(g)$ ，首先計算 $L(g)$ 對 $g$ 偏微分得到梯度，再用這個梯度更新 $g_{t-1}$ 得到 $g_{t}$ 來最小化損失函數。而根據上面講到的對於Boosting，是通過 $g_{t-1}(x)+alpha_{t}f_{t}(x)$ 得到 $g_{t}$ ，現在希望微分項 $-etafrac{partial L(g)}{partial g}$ 與 $alpha_{t}f_{t}(x)$ 具有相同的方向。

即 $sum_{n}exp(-widehat{y}^{n}g_{t-1}(x^{n}))(widehat{y}^{n})$ 與 $alpha_{t}f_{t}(x)$ 的方向越一致越好，這就可以轉換成最大化這兩項相乘的值。現在要最大化的式子變為 $sum_{n}exp(-widehat{y}^{n}g_{t-1}(x^{n}))(widehat{y}^{n})f_{t}(x)$ 。而式子中的 $exp(-widehat{y}^{n}g_{t-1}(x^{n}))$ 是在AdaBoost中獲得的權值。

下步是解決如何決定 $alpha_{t}$ 讓 $L(g)$ 的值最小，這時可以通過 $frac{partial L(g)}{partial alpha_{t}}=0$ 計算得到最優 $alpha_{t}$ 。

假設現在有對同一個數據集訓練了4個不用的模型，現在要用stacking的方法將4個模型的輸出合併起來。Stacking的做法是將4個模型的輸出作為輸入，通過一個最終的分類器（如果前面的模型用了較為複雜的模型，這裡可以考慮使用簡單的模型，例如邏輯回歸）。這時需要把訓練數據集分成兩個部分，一部分用來訓練前面4個模型，另外一部分用來訓練最終的模型。