XGBoost

摘要

提升樹是一種非常高效和廣泛應(yīng)用的機器學(xué)習(xí)算法。在這篇文章中，我們描述了一個名為XGBoost的可擴展的端到端的提升樹模型，數(shù)據(jù)科學(xué)家們在很多機器學(xué)習(xí)挑戰(zhàn)中廣泛應(yīng)用該系統(tǒng)并實現(xiàn)目前最好的結(jié)果。我們提出一種新穎的稀疏感知算法用于稀疏數(shù)據(jù)沛硅，一種weighted quantile sketch用于樹的學(xué)習(xí)。更重要的是绕辖，我們提供關(guān)于緩存訪問模式摇肌、數(shù)據(jù)壓縮和分片的見解，以構(gòu)建一個可擴展的提升樹模型仪际。通過結(jié)合這些方法围小，XGBoost可采用比現(xiàn)存系統(tǒng)少得多的資源來處理數(shù)十億規(guī)模的數(shù)據(jù)。

1. introduction

機器學(xué)習(xí)和數(shù)據(jù)驅(qū)動的方法在許多領(lǐng)域變得非常重要树碱。智能垃圾郵件分類器通過從大量的垃圾郵件數(shù)據(jù)和用戶反饋中學(xué)習(xí)來保護我們的郵箱肯适；廣告系統(tǒng)學(xué)習(xí)將正確的廣告與正確的背景相匹配；欺詐檢測系統(tǒng)保護銀行免受惡意攻擊成榜；異常事件檢測系統(tǒng)幫助實驗物理學(xué)家發(fā)現(xiàn)新的物理現(xiàn)象框舔。有兩個重要因素可以推動這些成功的應(yīng)用：使用能捕獲復(fù)雜數(shù)據(jù)依賴性的有效的（統(tǒng)計）模型，以及能從大型數(shù)據(jù)集里學(xué)習(xí)出模型的可擴展的學(xué)習(xí)系統(tǒng)赎婚。

在實際應(yīng)用的機器學(xué)習(xí)方法里雨饺，Gradient Tree Boosting （GBDT）是一個在很多應(yīng)用里都很出彩的技術(shù)。提升樹方法在很多有標準分類基準的情況下表現(xiàn)很出色惑淳。LambdaMART：一種用于排序的提升樹的變種，在排序問題中實現(xiàn)了目前最優(yōu)的結(jié)果饺窿。它除了被用于單獨的預(yù)測器歧焦，還在實際生產(chǎn)中被用于廣告點擊率預(yù)測。它是很多集成方法里的實際選擇，此外還用于Netflix這樣的比賽绢馍。

本文描述的可擴展的提升樹機器學(xué)習(xí)系統(tǒng)已經(jīng)開源了向瓷，它的影響力已經(jīng)被許多機器學(xué)習(xí)和數(shù)據(jù)挖掘的比賽所廣泛認可。拿機器學(xué)習(xí)大賽Kaggle舉例：2015年發(fā)布的29個獲勝方法里有17個用了XGBoost舰涌。在這些方案里猖任，有8個僅用了XGBoost，另外的大多數(shù)用它結(jié)合了神經(jīng)網(wǎng)絡(luò)瓷耙。對比來看朱躺，第二流行的方法，深度神經(jīng)網(wǎng)絡(luò)搁痛，只被用了11次长搀。這個系統(tǒng)的成功性也被KDDCup2015所見證了，前十的隊伍都用了XGBoost鸡典。此外源请，據(jù)勝出的隊伍說，很少有別的集成學(xué)習(xí)方法效果能超過調(diào)好參的XGBoost彻况。

