機器學習競賽大殺器XGBoost--原理篇

01-31

在機器學習競賽中被廣泛使用的XGBoost系統已經久負盛名，近期兩周時間我參加了一個京東金融的貸款預測競賽使用的就是XGB，之前雖然也簡單的使用過，但並沒有真正去深入了解這個系統，這次通過閱讀XGB原論文和官方Tutorials 之後才算有了一些深入的了解，本文將對XGB進行一個簡單的講解，以供小夥伴學習。

XGB是一個具有可擴展性的樹提升演算法機器學習系統，它的可擴展性體現在以下四個方面：

模型的scalability，弱分類器除cart外也支持lr和linear
策略的scalability，可以支持不同的loss functions，來優化效果，只要一、二階可導即可
演算法的scalability，做了很多細節工作，來優化參數學習和迭代速度，特徵壓縮技，bagging學習中的特徵抽樣，特徵選擇與閾值分裂的分位方法和並行方法等
數據的scalability，因為3中的優化，支持B級別的快速訓練和建模；同時也因為加上了正則項和隨機特徵抽樣，減少了過擬合問題

（來自王浩的一個回答。）

XGB系統的主要優勢及創新根據作者的描述，可以歸納為以下幾點：

一個新奇的（novel）處理稀疏數據的樹學習演算法；
使用近似樹學習（ approximate tree learning）理論利用分位數的描述，可以給每一個訓練實例一個合理的加權權重；
並行和分散式的設計使得學習速度非常快，建模更快速；
XGBoost exploits out-of-core computation 機制讓僅使用筆記本就可以處理數以億計的數據成為可能。
端到端系統使用最小的集群資源就可以處理大量的數據。

XGB被用於監督學習，監督學習指利用具有多個特徵的訓練數據xi來預測目標變數yi，在訓練數據中yi作為標籤是給定的。在正式介紹XGB之前，我們先來回顧一下監督學習的相關知識。

1、監督學習基礎理論

1.1、模型和參數

監督學習中的模型指利用給定的xi如何來預測目標yi的數學結構，對於最簡單的線性模型，它的模型結構如下：

它是一條組合輸入特徵權重的直線。預測值根據任務的不同具有不同的解釋，如回歸和分類。

參數就是我們的模型需要從數據中學習的一些數據，在線性回歸問題中，參數就是每一個特徵的係數 $theta$ 。通常，我們使用 $theta$ 來表示參數。

1.2、目標函數：訓練損失+正則化

依據對yi的不同理解，我們有不同的問題，比如回歸，分類和排序等，利用訓練數據我們需要找到一個方法來學習到最好的參數。因此我們需要定義一個目標函數來衡量模型學習到的參數的好壞。目標函數通常包含兩部分：訓練損失和正則化。使用數學公式表達如下：

L是訓練損失函數， $Omega$ 是正則項。訓練損失函數測量了我們的模型在訓練數據上如何學習，例如回歸任務的一個常用損失函數是均方誤差（MSE）：

另一個常用的損失函數是邏輯斯蒂回歸中的logistic loss

正則項用於控制模型的複雜度，也就是防止模型過擬合。聽上去有點抽象，那麼來看看下面這個例子吧。

左上角描繪的是用戶隨著時間的變化對某話題的感興趣程度的變化，如果使用step function來建模，可以看到右上角的模型基本上擬合到每一個數據點，然而也可以看到它太複雜了，也就是模型複雜度太高；而對於左下角模型，它雖然比較簡單，但是很多數據都沒有擬合到；最後看看右下角的模型，它簡單，而且基本擬合到所有數據點。因此我們說右下角的模型是最好的，對於一個機器學習的模型的通用原則是：簡單並且準確。模型往往需要在簡單和準確之中做一個折中，這種折中也成為偏差-方差的折中（bias-variance tradeoff）。

2、樹提升模型簡介

2.1、正則化的學習目標

對於給定的數據集，n個實例，m個特徵，

樹集成模型（下圖所示）使用K個函數的累加和來預測輸出。

這裡

是所有回歸樹（CART）函數空間，裡面的q表示每顆樹的結構，它將實例映射到相應的葉子節點的索引；T表示一棵樹的葉子節點個數；每一個fk相對應一個獨立的樹結構q和葉子節點權重w。與決策樹不同的是，每一個回歸樹在每一個葉子節點上包含了連續的分值，wi表示第i個葉子節點的得分。在上圖給定的例子中，我們使用樹的決策規則來將小男孩分類到對應的葉子節點，然後將所有分到的葉子節點所對應的分值相加，最後得到小男孩的最終得分2.9，因此，相較於老爺爺，小男孩玩電腦遊戲的可能性更大。

