李日天

Ensemble learning A survey是2018年發表的一篇關于集成學習的綜述性論文

發展

　在Surowiecki的書中The Wisdom of Crowds，當符合以下標準時，大眾的智慧可能會超過一個決策者

　　1. 獨立性:一個人的觀點不受他人觀點的影響。

　　2. 分散化:一個人能夠根據當地信息進行專門化和得出結論。

　　3.多樣性:一個人應該持有個人意見，即使它只是對已知事實的古怪解釋。

　　4. 聚合:存在將個人判斷轉變為集體決策的機制。

　這些概念在監督學習的背景下的表現已經被探索，Tukey (1977)提出了兩個線性回歸模型的集合。Tukey建議對原始數據擬合第一個線性回歸模型，對殘余的擬合第二個線性模型。Dasarathy和Sheela(1979)建議使用兩個或兩個以上不同類別的分類器組成一個分類性能更好的系統。90年代在這一領域取得了重大進展。Hansen and Salamon(1990)表明，在集成神經網絡時，可以降低神經網絡的泛化誤差。Schapire(1990)展示了在一個可能近似正確的意義上組合幾個弱學習器如何勝過一個強學習器。這項工作為著名的AdaBoost (adaptive boosting)算法奠定了基礎。

　集成學習的優點：1）過擬合避免。 2）計算性能優勢，集成學習降低了陷入局部最小值的風險。 3）最優假設可能在任何單一模型的空間之外。通過結合不同的模型，可以擴展搜索空間，從而更好地適應數據空間。

　集成學習處理的一些挑戰：

　　1）類別不平衡：許多算法面對類別不平衡時，偏好多數類，忽略少數類。集成學習可以應對這樣的問題，創建一個集合，其中每個基學習器都使用數據的是平衡子樣本進行訓練(Nikulin & Ng, 2009)。將隨機欠采樣技術與集成技術(如bagging或boost)相結合，可以顯著提高對階級不平衡問題的預測性能(Galar, Fernandez, Barrenechea, Bustince， & Herrera, 2012)。EUSBoost利用改進的欠采樣來促進基學習器的多樣性(Galar, Fernandez, Barrenechea， & Herrera, 2013)。

　　2）概念漂移：在許多實時機器學習應用程序中，特征和標簽的分布往往會隨著時間而改變，這種現象經常會影響模型的預測性能。動態加權多數(DWM)(Kolter & Maloof, 2003)，根據預測性能的變化動態創建和刪除單個決策樹。另一項研究考察了集成多樣性水平如何影響它們對新概念的概括(Minku, White， & Yao, 2010)。這項工作還表明，基學習器多樣性可以減少由漂移引起的“誤差的初始增加”（initial increase in error）。DDD(Minku & Yao, 2012)方法，在漂移檢測發生之前使用低多樣性森林。在檢測到漂移后，訓練新的低多樣性森林和高多樣性森林，并根據(a)老的高多樣性森林，(b)新的低多樣性森林和(c)老的低多樣性森林的加權多數投票對新實例進行預測。關于概念漂移的更多介紹可以參考我上一篇論文閱讀。

　　3）維度災難：增加輸入到機器學習模型中的特征的數量通常會成倍地增加搜索空間，因此，無法推廣的擬合模型的概率也會增加。(Bryll, Gutierrez-Osuna和Quek，2003)引入了屬性bagging (AB)，一種使用隨機選擇的特征子集來訓練誘導器的方法。AB還試圖通過評估不同子集大小所獲得的精度來確定特征子集的合適大小。(IDF; Huang, Fang, & Fan, 2010)通過應用指定的特征選擇機制來處理高維數據集。Rokach(2008)提出了一種搜索特征集最佳互斥劃分的算法，取代了隨機劃分。 最優特征集劃分(OFSP)方法創建固定數量的特征視圖，以降低維數和優化精度(Kumar & Minz, 2016)。

集成學習模型訓練策略

　集成模型一般有兩點原則，1）多樣性：的優越性能主要是由于使用了各種“inductive biases”(Deng, Runger, Tuv, & Vladimir, 2013). 2）表現性能，至少應該比隨機猜測高。

　不同類基學習器的集成并不總是能提高預測性能(Bi, 2012)。整體集成模型的預測性能  與 不相關的基學習器造成錯誤程度 是正相關的(Ali & Pazzani, 1995).

   (Chan & Stolfo, 1995a) 對不同的基學習器使用不同的訓練樣本，樣本可能是隨機的，也可能是基于類別分布的。

