- GBDT Algorithm

- XGBoost 1. GBDT Algorithm

GBDT(Gradient Boosting Decision Tree )是boosting Tree的一種，是以分類與回歸樹(CART)為基學習器，採用加法模型(Additive function Model)和前向分佈演算法(Forward stagewise algorithm),是Freidman在1999年提出來的，其關鍵是利用損失函數的負梯度在當前模型的值來擬合基學習器模型。

演算法的過程參考wepon的slides：

下面，我將詳細解釋演算法的過程：

Input:輸入訓練數據集 (x_{i},y_{i})，迭代次數 T， 以及損失函數 L_{1} . 這裡的初始化過程，參考了Freidman原文，目的是找到一個常數，使得初始經驗損失最低。

2. 對於每一次迭代t

2.1. 計算損失函數在當前點的負梯度，N 是訓練集的數目

2.2 計算第t 棵樹的參數，這裡 h_{t} 表示第 t 棵回歸樹， omega 表示第 t 棵回歸樹的參數，也就是回歸樹的切分變數(splitting variables)，切分點(splitting point)和葉子節點的值。至於為什麼是平方和的形式，我參考了一篇 paper

Instead of looking for the general solution for the boost increment in the function space, one can simply choose the new function increment to be the most correlated with ?gt(x). This permits the replacement of a potentially very hard optimization task with the classic least-squares minimization one. —《Gradient boosting machines, a tutorial》

我是這樣理解的，求解負梯度的通用具體形式太過複雜，可以近似建立一棵回歸樹來近似表示負梯度的值，如何近似呢，最簡單的就是平方和最小，所以優化問題就轉變成了最小二乘優化問題。

Freidman原文：This permits the replacement of the difficult function minimization problem by least-squares function minimization(11), followed by only a single parameter optimization based on the original criterion (12)

2.3 線性遍歷求步長 ho

2.4 更新模型，對於回歸樹，其本身就是一個加法模型(Additive function Model)，

式中 J 是葉子節點個數， R_j 是切分變數， b_j 是切分點

該過程可描述如下：

至於 eta_{m} 的求解，在Freidman的paper中，在基學習器是回歸樹，損失函數(loss function)是LDA(絕對值)的情況下， 上式中的 alpha_{m} 與 eta_{m} 是一起求解的。 上式(16)可以寫成以下形式：

其中 gamma_{j m} = alpha_{m} * eta_{m} , 因此問題就變成了求解 gamma_{j m} ，限制(constriction)為

由於 R_{jm} 在一棵回歸樹上上是互斥的，故上式可表示為：

gamma_{j m} = argmin_{gamma} sum_{x{i}in R_{j m}}|y{i} -F_{m-1}(x{i}) - gamma |

由於該條件(我也不太懂)

因此最終結果為：

其中，median即中值。

綜上所述， gamma_{j m} 為在第m次迭代過程中的殘差(當前值—上一模型的預測值)得中值，故LDA下的 GBDT 演算法如下：

3. 輸出模型

2. XGBoost

2.1 正則化(Regularization)

XGBoost是GBDT的加強版，這部分主要參考了陳天奇同學的 paper 和slide 。同樣使用加性模型(Addative model)和前向分佈演算法(Forward stagewise Algorithm)。個人感覺XGBoost與GBDT最大的區別在於目標函數的選擇，XGBoost在經驗損失函數的基礎上增加了正則項，使得學習出來的模型更加不容易過擬合

其中，正則化的部分包括葉子節點個數 T ， 葉節點分數(leaf scores) omega

2.2 梯度提升(gradient boosting)

上面的原始優化目標函數肯定是不好優化的，考慮到XGBoost採用的是加法模型，在 t 次迭代過程中，可以寫成

其中：

接下來，我們將 t 次迭代過程中的目標函數進行二階泰勒展開

首先回憶一下二階泰勒展開的公式：

所以， t 次迭代過程中的目標函數的泰勒展開為

其中： g_{i} h_{i} 分別表示損失函數對當前特徵值的一次，二次導數

