XGBoost入門系列第一講

01-24

Boosted Trees 介紹

XGBoost 是「Extreme Gradient Boosting」的簡稱，其中「Gradient Boosting」來源於附錄1.Friedman的這篇論文。本文基於 gradient boosted tree ，中文可以叫梯度提升決策樹，下面簡稱GBDT，同時也有簡稱GBRT，GBM。

監督學習

XGBoost 主要是用來解決有監督學習問題，此類問題利用包含多個特徵的訓練數據 $x_i$ ，來預測目標變數 $y_i$ 。在我們深入探討GBDT前，我們先來簡單回顧一下監督學習的一些基本概念。

模型與參數

在監督學習中模型（model）表示一種數學函數，通過給定 $x_i$ 來對 $y_i$ 進行預測。以最常見的線性模型（linear model）舉例來說，模型可以表述為 $hat{y_i}=sum_j heta_j x_{ij}$ ，這是一個輸入特性進行線性加權的函數。那麼針對預測值的不同，可以分為回歸或者分類兩種。

在監督學習中參數（parameters）是待定的部分，我們需要從數據中進行學習得到。在線性回歸問題中，參數用 $heta$ 來表示。

目標函數：訓練誤差 + 正則化

根據對 $y_i$ 的不同理解，我們可以把問題分為，回歸、分類、排序等。我們需要針對訓練數據，嘗試找到最好的參數。為此，我們需要定義所謂的目標函數，此函數用來度量參數的效果。

這裡需要強調的是，目標函數必須包含兩個部分：訓練誤差和正則化。

$Obj(Theta)=L( heta)+Omega(Theta)$

其中，LL表示訓練誤差函數， $Omega$ 表示正則項。訓練誤差用來衡量模型在訓練數據上的預測能力。比較典型的有用均方差來衡量。

$L( heta)=sum_i(y_i-hat{y_i})^2$

另外針對邏輯回歸，比較常見的損失函數為Logistic函數：

$L( heta)=sum_i[y_i ln(1+e^{-hat{y_i}}) + (1-y_i) ln(1+e^{hat{y_i}})]$

另外一個比較重要的部分就是正則項，這也是很多人容易忘記的部分。正則項是用來控制模型的複雜度，以防止過擬合（overfitting）。這聽起來有點抽象，那麼我們用下面的例子來說明。針對下面左上角的這幅圖，我們需要找到一個階梯函數來擬合圖中的數據點集合。那麼問題來了，下面剩下的三幅圖中，哪一個你認為是最好的呢？

答案是用紅色標註出來的這幅圖。為什麼呢？因為我們對於好的模型的判斷依據是簡單（simple）並且準確（predictive）。但這兩者又是相互矛盾的，在機器學習中我們也把這兩者也用 bias-variance 來表述。

複合樹模型（Tree Ensemble）

在前面我們已經介紹了監督學習，現在讓我們開始了解樹模型。首先先來了解一下xgboost所對應的模型：複合樹模型。複合樹模型是一組分類和回歸樹（classification and regression trees - CART）。這裡我們舉CART中的一個例子，一類分類器用來辨別某人是否喜歡計算機遊戲。

我們把家庭中的成員分到了不同的葉子節點，同時每個葉子節點上都有一個分數。CART與決策樹相比，細微差別在於CART的葉子節點僅包含判斷分數。在CART中，相比較於分類結果，每個葉子節點的分數給我們以更多的解釋。這讓CART統一優化節點更為容易，這在後面會有具體介紹。

通常情況下，在實踐中往往一棵樹是不夠用的。這個時候往往需要把多棵樹的預測結果綜合起來，這就是所謂的複合樹模型。

上面就是由兩棵樹組成的複合樹的例子。每棵樹上的分數簡單相加就得到了最終的分數。用數學式子可以表達如下：

$hat{y_i}=sum_{k=1}^{K}f_k(x_i),f_k in mathcal{F}$

$K$ 表示樹的數目， $f$ 是函數空間 $F$ 中的一個函數，FF表示CART的所有可能集合。所以我們的優化目標可以寫作：

$ext{obj}( heta)=sum_i^n l(y_i, hat{y_i}) + sum_{k=1}^K Omega(f_k)$

現在問題來了，隨機森林對應的模型是什麼呢？對了，也是複合樹模型。所以在模型的表述上，隨機森林和提升樹是一樣的，他們倆的區別只是在於如何訓練。這也就意味著，如果要寫一個關於複合樹模型的預測服務，我們只需要寫一個就可以同時支持隨機森林和提升樹。

提升樹（Tree Boosting）

介紹了模型之後，讓我們看看訓練部分。那麼我們是怎麼訓練這些樹的呢？對於所有的監督學習模型，答案也都是同樣，只需要做兩件事，定義目標函數，然後優化它。

