去年，俄羅斯的研究者 Alex Rogozhnikov 和 Tatiana Likhomanenko提出了一種集 bagging 和 boosting 兩者之長的混合演算法 InfiniteBoosting。機器之心對相關論文進行了簡要解讀和編譯。相關演算法的實現也已發布在 GitHub 上。

論文地址：https://arxiv.org/abs/1706.01109

代碼地址：https://github.com/arogozhnikov/infiniteboost

引言

集成方法有廣泛的應用和優良的準確度，因此自發明伊始就一直很引人注目。在集成方法大家庭中，bagging 和 boosting 演算法具有一些共同特性，但訓練過程卻不一樣。一般而言，bagging 有益於降低方差，而 boosting 則同時注重偏差和方差。但眾所周知 boosting 往往會與數據集過擬合，從而導致方差更高。

集成方法的有效性已經在數據競賽中得到了成功證明：Kaggle 挑戰賽中 60% 的獲勝方案都使用了 XGBoost（一種常見的 boosting 演算法）。一位競賽獲勝者 Qingchen Wang 甚至做出了這樣的極端表述：「我只使用 XGBoost。」

為了將 bagging 和 boosting 的最優特性結合到一起，該論文提出了一種混合演算法——InfiniteBoosting，其會構造一個任意大的集成樹（ensemble tree）並以梯度提升（gradient boosting）的方式訓練每個弱學習器。由於其混合特性，這個演算法構建的分類器能在每個訓練步驟降低偏差，同時還能控制過擬合。

bagging 和 boosting

首先看看 bagging 方法。bagging 是 bootstrap aggregatin（自舉匯聚演算法）的縮寫，下面的等式展示了它的原理：在自舉的數據集上訓練許多弱學習器 f_b(x)，然後取平均，輸出學習結果。這裡，自舉（bootstrap）的意思是從原始數據集隨機生成不同的數據樣本（擲 n 次 n 面骰子）。

遵循這一思想，可以很自然地引入隨機森林演算法，因為決策樹就是弱學習器的一種完美候選方法。單個決策樹具有低偏差和高方差等特性。在聚合了很多樹之後，偏差仍保持不變，但方差會下降。通過構建足夠大的隨機森林，我們可以實現儘可能低的恆定偏差。

現在再看 boosting。boosting 背後的基本思想是能否通過重點關注弱點的提升來修改弱學習器，使其變得更好。這是通過多次使用弱學習方法來獲得連續假設而實現的，其中每一次都會再次關注之前認為困難和誤分類的樣本。通過這種做法，boosting 能幫助弱學習器變強。下面的等式表明 boosting 的最終輸出是弱學習器的加權平均（投票法），其中 α_t 是考慮了前一次迭代的誤差後計算得到的權重。

下圖展示了 boosting 演算法的典型學習過程。每個學習器都會從上一個學習器的失敗中學習，並通過累積所有學習器的輸出而輸出正確結果。

InfiniteBoosting

InfiniteBoosting 的目標是通過 boosting 過程構建一個無限集成方法。不同於梯度提升方法，InfiniteBoosting 通過在每次迭代用權重 α_t 求所有弱學習器的平均，然後乘以被稱為 capacity 的常量 c，而不是梯度提升方法中那樣的線性組合。為了詳細說明它們的不同之處，這裡引用了原論文中的演算法過程：

分析

InfiniteBoosting 演算法引入了 bagging 和 boosting 的特性，其具有與梯度提升一樣的學習過程，但不同之處是會更新重新加權的輸出，而不是數學累積。我們可以輕鬆得出結論：這個演算法是一個隨機森林，其每個樹都會從其它樹中的錯誤中學習；或者說這是梯度提升的修改版本，只是更新方法不同。

該論文展示了這個演算法的有效性：只要每個樹在訓練數據上的輸出都是有界且連續的，那麼該演算法幾乎就肯定會收斂到解。同時，我們應該注意到任何機器學習演算法的誤差都是偏差和方差的總和。bagging 方法通過學習器之間的不關聯性來最小化方差，從而降低方差，但這會導致偏差略微上升。boosting 方法通過聚合不同模型的輸出來降低偏差，但這會導致方差增大。因此，這兩種方法的混合方法 InfiniteBoosting永遠無法突破其中任意一種方法的局限性，而且它可能無限逼近 bagging 或 boosting 的結果。

InfiniteBoosting 的明顯優勢是能讓 bagging 或 boosting 處理它們一開始並不適合處理的任務。換句話說，這種方法在不同的數據集或任務上是穩健的。當數據足夠時，其總能實現 bagging 和 boosting 其中之一的最佳表現。

但是，要收斂到一個固定點，其需要足夠大的數據集和更長的訓練時間。我猜測這個缺點不會妨礙太多應用，因為現在數據無處不在，計算資源也在隨時間增長。

實驗結果

我們可以根據結果得到結論：相比於梯度提升或隨機森林方法，InfiniteBossting 的結果相近但稍好一點。這個結果也與上一節的分析吻合。

結論

InfiniteBoosting 克服了 bagging 和 boosting 兩者的缺點，從而略微提升了表現水平。其最重要的方面是適應性。其延展了任何單獨的 bagging 和 boosting 方法的處理範圍，所以更多應用都能享受到 bagging 和 boosting 兩者的好處了。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！