對於中括弧內的第一項 ell(y_{i} - hat y ^{t-1}) 是確定值，即為一常數，故去除第一項得：

我們定義： I_{j} = left{ i |q{(x{i})} = j ight} 為在葉子節點 j 上的樣本集合，同時展開正則項，得到關於葉子節點 T 的目標函數，其中 omega_ j 是葉子節點 j 的葉子得分(leaf scores)，我們知道對於一棵確定的回歸樹，則對於每一個輸入，都會有確定的輸出（葉子得分 leaf scores ），即 f_{t}(x{i}) = w_{j}

這是一個二次項的求和問題，所以對於一個確定的葉子節點 j ，得到最佳葉子得分(leaf score) w_{j^*}

將 w_{j^*} 帶入(4)，得到在回歸樹 q_{(x)} 的 j 葉子節點的最優目標函數

其中，(6）式的物理意義類似於決策樹中的熵值(Entropy)或者基尼指數(Gini Index)，是用來度量該樹的結構，該值越小，樹的結構就越好。問題進行到這裡，如何確定樹結構的切分變數(splitting variable)和切分點(splitting point)是下一步的工作的關鍵，捨棄了樹結構遍歷(enumerate)的方式，XGBoost採用了一中貪婪演算法(Greedy Algorithm)，我們定義 I 為該節點上所有樣本的索引集， I_{L} ， I_{R} 分裂後左右子節點的樣本的索引集，即 I = I_{L}cup I_{R} ，

I=-{1over2} {*frac{(sum_{iin I} g_{i})^2} {sum_{iin I} h_{i} + lambda} +gamma}

I_{L}=-{1over2} {*frac{(sum_{iin I_L} g_{i})^2} {sum_{iin I_L}h_{i} + lambda} +gamma} I_{R}=-{1over2} {*frac{(sum_{iin I_R} g_{i})^2} {sum_{iin I_R}h_{i} + lambda} +gamma}

所以切分後損失減少值為(loss reduction)為

GAIN = I_{split}=I - I_{L} - I_{R}

這個公式類似於ID3中的信息增益或者基尼增益，XGBoost 就是利用這個公式計算出的值作為分裂條件， 且該值越大越好。在每一個節點的分裂中尋找最優切分變數(splitting variable)和切分點(splitting point)。

2.2.1 分裂點搜索演算法(splitting finding Algorithm)

如(7)所示，優化的下一步問題在於尋找最優切分變數(splitting variable)和切分點(splitting point)。陳天奇的文章中，介紹了兩種搜索演算法，一種是遍歷搜索演算法(原文稱做 Exact Greedy Algorithm)和一種近似的估計演算法(原文稱做 Approximate Algorithm)。

2.2.1.1 遍歷搜索演算法(Exact Greedy Algorithm)

這裡， k 代表第 k 個特徵 (k -th feature) j 代表的是第 j 個數據的下表(j-th single data)， x_{jk} 代表 k 個特徵的第 j 個值 。

該演算法首先會對第 k 個特徵的所有值進行排序，然後所有可能的分割點， 計算 GAIN (或者 L_{split} ) ， 選取值最大的(feature, value)去分割。當然，此方法比較耗時，而且容易過擬合(over-fitting)。

2.2.1.2 近似估計演算法(Approximate Algorithm)

與第一種方法的遍歷不同，近似估計演算法首先根據特徵值的分佈，確定 l 個分位數 S_{k} = left{s_{k1}, s_{k2},...,s_{kl} ight} ，利用這 l 個分位數將特徵 k 的取值區間截斷為 l+1 個子區間。然後分別在每個子區中將該區間中求各個樣本的一階和二階導數，並求和，得到該區間的一階和二階導數的統計量。後面在尋找最優分裂點時就只搜索這 l 個分位數點，並從這 l 各分位數點中找到 GAIN 最大的值，作為該特徵上最優分裂點。

對於分位數的使用，XGBoost有兩種形式，一種是全局(global)形式，一種是局部(local)形式。全局(global)形式只在演算法的初試階段只計算一次，在後面的計算（樹的各層構造中）仍然採用相同的分位數，全局形式(global)適合大部分的數的結構。局部形式(local)在每次分裂都會重新計算一次分位數，這種適合比較深的樹的結構。

至於如何確定分位數，這是一個比較難的問題，在陳天奇的paper中，給了一個supplement鏈接。不像大家平常見到的數都是等權重的，這裡不同特徵值有不同的權重。至於為什麼不同的特徵值有不同的權重，我們可以把(2)式改寫。

我們發現，這是關於 frac{g{i}}{h{i}} 的平方損失函數，其權重就是 h_{i} ，所以每一個特徵值的權重為損失函數關於各個特徵值的二階導數。求不等權重的分位點的演算法，陳天奇給了一個 supplement

由於這篇文章太過複雜，在本博客中就不解釋了，打算過段時間再專門寫一篇文章。當求解分位點的這個最大的問題解決之後，我們纔可以說瞭解 XGBoost演算法。演算法的具體步驟如下：

2.3 縮減(Shrinkage) 和列採樣(Column Subsampling)

縮減(Shrinkage) 就是在boosting的過程中，對於每一步生成的模型的前面乘以一個縮放因子 eta ，這就相當於，對於每一個生成的模型（回歸樹）的影響都乘以一個小於1的 eta ，也就是為了以後的優化留了一定的空間。

列採樣(Column Subsampling)在隨機森林用的比較多，主要是通過屬性擾動，來避免過擬合。具體步驟是，對回歸樹的每個結點，先從該結點 d 個屬性中隨機選擇一個包含 k 個屬性的子集，然後再從這個子集中選擇一個最優屬性用於劃分，一般來說， k=log_{2}d 。

2.4 對稀疏值的處理(Sparsity-aware Split Finding)

稀疏值的處理基本思想如下：在非葉子節點進行分裂時，增加一個default分支（branch），是的對於 k 特徵中，缺失值被分到這個分支（branch）。同時為了進一步提高Accuracy，缺失值可以有兩個分配方向，而最佳分配方向就從2個當中選取一個使得 GAIN 最大的方向。更重要的是，通過這樣的處理，我們使得處理稀疏值的計算量消耗(computation complexity)與稀疏值的數量成正比。

具體演算法如下：

2.5 並行計算(Column Block for Parallel Learning)

訓練過程中最耗時的步驟是排序，XGBoost實現了一種Column Block技術，首先在建樹之前，把每個特徵（feature）的所有數值，按照特徵大小順序排序，並且計算出梯度信息，壓縮（CSC）存儲在內存中，這樣的話，在以後的迭代中就可以使用索引來訪問這些梯度信息。

2.6 Cache-aware Access

column block按特徵大小順序存儲，相應的樣本的梯度信息是分散的，造成內存的不連續訪問，或者梯度信息沒有緩存到Cache中，降低了學習速度。

對於遍歷演算法(exact greedy algorithm)，我們為每一個Thread一個buffer中 ， 再統計梯度信息。對於近似演算法(approximate Algorithms)，我們通過手動選擇合適的Block size來解決這個問題。Block size 我們定義為在包含在一個block中最大的樣本數量。Block size太小，則影響並行計算，過大則會導致內存空間的浪費。作者是通過實驗來確定block size的大小。

2.7 Blocks for Out-of-core Computation

利用Block來進行核外計算(Out-of-core Computation)的核心思想是計算器一邊讀取數據(由獨立線程完成)，一邊計算，為此，作者採用了兩個策略：

1. 塊壓縮(Block Compression)block是逐特徵壓縮(by feature)，並且解壓工作也是由獨立線程完成。實際操作中，我們使用 block beginning Index -row Index得到一個偏移量，這個偏移量存儲在一個16 bits Integer ，也就是一個block存儲256條數據。2. 塊分片(Block Sharding)塊分片就是把數據分割到多個磁碟中，然後每一個磁碟分配一個讀取線程把數據讀取到buffer，最後訓練數據的線程再逐個從buffer讀取數據。
推薦閱讀：
相關文章