GBDT庫原理和使用的比較
GBDT擁有廣泛的應(yīng)用，然而GBDT在大數(shù)據(jù)集存在性能問題。為此很多GBDT方法都聚焦在模型加速和并行計算，在本文中對比了最近的GBDT系統(tǒng)的優(yōu)缺點。
背景介紹
有許多GBDT的庫，雖然這些庫提供了類似的功能，但它們的算法設(shè)計和系統(tǒng)實現(xiàn)有很大的不同：
XGBoost LightGBM CatBoost ThunderGBM
比如哪些部分分別在GPU和CPU上實現(xiàn)，以及樹增長的策略。但樹模型整體的構(gòu)建過程是類似的：每個決策樹的構(gòu)建深度從0到最大深度。采用基于貪心的節(jié)點分割算法遞歸地生長樹，直到達到終止條件。
求解每個節(jié)點的分裂點的方法包括精確方法和近似方法：
在精確的方法中會遍歷所有的特征值，以找到最大化增益的分割。對于高維數(shù)據(jù)集來說，找到精確的分割點的成本高得令人望而卻步。 在近似方法中，只嘗試由分位數(shù)或直方圖等技術(shù)生成的一些候選點。
GBDT并行訓(xùn)練
開發(fā)高效的GBDT訓(xùn)練并行算法具有挑戰(zhàn)性
最小化通信成本 計算資源的利用率 數(shù)據(jù)適應(yīng)性
Node Split
尋找一個節(jié)點的最佳分割點的傳統(tǒng)方法是通過枚舉所有分割點，這種方法對于取值空間較大的情況下是非常昂貴的。
當前并行GBDT系統(tǒng)常見解決方案是使用基于直方圖的近似，而不是枚舉所有可能的分裂點，或者說列舉多個有代表性的分裂點。
直方圖近似是效率和準確性之間的權(quán)衡，但這種解決方案不適用于高維和稀疏問題，因為每個維度都需要與一個直方圖關(guān)聯(lián)。 在并行算法中，需要維護的直方圖總數(shù)等于：線程數(shù)乘以特征數(shù)量。
Parallelism Granularity
并行度的關(guān)鍵粒度包括三個級別：
節(jié)點級別的并行 特征級別的并行 值級別的并行
在節(jié)點級并行：一個線程專門用于查找節(jié)點的最佳分割，因此它將計算節(jié)點中所有特性的所有值的增益。
在特征級并行中：一個線程專門用于僅為一個節(jié)點的一個特征查找最佳值。因此一個線程計算一個節(jié)點的一個特征的所有值的增益。
在值級并行性中：一個線程計算節(jié)點中一個特征的一個值的增益?；诙嗪薈PU的訓(xùn)練算法經(jīng)常會適應(yīng)節(jié)點級和特征級的并行性。
Training Data Partitioning
當訓(xùn)練問題由多個GPU或多個CPU處理時，需要對訓(xùn)練數(shù)據(jù)集進行分區(qū)，數(shù)據(jù)有三種劃分方法：
基于實例的分區(qū) 基于特征的分區(qū) 混合實例和特征的分區(qū)
基于實例的分區(qū)：將許多訓(xùn)練實例分配給機器，其余的實例分配給其他機器。這種分區(qū)方式的好處是，每臺機器都有存儲在其中的實例的全部信息。因此當計算一個實例的訓(xùn)練錯誤時，存儲該實例的機器可以很容易地計算出它。
相比之下，基于特性的分區(qū)會將多個特性的所有值分配給一臺機器。因此，計算訓(xùn)練錯誤要困難得多，因為機器沒有計算實例的所有信息。但是， 基于特征的劃分的優(yōu)點是，機器可以很容易地找到特征的最佳分割值，因為訓(xùn)練數(shù)據(jù)的所有特征值都存儲在一起。
混合劃分分區(qū)將訓(xùn)練數(shù)據(jù)集視為一個矩陣，每個GPU/CPU處理一個塊或瓷磚。主流GBDT可以使用基于實例的分區(qū)或基于特性的分區(qū)。由于實現(xiàn)和維護的復(fù)雜性，混合劃分方法并沒有得到廣泛的采用。
GBDT Training on CPUs
在CPU的并行中，有許多挑戰(zhàn)：
由于樹狀結(jié)構(gòu)的性質(zhì)，GBDT對數(shù)據(jù)的模式是不規(guī)則的。 在GBDT訓(xùn)練期間對特征值進行排序非常耗時。
為了解決這些挑戰(zhàn)，現(xiàn)有的GBDT庫可以在CPU上并行運行，并在并行性、節(jié)點分割和 訓(xùn)練數(shù)據(jù)分區(qū)方面采用不同的設(shè)計。
GBDT Training on GPUs
為了利用GPU 的能力，需要在優(yōu)化GBDT訓(xùn)練的并行性、節(jié)點分割和訓(xùn)練數(shù)據(jù)分區(qū)方面做大量的工作。
GPU上的XGBoost使用屬性級和節(jié)點級并行性，對于屬性級并行性，GPU線程塊用于計算屬性的最佳分割點。LightGBM CatBoost還使用尋找最佳分割點來避免在枚舉所有可能的分割點的同時消耗過多內(nèi)存。
System Comparison
所有實驗中不同庫的預(yù)測精度相似，與XGBoost和ThudergGBM相比，LightGBM和CatBoost往往具有較低的預(yù)測精度。
所有的庫都可以在GPU上運行來顯著提高效率。其次LightGBM通常在CPU上比其他現(xiàn)有庫工作得更好，CatBoost在GPU實現(xiàn)是非常好的，但也需要更多的顯存。
GBDT分布式訓(xùn)練
Load Balancing
根據(jù)實例或特性的數(shù)量進行負載平衡 根據(jù)特征值的數(shù)量進行負載平衡
Network Communication
網(wǎng)絡(luò)通信主要從兩個方面出發(fā)：構(gòu)建一個特征的直方圖和在所有特征中找到最佳特征。
挑戰(zhàn)和發(fā)展趨勢
挑戰(zhàn)
盡管擁有很多GBDT庫，但一個公平和健壯的基準測試仍然是相當具有挑戰(zhàn)性的開放問題。
數(shù)據(jù)隱私問題，當部署模型時用戶可以相對容易地從決策樹中提取信息。
自動化的功能工程和參數(shù)調(diào)優(yōu)，超參數(shù)對模型的精度影響非常大。
增量式學(xué)習(xí)和在線學(xué)習(xí)，在流失數(shù)據(jù)下如何訓(xùn)練已有模型。
發(fā)展趨勢
使用異構(gòu)集群的GPU。 在TPU和FPGA上使用GBDT。
相關(guān)閱讀：