在上述例子中，我們學習到了兩棵樹，並且每顆樹的決策變數不同，且他們具有決策先後順序，那麼這些決策（函數）是如何學習到的呢？我們通過最小化下面的目標函數來學習的：

這裡l是一個可微的凸損失函數，測量預測值和目標值的不同。 $Omega$ 是k顆樹的正則項，用於抑制模型的複雜度防止過擬合。當正則項的參數是0時，上述目標函數就是一個傳統的梯度樹提升模型。

這裡有幾個疑問：

每一顆樹的分支依據是如何確定的？（比如先分age，再分性別）
每一顆樹的分支分到哪裡為止？（比如is male？下面還要不要分支？）
每棵樹的葉子節點的權重分值是如何確定的？（為什麼有的是2，有的是0.9，有的是-1）
樹的顆數是如何確定的，多少顆樹是最合適的？

帶著以上幾個疑問我們繼續。

2.2、梯度樹提升

上述目標函數的參數本身是函數，這樣使用傳統的優化方法是不能優化到最優值的。相反，模型的訓練時採用加法的形式來訓練的，形式上，使用 $bar{y}_i^{(t)}$ 作為第i個實例在第t詞迭代中的預測值，我們需要添加ft來最小化下面的目標函數：

這意味著我們通過2.1節中的目標函數貪婪的添加ft來最大程度的改善我們的模型。對於上式，我們通常使用二階近似解來快速的優化目標：

它們是損失函數的一階和二階導。移除常數項，僅需優化下面的目標：

定義 $I_j={i|q(X_i)=j}$ 作為葉子節點j上面的實例集合，我們可以重寫上式：

對於固定的樹結構q(X)，我們可以葉子節點j的最優權重 $w_j^*$ :

計算這棵樹的最優值

這個公式也可以作為得分函數來測量樹結構q的質量（也就是學習的這棵樹對總體結果有沒有提升），下圖展示了如何計算一棵樹的分值

樹的計算分值月底，說明這個樹的結構越好。

由於訓練數據可能有很多特徵，構建一棵樹可能有許多種不同的構建形式，我們不可能枚舉所有可能的樹結構q來一一計算它的分值。貪心演算法從一個單獨樹葉開始迭代的增加分支。假設 $I_L$ 和 $I_R$ 是分割之後節點的左側和右側實例集合，令 $I=I_Lcup I_R$ ，那麼在節點分割後的損失減少量為：

這個公式通常用於在實踐中評估候選分裂節點是不是應該分裂。

2.3 收縮和列採樣

在防止模型過擬合方面，除了使用正則化項，收縮和列採樣也經常使用。收縮規模在樹提升的每一步迭代中通過因子 $eta$ 逐步增加收縮權重，這和隨機梯度下降的學習率相似。收縮技術降低了每一個單個的樹和葉子節點對之後要學習的樹結構的影響。列採樣在隨機森林中被使用，它除了能防止過擬合還能加塊並行演算法的計算速度。

3、分支節點分裂演算法

3.1、 Basic Exact Greedy Algorithm

在樹學習中，一個關鍵問題是如何找到每一個特徵上的分裂點，比如在本文的例子中，age的分裂節點是15歲，而不是其他年紀。為了找到最佳分裂節點，分裂演算法枚舉特徵上所有可能的分裂點，然後計算得分，這種演算法稱為 exact greedy algorithm，單機版本的XGBoost支持這種 exact greedy algorithm，演算法如下所示：

為了有效率的找到最佳分裂節點，演算法必須先將該特徵的所有取值進行排序，之後按順序取分裂節點計算 $L_{split}$ 。

3.2、近似演算法

exact greedy algorithm使用貪婪演算法非常有效的找到分裂節點，但是當數據量很大時，數據不可能一次性的全部讀入到內存中，或者在分散式計算中，這樣不可能事先對所有值進行排序，且無法使用所有數據來計算分裂節點之後的樹結構得分。為解決這個問題，近似演算法被應用進來。近似演算法首先按照特徵取值的統計分布的一些百分位點確定一些候選分裂點，然後演算法將連續的值映射到 buckets中，然後匯總統計數據，並根據聚合統計數據在候選節點中找到最佳節點。

近似演算法有兩個變體， global variant和 local variant。

3.3、加權分位數（Weighted Quantile Sketch）

在近似演算法中的重要步驟中是如何確定候選分裂點。通常特徵取值的百分位被用於生成候選分裂點。更進一步的我們可以令多集合

表示第k個特徵的每個訓練樣本的二階梯度統計。我們可以定義一個排序函數：