12 年後，樹模型 ABC-Boost 終於開源，精度超過 XGBoost、LightGBM

近期，前百度研究院副院長李平等人開源了多年的研究成果 Fast ABC-Boost 機器學習包。

開原始碼連線： http://github.com/pltrees/abcboost

據悉，該研究十多年前就已經開始，2010 年，李平發表了題為“Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost”的論文，2018 年的圖靈獎得主 Yoshua Bengio 當時還與人討論了李平在樹模型和 boosting 上的工作。

根據介紹，李平在 2007 年斯坦福大學博士畢業後，曾在任康奈爾大學和後羅格斯大學任教，並於 2013 年成為計算機系和統計系兩系的終身教授。其主要研究方向是演算法學習、高效檢索、機器儲存、資料流和推薦等，曾獲得 NIPS2014 最佳論文獎、ASONAM2014 最佳論文獎、KDD2006 最佳論文獎，以及美國空軍和青年科學家獎（AFOSR-YIP）、美國海軍傑出資料科學家獎（ONR-YIP）等獎項。

2020 年 1 月，李平開始擔任百度研究院副院長，其團隊與百度的鳳巢廣告、Feed 流、搜尋、百度知道、中文輸入法、百度地圖等業務部門展開合作，把研究成果應用到各項產品中。

在 Fast ABC-Boost 開源後，李平表示：“這個工作太實用了，本身影響力是巨大的，只不過有點可惜絕大部分使用者不會知道（也未必關心）原作者是誰。不過回想起來，我自己並沒有太去關心已經完成的工作，而是把精力放在做完全不同的新研究。這樣反而收穫更大。”

根據介紹，Fast ABC-Boost 的精度超過了經典的 XGBoost、LightGBM。本文將對這項研究工作進行詳細解讀。

概覽

“Fast ABC-Boost”軟體包是作者在康奈爾大學、羅格斯大學和百度研究院十多年工作的成果。下面是作者在康奈爾大學和羅格斯大學的課堂授課稿件：

• http://statistics.rutgers.edu/home/pingli/STSCI6520/Lecture/ABC-LogitBoost.pdf

• http://www.stat.rutgers.edu/home/pingli/doc/PingLiTutorial.pdf (pages 15–77)

一些機器學習研究人員可能仍然記得在 2010 年 http://hunch.net/?p=1467 論壇上的一些討論。在“Robust logitboost and adaptive base class (abc) logitboost”（2010 年，by Li）論文中，“Robust LogitBoost”和“Adaptive Base Class Boost”被作者提出來了。當時，研究人員很好奇，在深度學習研究人員開發的資料集上，增強樹演算法（boosted trees） 與深度神經網路相比，為什麼還是非常有效。

