CTR預估[九]: Algorithm-GBDT: Boosting Trees

01-24

作者：@三瘋蘭尼斯特 && @Ainika Peng

時間：2017年11月

出處：https://zhuanlan.zhihu.com/p/31607501

1.3.4 Boosting Trees

1.3.4.1 Regression Tree

Regression Tree本質上是一組線性劃分空間生成的規則的集合。這裡暫不考慮regularization。

形式化地定義一棵樹

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ T(x;Theta) = sum_{j=1}^J eta_j ·I(x in R_j)\ where ~ Theta = {R_j, eta_j}_1^J end{split}$
這和直接定義任意 $x$ 從屬 $R_j$ 得到值 $eta_j$ 是等價的： $xin R_j o T(x) = eta_j$

求解參數 $Theta$ ：

$hat{Theta} = argmin_Theta sum_{j=1}^J sum_{x_j in R_j} L(y_i, eta_j)$

直接優化求解參數是困難的，一般都是用近似估計：

Finding $eta_j$ given $R_j$

對於Regression問題，一般用落在region中的樣本均值 $eta_j = ar{y}_j$
對於0-1 loss的classification問題，用落在region中的label眾數

Finding $R_j$

一般都是用top-down recursive策略來優化

最優劃分和次優greedy劃分示意圖如下 -- greedy總是在父空間上二分的

1.3.4.2 Aside: Loss Function

Loss 函數衡量預估值 $f(x)$ 和真值 $y$ 之間的差異。針對有監督學習中常見的classification和regression問題，loss有如下區別：

Regression: loss雙向遞減 -- 對於和真值的差異，無論是大於真值還是小於真值都是類似的；
Classification: loss單向遞減 -- 對於negative margin比positive margin要有更大的懲罰力度。

Classification -- 0-1 Loss

Classification問題中，最直觀的loss是misclassification loss -- 預估值和真值相同為0不同為1，所以又稱0-1 loss

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ L(y, f(x)) &= I(y eq f(x))\ &= I(y·f(x)<0) end{split}$

這裡 $y·f(x)$ 表示margin，其中 $y in {+1, -1}$ 用來分割超平面兩邊的不同label。

但0-1 loss不是凸函數，直接優化困難，一般都用單調連續凸函數逼近0-1 loss。

Classification -- Binomial Deviance/Log Loss

在#1.1.2 中推導過，最小化log loss和最大化log likelihood等價，令

$egin{split}~~~~~~~~~~~~~~~~~~~~ P(y=+1~|~x) &= p(x) = frac{e^{f(x)}}{e^{-f(x)}+ e^{f(x)}} = frac1{1+e^{-2f(x)}} end{split}$

$y = 2y$ , log likelihood和之前LR中推導一致