這些結(jié)果說明我們的系統(tǒng)能在很廣泛的問題里獲得很好的結(jié)果谁尸。這些成功案例包括：網(wǎng)頁文本分類、顧客行為預(yù)測、情感挖掘瞧甩、廣告點擊率預(yù)測塑崖、惡意軟件分類、物品分類背镇、風(fēng)險評估、大規(guī)模在線課程退學(xué)率預(yù)測泽裳。雖然這些問題依賴于特定領(lǐng)域的數(shù)據(jù)分析和特征工程瞒斩，但選擇XGBoost是這些人的共識，這體現(xiàn)出了我們的系統(tǒng)的影響力和重要性涮总。

XGBoost獲取成功最重要的一個因素是在各種場景的可擴展性胸囱。該系統(tǒng)在單機上的運行速度比現(xiàn)有的主要解決方案快十倍以上， 在分布式或者內(nèi)存有限的環(huán)境下可以擴展到數(shù)十億個實例瀑梗。XGBoost的可擴展性是因為幾個重要系統(tǒng)和算法的優(yōu)化烹笔，這些創(chuàng)新包括：

1. 應(yīng)對稀疏數(shù)據(jù)的新穎樹學(xué)習(xí)算法

2. 一個理論上合理的weighted quantile sketch程序確保處理近似樹學(xué)習(xí)的實例權(quán)重

3. 并行和分布計算使學(xué)習(xí)速度更快，確保更快的進行模型探索

4. 更重要的是抛丽，XGBoost利用核外計算谤职，使數(shù)據(jù)科學(xué)家能夠在筆記本上處理數(shù)億個實例

5. 最后，更令人興奮的是將這些技術(shù)組合在一起亿鲜，形成一個端到端系統(tǒng)允蜈，它可以用最少的集群資源擴展到更大的數(shù)據(jù)。

這篇論文的主要貢獻：

1. 設(shè)計和實現(xiàn)了一種高度可擴展的端到端的提升樹系統(tǒng)

2. 提出了一個理論上可證明的weighted quantile sketch 進行高效率計算

3. 提出了一種新穎的基于稀疏感知的并行樹學(xué)習(xí)算法

4. 我們提出了一種有效的緩存感知塊結(jié)構(gòu)用于核外樹學(xué)習(xí)。

雖然在并行樹推廣方面有一些已有的工作饶套，但諸如核外計算漩蟆，緩存感知和稀疏感知學(xué)習(xí)等方向尚未被探索。更重要的是妓蛮，結(jié)合所有這些方面的端到端系統(tǒng)為實際使用情況提供了一種新穎的解決方案怠李。這使得數(shù)據(jù)科學(xué)家和研究人員能夠構(gòu)建提升樹算法的強大變種。除了這些主要的貢獻之外蛤克，我們還提出了一個改進正則化學(xué)習(xí)的方法捺癞。

在本文的其余部分安排如下。我們將在第二章節(jié)首先回顧一下提升樹咖耘，并介紹一個正則化的目標翘簇。然后，我們在第三部分介紹拆分查找方法儿倒，第四部分是系統(tǒng)設(shè)計版保，包括相關(guān)的實驗結(jié)果，為我們提到的每個優(yōu)化方法提供量化支持夫否。相關(guān)工作在第五節(jié)討論彻犁。詳細的端到端評估在第六部分。最后凰慈，我們在第七部分總結(jié)這篇論文汞幢。

2. 提升樹

我們在這一節(jié)中回顧了梯度樹提升算法。其推導(dǎo)過程與現(xiàn)有梯度提升理論的推導(dǎo)思路相同微谓。具體來說森篷，二階方法起源于Friedman等人的[12]。我們在正則目標上做了一些小的改進豺型，這在實踐中很有幫助仲智。

2.1 正則化學(xué)習(xí)目標

一個樹集成模型使用K個加性函數(shù)來預(yù)測輸出：

image.png

q?表示每個樹結(jié)構(gòu)，它將一個樣本映射到對應(yīng)的葉子結(jié)點上姻氨；T是葉子節(jié)點的個數(shù)钓辆；?表示一個獨立的樹結(jié)構(gòu)q和相對應(yīng)的葉子權(quán)重?。這里每個葉子結(jié)點輸出一個連續(xù)值肴焊，我們使用?表示第i個葉子結(jié)點的值前联。對于一個樣本，我們使用樹的決策規(guī)則將其分類到葉子節(jié)點娶眷，然后計算每棵樹對應(yīng)葉子節(jié)點的分數(shù)和(?)作為最后的輸出似嗤。

