摘要
Tree boosting是一種高效、應用廣泛的機器學習方法。在本文中，我們描述了一個名為XGBoost的可擴充端到端樹增強系統，該系統被資料科學家廣泛使用，在許多機器學習難題上取得了最新的成果。我們提出了一種新的稀疏資料稀疏感覺算法和權重分位數草圖的近似樹學習。更重要的是，我們提供了關于緩存通路模式、資料壓縮和分片的見解來建構一個可伸縮的樹增強系統。通過結合這些見解，XGBoost可以使用比現有系統少得多的資源擴充數十億個示例
1、介紹
在本文中，我們描述了XGBoost，一個可擴充的機器學習系統的樹增強。該系統以開放源碼包的形式提供。。
XGBoost成功背後的最重要因素是它在所有場景中的可伸縮性(scalability)。該系統在一台機器上的運作速度比現有的流行解決方案快十倍以上，并可在分布式或記憶體限制設定中擴充到數十億個示例。XGBoost的可伸縮性來自于幾個重要的系統和算法優化。這些創新包括：針對稀疏資料的處理，提出了一種新的樹學習算法。一個理論上合理的權重分位數草圖程式，使處理執行個體權值在近似樹學習。并行和分布式計算使學習速度更快，進而使模型探索速度更快。更重要的是：XGBoost利用核外計算，使資料科學家能夠在桌上型電腦上處理億萬個示例。最後，更令人興奮的是将這些技術組合在一起，使端到端系統能夠以最少的叢集資源擴充到更大的資料。本文的主要貢獻如下:
① 我們設計并建構了一個高度可擴充的端到端樹提升系統。
② 我們提出了一個理論上合理的權重分位數草圖，以有效的方案計算。
③ 介紹了一種新的稀疏感覺并行樹學習算法。
④ 我們提出了一種有效的緩存感覺塊結構用于核外樹學習
雖然已有一些關于parallel tree boosting的工作，但對于核外計算、緩存感覺和稀疏感覺學習等方向還沒有進行探索。更重要的是，結合所有這些方面的端到端系統為真實的用例提供了一種新穎的解決方案。這使得資料科學家和研究人員能夠建構強大的tree boosting算法變種。除了這些主要的貢獻之外，我們還在提出一個正則化學習目标方面做了額外的改進，為了完整起見，我們将包括這個目标。
2、果殼裡的tree boosting
在這一節中，我們将回顧梯度樹增強算法。這一推導是根據已有文獻中梯度推進的相同思路進行的。其中二階方法是由Friedman等人提出的。我們在反流目标上做了微小的改進，這在實踐中被發現是有用的。
2.1學習目标正規化
對于具有n個例子和m個特征的給定資料集 ,樹系綜模型使用K個加性函數預測輸出。(Tree Ensemble Model：對于給定例子的最終預測是每棵樹預測的總和)
回歸樹的空間(也稱為CART)，這裡q表示将示例映射到相應葉索引的每棵樹的結構。T是樹的葉節點數。每個fk對應一個獨立的樹結構q和葉權w。與決策樹不同，每個回歸樹在每個葉上都包含一個連續的分數，我們使用wi來表示第i個葉上的分數。對于給定的示例，我們将使用樹中的決策規則（由q給出）将其分類為葉子，并通過對相應葉子（由w給出）中的得分求和來計算最終預測。為了學習模型中使用的函數集，我們最小化以下正則化的目标
是損失函數去測量預測值y ̂與目标值yi的差别。第二項Ω懲罰模型的複雜性(即回歸樹函數)。額外的正則化項有助于平滑最終學習的權重，以避免過拟合。直覺地看，正則化的目标往往會選擇一個采用簡單的預測函數的模型。在Regularized greedy forest (RGF)模型中也采用了類似的正則化技術。我們的目标和相應的學習算法比RGF更簡單，更容易并行化。當正則化參數設定為零時，目标回落到傳統的梯度樹增強。
2.2 Gradient Tree Boosting
Eq.(2)中的樹系綜模型包含函數作為參數，傳統的歐幾裡得空間優化方法無法對其進行優化，相反，模型是以相加的方式訓練的。正式,讓y ̂_i(t)是第i個執行個體在第t次疊代時的預測，我們需要添加ft來最小化以下目标。
這意味着我們貪婪地根據公式(2)添加了最能改進我們模型的ft。二階近似可以用于在一般設定中快速優化目标
是關于損失函數的一階和二階梯度統計量。我們可以去掉常數項，在步驟t得到如下簡化的目标。
定義作為葉子j的執行個體集
将上式通過等式變換
對于固定結構q(x)，我們可以計算出最優權值ω_j^*的葉子j 通過
并計算出相應的最優值
上式可以作為一個評分函數來衡量樹結構q的品質。這個分數類似于評價決策樹的雜質分數，隻是它是針對更大範圍的目标函數而推導的。圖2說明了如何計算這個分數。
通常不可能枚舉所有可能的樹結構q，取而代之的是貪婪算法，即從單個葉子開始，疊代地向樹中添加分支。假設IL和IR是拆分後左右節點的執行個體集。
2.3 收縮和柱取樣（Shrinkage and Column Subsampling）
除了第2.1節中提到的正則化目标外，還使用了另外兩種技術來進一步防止過拟合。第一種技術是由弗裡德曼提出的收縮技術，收縮以一個因素η衡量新增的權重每一步後的樹形提升。與模型優化中的學習率相似，收縮減小了每棵樹的影響，為未來樹改進模型留下了空間。
第二種技術是列(特征)子抽樣。這種技術在随機森林中使用，它是在一個用于增強梯度的商業軟體中實作的，但在現有的開源包中沒有實作。根據使用者回報，使用列子抽樣比傳統的行子抽樣(也支援行子抽樣)更能防止過拟合。列子樣本的使用也加速了後面描述的并行算法的計算。
3、分裂發現算法
建構樹,尋找分裂點的時候的問題
1、沿着【哪個次元】切
2、在這個次元上，将【取值大于幾】的樣本切到右子樹
3.1 精确貪心算法(Basic Exact Greedy Algorithm)
一個直覺的想法，就是寫兩層循環窮舉這兩個參數，逐個嘗試後保留最優的切分方案。 這就是論文中的算法1: Exact Greedy Algorithm for Split Finding
3.2 近似算法
精确貪婪算法貪婪地枚舉所有可能的分裂點，是一種非常強大的算法。然而，當資料不能完全裝入記憶體時，就不可能有效地這樣做。在分布式環境中也會出現相同的問題。為了在這兩種情況下支援有效的梯度樹增強，需要一種近似算法。
上述精确貪心方法性能不好，因為在内層循環中需要周遊每個特征次元的每種取值。 設有 m維特征，每個特征的取值平均有s種，則周遊成本就是O(m·s)
一個直覺的想法是：上述複雜度中的s 來源于對特征的每種取值都逐個嘗試， 這觀察得太細了。如果我們把各種特征的取值都大緻分到10個桶，而非精确到具體每一個取值，則複雜度變成O(m·10)
通過特征的分布，按照分布式權重直方圖算法确定一組候選分裂點，通過周遊所有的候選分裂點來找到最佳分裂點。在尋找split point的時候，不會枚舉所有的特征值，而會對特征值進行聚合統計，然後形成若幹個bucket(桶)，隻将bucket邊界上的特征值作為split point的候選，進而獲得性能提升。 算法二給出的是global的算法
該算法有兩種變體，取決于何時給出建議。全局變量在樹構造的初始階段提出了所有的候選分割，并在所有層次上使用相同的分割查找建議。局部變體在每次分割後重新提出。
① 所謂"per tree(global) proposal"是指
在建樹之前，隻有一個根節點，所有樣本都在一起。
針對這種情況，求解并記下建樹前的最優分桶方案。
随後，逐層深化建構樹；在建樹過程中，樣本逐漸被分割到各個子樹
考慮具體某一次split動作，目前節點下，待分割的樣本集合與全集不一樣早前的最優分桶方案變得"未必合理"了，但是global假設它仍然近似合理，隻需算一次proposal即可但是考慮到後續無法再細化分桶效果，是以這一次要盡可能分得細一點。
②"per split(local) proposal"是指
每次執行split之前，現算現用此時的最優分割方案适合于較深的樹結構
local不用像global方式那樣設定分桶分的很細，因為它是有針對性的設定，可以在很粗粒度上就達到相同的效果
上述 "算法2"遺留了一個問題: 怎麼分桶?
比較naive的想法是：就按照該次元上的取值大小，等寬/等頻分桶呗。 這也未嘗不可，不過作者有個更巧妙的做法: 按照【對loss的影響權重】等寬分桶. e.g. 如果隻允許分3個桶，就在該特征的取值範圍上切兩刀成三段，使得每一段内的樣本們對loss的影響權重之和占總體比例都約為 33%
如果損失函數是Square loss，即 ,那麼實際上是不帶權(每個樣本的權重一樣)。 如果損失函數是Log loss，則h = pred ∗ (1− pred) h=pred∗(1−pred)h=pred∗(1−pred). 這是個開口朝下的一進制二次函數，是以最大值在p r e d = 0.5 pred=0.5pred=0.5。當pred在0.5附近，值都比較大，也就是權重都比較大，在切直方圖時，我們希望桶比較均勻，是以這部分就會被切分的更細。
ε為采樣率，直覺上了解，我們最後會得到1/ε個分界點。注意，這裡的ε就是每個桶的比例大小
3.4 存在稀疏值時的分裂 Sparsity-aware Split Finding
在許多現實問題中，輸入x是稀疏的是很常見的. 稀疏性可能有多種原因:1)資料中存在缺失值;2)統計中經常出現零記錄;3)特征工程的工件，如單點編碼. 重要的是要使算法意識到資料中的稀疏模式。為了做到這一點，我們建議在每個樹節點中添加一個預設方向。
當稀疏矩陣x中缺少值時，執行個體将分類為預設方向. 在每個分支中有兩個預設方向的選擇。該算法将不存在視為缺失值，并學習處理缺失值的最佳方向。當不存在對應于使用者指定的值時，通過将枚舉限制為一緻的解決方案，也可以應用相同的算法。
據我們所知，大多數現有的樹學習算法要麼隻針對密集資料進行優化，要麼需要特定的程式來處理有限的情況，比如分類編碼
4、系統設計
4.1針對記憶體優化（列分塊）
選擇分裂點時候需要排序，為了減少排序的成本，論文提出将資料存儲在記憶體單元中，稱之為block。每個block中的資料每列根據特征取值排序，并以壓縮列（CSC）格式儲存。這種輸入資料布局隻需要在訓練前計算一次，可以在後續疊代中重複使用。對應精确算法采用一個block，對于近似算法有多個block分别不同的資料子集。
在精确算法中，我們将整個資料集存儲在單個block中，并通過對預排序的資料進行線性掃描來實作分割點搜尋。我們集體對所有葉子進行分割查找，這樣隻需掃描一次block就可以得到所有葉子節點處所有候選分裂節點的統計資訊。圖6顯示了如何将資料集轉換成相應格式并使用block結構找到最優分割。
當使用近似算法時，可以使用多個block，每個block對應于資料集中的不同的行子集。不同的block可以分布在機器上，或者在非核心設定中存儲在磁盤上。使用排序結構，分位數查找步驟在完成排序的列上就變成了線性掃描。這對于在每個分支中頻繁更新候選分割點的本地優先算法非常有價值。直方圖聚合中的二分搜尋也變成了線性時間合并樣式算法。
可以并行地收集每個列的統計資訊，進而為拆分查找提供并行算法。重要的是，列塊結構還支援列子抽樣，因為很容易在塊中選擇列的子集。
4.2 Cache-aware Access
雖然block結構有助于優化分割點查找的時間複雜度，但是算法需要通過行索引間接提取梯度統計量，因為這些值是按特征的順序通路的，這是一種非連續的記憶體通路（意思就是按值排序以後指針就亂了）。 分割點枚舉的簡單實作在累積和非連續記憶體提取之間引入了即時讀/寫依賴性。 當梯度統計資訊不适合CPU緩存進而發生緩存未命中時，這會減慢分割點查找的速度。
對于貪心算法，我們可以通過緩存感覺預取算法來緩解這個問題。 具體來說，我們在每個線程中配置設定一個内部緩沖區，擷取梯度統計資訊并存入，然後以小批量方式執行累積。 預取的操作将直接讀/寫依賴關系更改為更長的依賴關系，有助于資料行數較大時減少運作開銷。 圖7給出了Higgs和Allstate資料集上緩存感覺與非緩存感覺算法的比較。 我們發現，當資料集很大時，實作緩存感覺的貪婪算法的運作速度是樸素版本的兩倍。
對于近似算法，我們通過選擇正确的block尺寸來解決問題。 我們将block尺寸定義為block中包含的最大樣本數，因為這反映了梯度統計量的高速緩存存儲成本。 選擇過小的block會導緻每個線程的工作量很小，并行計算的效率很低。 另一方面，過大的block會導緻高速緩存未命中現象，因為梯度統計資訊不适合CPU高速緩存。良好的block尺寸平衡了這兩個因素。 我們在兩個資料集上比較了block大小的各種選擇，結果如圖9所示。該結果驗證了我們的讨論，并表明每個塊選擇2^16個樣本可以平衡緩存資源利用和并行化效率。
4.3 Blocks for Out-of-core Computation
我們系統的一個目标是充分利用機器的資源來實作可擴充的學習。 除處理器和記憶體外，利用磁盤空間處理不适合主記憶體的資料也很重要。為了實作核外計算，我們将資料分成多個塊并将每個塊存儲在磁盤上。在計算過程中，使用獨立的線程将塊預取到主存儲器緩沖區是非常重要的，因為計算可以是以在磁盤讀取的情況下進行。但是，這并不能完全解決問題，因為磁盤讀取會占用了大量計算時間。減少開銷并增加磁盤IO的吞吐量非常重要。 我們主要使用兩種技術來改進核外計算。
Block Compression 我們使用的第一種技術是塊壓縮。該塊從列方向壓縮，并在加載到主存儲器時通過獨立的線程進行解壓。這可以利用解壓過程中的一些計算與磁盤讀取成本進行交換。我們使用通用的壓縮算法來壓縮特征值。對于行索引，我們通過塊的起始索引開始減去行索引，并使用16位整型來存儲每個偏移量。這要求每個塊有2^16個樣本，這也被證明是一個好的設定。在我們測試的大多數資料集中，我們實作了大約26％到29％的壓縮率。
Block Sharding第二種技術是以另一種方式将資料分成多個磁盤。為每個磁盤配置設定一個實作預取的線程，并将資料提取到記憶體緩沖區中，訓練線程交替地從每個緩沖區讀取資料。當有多個磁盤可用時，這有助于提高磁盤讀取的吞吐量
2020_9_20 組會