　(Brown, Wyatt, & Tiňo, 2005) 改變基學習器的收斂路徑來產生不同的學習器，例如，決策樹中在選擇最佳劃分屬性時加入隨機性。

　Distributing neighbors (Maudes, Rodríguez, & García-Osorio, 2009) 是一種通過生成原始特征的不同組合來擴展特征空間的方法

　(Lin & Chen, 2012)通過改變一些超參數來獲得不同的學習器。例如，用不同的學習率、不同的層次和屬性等來訓練一個神經網絡誘導器。

　(Chawla, Hall, Bowyer, & Kegelmeyer, 2004). horizontal partitioning水平分割數據集，將數據集分成包含整個特征集的多個集合。

　(Rokach, 2008). Vertical partitioning垂直分割將數據集分為使用相同樣本，不同特征的多個集合.

　(Feating; Ting, Wells, Tan, Teng, & Webb, 2011) 特征子空間聚合方法，通過預定的特征數量將數據分割。

　(Feating; B?aszczy
nski, Stefanowski, & S?owi
nski, 2016)有序一致性驅動的特征子空間聚合，將屬性空間細分為局部區域。該方法對產生一致區域的分區進行優先排序。CoFeating在具有大量屬性的數據集中表現良好。

　(Dietterich & Bakiri, 1995) ECOC碼將 多個二分類器組合成多分類器。文章很多，不介紹。

　(Zhong & Cheriet, 2013) AECOC 在訓練不同的二進制分類器時增加了常規約簡（ conventionality reduction ）過程。

　n元糾錯編碼方案是一種最近發展起來的方法，它將主要的多類分類器分解為更簡單的多類子問題(Zhou，Tsang, Ho， & Muller, 2016)。

　(Zhang & Zhang, 2008).RotBoost是結合了 旋轉森林 和 AdaBoost的一種方法，在每一輪迭代中，都生成一個新的Rotation Matrix旋轉矩陣來生成新的數據集，然后再用AdaBoost。

　(Bernard, Adam， & Heutte, 2012)動態隨機森林，自適應樹歸納。每棵樹的訓練都是由它如何補充已經訓練過的樹來指導的。通過使用與隨機森林相關的重采樣方法和隨機化過程來實現。

　(Garc?a-Pedrajas, Garc?a-Osorio, & Fyfe, 2007).每輪都對被誤分類的樣本創建新基學習器。　

　(Blaser & Fryzlewicz, 2016)隨機旋轉集成，在訓練每個基學習器時都對特征空間進行旋轉。該方法對包含許多連續特征的問題是有效的。

集成學習結果聚合策略

　權重法，權重法適用于基學習器的性能可比較的情況。投票法就是最簡單的權重法，

　　在貝葉斯組合方法中，權重是基于給定整個數據集得到模型的概率概率(Duan, Ajami，Gao， & Sorooshian, 2007)

　　(Schapire and Singer ，1998)使用基于置信度的結果聚合，置信度的計算是基于決策樹可到達的葉節點數量。

　　(Derbeko, El-Yaniv， & Meir, 2002)是方差優化bagging or bogging的方法，基于方差來做的。

　　權值也可以通過使用目標函數來分配，即將權重也作為學習的一環，目標是誤差最小(Mao et al.， 2015)。

　　(Haque, Noman, Berretta， & Moscato, 2016)提出使用Matthews相關系數(MCC)作為權重選擇的度量。

　Meta-learning method:元學習是讓學習器學會學習的一種表述。在元學習中，一個基學習器的輸出將作為元學習的輸入，最終產生輸出。

　　Stacking是最流行的元學習技術(Wolpert, 1992)，該方法通過使用元學習器，試圖歸納出哪些基本模型是可靠的，哪些是不可靠的。在stacking中，我們創建了一個元數據集，其中包含了在原始數據集中發現的相同數量的實例。

　　Troika (Menahem, Rokach， & Elovici, 2009)旨在提高多類數據集的預測性能

　　Arbiter trees, combiner trees and grading(Chan & Stolfo, 1995b;Seewald & Furnkranz, 2001)是為集成基學習器的輸出而開發的額外元學習算法。