自那次討論以來，已經過去了十年。不必多說，深度神經網路在許多研究和實踐領域取得了巨大的成功。在作者開發了這些增強樹演算法之後，比如：“Learning to rank using multiple classification and gradient boosting”論文（作者等人，2007）、“Adaptive base class boost for multi-class classification”論文（作者等人，2008）、“ABC-Boost: Adaptive base class boost for multi-class classification”論文（作者等人，2009）、“ Fast abc-boost for multi-class classification”論文（作者等人，2010a）、“Robust logitboost and adaptive base class (abc) logitboost”論文（作者等人，2010b）。他精力轉移到其他許多有趣的研究課題，包括隨機素描（randomized sketching）、雜湊方法（例如，Li and Zhao ，2022b）、近似近鄰搜尋和神經網路排序（例如，Tan 等人，2021）、深度神經網路和近似近鄰搜尋廣告（例如，Fan 等人,2019 ；Fei 等人，2021 ）、大規模 CTR 模型的 GPU 架構（例如，Zhao 等人，2022a）、另見媒體報道 (www.nextplatform.com/2021/06/25/a-look-at-baidus-industrial-scale-gpu-training-architecture）、廣告 CTR 模型壓縮（例如，Xu 等人，2021 ）、AI 模型安全（例如，Zhao 等人，2022b）、隱私、理論等，以及機器學習在自然語言處理、知識圖和視覺中的應用。

儘管，深度神經網路取得了廣泛的成功，但作者發現增強樹演算法在實踐中仍然非常有用，例如搜尋結果排名、股價預測、金融風險模型等。例如，作者在百度的輸入法編輯器（IME）使用了增強樹演算法，並在手機上部署了樹模型（Wang 等人，2020）。根據作者自己的經驗，發現增強樹演算法非常適合具有少於 10000 個特徵和少於一億個訓練樣本的預測任務。對於使用具有數千億訓練樣本的極高維稀疏資料的應用（例如廣告 CTR 預估），通常深度神經網路更方便或更有效。

正如最近一篇關於決策樹綜述的論文（Fan 和 Li，2020）所總結的那樣，在過去 15 年左右的時間裡，多種實現技術提升了增強樹演算法的精度和效率，包括:

• 與基於僅使用一階增益資訊相比，使用二階增益資訊公式的樹分裂實現（李，2010b）（即“Robust LogitBoost”）通常可以提升精確度（Friedman，2001）。它現在是流行的樹模型平臺中的標準實現。

• 李等人（2007）提出的自適應分箱策略有效地將特徵值轉換為整數值，大大簡化了實現，並提高了樹模型的效率。分箱技術也是流行樹模型平臺的標準實現。

• 用於多分類的“adaptive base class boost”（ABC-boost）模式（Li，2008，2009，2010a，b；Li and Zhao，2022a）通過重寫經典多分類邏輯迴歸損失函式的導數，在許多情況下可以大大提高多分類任務的準確性。

• 開源軟體包 http://github.com/pltrees/abcboost， 包括：幫助使用者安裝軟體包並將其用於迴歸、分類和排序的文件。作者將回歸和分類結果與兩種流行的增強樹模型平臺，即 LightGBM 和 XGBoost 進行了比較，並注意到在準確性方面存在一些差異。這一觀察結果很有趣（也可能令人困惑），因為他們基本上實現了相同的演算法：（i）訓練前的特徵分箱（直方圖構建），如李等人（2007 年）所述；和（ii）李（2010b）中推導的樹分裂的二階增益資訊公式。同一演算法的實現如何輸出明顯不同的結果？

作者意識到這種差異可能是由於在實現特徵分箱過程中的差異造成的。李等人（2007）設計了一種過於簡單的定長分箱方法，而 LightGBM 和 XGBoost 似乎使用了更精細的處理。也許與直覺相反，實驗表明，李等人（2007）中非常簡單的分箱方法在測試的資料集上產生了更準確的結果。

因此，在本報告中，首先描述了 ABC-Boost 包中使用的簡單分箱方法，然後演示瞭如何使用 ABC-Boost 進行迴歸、二分類和多分類任務。對於每項任務，作者還報告了基於 2022 年 6 月最新版本的 LightGBM 和 XGBoost 的實驗結果。

特徵預處理固定長度的分箱方法

迴歸樹（Brieman 等人，1983）是分類、迴歸和排序任務的基礎構建模組。樹的思想是基於一些“增益”標準以軸對齊的方式遞迴劃分資料點，並報告最終（子劃分）區域中資料點的平均（或加權平均）響應作為預測值。子劃分的區域作為一個樹來組織或者檢視，葉節點對應於最終的子劃分區域。

因此，一項關鍵任務是計算每個特徵的最佳分割點，並通過將當前節點中的資料點分成兩部分來選擇最佳特徵（即增益最大的特徵）來進行實際分割。該過程遞迴繼續，直到滿足某些停止標準。在李等人（2007）之前，典型的樹實現首先根據特徵值對每個維度的資料點進行排序，並需要在分割後跟蹤資料點。如圖 1 所示，李等人（2007）首先將特徵值量化（分箱）為整數，然後按照自然順序排序。這個技巧大大簡化了實現。如果分箱總數不太大，可以使程式更高效。圖 1 中的分箱也適用於資料分佈，因為它僅在有資料的地方分配分箱值。

如以下 matlab 程式碼所示，分箱方法非常簡單：首先從非常小的初始分箱長度開始（例如，10^−10） ，預先指定最大的分箱引數，比如 128 或者 1024。對於每個特徵，根據特徵值對資料點進行排序。將分箱編號從最小到最大分配給資料點，只要有資料點，就一直分配，直到所需的分箱數量超過 MaxBin。然後通過加倍分箱長度來重新開始。

這種分箱程式有許多明顯的優點。它非常簡單，易於實現。它自適應資料分佈。此處理不會影響已排序類別變數的特徵。這種處理的缺點也很明顯。它絕不是任何意義上的“最優”演算法，作者期望它可以在許多方面得到改進。例如，使用固定長度時，如果 MaxBin 設定得太小（如，10），可能會看到較差的精度。另一方面，如果 MaxBin 設定得太小，樹演算法本身將無法很好地工作。如本報告後面的實驗所示，這種極其簡單的分箱方法對樹表現非常好。作者提供了 matlab 程式碼，以幫助讀者更好地理解該過程，並幫助研究人員改進其分箱演算法（和樹演算法平臺）。

總之，這種看似非常簡單（固定長度）的分箱演算法能適用於增強樹方法，可能有兩個主要原因：

• 對於增強樹，允許的最大分箱數（即 MaxBin 引數）無論如何都不應太小。如果資料量化過粗，將丟失太多資訊。對於如此多的分箱（例如，MaxBin=1000），就增強樹的精度而言，改進這種固定長度策略可能並不那麼容易。

• 不應該期望所有特徵都使用相同數量的分箱。通常，在一個數據集中，特徵可能會有很大差異。例如，一些特徵可能是二值的（即，使用 MaxBin=1000 也只能生成兩個值），一些特徵可能只有 100 個不同的值（即，使用 MaxBin=1000 仍最多隻能生成 100 個值），而一些特徵確實需要更多的量化級別。因此，引數 MaxBin 只是一個粗略的準則。根據給定的 MaxBin 過於努力地“優化”分箱過程可能會適得其反。

實際上，作者建議將 MaxBin=100（或 128）設定為開始點。如果精度不令人滿意，可以逐漸將其增加到 MaxBin=1000（或 1024）。根據作者的經驗，當 MaxBin 大於 1000 時，很難觀察到明顯更好的精度。

在接下來的三節中，將介紹使用 Fast ABC-Boost 軟體包進行迴歸、二分類和多分類的實驗結果。通過將 MaxBin 從 10 更改為 10^4，將結果與 LightGBM 和 XGBoost 進行比較，以說明 MaxBin 對精度的影響。此外，作者觀察到，一旦啟用多執行緒，結果變得不確定，儘管隨機變化通常不會太大。為了嚴格確保確定性結果（用於清晰的比較），作者將所有實驗作為單執行緒執行。

Lp 迴歸

讀者請參閱關於 Lp 增強迴歸的詳細報告（Li and Zhao，2022c）。一個訓練資料集{yi，xi}(i=1,n)，其中 n 是樣本數，xi 是第 i 個特徵，yi 是第 i 個標籤。Lp 迴歸的目標是建立模型 F（x），以最小化 Lp 損失：

使用“加法模型”（Friedman 等人，2000；Friedman，2001），假設 F 是 M 項的總和：

其中，基學習器 fm(x) 是一棵迴歸樹，以分段貪婪的方式從資料中學習。根據 Friedman 等人（2000）的想法，在每次增強迭代中，通過加權最小二乘法擬合 fm，響應值{zi}和權重{wi}：

李（2010b）推導了使用響應值{zi}和權重{wi}建立迴歸樹時，確定分裂位置所需的相應增益公式。歷史上，基於加權最小二乘法的增強方法被認為存在數值問題（Friedman 等人，2000，2008），因此後來 Friedman（2001）提出僅使用一階導數擬合樹，即，

現在很清楚，如李（2010b）所示，可以推匯出使用二階資訊計算增益的顯式的和數值穩定 / 魯棒的公式。

基於二階資訊的樹分裂準則

考慮一個具有 N 個數據點和一個特定特徵的樹節點。權重 wi 和響應值 zi，i=1 到 N。已經根據特徵值的排序順序對資料點進行了排序。樹分裂過程是查詢索引 s，1≤ s<N，因此如果在 s 處分割，加權平方誤差（SE）減少得最多。也就是說，尋求 s 最大化：

這個過程在數值上是魯棒、穩定的，因為，不需要直接計算響應值 zi=-Li’//Li’’，它可以（並且應該）很容易地接近無窮大。由於原始 LogitBoost（Friedman 等人，2000）使用了單個響應值 zi=-Li’//Li’’，因此該過程被認為存在數值問題，這是 Friedman（2001）僅使用一階導數構建樹的動機之一。因此增益公式成為:

Lp 增強演算法

演算法 1 描述了 Lp 增強迴歸樹使用的分裂增益公式（7）（對於 p≥ 2） 或樹分裂增益公式（8）（對於 1≤ p<2）。注意，在構建樹之後，終端節點的值通過以下公式計算：

這解釋了演算法 1 的第 5 行。當 1≤ p<2，作者遵循 Friedman（2001），使用一階導數建立具有分裂增益公式（8）的樹，並將終端節點更新為

實驗

遵循 http://github.com/pltrees/abcboost 上的說明，使用者可以安裝 Fast ABC-Boost 軟體包。假設可執行檔案位於當前目錄，資料集位於“data/”目錄。“comp-cpu”資料集有 libsvm 和 csv 兩種格式，有 4096 個訓練樣本和 4096 個測試樣本。在終端，執行以下命令

建立一個 L2 迴歸增強模型，J=20 個葉節點，ν=0.1 收縮率，最多迭代 10000 次。最大分箱數（MaxBin）設定為 1000。作者採用保守的早期停止標準，在 Lp 損失低於以下值後讓程式退出

其中ε預設為 10^5。在本例中，程式在 933 次迭代後退出（而不是 10000 次迭代）。在訓練後，將在當前目錄中建立兩個檔案：

為了在測試資料集上測試訓練後的模型，執行

它會生成另外兩個（文字）檔案來儲存測試結果：

.testlog 檔案記錄了測試損失和其他資訊。“.prediction”儲存最終（或指定）迭代中所有測試樣本的迴歸預測值。

用引數 J∈ {6, 10, 20}, ν ∈ {0.06，0.1，0.2}，p 從 1 到 10，MaxBin 從 10 到 10^4 進行實驗。圖 2 繪製了每個 MaxBin 值的最佳（在所有引數和迭代中）測試 MSE。在每個面板上，實心曲線繪製 L2 迴歸的最佳測試 MSE 和 Lp 迴歸的虛線曲線（在最佳 p 處）。右面板是左面板的放大版本，重點放在 100 到 10^4 的 MaxBin 上。對於這個資料集，使用 MaxBin=1000 可以獲得很好的結果，而使用較大的 MaxBin 值不會產生更好的結果。

圖 3 繪製了所有三個包的 L2 迴歸的最佳測試 MSEs：ABC-Boost（L2）、XGBoost 和 LightGBM，MaxBin 範圍為 10 到 10^4。同樣，右面板只是左面板的放大版本。當然，如圖 2 所示，ABC-Boost 將能夠通過使用 p≠2 的 Lp 迴歸實現更低的 MSE。

最後，圖 4 繪製了所有迭代的測試 L2 MSEs，在一組特定的引數 J、ν和 MaxBin 下。注意，ABC-Boost 包在等式（9）中設定了保守停止標準。

使用魯棒 LogitBoost 分類

同樣，用{yi，xi}(i=1,n) 表示訓練資料集，其中 n 是訓練樣本數，xi 是第 i 個特徵向量，yi∈ {0，1，2，…，K− 1} 是第 i 類標籤，其中 K=2 表示二分類，K≥ 3 表示多類分類。假設類概率 p(i,k) 為

其中 F 是 M 項的函式：

其中，基學習器 fm 是一棵迴歸樹，通過最小化負對數似然損失進行訓練：

其中，如果 yi=k，則 r(i,k)=1，否則，則 r(i,k)=0。優化過程需要損失函式（12）的前兩個導數，分別對應於函式值 F(i,k)，如下所示：

這些是教科書中的標準結果。

基於二階資訊的樹分裂準則

再次，考慮具有 N 個權重 wi 和 N 個響應值 zi，i=1 到 N 的節點，假設其根據相應特徵值的排序順序排序。樹分裂過程尋求 t 最大化

因為計算涉及∑p(i,k)（1− p(i,k) 作為一個組，該程式在數值上是魯棒、穩定的。這解決了 Friedman 等人（2000）的擔憂；Friedman（2001）；Friedman 等人（2008 年）。相比之下，MART（Friedman，2001）使用一階導數來構造樹，即，

演算法 2 使用等式（14）中的樹分裂增益公式描述魯棒的 LogitBoost。注意，在構建樹之後，終端節點的值通過以下公式計算：

這解釋了演算法 2 的第 5 行。對於 MART（Friedman，2001），該演算法幾乎與演算法 2 相同，除了第 4 行，MART 使用樹分裂增益公式，等式（15）。

注意，對於二分類（即 K=2），只需要在每次迭代中構建一棵樹。

二分類實驗

二分類資料集“ijcnn1”包含 49990 個訓練樣本和 91701 個測試樣本，可在 http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/dataset/binary.html 檢視。這個在一次比賽中使用了該資料集，獲得冠軍的是 LIBSVM（核 SVM），測試誤差為 1293 個（在 91701 個測試樣本中）。

再次在終端發出以下命令

使用 J=20 個葉節點、ν=0.1 收縮率和 M=10000 次迭代，MaxBin=1000，使用“魯棒 LogitBoost”演算法訓練二分類模型。建立兩個檔案：

打印出“.trainlog”檔案的前 3 行和後 3 行：

其中第二列是訓練損失，第三列是訓練誤差。同樣，為了確保輸出確定性結果，使用單執行緒訓練所有場景。在這裡，作者想強調的是，由於潛在的有利隨機效應，多執行緒程式可能輸出更好（但不確定）的結果。

下一個命令

輸出測試結果

.testlog 檔案的最後 10 行如下所示：

其中第三列記錄了測試錯誤。回想一下，LIBSVM 的最佳結果是 1293。注意，在 Li（2010b）的附錄中，也給出了在 ijcnn1 資料集上的實驗結果。

圖 5 繪製了最佳測試誤差，以比較 J∈ {10, 20}的魯棒 LogitBoost 和 MART, ν ∈ {0.06，0.1}，M=10000。給出了關於 MaxBin（最大分箱數）的結果，以說明分箱對分類錯誤的影響。事實上，當 MaxBin 設定為小於 100 時，在該軟體包中實現的簡單固定長度分箱演算法的精度並不好。同樣，這是意料之中的。

圖 6 在相同的 MaxBin 值下比較了魯棒 LogitBoost 與 XGBoost 和 LightGBM。顯然，當 MaxBin 設定為小於 100 時，在作者的包中實現的簡單固定長度分箱方法的精度並不好。另一方面，在選擇遠大於 100 的 MaxBin 處獲得最佳（最低）誤差（事實上，該資料集為 2000）。

雖然，確實希望有相當大的空間來改進簡單（固定長度）的分箱演算法，但作者也承認，在使用這種分箱方案大約 15 年後，還沒有找到一種普遍（或非常）好的演算法。

最後，在圖 7 中，繪製了每組引數（J，ν，MaxBin）的所有 M=10000 次迭代的測試誤差歷史，以比較 RobustLogitBoost 與 XGBoost 和 LightGBM。希望從圖中可以清楚地看出，從業者可能希望重新回顧這個簡單的分箱方法，以進一步更好地理解為什麼它工作得如此好，並進一步提高其精度。

用於多分類的 ABC-Boost

“自適應基類增強”（ABC-Boost）的思想起源於（Li，2008），其中將多類邏輯迴歸的經典（教科書）導數重寫為：

這裡，記作，

在上面，假設類 0 是“基類”，並對 Fi 值使用“sum-to-zero”約束。在實際實現中，需要在每次迭代中識別基類。

如 Li（2009，2010b）所示，“窮舉搜尋”策略在準確性方面效果良好，但效率極低。Li（2008）的未發表技術報告提出了“worst-class”搜尋策略，而 Li（2010a）的另一份未發表報告提出了“gap”策略。最近，Li 和 Zhao（2022a）通過引入三個引數開發了一個統一的框架來實現“快速 ABC-Boost”：（i）“搜尋”引數 s 限制了對 s-worst 類中基類的搜尋。（ii）“gap”引數 g 表示僅在每個 g+1 迭代中進行基類搜尋。（iii）最後“預熱”引數 w 指定搜尋僅在為 w 迭代訓練了魯棒 LogitBoost 或 MART 之後開始。

演算法 3 總結了快速 ABC-Boost 的統一框架。雖然它引入了其他引數（s、g、w），但好訊息是，在大多數情況下，精度對這些引數並不敏感。事實上，Li（2008）最初提出的“worst-class”策略已經非常有效，儘管在某些情況下可能會導致“災難性失敗”。在某種意義上，引入這些引數（s、g、w）主要是為了避免“災難性失敗”。

在演算法 3 中，ABC-RobustLogitBoost 中樹分裂的增益公式類似於（14）：

使用 UCI“covtype”資料集進行演示。該資料集包含 581012 個樣本，將其分為一半用於訓練 / 測試。這是一個 7 個類的分類問題。在實驗中，假設 J=20，ν=0.1，M=1000。執行以下命令：

./abcboost_train -method abcrobustlogit -data data/covtype.train.csv -J 20 -v 0.1 -iter 1000 -search 2 -gap 10 ./abcboost_predict -data data/covtype.test.csv -model covtype.train.csv_abcrobustlogit2g10_J20_v0.1_w0.model

訓練並測試 s=2 和 g=10 的“ABC RobustLogitBoost”。當然，也可以像演算法 2 那樣訓練規則的魯棒 LogitBoost。圖 8 比較了四種不同方法的測試誤差：Robust LogitBoost、ABC Robust LogitBoost、XGBoost 和 LightGBM，用於分箱引數 MaxBin 從 10 到 10^4。

圖 8 顯示，當 MaxBin=10 時，在作者的包中實現的簡單固定長度分箱方案表現不佳。這是意料之中的。對於這個多分類任務，很明顯，“ABC 魯棒 LogitBoost”大大改進了“魯棒 LogitBoost”。

最後，圖 9 繪製了四種方法的測試誤差歷史。

結論

十年前（或更早），作者完成了 Li 等人（2007）在增強技術和樹模型方面的貢獻；Li（2008、2009、2010a、b），這產生了很多有趣討論（參見示例討論） http://hunch.net/?p=14672010 年），並推動了使用（i）特徵組合的流行增強樹平臺的開發；（ii）樹分裂的二階增益公式，作為標準實現。然後，作者將興趣轉移到其他主題，包括深度神經網路和商業搜尋引擎的計算廣告；雖然作者在商業廣告應用中廣泛使用深度神經網路，但增強樹在工業中仍然非常流行。作者自己的“經驗法則”是，如果應用程式具有少於 10000 個（手工製作或預生成的）特徵和少於一億個訓練樣本，則應首先嚐試增強樹。

注意到，“自適應基類提升”（ABC boost）尚未成為流行的提升樹平臺的一部分。這可能是因為在正式發表的論文（Li，2009，2010b）中，作者只報告了計算成本高昂的窮舉搜尋策略，這可能會阻止從業者嘗試 ABC-Boost。因此，作者決定釋出“快速 ABC-Boost”，這實際上是 Li 和 Zhao（2022a）總結的過去 15 年努力的結果。

最後，值得一提的是，在作者所有關於增強技術和樹模型的論文中，包括 Li 等人（2007），在實現過程中，始終使用“最佳優先”的樹生長策略。Li 是在 2000 年初參加弗裡德曼教授的課堂（並擔任他的助教）時產生這個想法的。見本教程第 76-77 頁 http://www.stat.rutgers.edu/home/pingli/doc/PingLiTutorial.pdf。這是作者在康奈爾大學和羅格斯大學工作期間編譯的課件。

論文原文連結：

http://arxiv.org/pdf/2207.08770.pdf

開原始碼連線：

http://github.com/pltrees/abcboost