$egin{split}~~~~~~~~~~~~~~~~~~~~ likelihood(y$

log loss為

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ L(y, f(x)) &= log left(1+ e^{-yf(x)} ight)\ &s.t. ~ y in {+1,-1} end{split}$

註：兩者等價推導需要注意只在 $y in {+1, -1}$ 情況下

此時

$~~~~~~~~~~~~~~~~~~~~f^*(x) = argmin_{f(x)} E_{Y|x} left( log left(1+ e^{-yf(x)} ight) ight) = frac12logfrac{P(Y=1|x)}{P(Y=-1|x)}$

Classification -- Exponential Loss

Exponential Loss 可以認為是在總體（population，無窮數據集）上和log-loss等價的loss，因為

$~~~~~~~~~~~~~~~~~~~~f^*(x) = argmin_{f(x)} E_{Y|x} left( e^{-yf(x)} ight) = frac12logfrac{P(Y=1|x)}{P(Y=-1|x)}$

和log-loss的總體期望是一致的。

但當數據不是無窮時， Exponential Loss比log-loss對於誤分類的懲罰更重（loss值更大）：前者是指數增長，後者是線性增長。

$e^{-yf(x)}$ 本身不是任何對數似然，但其在additive model下有優良的計算特性

Regression -- Absolute Error Loss/Squared Error Loss/Huber Loss

Regression的情況和Classification中對比Log-loss和Exponential Loss有些相似

從統計學的觀點出發，Absolute Error Loss有更好的統計特性，對錯誤 $y-f$ 的懲罰更合理，更robust；但 Squared Error Loss 的計算性質更好。

Loss Comparison

1.3.4.3 GBM with Trees

GBM演算法框架如下

Algorithm: Gradient Boost Machine
# 賦初始值
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~F_0(x) = arg min_ ho sum_{i=1}^N L(y_i, ho)$
For m = 1 to M do:
- # 求梯度
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ilde{y}_i = - left[ frac{partial L(y_i, F(x_i))}{partial F(x_i)} ight]_{F(x)= F_{m-1}(x)}$
- # 求方向

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~alpha_m = argmin_{alpha, eta} sum_{i=1}^N left[ ilde{y}_i - eta h(x_i; alpha) ight]^2$
- # 求步長
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ho_m = argmin_ ho sum_{i=1}^N Lleft(y_i, F_{m-1}(x_i) + ho h(x_i; alpha_m) ight)$
- # 迭代stage
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~F_m(x) = F_{m-1}(x) + ho_mh(x;alpha_m)$

註：GBM中賦初始值的部分，即取Loss對F求梯度=0，以log-loss為例
$egin{split}~~~~~~~~~~ &~~~ frac{partial log(1+e^{-2yf})}{partial f} = frac{-2ye^{-2yf}}{1+e^{-2yf}} =0\ & o sum_{i:y_i=1} frac{-2e^{-2f}}{1+e^{-2f}} + sum_{i:y_i=-1} frac{2e^{2f}}{1+e^{2f}} = 0 ~~~&#令m個+, n個-\ & o frac{-2me^{-2f}}{1+e^{-2f}} + frac{2ne^{2f}}{1+e^{2f}} = 0 &#左邊上下都乘以e^{2f}\ & o frac{m}n = e^2f &# ar{y} = frac{1·m + (-1)·n}{m+n}\ & o f = frac12logfrac{1+ar{y}}{1-ar{y}} end{split}$

一組Boosting Tree即定義base learner=Tree的boosting

$egin{split}~~~~~~~~~~ F_M(x) &= sum_{m=1}^M T(x; Theta_m) \ &= F_{m-1}(x) + ho_mT(x; Theta_m) &#stagewise\ &= F_{m-1}(x) + ho_m sum_{j=1}^J eta_j ·I(x in R_j) &#add ~tree~ def\ &= F_{m-1}(x) + sum_{j=1}^J gamma_{jm} ·I(x in R_j) &#gamma_{jm} = ho_meta_j end{split}$

由於參數 $gamma_{jm}$ 之間不相關，求解參數 ${gamma_{jm}}_1^J$ 可以簡化為求解參數 $gamma_{jm}$

$~~~~~~~~~~~~~~~~~~~~gamma_{jm} = argmin_{gamma} sum_{x_i in R_j} Lleft( y_i, F_{m-1}(x_i) + gamma ight)$

如果是Squared Error Loss，即最小化殘差residual，最優值為region中殘差的均值 $egin{split}~~~~~~~~~~~~~~~~~~~~ gamma_{jm} = argmin_{gamma} sum_{x_i in R_{jm}} left( (y_i - F_{m-1}(x_i)) - gamma ight)^2 end{split}$

如果是Absolute Error Loss，即擬合當前殘差的sign， 最優值為region中殘差的中位數 $egin{split}~~~~~~~~~~~~~~~~~~~~ gamma_{jm} = argmin_{gamma} sum_{x_i in R_{jm}} left| (y_i - F_{m-1}(x_i)) - gamma ight| end{split}$

如果是Log Loss，沒有封閉解，需要用牛頓法近似

$egin{split}~~~~~~~~~~~~~~~~~~~~ gamma_{jm} &= argmin_{gamma} sum_{x_i in R_{jm}} log left( 1 + e^{-2y_i(F_{m-1}(x_i) +gamma)} ight) \ &approx frac{sum_{x_i in R_{jm}} ilde{y}_i }{sum_{x_i in R_{jm}} | ilde{y}_i|(2- ilde{y}_i) } end{split}$

如果是Exponential Loss，最優值為region中的加權對數幾率 $egin{split}~~~~~~~~~~~~~~~~~~~~ gamma_{jm} &= argmin_{gamma} sum_{x_i in R_{jm}} log e^{-2y_i(F_{m-1}(x_i) +gamma)} \ &= log frac{sum_{x_i in R_{jm}} w_i^{(m)} I(y_i = 1) }{sum_{x_i in R_{jm}} w_i^{(m)} I(y_i = -1) } end{split}$
其中權重為 $w_i^{(m)} = e^{-y_i}f_{m-1}(x_i)$

1.3.4.4 XgBoost

前面#1.3.3 中對比了Friedman和陳天奇處理Loss上的區別。陳天奇的定義Objective中直接加入了正則項

$egin{split}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Obj &= L(Theta) + Omega(Theta) end{split}$

定義：

Regression Tree Leaf 節點數： $K$
如樣本 $x_i$ 從屬leaf node $q(x)$ , $w_{q(x)}$ 是leaf node對應的權重

定義Regression Tree的Regularization

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Omega( T(x; Theta_m)) = eta T + frac12 lambda sum_{j=1}^T w_j^2$

正則相當於控制了

樹的size不要過大
leaf node權重不要過大

使用stagewise之後，第 $m$ 步 $egin{split}~~~~~~~~~~ Obj_m &= L(Theta_m) + Omega(Theta_m) &#Loss + Reg\ &= sumlimits_{i=1}^N L(y_i, F_{m-1}(x_i) + T(x_i; Theta_m) ) + Omega(Theta_m) &#Stagewise~ Loss\ &approx sumlimits_{i=1}^N left[ L(y_i, F_{m-1}(x_i)) + g_i T(x_i; Theta_m) + frac{1}{2} q_i T^2(x_i; Theta_m) ight] + Omega(Theta_m) ~~~~&#2nd ~Order ~Taylor\ &approx sumlimits_{i=1}^N left[ g_i T(x_i; Theta_m) + frac{1}{2} q_i T^2(x_i; Theta_m) ight] + Omega(Theta_m) + constant &#remove~no~Theta~part\ &approx sumlimits_{i=1}^N left[g_i w_{q(x_i)} + frac12 q_i w_{q(x_i)}^2 ight] + eta K + frac12 lambda sum_{j=1}^T w_j^2&# remove ~constant\ &= sum_{j=1}^Tleft[ left(sum_{iin I_j }g_i ight) w_j + frac12 left(sum_{iin I_j }q_i + lambda ight) w_j^2 ight] + eta K&# group ~ by ~leaf\ &= sum_{j=1}^Tleft[ G_j w_j + frac12 left(Q_i + lambda ight) w_j^2 ight] + eta K end{split}$

其中使用了如下參數替代化簡

Loss 一階梯度： $g_i = frac{partial L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)}$
Loss 二階梯度： $q_i = frac{partial ^2 L(y_i, F_{m-1}(x_i))}{partial F_{m-1}(x_i)}$
按照leaf node聚組的一階梯度 $G_j = sum_{iin I_j }g_i$
按照leaf node聚組的二階梯度 $Q_j = sum_{iin I_j }q_i$