例如：

image.png

我們最小化一下的正則化對象：

image.png

上式所加的正則化幫助平滑最終學(xué)習(xí)的權(quán)重避免過擬合。直覺上來說届宠，正則化對象將傾向于挑選出一個簡單双谆、可預(yù)測的函數(shù)壳咕。我們的目標函數(shù)和相應(yīng)的學(xué)習(xí)算法更為簡單，更容易并行化顽馋。當正則化參數(shù)設(shè)置為0時，目標函數(shù)將回到傳統(tǒng)的梯度提升樹

2.2 梯度提升樹

image.png

我們貪婪的添加?來最大的提升我們的模型幌羞。二階近似用于快速的優(yōu)化目標對象

image.png

我們?nèi)コ?shù)項

image.png

image.png

等式6可以作為一個評分函數(shù)來衡量一個樹型結(jié)構(gòu)q的質(zhì)量寸谜。
下圖展示了樹的評分怎么計算

image.png

正常情況下我們不能列舉所有的結(jié)構(gòu)q，因此提出一個貪婪算法属桦，他從單個葉子開始熊痴，迭代的向樹中添加分支

image.png

2.3 Shrinkage and Column Subsampling

除了上述所說的添加正則對象之外，還有兩種技術(shù)被引入來進一步防止過擬合

1. shrinkage：在提升樹的每一步添加一個因子作為權(quán)重聂宾。 類似于學(xué)習(xí)率果善，它降低每個樹個體的影響， 留下空間給未來的樹提高模型

2. 第二個技術(shù)是特征的二次采樣系谐，這種技術(shù)也被用于隨機森林巾陕。該方法實際效果好于行的采樣，同時也加速計算后面所描述的并行算法

3. 劃分查找算法

3.1 Basic Exact Greedy Algorithm

樹學(xué)習(xí)的一個關(guān)鍵問題在于尋找等式7中的最優(yōu)劃分點纪他。一種最簡單的方法是尋找所有特征的所有劃分點（Exact Greedy Algorithm ）鄙煤。它列舉所有連續(xù)特征的可能劃分點在計算上是苦難的。為了更高效茶袒，該算法必須首先排升序排列所有的特征值梯刚，按排序順序訪問數(shù)據(jù)，累積梯度統(tǒng)計薪寓。

image.png

3.2 近似算法

當數(shù)據(jù)量十分龐大亡资，以致于不能全部放入內(nèi)存時，精確的貪婪算法就不可能很有效率向叉，通樣的問題也出現(xiàn)在分布式的數(shù)據(jù)集中锥腻，為了高效的梯度提升算法，在這兩種背景下植康，近似的算法被提出使用旷太。

近似算法首先根據(jù)特征分布的百分數(shù)提出侯選劃分點。該算法將連續(xù)特征映射到候選點對應(yīng)的桶進行劃分销睁，聚集統(tǒng)計信息供璧，查找最優(yōu)解決方案。

該算法的主要思想如下：枚舉所有特征冻记，根據(jù)特征睡毒，比如是第 k 個特征的分布的分位數(shù)來決定出 l個候選切分點 ? ，然后根據(jù)這些候選切分點把相應(yīng)的樣本映射到對應(yīng)的桶中冗栗，對每個桶的 G,H 進行累加演顾。最后在候選切分點集合上貪心查找

這里給了近似算法的兩種變體供搀，主要是根據(jù)候選點來源不同進行區(qū)分：