假設我們有如下的目標函數（需要切記目標函數必須包含損失函數及正則項）

$ext{obj}=sum_{i＝1}^n l(y_i, hat{y_i}^{(t)}) + sum_{k=1}^t Omega(f_i)$

增量訓練（Additive Training）

首先我們需要問的是，這些樹的參數是什麼？我們會發現，我們所要學習的就是這些 fifi方法，每個方法中定義樹的結構以及葉子節點的分數。這比傳統最優化問題要更難，傳統最優化問題我們可以通過梯度來解決。而且我們無法在一次訓練所有的樹。相反，我們用增量（additive）的方式：每一步我們都是在前一步的基礎上增加一棵樹，而新增的這棵樹是為修復上一顆樹的不足。，我們把每tt步的預測用 $hat{y_i}^{(t)}$ 表示，這樣我們就有了：

$egin{split} hat{y}_i^{(0)} &= 0 \ hat{y_i}^{(1)} &= f_1(x_i) = hat{y_i}^{(0)} + f_1(x_i) \ hat{y_i}^{(2)} &= f_1(x_i) + f_2(x_i)= hat{y_i}^{(1)} + f_2(x_i) \ & dots \ hat{y_i}^{(t)} &= sum_{k=1}^t f_k(x_i)= hat{y_i}^{(t-1)} + f_t(x_i) end{split}$

這裡還有疑問的是，在每一步中如何確定哪棵樹是我們需要的呢？一個很自然的想法就是，增加這棵樹有助於我們的目標函數。

$egin{split} ext{obj}^{(t)} &= sum_{i=1}^n l(y_i, hat{y_i}^{(t)}) + sum_{i=1}^tOmega(f_i) \ & = sum_{i=1}^n l(y_i, hat{y_i}^{(t-1)} + f_t(x_i)) + Omega(f_t) + constant end{split}$

我們用MSE（均方差）作為損失函數，這樣式子就變成了：

$egin{split} ext{obj}^{(t)} & = sum_{i=1}^n (y_i - (hat{y_i}^{(t-1)} + f_t(x_i)))^2 + sum_{i=1}^tOmega(f_i) \ & = sum_{i=1}^n [2(hat{y_i}^{(t-1)} - y_i)f_t(x_i) + f_t(x_i)^2] + Omega(f_t) + constant end{split}$

對於用MSE求出來的損失函數式子比較友好，包含一個一階項和一個二次項。但是對於其他形式，就很難推導出這麼友好的損失函數式子了。那麼針對這種情形，我們就用泰勒展開公式（參考附錄4， $x$ 取值 $hat{y_i}^{(t-1)} + f_t(x_i)$ ， $a$ 取值 $hat{y_i}^{(t-1)}$ 來逼近：

$ext{obj}^{(t)} = sum_{i=1}^n [l(y_i, hat{y_i}^{(t-1)}) + g_i f_t(x_i) + frac{1}{2} h_i f_t^2(x_i)] + Omega(f_t) + constant$

其中 $g_i$ 和 $h_i$ 定義如下：

$egin{split} g_i &= partial_{hat{y_i}^{(t-1)}} l(y_i, hat{y}_i^{(t-1)}) \ h_i &= partial_{hat{y_i}^{(t-1)}}^2 l(y_i, hat{y}_i^{(t-1)}) end{split}$

然後針對上述式子，我們刪除常數項，那麼在 $t$ 目標函數就變成：

$sum_{i=1}^n [g_i f_t(x_i) + frac{1}{2} h_i f_t^2(x_i)] + Omega(f_t)$

選擇新的一棵樹，上述式子就是優化目標。這樣的優化目標有一個優點，式子只需要考慮 $g_i$ 和 $h_i$ 。這就是xgboost為什麼能支持自定義損失函數的原因。我們能夠優化每一個損失函數，包括邏輯回歸和加權邏輯回歸，只需要把對應的 $g_i$ 和 $h_i$ 作為輸入傳入即可。

模型複雜度

現在講講正則化。那麼如何定義 $Omega(f)$ 呢，在此之前，我們需要定義 $f(x)$ ：

$f_t(x) = w_{q(x)}, w in R^T, q:R^d ightarrow {1,2,cdots,T} .$

這裡 $w$ 表示葉子節點上的分數所組成的向量， $q$ 表示每個數據映射到相應葉子節點的對應關係函數， $T$ 表示葉子節點的數量。在XGBoost中，我們用如下公式定義複雜度：

$Omega(f) = gamma T + frac{1}{2}lambda sum_{j=1}^T w_j^2$

當然還有其他公式來定義複雜度，但是我們發現上述式子在實踐過程中表現很好。其他樹相關的演算法包不怎麼認真對待正則化，甚至直接忽視掉。

如何計算樹葉子節點上的分數

