GBDT与xgboost

1. 泰勒公式

• 定义：泰勒公式是一个用函数在某点的信息描述其附近取值的公式。 局部有效性

• 基本形式：f(x) = ∑∞n=0f(n)(x0)n!(x−x0)n$f(x)=\sum _{n=0}^{\mathrm{\infty }}\frac{f^{(n)}(x_0)}{n!}(x-x_0{)}^n$

  • 一阶泰勒展开：f(x)≈f(x0)+f′(x0)(x−x0)$f(x)\approx f(x_0)+f^{\prime }(x_0)(x-x_0)$
  • 二阶泰勒展开：f(x)≈f(x0)+f′(x0)(x−x0)+f′′(x0)(x−x0)22$f(x)\approx f(x_0)+f^{\prime }(x_0)(x-x_0)+f^{″}(x_0)\frac{(x-x_0{)}^2}{2}$
  • 迭代形式：假设 xt=xt−1+Δx$x^t=x^{t-1}+\mathrm{\Delta }x$，将 f(xt)$f(x^t)$ 在 xt−1$x^{t-1}$ 处进行泰勒展开：
    
    f(xt)=f(xt−1+Δx)≈f(xt−1)+f′(xt−1)Δx+f′′(xt−1)Δx22(1)(2)$$\begin{array}{}\text{(1)}& f(x^t)& =f(x^{t-1}+\mathrm{\Delta }x)\text{(2)}& & \approx f(x^{t-1})+f^{\prime }(x^{t-1})\mathrm{\Delta }x+f^{″}(x^{t-1})\frac{{\mathrm{\Delta }x}^2}{2}\end{array}$$

2. 梯度下降法（Gradient Descend Method）

  在机器学习任务中， 需要最小化损失函数 L(θ)$L(\theta )$， 其中 θ$\theta$ 是要求解的模型参数。 梯度下降法常用来求解这种无约束最优化问题， 它是一种迭代方法： 选取初值 θ0${\theta }^0$， 不断迭代， 更新 θ$\theta$ 的值， 进行损失函数的极小化。

• 迭代公式：θ=θt−1+Δθ$\theta ={\theta }^{t-1}+\mathrm{\Delta }\theta$

• 将 L(θt)$L({\theta }^t)$ 在 θt−1${\theta }^{t-1}$ 处进行一阶泰勒展开：
  

  L(θt)=L(θt−1+Δθ)≈L(θt−1)+L′(θt−1)Δθ(3)(4)$$\begin{array}{}\text{(3)}& L({\theta }^t)& =L({\theta }^{t-1}+\mathrm{\Delta }\theta )\text{(4)}& & \approx L({\theta }^{t-1})+L^{\prime }({\theta }^{t-1})\mathrm{\Delta }\theta \end{array}$$

• 要使得 L(θt)<L(θt−1)$L({\theta }^t)<L({\theta }^{t-1})$，可使：Δθ=−αL′(θt−1)$\mathrm{\Delta }\theta =-\alpha L^{\prime }({\theta }^{t-1})$，则：θt=θt−1−αL′(θt−1)${\theta }^t={\theta }^{t-1}-\alpha L^{\prime }({\theta }^{t-1})$
  这里 α$\alpha$ 是步长，可通过 line search 确定，但一般直接赋一个小的数。

3. 牛顿法（Newton’s Method）

• 将 L(θt)$L({\theta }^t)$ 在 θt−1${\theta }^{t-1}$ 处进行二阶泰勒展开：
  

  L(θt)=L(θt−1+Δθ)≈L(θt−1)+L′(θt−1)Δθ+L′′(θt−1)Δθ22(5)(6)$$\begin{array}{}\text{(5)}& L({\theta }^t)& =L({\theta }^{t-1}+\mathrm{\Delta }\theta )\text{(6)}& & \approx L({\theta }^{t-1})+L^{\prime }({\theta }^{t-1})\mathrm{\Delta }\theta +L^{″}({\theta }^{t-1})\frac{{\mathrm{\Delta }\theta }^2}{2}\end{array}$$
  
    为了简化分析过程，假设参数是标量（即 θ​$\theta$ 只有一维），则可将一阶和二阶导数分别记为 g$g$ 和 h$h$：
  
  L(θt)≈L(θt−1)+gΔθ+hΔθ22$$L({\theta }^t)\approx L({\theta }^{t-1})+g\mathrm{\Delta }\theta +h\frac{{\mathrm{\Delta }\theta }^2}{2}$$

