# GBDT演算法原理深入解析

## 機器學習的關鍵元素

Obj(Θ)=L(Θ) Ω(Θ)

Obj(\Theta)=L(\Theta) \Omega(\Theta)

GBDT演算法可以看成是由K棵樹組成的加法模型：

y^i=∑k=1Kfk(xi),fk∈F(0)

\hat{y}_i=\sum_{k=1}^K f_k(x_i), f_k \in F \tag 0

y^0iy^1iy^2iy^ti=0=f1(xi)=y^0i f1(xi)=f1(xi) f2(xi)=y^1i f2(xi)⋯=∑k=1tfk(xi)=y^t−1i ft(xi)

\begin{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) \\
& \cdots \\
\hat{y}_i^t &= \sum_{k=1}^t f_k(x_i) = \hat{y}_i^{t-1} f_t(x_i) \\
\end{split}

Obj(t)=∑i=1nl(yi,y^ti) ∑i=itΩ(fi)=∑i=1nl(yi,y^t−1i ft(xi)) Ω(ft) constant(1)

\begin{split}
Obj^{(t)} &= \sum_{i=1}^nl(y_i, \hat{y}_i^t) \sum_{i=i}^t \Omega(f_i) \\
&= \sum_{i=1}^n l\left(y_i, \hat{y}_i^{t-1} f_t(x_i) \right) \Omega(f_t) constant
\end{split}\tag{1}

Obj(t)=∑i=1n(yi−(y^t−1i ft(xi)))2 Ω(ft) constant=∑i=1n[2(y^t−1i−yi)ft(xi) ft(xi)2] Ω(ft) constant(2)

\begin{split}
Obj^{(t)} &= \sum_{i=1}^n \left(y_i – (\hat{y}_i^{t-1} f_t(x_i)) \right)^2 \Omega(f_t) constant \\
&= \sum_{i=1}^n \left[2(\hat{y}_i^{t-1} – y_i)f_t(x_i) f_t(x_i)^2 \right] \Omega(f_t) constant
\end{split}\tag{2}

—-維基百科

f(x Δx)≈f(x) f′(x)Δx 12f′′(x)Δx2(3)

f(x \Delta x) \approx f(x) f'(x)\Delta x \frac12 f”(x)\Delta x^2 \tag 3

Obj^{(t)} = \sum_{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) g_if_t(x_i) \frac12h_if_t^2(x_i) \right] \Omega(f_t) constant \tag 4

Obj^{(t)} \approx \sum_{i=1}^n \left[ g_if_t(x_i) \frac12h_if_t^2(x_i) \right] \Omega(f_t) \tag 5

## GBDT演算法

Obj(t)≈∑i=1n[gift(xi) 12hif2t(xi)] Ω(ft)=∑i=1n[giwq(xi) 12hiw2q(xi)] γT 12λ∑j=1Tw2j=∑j=1T⎡⎣(∑i∈Ijgi)wj 12(∑i∈Ijhi λ)w2j⎤⎦ γT(6)

\begin{split}
Obj^{(t)} &\approx \sum_{i=1}^n \left[ g_if_t(x_i) \frac12h_if_t^2(x_i) \right] \Omega(f_t) \\
&= \sum_{i=1}^n \left[ g_iw_{q(x_i)} \frac12h_iw_{q(x_i)}^2 \right] \gamma T \frac12 \lambda \sum_{j=1}^T w_j^2 \\
&= \sum_{j=1}^T \left[(\sum_{i \in I_j}g_i)w_j \frac12(\sum_{i \in I_j}h_i \lambda)w_j^2 \right] \gamma T
\end{split}\tag 6

Obj(t)=∑j=1T[Giwj 12(Hi λ)w2j] γT

Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j \frac12(H_i \lambda)w_j^2 \right] \gamma T

w∗j=−GjHj λ(7)

w_j^*=-\frac{G_j}{H_j \lambda} \tag 7 此時，目標函式的值為

Obj=−12∑j=1TG2jHj λ γT(8)

Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j \lambda} \gamma T \tag 8

1. 列舉所有可能的樹結構qq
2. 用等式(8)為每個qq計算其對應的分數ObjObj，分數越小說明對應的樹結構越好
3. 根據上一步的結果，找到最佳的樹結構，用等式(7)為樹的每個葉子節點計算預測值

1. 從深度為0的樹開始，對每個葉節點列舉所有的可用特徵
2. 針對每個特徵，把屬於該節點的訓練樣本根據該特徵值升序排列，通過線性掃描的方式來決定該特徵的最佳分裂點，並記錄該特徵的最大收益（採用最佳分裂點時的收益）
3. 選擇收益最大的特徵作為分裂特徵，用該特徵的最佳分裂點作為分裂位置，把該節點生長出左右兩個新的葉節點，併為每個新節點關聯對應的樣本集
4. 回到第1步，遞迴執行到滿足特定條件為止

Gain=12[G2LHL λ G2RHR λ−(GL GR)2HL HR λ]−γ

Gain=\frac12 \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}\right] – \gamma 其中，−γ-\gamma項表示因為增加了樹的複雜性（該分裂增加了一個葉子節點）帶來的懲罰。

1. 演算法每次迭代生成一顆新的決策樹
2. 在每次迭代開始之前，計算損失函式在每個訓練樣本點的一階導數gig_i和二階導數hih_i
3. 通過貪心策略生成新的決策樹，通過等式(7)計算每個葉節點對應的預測值
4. 把新生成的決策樹ft(x)f_t(x)新增到模型中：y^ti=y^t−1i ft(xi)\hat{y}_i^t = \hat{y}_i^{t-1} f_t(x_i)