那麼在增量學習過程中，如何選擇這棵新增的樹呢？要解決這個問題，我們先解決一下其中這個子問題：假設這棵樹的結構已經確定了，如何來計算葉子節點上的分數？

這一部分是推廣過程中比較神奇的一個步驟。根據上述過程，我們寫出第 $t$ 步樹的目標值：

$egin{split}Obj^{(t)} &approx sum_{i=1}^n [g_i w_{q(x_i)} + frac{1}{2} h_i w_{q(x_i)}^2] + gamma T + frac{1}{2}lambda sum_{j=1}^T w_j^2 \ &= sum^T_{j=1} [(sum_{iin I_j} g_i) w_j + frac{1}{2} (sum_{iin I_j} h_i + lambda) w_j^2 ] + gamma T end{split}$

這裡 $I_j = {i|q(x_i)=j}$ 表示每個映射到第jj個葉子節點對應的數據樣本。需要注意的是，因為映射到相同葉子節點上的數據樣本他們的分數是相同的，所以在第二行我們改變了一下求和 $sum$ 順序。同時我們令 $G_j = sum_{iin I_j} g_i , H_j = sum_{iin I_j} h_i$ 以及 $H_j = sum_{iin I_j} h_i$ ，那麼上述公式簡化為：

$ext{obj}^{(t)} = sum^T_{j=1} [G_jw_j + frac{1}{2} (H_j+lambda) w_j^2] +gamma T$

在上述式子中，每一個 $w_j$ 是相互獨立的，那麼針對一元二次方程 $G_jw_j+frac{1}{2}(H_j+lambda)w_j^2$ 而言，可以比較容易求出當新增的這棵樹的結構 $q(x)$ 已知的情況下，目標函數最小值下的 $w_j$ ：

$egin{split}w_j^ast = -frac{G_j}{H_j+lambda}\ ext{obj}^ast = -frac{1}{2} sum_{j=1}^T frac{G_j^2}{H_j+lambda} + gamma T end{split}$

最後的式子計算的是樹 $q(x)$ 的優劣：

如果上面的式子看著比較複雜的話，那麼根據上面的這幅圖來看如何計算這些分數，就會顯得更直觀些。一旦樹的結構已知的話，我們只需要通過計算每個節點上的 $g_i$ 和 $h_i$ ，然後把各個葉子節點上的這些數值加起來，用上述方程式就可以計算這棵樹的優劣了。

如何學習樹的結構

現在我們已經知道一旦樹的結構固定下來以後，如何來計算葉子節點上的分數，以及計算這棵樹的優劣。那麼關於現在我們要來解決如何來學習這棵樹的結構。比較簡單粗暴的方法就是遍歷所有可能的樹結構，然後從中找到最好的那棵樹。但是這也是不切實際的，因為需要遍歷的情況實在是太多了。所以我們來尋求一種貪婪的解法，就是在樹的每個層構建的過程中，來優化目標。那麼這裡假設在某一層的構建過程中，假設特徵已經選定，我們先如何進行二叉劃分呢，以及是不是需要進行劃分？我們可以通過下面的式子來計算劃分之後，在目標上所獲得的收益（這個收益越越好，負數表示收益為負）：

$Gain = frac{1}{2} left[frac{G_L^2}{H_L+lambda}+frac{G_R^2}{H_R+lambda}-frac{(G_L+G_R)^2}{H_L+H_R+lambda} ight] - gamma$

上面的這個式子可以分解為 1) 若是劃分，劃分後左邊節點的收益 2) 或是劃分，劃分後右邊節點的收益 3) 如不劃分，原先節點的收益 4) 劃分後正則項的收益。通過上述式子比較容易看到，當劃分後葉子節點所帶來的新增收益小於 $Y$ ，我們最好還是不要進行二叉劃分，保留原樣是最好的。這也是日後做剪枝的依據。

那麼針對排序後的特徵，我們所要做的就是遍歷各種劃分，找到一個最好的劃分點，如下圖表示。

那麼這裡還有一個問題就是在構建樹的結構過程中，在某一層如何進行特徵選擇呢？這裡提供了一種比較簡單的方式就是遍歷每一種特徵，然後根據上述式子的Gain，找到最大的Gain值對應的特徵。

關於XGBoost的最後幾句話

我們花了很長時間來講解 Boosted Tree，那麼XGBoost相較於Boosted Tree，又做了哪些額外的事情呢？XGBoost是遵循上述Boosted Tree思想的工程實現，但同時又考慮兼顧系統優化和機器學習原理，最大化的保證可擴展性、便捷性以及準確性。

英文文章標題：《Introduction to Boosted Trees》作者：Tianqi Chen

本文為BigQuant - 人工智慧量化投資平台整理，如需轉載請通過 i@bigquant.com與我們聯繫！

XGBoost 入門系列第一講