1 論文簡介
XGBoost的作者是曾在華盛頓大學研究機器學習的大牛陳天齊，XGBoost全稱是eXtreme Gradient Boosting，從名稱看XGBoost仍然是GBDT，在GBDT基礎上優化和增強。XGBoost以出衆的效率和較高的預測準确率在各大算法比賽中被廣泛使用。這篇文章介紹了XGBoost這種可擴充、端到端的Boosting Tree的新算法。
文章先介紹了Boosting Tree在現在機器學習領域中非常出彩，而XGBoost作為一種先進的Boosting Tree，被各大比賽的選手們廣泛使用。2015年的Kaggle和KDDCup中，所有top排名的隊伍都使用XGBoost。
XGBoost成功背後的最重要因素是在所有情況下的可擴充性。XGBoost在單台機器上的運作速度比現有流行解決方案快十倍以上，可在分布式或記憶體有限的環境中擴充到數十億個執行個體。XGBoost的可擴充性是由于幾個重要的系統和算法優化。文章介紹了這些創新：一種新穎的
稀疏資料感覺算法，用于處理稀疏資料；一種
合理的權重分位數略圖(weighted quantile sketch)能夠在近似學習中處理有權重特征的資料。論文還提出了
緩存通路模式，
資料壓縮和分片的方法。通過結合這些方法，XGBoost可擴充、并行和分布式處理使學習速度更快，用比現有系統少得多的資源來處理數十億規模的資料。
2 Boosting Tree簡介
2.1 Boosting Tree正則化項優化
文章先簡單介紹了Gradient Boosting Tree。使用k棵獨立的回歸樹（CART）使用Boosting內建預測，F包含所有k棵樹。
這裡，q是映射到樹葉子節點索引的函數，T是葉子節點數，w是葉子權重，連續值，也叫score，是映射到該節點的預測值。
下圖是Boosting Tree內建學習的示例。tree1中，+2是預測男孩對遊戲感興趣的權重w1，tree2中，+0.9是對男孩的權重w2。最終預測結果是兩棵樹的score簡單加和。
下圖是Boosting Tree的目标函數，前一項l是損失項，描述模型拟合訓練資料的優劣，從訓練資料預測有多好。後一項Ω是正則化項，Ω作為懲罰項減少模型複雜度，能平滑權重系數防止過拟合。這裡
是葉子數，w是葉子權重，分别是L1和L2的正則化項。
下圖是Boosting tree目标函數的另一種寫法。根據加法模型，
第t棵樹是在第t-1棵樹的基礎上學習優化而來，根據t-1棵樹的預測值，計算殘差，再拟合第t棵殘差樹。
注意：這裡
殘差，是下一輪要預測的目标值。
是泰勒公式裡的
。
這裡用到了高數知識泰勒展開公式。
根據泰勒二階展開，g和h是損失函數的一階和二階導數。
對上式去掉常數項，這裡t-1棵樹的loss已經計算出來，可以作為常數項去除。（待進一步明确）
使用公式（2）替換公式（3）中的懲罰項。
目标函數現在是w的函數。對w求導求極值，令求導結果等于0。
可得到目标函數的最優值。w越小，樹的結構就越好，預測的越好。
把公式（5）帶回到公式（4），計算平方後合并同類項，
目标函數（6）是score函數，可用來衡量樹結構品質的優劣和預測的好壞。
可以窮舉所有的樹結構q，利用公式（6）計算每棵樹score，利用公式（5）優化葉節點權重，求最小化權重w。但樹是無限多的，不可能窮舉。實際中使用貪心算法，從一個節點出發，分割後形成一棵樹。分割點的選擇使用下圖公式Gain的計算來選擇。
HL左子樹分數，HR右子樹分數，第三項是不分割可以得到的分數。減第三項表示分割後比分割前變化量，
最後一項
是加入新葉子節點引入的複雜度代價
公式（7）同上，是Gain的另一種寫法。
2.2 Shrinkage和subsampling防止過拟合
除了正則化項，Boosting Tree還加入了兩項技術防止過拟合。第一項Shrinkage類似于随機梯度下降的步長（學習率），shrinkage是每次tree boosting後增加的學習率權重，能減少個體的影響，為後續的tree boosting留下更多空間，防止在建構某棵樹時過拟合。第二項subsampling類似于RF裡的列抽樣，除了防止過拟合，subsampling還能在後續章節提到的并行計算加速計算。
3 如何尋找分割點的算法
3.1 傳統貪心算法（Basic Exact Greedy Algorithm）
傳統貪心算法，周遊所有分割點，選擇最優分割點。如果有2個特征組合，一共有4對取值，窮舉後要計算4次才能選擇最優分割點。
傳統算法必須先對特征值排序，然後周遊資料計算梯度值。缺點就是效率差，資料可能都不能全放進記憶體。
3.2 近似算法（Approximate Algorithm）
近似算法和傳統貪心算法周遊所有分割點的做法不同，根據特征分位數的分布情況，給出備選特征分割點的建議（proposal）。
近似算法建議有兩種方法，
Global方法在建樹前對所有候選特征做分割選擇，給出建議。并且在下層子樹建構時都用建樹時同樣的選擇。Global全局考慮，是以需要更多的候選特征。
Local方法在每次分割後re-propose，是對global分割後的優化，local方法提出的重新優化分割更精确，在更深的子樹上分割更精确。但Local需要的候選特征更少。
現有的近似算法中，可以直接使用梯度分位數統計資訊，也可以使用其他如二分政策（binning strategy）。梯度分位數統計在後續章節的分布式計算表現出色，甚至可接近傳統貪心算法的準确度。
3.3 權重分位數略圖 （weighted quantile sketch）
近似算法很重要的一步就是找到備選分割點。通常情況會均勻挑選一個特征的分位數作為候選。集合
表示樣本第k個特征的特征值，h表示第n個樣本損失函數的二階梯度。據此定義一個排序函數：
（式8）
對于每個分割點，其函數值
表示用此分位點下包含的二階導之和的比例
函數目标是找到一組候選的分割點
滿足條件（式9）。即相鄰的兩個分割點之間的間隔小于給定的ε。這裡的ε是一個近似系數。
直覺上看，這大緻表示總共選出1/ε個候選點。這裡每一個點都按照其二階導h進行權重。為了說明為何可以使用二階導h作為權重，可以把等式3改寫成如下形式。
即gi/hi做label時的L2損失平方乘以hi作為權重。
對于大規模資料集來說，很重要的是尋找符合條件的候選分割點。已有的分位數略圖算法可以解決當樣本權重相同時的問題。然而，還沒有哪個現成的分位數略圖算法可以解決權重不同的樣本資料。是以，大多數近似算法使用随機抽樣或啟發式的方法，這些方法要不是有失敗的可能，要不就是沒有理論支撐。
為了解決這個問題，論文引入了一個新穎的，有理論支撐的分布式權重分位數略圖算法，其大意是提出一個可以支援融合與剪枝操作的資料結構。而每一個合并與剪枝操作又能保證一定量級上的準确度。細節算法和證明見原論文中的連結。（待進一步閱讀）
3.4 稀疏資料感覺分割算法（Sparsity-aware Split Finding）
現實資料出現稀疏矩陣（Sparsity）非常普遍，比如存在缺失值，大量的0值，特征工程使用one hot encoding獨熱編碼。是以，在每個樹節點增加預設方向，讓算法知道當資料出現稀疏的情況，仍能快速準确分割。
如下圖所示，紅色是樹節點的預設方向，樣本X2中性别是缺失值，根據預設方向仍然可以被分割。
确定預設方向有兩種方法，最優方法也是default使用的是，隻收集非缺失值，從非缺失值資料的統計資訊學習到最好的預設方向。
和其他算法相比，XGBoost能很好處理稀疏資料，随着資料量複雜度線性增長。使用稀疏矩陣感覺算法的XGBoost，在實驗中比其他算法快50倍，
4 系統實作
4.1 塊存儲
資料按列排序後在記憶體中以塊（block）存儲
排序很費時間，是以資料按列排序後在記憶體中以塊存儲，塊中資料按列排序後以列壓縮（CSC）方式存儲。所有樣本資料在計算前隻需做一次排序，後續疊代多次使用排序結果。
傳統貪心算法裡，把所有資料集存儲在一個block裡，分割時可對預先排序的資料線性查找。是以一次掃描獲得的資料統計資訊，可以在後續各級分支計算上多次使用。
下圖描述了這個過程。
在近似算法中，塊結構也非常有用。整個資料使用多個塊，每個塊是整個資料集的子集。多個塊可以分布在多台機器上，也可以從記憶體放在磁盤上。塊中預排序的資料，分位數的計算分割也可以線性掃描。Local propose可以很友善在一個分支上頻繁的做優化建議，二分搜尋（binary search）也可在合并算法上線性計算。
在并行分割搜尋時，可并行為每列資料收集統計資訊，更有效率。塊結構也能在列抽樣（subsampling）操作時很友善選取列資料。
傳統貪心算法的複雜度是
，d是樹的最大深度，K棵樹，
是資料中非缺失的樣本數。如果使用塊結構，Tree Boosting的複雜度是
，這裡
是一次預處理排序，是以塊結構節省了logn系數的開銷。
近似算法中，二分查找算法的複雜度是
，這裡q是特征數，通常特征數量是32到100，logq還是有一定開銷。如果使用塊結構，複雜度是
，B是塊中能包含的最大行數。塊結構也節省了logq系數的開銷。
4.2 緩存通路機制
塊結構方法簡化了節點分割計算時的複雜度，但會頻繁讀取不連續記憶體裡的行資料，記憶體不連續降低了節點分割計算的速度。
緩存通路機制能解決傳統貪心算法裡通路不連續記憶體資料的問題。先把梯度統計資訊資料放在每個線程的緩存裡，能直接在記憶體中讀寫，減少運作開銷。
下圖顯示了在大資料量比較（10M）中，緩存通路機制比無緩存快2倍速度。值得注意的資料量1M時，緩存通路機制沒有明顯的速度提升。
近似算法裡，調整合适的塊結構大小能減少運作開銷。如果選擇太小的塊結構不能充分發揮并行特性，太大的塊結構可能使梯度統計資訊不能裝入cache，緩存無法命中。考慮這兩種情況要選擇合适的塊大小。從下圖兩個資料集給出的實驗結果，選擇每個塊中包括
樣本的塊大小效果最好，同時平衡了緩存命中和并行。
4.3 磁盤資料的塊壓縮和資料分片技術
當資料不能全部裝入記憶體，資料以塊存儲在磁盤上。除了CPU和記憶體，也充分對磁盤讀取進行優化。
主要有2個技術，塊壓縮技術對磁盤上的block按列做壓縮。
資料分片技術，把資料分片到多個磁盤上，每個磁盤分别存儲資料并讀取到記憶體中。這兩個技術都增加了磁盤吞吐量。
5 總結
論文讀畢，深感作者考慮全面。
論文介紹XGBoost在目标函數設計上增加了L1和L2正則項，限制葉子節點數目，降低葉子權重。同時Shrinkage能降低步長，消除個别樹過拟合，為後續樹提升留出更多空間。
在算法設計上，論文提出近似算法，global全局考慮分割點，local細節優化global後的分割結果。權重分位數從分位數統計資訊提升近似算法性能。預設方向在實戰中為稀疏資料樹的分割提供幫助。
在系統實作上，XGBoost 提出了塊結構，Cache存取，磁盤資料的壓縮和分片技術。
綜合看，XGBoost從CPU（算法設計），MEM（Cache），Disk（壓縮和分片）各方面考慮，極盡優化之能。XGBoost既快又準，橫掃各大比賽成為大殺器令人稱道。
相關文獻：
《
XGBoost: A Scalable Tree Boosting System》 : Tianqi Chen, Carlos Guestrin
XGBoost Documentation