因為 $Obj$ 是關於 $w$ 的二次項形式，可以解得

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w_j^* = - frac{G_j}{Q_j + lambda}$

上訴最優解帶入前述Obj, XgBoost最終Obj化為

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Obj = -frac12 sum_{j=1}^T frac{G_j^2}{Q_j + lambda} + eta K$

Tree Generation and Split Finding

XgBoost中一個非常棒的特性是：使用和Objective直接相關的指標進行split。在實踐中，樹生長使用的是greedy strategy方法。

如果某個node上擁有的數據 $I$ 被某個split $s$ 分割成兩棵子樹 $I_L$ & $I_R$ ，loss reduction為

$~~~~~~~~~~~~~~~~~~~~L_{split}= frac12 left[ frac{G_L^2}{Q_L + lambda} + frac{G_R^2}{Q_R + lambda} - frac{(G_L+G_R)^2}{Q_L + Q_R+ lambda} ight] - eta$

上述可以理解為「左子樹 + 右子樹 - 不分割情況 - 分割產生的多1個leaf的複雜度」

有了分割標準，如何尋找分割點split?

最簡單的方法，窮舉所有split

Solution 1: Exact Greedy

Methods:

for k in every_feature:

for j in every_split of feature k:

find split that max gain

Flaw:

data太大效率低，可能無法放入內存
並行化會出問題

Solution: 近似演算法近似，縮小分割點candidate集合

如果開始有1M個分割點無法放入內存，通過演算法縮減到1k個即可放入內存
可以在建樹之前(global)分一次，也可以每個節點split的時候分一次(local)

近似演算法需要一個方法可以縮減候選集

XgBoost中Objective推導中#4步

