內建學習

內建學習(ensemble learning)通過建構并集合多個學習器完成學習任務，有時也被稱為多分類器系統(multi-classifier system)、基于委員會的學習(committee based learning)等。先産生一組“個體學習器”(invidual learner)，再用某種政策将它們結合起來。個體學習器通常由一個現有的學習算法從訓練資料中産生，例如C4.5決策樹、BP神經網絡算法等，此時內建中隻包含同種類型的個體學習器，例如“決策樹內建”中全是決策樹，“神經網絡內建”中全是神經網絡，這樣的內建是“同質”的(homogeneous)。同質內建中的個體學習器亦稱為“基學習器”(base learner)，相應的算法稱為“基學習算法”(base learning algorithm)。內建也包含不同類型的個體學習器。例如同時包含決策樹和神經網絡，這樣的內建是“異質”的(heterogeneous)。異質內建中的個體學習器由不同的學習算法生成，這時就不再有學習算法；相應的，個體學習器一般不稱為學習器，常稱為“元件學習器”(component learner)或直接稱為個體學習器。

內建學習通過将多個學習器進行組合，常可獲得比單一學習器顯著優越的泛化性能。這對“弱學習器”(weak learner)尤為明顯，是以內建學習的很多理論研究都是針對弱學習器進行的，而基學習器有時也直接稱為弱學習器。但需注意的是，雖然理論上來說使用弱學習器內建足以獲得好的性能，但在實踐中出于種種考慮，例如希望使用較少的個體學習器，或是重用關于常見學習器的一些經驗等，人們往往會使用比較強的學習器。

在一般經驗中，如果把好壞不等的東西摻到一起，那麼通常結果會是比最壞的要好一些，比最好的要壞一些。內建學習把多個學習器結合起來，如何能獲得比最好的單一學習器更好的性能呢？要獲得好的內建，個體學習器應“好而不同”，即個體學習器要有一定的“準确性”，即學習器不能太壞，并且要有“多樣性”(diversity)，即學習器具有差異。

我們來做一個簡單的分析，考慮二分類問題

和真實函數

，假定基分類器的錯誤率為

，即對每個基分類器器

有

假設內建通過簡單投票結合T個基分類器，若有超過半數的基分類器正确，則內建分類就正确

假設基分類器錯誤率互相獨立，則由Hoeffiding不等式可知，內建的錯誤率為

上式顯示出，随着內建中個體分類器數目T的增大，內建的錯誤率将指數級下降，最終趨向于零。然而我們必須注意到，上面的分析有一個關鍵假設：學習器的誤差互相獨立，在現實任務中，個體學習器是為解決同一問題訓練出來的，它們顯然不可能互相獨立！事實上，個體學習器的“準确性”和“多樣性”本身就不存在沖突。一般的，準确性很高之後，要增加多樣性就需犧牲準确性。事實上，如何産生并結合“好而不同”的個體學習器，恰是內建學習的核心。根據個體學習器的生成方式，目前的內建學習方法大緻可分為兩大類，即個體學習器存在強依賴關系，必須串行生成的序列化方法，以及個體學習器間不存在強依賴關系、可同時生成的并行化方法；前者的代表是Boosting後者的代表是Bagging和“随機森林”(Random Forest)。

Boosting是一族可将若學習器提升為強學習器的算法，這族算法的工作機制類似：先從初始訓練集訓練出一個學習器，再根據基學習器的表現對訓練樣本進行調整，使得先前基學習器做錯的訓練樣本在後續受到更多關注，然後基于調整後的樣本分布來訓練下一個基學習器，如此重複進行，直至學習器數目達到事先指定的值T，最終将這個T個基學習器進行權重結合。Boosting族算法最著名的代表是AdaBoost，如下所示，其中

，

是真實函數。

輸入：訓練集

;            基學習算法

           訓練輪數T。 過程：

for t = 1,2,...,T do

     if 

  then break

end for 輸出：

若H(x)能令指數損失函數最小化，則考慮對H(x)的偏導

令上式為零可解得

是以，有

這意味着sign(H(x))達到了貝葉斯最優錯誤率。換言之，有指數損失函數最小化，則分類錯誤率也将最小化；這說明指數損失是分類任務原本0/1損失函數的一緻性(consistent)替代損失函數。由于這個替代函數有更好的數學性質，例如它是連續可微函數，是以我們用它代替0/1損失函數作為優化目标。在AdaBoost算法中，第一個分類器

是通過直接将學習算法用于初始資料分布而得；此後疊代地生成

和

，當基分類器

基于分布

産生後，該基分類器的權重

應使得

最小化指數損失函數：

其中

，考慮指數損失函數的導數

這恰是上面算法中第6行的分類器權重更新公式。

AdaBoost算法在獲得

之後樣本分布将進行調整，使下一輪學習器

能糾正

的一些錯誤。理想的

的全部錯誤，即最小化

注意到

，上式可使用

的泰勒展開式近似為

于是理想的學習器

是一個常數，令