• 要使得 L(θt)$L({\theta }^t)$ 极小，即让 gΔθ+hΔθ22$g\mathrm{\Delta }\theta +h\frac{{\mathrm{\Delta }\theta }^2}{2}$ 极小，可令：∂(gΔθ+hΔθ22)∂Δθ=0$\frac{\mathrm{\partial }\left(g\mathrm{\Delta }\theta +h\frac{{\mathrm{\Delta }\theta }^2}{2}\right)}{\mathrm{\partial }\mathrm{\Delta }\theta }=0$
  求得 Δθ=−gh$\mathrm{\Delta }\theta =-\frac{g}{h}$ ，故：θt=θt−1+Δθ=θt−1−gh${\theta }^t={\theta }^{t-1}+\mathrm{\Delta }\theta ={\theta }^{t-1}-\frac{g}{h}$
  参数 θ$\theta$ 推广到向量形式，迭代公式：θt=θt−1−H−1g${\theta }^t={\theta }^{t-1}-H^{-1}g$
  这里 H$H$ 是海森矩阵

4. 从参数空间到函数空间

• GBDT 在函数空间中利用梯度下降法进行优化
• XGBoost 在函数空间中用牛顿法进行优化

注：实际上GBDT泛指所有梯度提升树算法， 包括XGBoost， 它也是GBDT的一种变种， 这里为了区分它们， GBDT特指“Greedy Function Approximation： A Gradient Boosting Machine” 里提出的算法， 它只用了一阶导数信息。

5. Gradient Boosting Tree 算法原理

• Friedman于论文” Greedy Function Approximation…”中最早提出GBDT

• 其模型 F$F$ 定义为加法模型：
  

  F(x;w)=∑t=0Tαtht(x;wt)=∑t=0Tft(x;wt)$$F(x;w)=\sum _{t=0}^T{\alpha }_t{h}_t(x;w_t)=\sum _{t=0}^T{f}_t(x;w_t)$$
  
    其中， x$x$ 为输入样本， h$h$ 为分类回归树， w$w$ 是分类回归树的参数，α$\alpha$ 是每棵树的权重。

• 通过最小化损失函数求解最优模型：
  

  F∗=argminF∑i=0NL(yi,F(xi;w))$$F^{\ast }=arg\underset{F}{min}\sum _{i=0}^{N}L(y_i,F(x_i;w))$$
  
    NP难问题 -> 通过贪心法， 迭代求局部最优解

6. 详解 XGBoost

6.1 模型函数形式

  给定数据集 D={(Xi,yi)}$D=\{(X_i,y_i)\}$，XGBoost进行 additive training， 学习K棵树， 采用以下函数对样本进行预测：

  这里 F$F$ 是假设空间，f(x)$f(x)$ 是回归树（CART）：

  q(x)$q(x)$ 表示将样本 x$x$ 分到了某个叶子节点上， w$w$ 是叶子节点的分数（leaf score），所以 wq(x)$w_{q(x)}$ 表示回归树对样本的预测值

• 例子：预测一个人是否喜欢电脑游戏
  

  回归树的预测输出是实数分数， 可以用于回归、 分类、 排序等任务中。 对于回归问题， 可以直接作为目标值， 对于分类问题， 需要映射成概率， 比如采用逻辑函数：σ(x)=11+e−z$\sigma (x)=\frac{1}{1+e^{-z}}$

6.2 目标函数

• 参数空间中的目标函数：
  
    误差函数可以是square loss， logloss等， 正则项可以是L1正则，L2正则等。

  Ridge Regression（岭回归） ：∑ni=1(yi−θTxi)2+λ||θ||2$\sum _{i=1}^n(y_i-{\theta }^T{x}_i{)}^2+\lambda ||\theta |{|}^2$
  LASSO：∑ni=1(yi−θTxi)2+λ||θ||1$\sum _{i=1}^n(y_i-{\theta }^T{x}_i{)}^2+\lambda ||\theta |{|}_1$

6.3 正则项

• XGBoost的目标函数（函数空间）
  

  L(ϕ)=∑il(yi^,yi)+∑kΩ(fk)$$\mathcal{L}(\varphi )=\sum _{i}l(\widehat{y_i},y_i)+\sum _k\mathrm{\Omega }(f_k)$$
  
    正则项对每棵回归树的复杂度进行了惩罚

• 相比原始的GBDT， XGBoost的目标函数多了正则项， 使得学习出来的模型更加不容易过拟合。

• 有哪些指标可以衡量树的复杂度？
  树的深度， 内部节点个数， 叶子节点个数(T)， 叶节点分数(w)…
  XGBoost采用的：
  
  Ω(f)=γT+12λ||w||2$$\mathrm{\Omega }(f)=\gamma T+\frac{1}{2}\lambda ||w|{|}^2$$
  
    对叶子节点个数进行惩罚， 相当于在训练过程中做了剪枝

6.4 误差函数的二阶泰勒展开

• 第 t$t$ 次迭代后， 模型的预测等于前 t−1$t-1$ 次的模型预测加上第 t$t$ 棵树的预测：
  

  yi^(t)=yi^(t−1)+ft(xi)$${\widehat{y_i}}^{(t)}={\widehat{y_i}}^{(t-1)}+f_t(x_i)$$