1. 全局變體提議所有的劃分候選在最初樹的構(gòu)建階段確定，后期每個葉子使用相同的提議尋找劃分點钠至。全局變體需要更多的候選點葛虐，因為在每次劃分之后候選點不會改善。需要設(shè)置更小的分位數(shù)間隔棉钧，這里用 ? 表示屿脐，3分位的分位數(shù)間隔就是 1/3，產(chǎn)生更多的桶宪卿，特征分裂查找基于候選點多的诵，計算較慢，但只需在全局執(zhí)行一次佑钾，全局分桶多次使用西疤。

2. 局部變體在每次分裂時重新分桶：每次分裂重新局部（local）分桶，可以設(shè)置較大的 ? 休溶，產(chǎn)生更少的桶代赁，每次特征分裂查找基于較少的候選點，計算速度快邮偎，但是需要每次節(jié)點分裂后重新執(zhí)行管跺，論文中說該方案更適合樹深的場景。

當給定足夠的候選點時禾进，全局變體將達到和局部變體相同的精度豁跑。同時，我們也發(fā)現(xiàn)泻云，當百分位策略給定合理的近似水平時艇拍，也可以得到和 Exact Greedy Algorithm 相同的精度

3.3 Weighted Quantile Sketch

近似算法中一個重要的步驟為提出候選劃分點。通常情況下宠纯，一個特征的分位數(shù)使候選分裂點均勻地分布在數(shù)據(jù)集上卸夕。

image.png

image.png

上式可視作標簽為?且權(quán)重為?的平方誤差

其實基于帶權(quán)分位數(shù)方案的思想很簡單，就是如下圖所示引入樣本權(quán)重

img

3.4 稀疏感知的劃分查找

許多真實世界中的問題婆瓜，數(shù)據(jù)可能是稀疏的快集，主要原因如：存在缺失值、統(tǒng)計中0項廉白、特征工程中one-hot等編碼个初。對于數(shù)據(jù)的稀疏模式的感知是非常重要的。本文算法提出了在每個樹節(jié)點提添加一個默認方向猴蹂。即當一個實例值是缺失時院溺，該實例會被分類到默認方向。最優(yōu)默認方向從數(shù)據(jù)中學(xué)取

image.png

算法展示如下：

image.png

眾所周知磅轻，大多數(shù)樹學(xué)習(xí)模型要么只優(yōu)化稠密數(shù)據(jù)珍逸，要么要對類似于分類編碼值類的有限樣例進行特定的處理逐虚。XGBoost以一種統(tǒng)一的方式處理所有的稀疏模式。更重要的是該方法利用稀疏性使計算復(fù)雜度與輸入中非缺失樣例的數(shù)量呈線性關(guān)系谆膳。

下圖展示了稀疏感知和簡單實施（不考慮稀疏性）的比較叭爱。我們發(fā)現(xiàn)稀疏感知比簡單算法快50倍。

image.png

4.系統(tǒng)設(shè)計

4.1 Column Block for Parallel Learning

樹學(xué)習(xí)大多數(shù)時間消耗在獲取數(shù)據(jù)的排序上/為了降低排序成本漱病，我們提出了將數(shù)據(jù)存儲在內(nèi)存單元中（block）涤伐，每個block的數(shù)據(jù)以列壓縮CSC形式存儲，每列通過對應(yīng)的特征值排序缨称。輸入數(shù)據(jù)僅需要在訓(xùn)練之前計算一次，之后的迭代中可以重復(fù)使用祝迂。

在exact greedy algorithm中睦尽，我們存儲整個數(shù)據(jù)集在單個block中，通過對預(yù)排序的條目線性掃描運行劃分搜索算法型雳。我們對所有的葉子節(jié)點做劃分查找当凡，因此對block的一次掃描可以收集所有葉子分支上劃分候選點的統(tǒng)計信息。

block結(jié)構(gòu)對近似算法也是有幫助的纠俭⊙亓浚可以使用多個block，每個block對應(yīng)數(shù)據(jù)集中行的子集冤荆，不同的block可以分布在不同的機器上或者核外硬盤上朴则。使用排序結(jié)構(gòu)，分位數(shù)查找步驟變成對排序后的列進行線性查找钓简。這對局部近似變體是非常有價值的乌妒，因為該變體在每個分支頻繁的產(chǎn)生候選點。

