梯度提升機（GBM）的重要性無需多言，但傳統的 GBM 仍存在一些固有缺點。近日，南京大學周志華, 創新工場馮霽等人提出了一種新型的軟梯度提升機（sGBM），並基於此構建了新型的軟梯度提升決策樹（sGBDT），作為XGBoost的替代性模型。相比於傳統的「硬」GBM，sGBM 在準確度、訓練時間和增量學習，多維度回歸等多方面都有更優的表現。
論文連結：https://arxiv.org/pdf/2006.04059.pdf
梯度提升機（GBM）已被證明是一種成功的函數近似器並已在多種不同的領域得到了廣泛應用。GBM 的基本思想很簡單，即訓練一系列基學習器（base learner）並且這些學習器的目標是按順序最小化某個預定義的可微分損失函數。
在構建這些學習系統時，通常的做法是用不可微分的決策樹充當基學習器。梯度提升決策樹（GBDT）及 XGBoost、LightGBM 和 CatBoost 等變體，是最常見也是最廣泛使用的具體模型實現。
現階段，對於表格式數據而言，GBDT 模型仍舊是最佳選擇，其應用領域也很廣泛，從協同過濾到信息檢索再到粒子發現均有其身影。但是，此類模型較難用於在線學習，因為流數據的環境是會變化的，而基模型在訓練完成後難以隨環境而變化。
另一方面，同 GBM 不同，可微分編程不僅需要損失函數是可微分的，學習模塊也需要可微分。具體來說，通過將多個可微分學習模塊構建為任意有向無環圖（DAG）形式，就可通過隨機梯度下降或其變體優化方法來聯合優化其整個結構。這樣的系統有一些出色的特性，包括強大的表徵學習能力、可擴展性以及可在線使用。
2018 年，周志華和馮霽等人發表的一篇 NeurIPS 論文提出了一種用於表徵學習的多層梯度提升決策樹（mGBDT），這項研究開創性地融合了上述兩個研究方向的優勢。具體來說，mGBDT 具有和可微分編程模型一樣的分層表徵能力，同時又具備非可微分模型的一些優良特性，因此能以更好的方式處理表格式數據。這項開創性研究帶來了新的挑戰和機遇，但也存在很大的進一步探索空間。
今天要介紹的這項研究是周志華，馮霽等人在相關問題上的又一種開創性思考。這一次，他們研究的不是如何構建一個能像可微分程序一樣工作的 GBM，而是探索了如何構建能像不可微分的 GBM 一樣工作的可微分系統。軟梯度提升機（Soft Gradient Boosting Machine）就是他們的探索成果。這種「軟」版本的 GBM 是將多個可微分的基學習器連接在一起，受 GBM 啟發，同時引入了局部損失與全局損失，使其整體結構可以得到聯合優化。在此基礎上，他們還提出使用軟決策樹（soft decision tree）來充當基學習器，在硬決策樹不是最合適的選擇時，軟決策樹對應的軟梯度提升決策樹就可被視為 XGBoost 的替代選擇。據介紹，這種設計具有如下優勢：
首先，相比於傳統的（硬）梯度提升機，軟梯度提升機的訓練速度更快。軟 GBM 不是一次一個地訓練基學習器，而是能同時訓練所有基學習器。該團隊也對該設計進行了實驗實測，結果表明在使用同樣的基學習器時，軟 GBM 在多個基準數據集上能帶來超過 10 倍的速度提升，同時還有更勝一籌的準確度。此外，在擬合傳統 GBM 模型時，一個基學習器必須在「看」完所有訓練數據之後才能轉向下一個學習器；這樣的系統不適合增量學習或在線學習。而軟 GBM 天生就具備這樣的能力。
其次，XGBoost 等當前的 GBDT 實現使用了 CART 作為基學習器，因此不能很直接地用於多維回歸任務。但 sGBDT 可使用軟決策樹作為基學習器來自然地處理這些任務。這樣的特性也使得 sGBDT 更適用於知識蒸餾或二次學習，因為蒸餾過程會將分類的 one hot 標籤轉換為一個在訓練集上的稠密向量。
最後，由於局部和全局的損失注入，軟 GBM 會讓基學習器之間的交互呈指數增長，使得該系統能比對多個基學習器使用軟平均 (soft averaging, 可微加權平均集成) 的方法更有效和更高效。
先從 GBM 講起
在詳細介紹新提出的方法之前，先來看看梯度提升機（GBM）的工作方式。具體來說，對於給定的數據集
，GBM 的目標是獲得函數 F*(x) 的一個優良近似，而評估標準是看其能否在實驗中最小化損失
。
GBM 假設 F*(x) 有這樣的加法展開形式：
，
其中
由 θ_m 參數化，而 β_m 是第 m 個基學習器的係數。
GBM 的訓練過程是基於訓練數據學習參數
。GBM 首先假設
，然後就能按順序決定
和 β_m。首先，給定 y^i 和 GBM 前一輪獲得的預測結果，
GBM 可為每個訓練樣本計算出所謂的殘差：
其次，下一個基學習器 h_m 會與該殘差進行擬合。係數 β_m 則通過最小二乘法確定或設定為常數。最後，完成對學習器 h_m 和係數 β_m 的參數更新之後，就可以將其用作條件來更新 GBM 的預測結果：
圖 1：GBM 和 sGBM 示意圖
然後進入下一輪訓練流程。算法 1 總結了這個訓練過程，圖 1 左圖也給出了其示意圖。
算法 1：常規（硬）GBM 的訓練過程
sGBM 有何不同？
可以看出，GBM 的訓練過程難以並行化，因為只有在一個基學習器擬合之後才能轉向下一個基學習器。也因為這個原因，這類算法也難以在線應用。
軟梯度提升機（sGBM）就是針對這些問題而提出的。該研究團隊首先假設所有基學習器都是可微分的。然後，他們沒有選擇為相連的基學習器執行軟平均，而是提出使用兩種類型的損失函數——全局損失和局部損失；將這兩種損失函數注入訓練過程之後，可使得基學習器之間的交互成指數增長，進而實現梯度提升效果（而非所有基學習器的直接加權平均）。
具體來說，令 M 為可微分基學習器的數量，其中每個基學習器的參數為 θ_m。這裡 M 是預先確定的，指定了訓練之前所使用的基學習器的數量。和硬 GBM 一樣，sGBM 的輸出為所有基學習器的輸出之和：
。訓練中整個結構的最終損失定義為
。其中，l_m 是基學習器的損失：
，而 o_m 則是當前學習器 h_m 的輸出，r_m 是對應的殘差
圖 1 右圖為新提出的 sGBM 的示意圖。可以看到，輸入數據的流動過程是一個有向無環圖（DAG），因此其整個結果都可通過 SGD 或其變體進行訓練，即最小化局部和全局損失目標。算法 2 闡釋了這一過程。
算法 2：訓練 sGBM
軟梯度提升決策樹
下面來看看適合 sGBM 的基學習器。研究者在論文中探討了基學習器是決策樹的具體情況。
梯度提升決策樹（GBDT）是 GBM 應用最廣的實例之一，其使用了硬（而且通常較淺）的二叉決策樹作為基學習器。具體來說，這個硬決策樹內每個無葉的節點會形成一個軸平行的決策平面，每個輸入樣本都會根據對應的決策平面被引導至左側或右側的子節點。這樣的流程是按遞歸方式定義的，直到輸入數據抵達葉節點。最終的預測結果是輸入樣本所在的葉節點內的類分布。
XGboost、LightGBM 和 CatBoost 等 GBDT 的成功實現已經證明 GBDT 是一種絕佳的數據建模工具，尤其是對於表格式數據而言。
另一方面，軟決策樹使用了 logistic 單元作為內部非葉節點的路由門，而輸入樣本的最終預測結果是所有葉節點之間的類別分布的加權和，其中權重是由在內部節點上沿決策路徑的 logit 積確定。這樣的結構可通過隨機梯度下降進行訓練，圖 2 給出了示意圖。
圖 2：單個軟決策樹的示意圖
當使用軟決策樹作為基學習器時，對應的軟 GBDT 相較於硬 GBDT 有多項優勢。第一，硬 GBDT 並非處理流數據的最佳選擇；而 sGBDT 是參數化的，因此整個系統可以根據環境更快地進行調整。第二，在面對多輸出回歸任務時，硬 GBDT 必須為每個樹設置一個維度，這會導致訓練效率低下；相較而言，由於 sGBDT 會同時訓練所有樹，因此速度會快得多。
實驗
sGBM 的有效性也在實驗之中得到了驗證。具體來說，研究者基於同樣的基學習器比較了傳統硬 GBM 和新提出的軟 GBM 在準確度、訓練時間、多輸出回歸、增量學習任務和知識蒸餾能力上的表現。
準確度方面的表現比較如表 2 所示。可以看到，sGBM_CNN 在圖像分類任務上的表現優於 GBM_CNN，而 sGBM_MLP 在除 Letter 數據集之外的幾乎所有數據集上都有優於 GBM_MLP 的表現。在使用樹方法時，相較於經典的 XGBoost 模型，sGBDT 僅在 Letter 和 USPS 數據集上得到了較差的結果。
表 2：分類準確度（均值 ± 標準差）比較。
圖 3 和圖 4 則展示了 sGBM 相較於傳統 GBM 的速度提升效果。可以看出，效果極其顯著，這主要得益於 sGBM 能自然地同時訓練所有基學習器。
圖 3：sGBM 對訓練的加速效果。很顯然，基學習器越多，加速效果越顯著。
圖 4：使用 MLP 和 CNN 作為基學習器時的訓練時間（秒）。
研究者也探索了添加更多基學習器能否有助於提升準確度表現。結果見圖 5，可以看出，答案是肯定的，可以認為主要原因是在 sGBM 的架構設計中基學習器之間有更多的交互。
圖 5：具有不同數量的基決策樹的 sGBDT 的學習曲線
下表 3、圖 6 和表 4 則分別給出了 sGBDT 在多輸出回歸任務、增量學習設置及知識蒸餾上的表現。總體而言，sGBDT 相較於傳統 GBDT 基本都有更優的表現。
表 3：使用 10 個基學習器的均方誤差（均值 ± 標準差）。可以看到 sGBDT 在大多數數據集上表現更優，另需注意 sGBDT 可輕鬆自然地插入其它任務，而硬 GBDT 需要一些額外的修改才行。
圖 6：在增量學習設置下的表現比較。相比於 XGBoost，sGBDT 在收斂速度方面優勢明顯。此外，sGBDT 相比於離線設置的準確度下降也更低。
表 4：sGBDT 和 XGBoost 的知識蒸餾能力對比。sGBDT 同樣表現更佳，作者認為原因是 XGBoost 及其它使用硬 CART 樹作為基模型的 GBDT 實現在執行多維回歸任務時，負責目標維度的樹之間交互更少，使得模型難以蒸餾存在於標籤分布向量之中的信息。