$egin{split}~~~~~~~~~~ &~~~~ sumlimits_{i=1}^N left[ g_i T(x_i; Theta_m) + frac{1}{2} q_i T^2(x_i; Theta_m) ight] + Omega(Theta_m) + constant \ &= sumlimits_{i=1}^Nfrac{1}{2} q_i left[T(x_i; Theta_m) + frac{g_i}{q_i} ight]^2 + Omega(Theta_m) + constant end{split}$

可以等價為Weighted Square Loss，其中 $weight=q_i$

於是縮小候選集的過程可以認為是一個加權分位數的過程(Weighted Quantile Sketch)

Weighted Quantile Sketch

整個Candidate尋找過程可以形式化表述為

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~S={s_1,s_2,dots, s_{n+1}} o S$

對於加權&不加權數據如下，縮小candidate過程類似於取 $Y=SUM(X)$ 的b等分過程，之後通過反查對應Y值得X值來確定candidate，如果直接對應的X值沒有，則通過計算X更接近左右哪個點來確定

定義：

$w(D)$ 所有值的權重之和
$r_D^-$ 小於當前值所對應的w之和
$r_D^+$ 包含當前值所對應的w之和

Methods:

init $w(D)$
For $j$ in sorted $(x)$ :

init $x, r_D^-, r_D^+, w_D$

For $i$ in $(1, b+1)$ :

$d = frac{i-1}{b}w(D)$
if $d < frac12[r_D^-(x_1) + r_D^+(x_1)]$ :

return $x_1$

if $d > frac12[r_D^-(x_k) + r_D^+(x_k)]$ :

return $x_k$

Find $i$ suits $frac12[r_D^-(x_i) + r_D^+(x_i)] leq d leq frac12[r_D^-(x_{i+1}) + r_D^+(x_{i+1})]$
if $d < {[r_D^-(x_i) +w_D(x_i) ] + [r_D^+(x_{i+1}) - w_D(x_{i+1}) ]}/2$

return $x_{i}$

else

return $x_{i+1}$

假設有如下example

下圖為取累計頻率(無權重)和累計權重的三等分點，可以看出，實例中累計weight的更接近中心(3)

上述例子中的數據如下，

假設三等分即 $b=3$ ，如要求 $i=3$ 的點， $w(D)=30$ ， $d=20$ ,在20和22.5中和20更接近，則返回20對應的 $x=4$

1.3.4.5 XgBoost並行化

Boosting框架下，tree之間不可並行，可能的並行策略有

Boosting演算法各Stage之間相互依賴，無法並行，只能在Stage內尋找並行化的可能性

1. 按行並行化，將樣本按行分成N份，分別在N個節點上做計算；
2. For every Stage(Tree)

1. 在0號節點上對特徵隨機採樣，生成建立一棵樹需要用到的特徵，並分發到N個節點上；
2. 在0號結點上維護每一維採樣特徵所有可能的特徵值；
3. 將每一維特徵的每一個可能的特徵值分發到N個節點上；
4. 每一個節點並行計算該節點上所有樣本與分發得到的特徵值的比較結果，分割成左右子樹，並計算增益；
5. 歸併所有節點的增益，在0號結點得到每一個特徵在每一個特徵值的增益(f，v，incr)；
6. 在0號結點上找出最大的(f，v，incr)，並作為本次的最佳裂點，分發到N個節點上；
7. N個節點將樣本分割成左右子樹；
8. 對左右子樹繼續上面過程，直到葉子節點數目滿足要求。

GBDT組織方式和傳送門：

GBDT的前序兩篇：

CTR預估[七]: Algorithm-GBDT: Preliminary

Ensemble方法bagging和boosting的比較：GBDT所屬boosting演算法，說GBDT之前需要對boosting是什麼有個了解
Aside: bias and variance: bias/var tradeoff是機器學習永恆的話題，而bagging和boosting的分析，尤其是後面的RF依然會用到

CTR預估[八]: Algorithm-GBDT: Parameter Space Estimation and Function Space Estimation

函數空間和參數空間優化：GBDT本質上是從函數空間優化開始的，所以在講具體的boosting trees之前，從兩者的比較開始更佳 -- 注意，本節雖然全部為推導，但個人認為對於理解GBDT至關重要，否則更像是無根之木 （傳送門：）

Boosting Trees： GBM 和 GBDT; GBDT 的核心推導（傳送門：CTR預估[九]: Algorithm-GBDT: Boosting Trees）
Aside： Random Forest; 作為bagging的優秀代表，後面比較GBDT+LR 而非 RF+LR會用到（傳送門：CTR預估[十]: Algorithm-Random Forest）