搜集每列的統(tǒng)計信息也可以是并行化的外邓，提供劃分查找的并行化算法撤蚊。即列block支持列采樣，在每個塊中搜集列子集的統(tǒng)計信息损话。

談一談自己的理解

1. 這里數(shù)據(jù)采用CSC的壓縮形式進行存儲侦啸，block中保存排序后的特征值和對樣本的引用。由于數(shù)據(jù)的稀疏性丧枪，采用CSC壓縮方式可以更為高效的提出特征值光涂。

2. 對于同時對不同葉子結(jié)點進行劃分查找，將不同葉子節(jié)點數(shù)據(jù)放入不同block可以進行并行查找

3. 對于列的信息統(tǒng)計豪诲，可以在并行對不同的特征進行劃分點查找顶捷，即特征的并行化處理。

4.2 Cache-aware Access

雖然提出的block結(jié)構(gòu)能夠幫助優(yōu)化劃分查找的計算復(fù)雜度屎篱，但由于在順序訪問特征值時服赎，訪問的是一塊連續(xù)的內(nèi)存空間葵蒂。需要間接通過行索引獲取樣本梯度信息，這并不是連續(xù)的內(nèi)存空間重虑。

對于exact greedy algorithm践付，我們設(shè)置緩存預(yù)取算法來解決這個問題。即我們在每個線程中分配一個buffer缺厉，讀取梯度信息存儲在buffer中永高。這種預(yù)取策略幫助降低數(shù)據(jù)過大時的運行時間。

在近似算法中提针，對塊的大小進行了合理的設(shè)置命爬。定義Block的大小為Block中最多的樣本數(shù)。設(shè)置合適的大小是很重要的辐脖，設(shè)置過大則容易導(dǎo)致命中率低饲宛，過小則容易導(dǎo)致并行化效率不高。經(jīng)過實驗嗜价，發(fā)現(xiàn)?比較好

4.3 "核外"塊計算

系統(tǒng)目標在于充分利用機器資源進行可擴展的學(xué)習(xí)艇抠。除了處理器和內(nèi)存之外，利用磁盤空間處理不能放入內(nèi)存的數(shù)據(jù)是很重要的久锥。為了確保核外計算家淤，我們將數(shù)據(jù)劃分為多個block，并將block存入磁盤瑟由。在計算中使用獨立線程預(yù)讀取block到緩存絮重。因此計算和磁盤讀取可以同步進行。但是由于磁盤讀取耗時過長错妖，降低開銷和增加磁盤IO的吞吐量非常重要绿鸣。我們主要使用兩種技術(shù)來改進核外計算。

1. 數(shù)據(jù)塊壓縮：對數(shù)據(jù)塊按列壓縮暂氯，在將數(shù)據(jù)傳輸?shù)絻?nèi)存中潮模，最后再由獨立的線程解壓縮。即將磁盤的讀取消耗轉(zhuǎn)換為解壓縮所消耗的計算資源痴施。

2. 數(shù)據(jù)塊分區(qū)：將數(shù)據(jù)分片到多個磁盤擎厢，每個磁盤分配一個預(yù)取線程，將數(shù)據(jù)fetch到in-memory buffer辣吃，再有訓(xùn)練線程從各個緩存中讀取數(shù)據(jù)动遭。訓(xùn)練線程交替讀取多塊緩存的同時，計算任務(wù)也在運轉(zhuǎn)神得，提升了硬盤總體的吞吐量厘惦。

5. 相關(guān)工作

6. 端到端評估

這里主要是對XGBoost和其他模型的比較，簡單介紹其中的討論

1. columns subsample：文中兩次實驗發(fā)現(xiàn)對列采樣的結(jié)果比使用全部特征的精度稍低哩簿，這可能是因為特征中含有某些重要特征宵蕉，貪婪的選擇特征可能是有益的酝静；但也有實驗發(fā)現(xiàn)列采樣反而會提高泛化精度，這可能是因為列采樣幫助預(yù)防過擬羡玛。