　　加權bagging (Shieh & Kamm, 2009)的特點是一個預處理過程，在這個過程中，利用核密度估計器根據點與目標類的接近程度給點分配概率權重。

　　(ME)是元學習的一種非常流行的變體，它依賴于分治的思想，因為問題空間是由幾個experts來劃分的。ME使用錯誤函數來為數據空間的不同分布定位最合適的基模型(Jacobs, Jordan, Nowlan， & Hinton, 1991)

　　Omari and Figueiras-Vidal (2015)使用了一種后聚合方法用于集成大規模的決策樹。第一步，用權重法對 每一個決策樹進行初始聚合。第二步，用機器學習的方法對初始聚合的結果進行再聚合。

算法

　AdaBoost的變體

　　Soft margin Adaboost (Ratsch，Onoda， & Muller, 2001) 在算法中使用正則化來緩解離群值的影響

　　Modest Adaboost (Vezhnevets & (Vezhnevets, 2005) 增加了正則化，提高了模型的泛化，但降低了訓練的準確性

　　SpatialBoost (Avidan, 2006) 將 Spatial reasoning與Adaboost結合。

　　Palit and Reddy (2012) 使用MapReduce模式，做了可并行的AdaBoost.PL and LogitBoost.PL

 　bagging的變體

　　改進的bagging算法(IBA; Jiang, Li, Zheng, & Sun, 2011)，采樣過程中加入了信息熵，提高了一定的泛化能力。

　　online bagging（Oza, 2005）提高了運行速度。

　　Waggingg (weight aggregation; Bauer & Kohavi, 1999)對每個樣本分配權重。

　　在Double-bagging(Hothorn & Lausen, 2003)中，每次迭代使用包外示例訓練兩個分類器

　隨機森林or隨機子空間

　　具有實時性的Random Forest 考慮了概念漂移的影響(Saffari, Leistner, Santner, Godec, & Bischof, 2009)，該版本增加了一種時間加權方案，該方案根據樹在不同時間間隔內的誤差自適應地排除一些樹，然后生長新的樹來替代被排除的樹。

　　random subspace method (RSM; Ho, 1998)不需要使用決策樹作為基學習器。

　　(Kamath & Cantu-Paz, 2001)使用特征分割后的樣本中的一部分來訓練。

　　Kulkarni and Sinha (2013)專門做了一篇關于隨機森林的綜述。

　　(Han, Jiang, Zhao, Wang, & Yin, 2018)最近的研究發現，與極限學習機、支持向量機和神經網絡相比，隨機森林的魯棒性和穩定性更強，特別是在訓練集較小的情況下。

　Gradient boosting machines

　　梯度提升算法與其他技術不同的地方是，GBM優化應用于函數空間（function space.）？？？更具體的，GBM，計算一連串的回歸樹，每一棵連續樹預測前一棵樹的偽殘差并給出一個可微的損失函數。通常它的數比RF更廣，而RF則更深。

　　使用隨機梯度增強方法(Friedman, 2002)可以減少過擬合，該方法使用從原始數據集中采樣的小子集連續訓練樹。

　　XGBoost (Chen & Guestrin, 2016)是一個可調整的機器學習系統，用于樹提升。XGB對GMB進行了幾點優化，首先是特征選擇上，(a)處理稀疏數據的節點默認方向，(b)使用合并和修剪操作處理加權數據，(c)有效地枚舉所有可能的分割，以便分割閾值得到優化。XGBoost中另一個重要的改進是，它在GBM中呈現的損失函數中添加了一個正則化組件，目的是創建更簡單、更有泛化能力的集成學習器。最后，XGBoost可以運行的很快，它支持分布式運算。

　　LightGBM是微軟開發的另一種梯度增強方法，也有很多文章介紹。

　rotation forest

　　旋轉森林是通過旋轉特征來生成多樣性的方法，當訓練集形成時，特征被隨機劃分為K個子集，并對每個子集應用PCA。有效的為每一個基學習器提供了有效的特征。除了促進樹間的多樣性，旋轉樹還減輕了決策樹只將輸入空間分割成與原始特征軸平行的超平面的限制。但是該算法，計算成本高于隨機森林，其旋轉后的特征可解釋性降低。

　　Schclar and Rokach (2009)推薦使用隨機選擇特征，而不是PCA選擇特征。每一個派生特征都是原始特征的線性組合。

　　(Ahmad & Brown, 2014)隨機投影隨機離散化集合(RPRDE)是一種旋轉森林變體，它從連續特征中創建離散特征

　Extremely randomized trees

　　是另一種在訓練過程中注入隨機性的方法。除了從隨機子集中選擇最優特征，特征分割點也具有隨機性。與隨機森林的區別還包括，并不對訓練集做預處理。. Geurts et al.證明了雖然極限隨機數有高偏差和方差，但足夠大的樹集合可以消除這一點。

　集成學習與深度學習

　　Deep neural decision forests (Kontschieder, Fiterau, Criminisi, & Rota Bulo, 2015) 結合了決策森林和神經網絡。通過隨機反向傳播使決策樹生成決策森林。

　　另一個由cnn組成的集成的例子，最近被開發用于面部表情識別任務(Wen et al.， 2017)。

　　gcForest (Zhou & Feng, 2017)是一種將集成方法與DNNs相結合的新方法，與上述方法不同，它將神經元替換為隨機森林模型，將每個隨機森林的輸出向量作為下一層的輸入。當輸入是高維的時候，它通過應用多粒度掃描來支持表示學習。

　對比

　　(Dietterich, 2000) 比較了由C4.5決策樹組成的randomizing、bagging和boost集合。實驗表明，在數據噪聲較小的情況下，boosting能獲得最佳效果。

　　(Bauer & Kohavi）研究發現，bagging降低了不穩定方法的方差，而boosting方法降低了不穩定方法的偏差和方差，但增加了穩定方法的方差。

　　Banfield, Hall, Bowyer和Kegelmeyer(2007)用57個公開數據集進行了一項實驗，將bagging與其他7種基于隨機的技術進行比較。最好的方法僅在8個數據集中比bagging準確率高。有1000顆樹的隨機森林和boosting有著最好的平均排名。

集成學習簡化模型

　減少集成學習的規?？赡芸瓷先档图蓪W習的泛化能力，（Zhou, Wu, and Tang, 2002）證明了“many-could-be-better-than-all”，這使降低學習器規模而保持性能變得有道理。

　通常有兩類“剪枝”策略 Ranking 和 Search-based，排序法通過閾值選擇靠前的基學習器；

　Caruana, Niculescu-Mizil, Crew, Ksikes(2004)提出了一個向前逐步選擇程序，以便從眾多誘導因子中選擇最相關的誘導因子(就預測性能而言)。

　FS-PP-EROS (Hu, Yu, Xie, and Li, 2007)生成一個選擇性的粗糙子空間集合。該方法進行了精確引導的前向搜索，尋找最相關的成員。實驗結果表明，該方法在提供較小的集成的同時，優于bagging方法.

　AB (Bryll et al.， 2003)使用wrapper approach評估隨機選擇的top-N性能的學習器。

　Margineantu and Dietterich (1997)提出基于kappa統計值的選擇方法。

　hang和Wang(2009)提出了一種具體的隨機森林修剪方法，該方法使用了三種度量，將準確性和多樣性考慮在內。

　Dai(2013)提出了四種適合于時間序列域的基于排序的剪枝評價指標。

　GASEN算法，在給定的集合中選擇最合適的誘導器(Zhou et al.， 2002)。首先，GASEN給每個模型分配一個隨機權重。然后使用遺傳算法對權重進行改進，從而表明模型在集成中的適合度，并去除權重較低的基礎模型。

　Prodromidis, Stolfo(2001)引入了一種基于后向相關的修剪類型，它根據基本模型的輸出進行訓練，并刪除與元分類器相關性較低的成員。

　森林修剪(FP;Jiang, Wu， & Guo, 2017)是最近開發的一種剪枝方法，它關注于一個決策樹的集合，在這個集合中，樹的分支是基于一個叫做分支重要性的新度量來剪枝的，該度量表示集合中單個分支和節點的重要性。

結論

　集合法在做重要決定之前，通過征詢不同意見來模仿人的本性。這些方法的主要思想是權衡幾個單獨的模型，并將它們結合起來，以提高預測性能。本文回顧了該領域的主要方法和技術，同時討論了培訓機構的核心原則。希望對你有所幫助。

Sagi, O, Rokach, L. Ensemble learning: A survey. WIREs Data Mining Knowl Discov. 2018; 8:e1249.