• 此时目标函数可写作：
  

  L(t)=∑inl(yi^(t−1)+ft(xi),yi)+Ω(ft)$${\mathcal{L}}^{(t)}=\sum _i^{n}l({\widehat{y_i}}^{(t-1)}+f_t(x_i),y_i)+\mathrm{\Omega }(f_t)$$
  
    公式中 yi$y_i$, yi^(t−1)${\widehat{y_i}}^{(t-1)}$ 都已知， 模型要学习的只有第 t$t$ 棵树 ft$f_t$

• 将误差函数在 yi^(t−1)${\widehat{y_i}}^{(t-1)}$ 处进行二阶泰勒展开：
  

  L(t)≃∑i=1n[l(yi,y^(t−1))+gift(xi)+12hif2t(xi)]+Ω(ft)$${\mathcal{L}}^{(t)}\simeq \sum _{i=1}^n[l(y_i,{\hat{y}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\mathrm{\Omega }(f_t)$$
  
    公式中，gi=∂y^(t−1)l(yi,y^(t−1))hi=∂2y^(t−1)l(yi,y^(t−1))$g_i={\mathrm{\partial }}_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}^{(t-1)})h_i={\mathrm{\partial }}_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}^{(t-1)})$

• 将公式中的常数项去掉， 得到：
  

  L˜(t)=∑i=1n[gift(xi)+12hif2t(xi)]+Ω(ft)$${\tilde{\mathcal{L}}}^{(t)}=\sum _{i=1}^n[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\mathrm{\Omega }(f_t)$$

• 把 ft$f_t$，Ω(ft)$\mathrm{\Omega }(f_t)$ 写成树结构的形式， 即把下式代入目标函数中
  

  f(x)=wq(x)Ω(f)=γT+12λ||w||2$$f(x)=w_{q(x)}\mathrm{\Omega }(f)=\gamma T+\frac{1}{2}\lambda ||w|{|}^2$$

• 得到：
  

  L˜(t)=∑i=1n[gift(xi)+12hif2t(xi)]+Ω(ft)=∑i=1n[giwq(xi)+12hiw2q(x)]+γT+λ12∑j=1Tw2j(7)(8)$$\begin{array}{}\text{(7)}& {\tilde{\mathcal{L}}}^{(t)}& =\sum _{i=1}^n[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\mathrm{\Omega }(f_t)\text{(8)}& & =\sum _{i=1}^n[g_i{w}_{q(x_i)}+\frac{1}{2}{h}_i{w}_{q(x)}^2]+\gamma T+\lambda \frac{1}{2}\sum _{j=1}^T{w}_j^2\end{array}$$
  
    上面第一个 ∑$\sum$ 是对样本累加，第二个 ∑$\sum$ 是对叶节点累加，如何统一起来呢？

• 定义每个叶节点 j$j$ 上的样本集合为：Ij={i|q(xi)=j}$I_j=\{i|q(x_i)=j\}$
  则目标函数可以写成按叶节点累加的形式：
  

  L˜(t)=∑j=1T⎡⎣(∑i∈Ijgi)wj+12(∑i∈Ijhi+λ)w2j⎤⎦+γT=∑j=1T[Gjwj+12(Hj+λ)w2j]+γT(9)(10)$$\begin{array}{}\text{(9)}& {\tilde{\mathcal{L}}}^{(t)}& =\sum _{j=1}^T\left[(\sum _{i\in I_j}{g}_i)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2\right]+\gamma T\text{(10)}& & =\sum _{j=1}^T\left[G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2\right]+\gamma T\end{array}$$

• 如果确定了树的结构（即 q(x)$q(x)$ 确定） ， 为了使目标函数最小， 可以令其导数为 0， 解得每个叶节点的最优预测分数为：
  

  w∗j=− GjHj+λ$$w_j^{\ast }=-\frac{G_j}{H_j+\lambda }$$
  
    代入目标函数， 得到最小损失为：
  
  L˜∗=− 12∑j=1TG2jHj+λ+γT$${\tilde{\mathcal{L}}}^{\ast }=-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$$

6.5 回归树的学习策略

• 当回归树的结构确定时， 我们前面已经推导出其最优的叶节点分数以及对应的最小损失值， 问题是怎么确定树的结构？

  暴力枚举所有可能的树结构， 选择损失值最小的 - NP难问题
  贪心法， 每次尝试分裂一个叶节点， 计算分裂前后的增益， 选择增益最大的

• 分裂前后的增益怎么计算？
  ID3算法采用信息增益
  C4.5算法采用信息增益比
  CART采用Gini系数
  XGBoost呢？

6.6 XGBoost 的打分函数

  G2jHj+λ$\frac{G_j^2}{H_j+\lambda }$ 衡量了每个叶子节点对总体损失的的贡献， 我们希望损失越小越好， 则其值越大越好。
  因此， 对一个叶子节点进行分裂， 分裂前后的增益定义为：

  Gain$Gain$ 的值越大， 分裂后 L$\mathcal{L}$ 减小越多。 所以当对一个叶节点分割时， 计算所有候选(feature,value)对应的 gain， 选取 gain 最大的进行分割

6.7 树节点分裂方法（Split Finding）