7. XGBoost優(yōu)缺點

7.1 優(yōu)點

• 精度更高：GBDT 只用到一階泰勒展開别智，而 XGBoost 對損失函數(shù)進行了二階泰勒展開。

• 靈活性更強： GBDT 以 CART 作為基分類器稼稿，XGBoost 不僅支持 CART 還支持線性分類器薄榛，使用線性分類器的 XGBoost 相當于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。此外让歼，XGBoost 工具支持自定義損失函數(shù)敞恋，只需函數(shù)支持一階和二階求導(dǎo)；

• 正則化：XGBoost目標函數(shù)中加入了正則化項谋右，用于控制模型的復(fù)雜度耳舅。正則項中包含樹的葉子節(jié)點個數(shù)、葉子節(jié)點權(quán)重的L2范數(shù)倚评。正則項降低了模型的方差，使學(xué)習(xí)出來的模型更加簡單馏予，有助于防止過擬合天梧，這也是XGBoost優(yōu)于傳統(tǒng)GBDT的一個特性。

• Shrinkage：在提升樹的每一步添加一個因子作為權(quán)重霞丧。 類似于學(xué)習(xí)率呢岗，它降低每個樹個體的影響， 留下空間給未來的樹提高模型

• 列采樣：這種技術(shù)也被用于隨機森林蛹尝。不僅能降低過擬合后豫，還能減少計算

• 可并行的近似算法： 樹節(jié)點在進行分裂時，我們需要計算每個特征的每個分割點對應(yīng)的增益突那，即用貪心法枚舉所有可能的分割點挫酿。當數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下，貪心算法效率就會變得很低愕难，所以XGBoost還提出了一種可并行的近似算法早龟，用于高效地生成候選的分割點。這種方法對特征值排序猫缭，以加權(quán)分位數(shù)取候選點

• 稀疏感知：對于特征的值有缺失的樣本葱弟，XGBoost采用的稀疏感知算法可以自動學(xué)習(xí)出它的分裂方向。

• XGBoost并行計算：XGBoost的并行是在特征粒度上的猜丹。決策樹學(xué)習(xí)最耗時的一個步驟就是對特征的值進行排序芝加。XGBoost以CSC壓縮對數(shù)據(jù)存儲入block并進行排序，后面的迭代中重復(fù)的使用該結(jié)構(gòu)射窒，減少計算量藏杖。在進行節(jié)點的分裂時将塑，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂制市，那么各個特征的增益計算就可以開多線程進行抬旺。

• 緩存訪問：由于對樣本梯度的訪問是不連續(xù)的，這里在每個線程設(shè)置一個buffer祥楣，讀取梯度信息存儲在buffer中开财。這種預(yù)取策略幫助降低數(shù)據(jù)過大時的運行時間。

• 核外塊計算：采用獨立的線程預(yù)讀取block到緩存误褪，實現(xiàn)計算和磁盤讀取同時進行责鳍；同時為了提高效率采用數(shù)據(jù)塊壓縮和數(shù)據(jù)塊分割放入不同磁盤，多個線程同時讀取多個磁盤提高效率兽间。

7.2 缺點

• 雖然利用預(yù)排序和近似算法可以降低尋找最佳分裂點的計算量历葛，但在節(jié)點分裂過程中仍需要遍歷數(shù)據(jù)集；
• 預(yù)排序過程的空間復(fù)雜度過高嘀略，不僅需要存儲特征值恤溶，還需要存儲特征對應(yīng)樣本的梯度統(tǒng)計值的索引，相當于消耗了兩倍的內(nèi)存帜羊。

參考：

深入理解XGBoost咒程，優(yōu)缺點分析，原理推導(dǎo)及工程實現(xiàn)

XGBoost 論文翻譯+個人注釋