對GBDT, Xgboost 和 LightGbm 的理解

對於機器學習問題，我們尋找函數使得如下損失最小，

$\f^{*} = arg min_{f in H} L(y,f(x))$

其中，

$\L(y,f(x)) = sum_{i=1}^{n}l(y_i,f(x_i))$

Boosting方法假設為一系列基模型的加權和，

$\f_m=sum_{i=1}^{m}h(x;alpha_i)$

其中為基模型，為參數。採用向前迭代演算法求解 ,

$\alpha_m = arg min_{alpha}L(y,f_{m-1}(x)+ h(x;alpha))$

從而得到第步的模型：

$\f_m(x) = f_{m-1}(x)+h(x;alpha_m)$

1、GBDT

下面假設基模型為決策樹（Decision Tree），並使用梯度下降法求解最優參數，這樣的模型叫做Gradient Boosting Decision Tree(GBDT）。

讓達到最小，只需讓每一個樣本的損失最小，於是沿著梯度方向搜索最優步長即可。從而得到：

$\h(x_i;alpha_m) =C frac{partial l(y_i,f_{m-1}(x_i))}{partial f_{m-1}(x_i)}$

由於的取值乘以一個常數不影響決策樹葉子對應的區域(但影響取值），不妨認為

$\h(x_i;alpha_m) = frac{partial l(y_i,f_{m-1}(x_i))}{partial f_{m-1}(x_i)}$

這樣我們得到了第個基模型在個樣本上的取值，由於模型要適用於未知數據，因此需要有一個參數化的表達。我們需要求解參數，對於決策樹，參數就是葉子節點對應的區域和取值，這並不是一個困難的問題。

剛剛提到了葉子節點對應的取值並不準確，因此還需要進一步求解這個值。對於每一個葉子節點上的樣本，通過最小化節點上的樣本的損失得到最優值。設第個基模型的第個葉子對應的區域為 $R_{jm}$ ，則這個區域上的取值 $gamma_{jm}$ 可以通過極小化下式得到：

$\gamma_{jm} = arg min_{gamma}sum_{x_i in R_{jm}}l(x_i,f_{m-1}(x_i)+gamma)$

這樣就得到了第個基模型。在現實使用中，為了避免過擬合，通常可以乘以一個收縮係數，即：

$\f_m(x)=f_{m-1}(x)+gamma h(x;alpha_m)$

2、Xgboost 和 LightGbm

使用梯度下降法只得到了原損失函數的一階近似，類似於梯度下降和牛頓法的關係，我們可以將損失函數進行二階泰勒展開：

$l(y,f_{m-1}(x)+h(x;alpha_m))$

$=l(y,f_{m-1}(x))+frac{partial l(y,f_{m-1}(x))}{partial f_{m-1}(x)}h(x;alpha_m)+frac{1}{2}frac{partial^2 l(y,f_{m-1}(x))}{partial^2 f_{m-1}(x)}h^2(x;alpha_m)$

$=l(y,f_{m-1}(x))+g_{m-1}(x)h(x;alpha_m)+frac{1}{2}k_{m-1}(x)h^2(x;alpha_m)$

$=g_{m-1}(x)h(x;alpha_m)+frac{1}{2}k_{m-1}(x)h^2(x;alpha_m)+C ag1$

其中C不影響。

Xgboost同時考慮瞭如下正則項：

$\Omega(h(x;alpha_m))=frac{1}{2}lambda||gamma_m||^2+eta T$

其中為葉子節點上的取值，為葉子節點的數量。於是優化目標為：

$\L = sum_{i=1}^nl(y,f_{m-1}(x_i)+h(x_i;alpha_m)) +frac{1}{2}lambda||gamma_m||^2+eta T$

假設葉子節點的區域已經確定了，那麼各個區域上的取值該怎麼計算呢？（對於一個特定的區域，為常數）對於第j個區域，

$\gamma_{jm} = arg min_{gamma}(sum_{x_i in R_{jm}}g_{m-1}(x_i)gamma+frac{1}{2}k_{m-1}(x_i)gamma^2)+frac{1}{2}lambdagamma^2\ = arg min_{gamma}G_{m-1,j}gamma+frac{1}{2}(K_{m-1,j}+lambda)gamma^2\ =-frac{G_{m-1,j}}{K_{m-1,j}+lambda}$

且第個區域上的最小損失為：

$\L_j=-frac{1}{2}frac{G^2_{m-1,j}}{K_{m-1,j}+lambda}$

總的損失為，

$\L = sum_jL_j+eta T$

定義L的相反數為得分S，接下來最大化S。

然而現在的問題是，我們不知道每個區域長什麼樣。怎麼辦？辦法是從頭開始分裂。分裂前的得分為：

$\S_{before}=frac{G_{m-1}}{K_{m-1}+lambda}$

$G_{m-1}$ 是所有樣本的一階導數， $K_{m-1}$ 是所有樣本的二階導數。給定一個特徵和閾值，分裂後的得分為：

$\S_{after}=frac{G_{m-1,L}}{K_{m-1,L}+lambda}+frac{G_{m-1,R}}{K_{m-1,R}+lambda}-eta$

$G_{m-1,L}$ 表示左邊樣本的一階導數，其它同理。記錄使得 $S_{after}$ 最大的特徵和閾值，如果 $S_{after}>S_{before}$ ，則完成這次分裂，繼續尋找下次分裂，否則停止分裂。

3、最佳分裂點

搜索最佳分裂點時一個特別耗時的過程。

對於連續特徵，可以只搜索特定分位點，但這樣並不是一種高效而穩健的方法。

對(1)配方，可以得到：

$\=frac{1}{2}k_{m-1}(x)(h(x;alpha_m)-frac{g_{m-1}(x)}{k_{m-1}(x)})^2+C$

$frac{1}{2}k_{m-1}(x)$ 可以看作樣本損失的權重。於是，Xgboost的論文中以樣本的二階導數作為樣本權重，提出了weigthed Quantile 方法，重新尋找分位點。 $k_{m-1}(x)$ 依賴於最新的模型，需要多次計算。

LightGbm則採用了直方圖加速辦法。先將特徵離散為區間（bins），然後計算每個區間上的樣本的一階導數和二階導數，最後搜索次數為區間數量，大大減小時間複雜度和空間複雜度。

對於類別變數，可以用Label對應的正樣本的比例作為數值，對label進行排序。比如，顏色這個特徵下有紅、橙、黃、綠、青、藍、紫7個取值，每個值對應的正樣本的比例為紅(0.7)、橙(0.2)、黃(0.8)、綠(0.3)、青(0.5)、藍(0.4)、紫(0.6)。可以將顏色排序為黃、紅、紫、青、藍、綠、橙，這樣只需要分裂6次，大大降低複雜度（原來需要分裂次），有文獻證明這樣的排序能達到cross entropy或 gini index的最優值。