表示一個分布

根據指數期望的定義這等價于令

由

，有

則理想的基學習器

由此可見，理想的

将在分布

下最小化分類誤差，是以，弱分類器将基于分布

來訓練，且針對

的分類誤差應小于0.5。這在一定程度上類似“殘差逼近”的思想，考慮到

的關系，有

Boosting算法要求基學習器能對特定的資料分布進行分布，這可通過“重賦權法”(re-weighting)實施，即在訓練過程的每一輪中，根據樣本分布為每個訓練樣本重新指派一個權重。對無法接受帶權樣本的基學習算法，則可以通過“重采樣法”(re-samping)來處理，即在每一輪學習中，根據樣本分布對訓練集重新進行采樣，再通過重采樣而得到的樣本集對基學習器進行訓練。一般而言，這兩種做法沒有顯著的優劣差别。需注意的是，Boosting算法在訓練的每一輪都要檢查目前生成的基學習器是否滿足基本條件，一旦條件不滿足，則目前學習器即被抛棄，且學習過程停止。在此種情形下，初始設定的學習輪數T也許還遠未達到，可能導緻最終內建中隻包含很少的基學習器而性能不佳。若采用“重采樣法”，則可獲得“重新開機動”機會以避免訓練過程早停止，即在抛棄不滿足條件的目前基學習器之後，可根據目前分布重新對訓練樣本進行采樣，再基于新的采樣結果重新訓練出學習器，進而使得學習過程可以持續到預設的T輪完成。

從偏差-方差分解的角度看，Boosting主要關注降低偏置，是以Boosting能基于泛化能相當弱的學習器建構出很強的內建。我們以決策樹樁為基學習器。

欲得到泛化性能很強的內建，內建中的個體學習器應該盡可能互相獨立；雖然“獨立”在現實任務中無法做到，但可以設法使基學習器盡可能具有較大的差異，給定一個訓練資料集，一種可能的做法是對訓練樣本進行采樣，産生出若幹不同的子集，再從每個資料子集中訓練出一個基學習器。這樣由于訓練資料的不同，我們獲得的基學習器可望具有比較大的差異。然而，未獲得好的內建，我們同時還希望個體學習器不能太差。如果采樣出的每個子集都完全不同，則每個基學習器隻用到了一小部分訓練資料，甚至不足以進行有效學習，這顯然無法確定産生出比較好的基學習器。為解決這個問題，我們可考慮使用互相有交疊的采樣子集。

Bagging是并行式內建學習方法最顯著的代表。從名字即可看出，它直接基于自助采樣法(bootstrap sampling)給定包含m個樣本的資料集。我們先随機取出一個樣本放入采樣集中，再把該樣本放回初始初始資料集，使得下次采樣時該樣本仍可能被選中，這樣，經過m次随機采樣操作，我們得到含m個樣本的采樣集，初始訓練集中有的樣本在采樣集中出現多次，有的則從未出現。

照這樣，我們可采樣出T個含m個訓練樣本的采樣集訓練出一個基學習器，再将這些基學習器進行結合。這就是Bagging的基本流程。在對預測輸出進行進行結合時，Bagging通常對象分類任務是用簡單投票法，對回歸任務使用簡單平均法。若分類預測時出現兩個類收到同樣票數的情形，則最簡單的做法是随機選擇一個，也可以進一步考察學習器投票的置信度來确定最終勝者，Bagging的算法描述下圖所示。

           訓練輪數T. for t = 1,2,..,T do

假定基學習器的計算複雜度為O(m)，則Bagging的複雜度大緻為T(O(m)+O(s))。考慮到采樣與投票/平均過程的複雜度O(s)很小，而T通常是一個不太大的常數，是以訓練一個Bagging內建與直接使用基學習算法訓練一個學習器的複雜度同階，這說明Bagging是一個很高效的內建學習算法。另外，與标準AdaBoost隻适用于二分類不同，Bagging能不經修改地用于多分類、回歸任務。

值得一提的是，自助采樣過程還給Bagging帶來了另一個優點：由于每個基學習器隻使用了初始訓練集中的63.2%的樣本，剩下的月36.8%的樣本可用作驗證集來對泛化性能進行“包外估計”。為此需記錄每個基學習器所使用的訓練樣本，不妨令

表示

實際使用的訓練樣本集。令

表示樣本x的包外預測，即僅考慮那些未使用x訓練的基學習器在x上的預測，有

 則Bagging泛化誤差的外包估計為

事實上，外包樣本還有許多其他用途，例如當基學習器是決策時，可使用外包樣本來輔助剪枝，或用于估計決策樹中各結點的後驗機率以輔助對零訓練樣本結點的處理；當基學習器是神經網絡時，可使用外包樣本來輔助早期停止以減小過拟合的風險。從偏差-方差分解的角度看，Bagging主要關注降低方差，是以它在不剪枝決策樹、神經網絡等易受樣本擾動的學習器上效果更為明顯，我們以基于資訊增益劃分。