GBDT(Gradient Boosting Decision Tree)

[TOC]

GBDT

GBDT的提出

什么是GBDT？

  这里讲GBDT其实是GBM（Gradient Boosting Machine）基学习器使用回归树时的一种具体实现形式,简单来讲，GBDT与上一节讲的AdaBoost类似，它也是一种前向分步加性模型，假设它要学习M个学习器，那么在第$m$次迭代的时候，第m个学习器的学习要经过前$m-1$个学习器的指导，并且每个学习器有一个对应的权重，最后加权相乘求和就是最后要求解的模型:
$$
\hat{f}(x) = \sum_{m=1}^M \beta_mG_m(x).
$$
$\hat{f}(x)\text{是完美函数}f(x)$在数据集上的近似。

为什么要提出GBDT?

  为了求出$\beta_m$和$G_m(x)$，一般情况下我们需要给出一个用来度量$\hat{f}(x)$在数据集上的表现、拟合情况，也就是所谓的损失函数。我们知道AdaBoost在样本集上极小化指数损失函数来求得权重$\beta_m$和$G_m(x)$，在上一节的讨论中，我们发现指数损失函数有时候鲁棒性没有那么好，对于不同的数据集，我们可能有尝试其他损失函数的需求，比如说对率损失，在做回归任务的时候也需要不同的损失函数。回顾AdaBoost，在每一步迭代的时候，指数损失很自然地把前$m-1$次的结果作为了样本的权重。对于一般的损失函数，我们得到下面优化目标：
\begin{equation}
\begin{array}{c l}
\min & \sum_{i=1}^n L(y_i,f_{m-1}(x_i)+\beta_mG_m(x_i))
\end{array}
\end{equation}
在回归任务中，当损失函数为平方损失时，也是比较容易优化的，因为使用平方损失函数，上式就变为
\begin{equation}
\begin{array}{c l}
\min & \sum_{i=1}^n \left(\left(y_i-f_{m-1}(x_i)\right)-\beta_mG_m(x_i))\right)^2\
\end{array}
\end{equation}
实际上是在拟合前$m-1$次的结果与真实因变量的残差。

算法流程和推导

从函数空间的角度去优化$f(x)$

  假设我们要优化如下目标函数
$$L(f)$$
对于这样一个无约束的优化问题，使用梯度下降法来求最优解，$f_0$为初始点，那么得到如下迭代序列：
$$f_m = f_{m-1} - \rho_m g_m，$$
其中
\begin{equation}
g_m = \frac{\partial L(f)}{\partial f}\Big|_ { f = f_ {m-1}}
\end{equation}
$\rho_m $由线搜索得到：
$$\rho_m = \arg \min_{\rho} L(f_{m-1} - \rho g_m)$$
最终得到
$$
\begin{array}{c l}
f_m & = f_{m-1} - \rho_m g_m \
& = f_{m-2} - \rho_{m-1}g_{m-1} - \rho_{m}g_m \
& \cdots \
& = f_0 + \sum_{i=1}^m -\rho_i g_i
\end{array}
$$

分析

1. 梯度下降法求$L(f)$最优解的迭代步骤与前向分步加性模型形式上一样，都是通过迭代逐渐地逼近最优解$f^{\ast}$
2. $f^{\ast}$是产生当前数据集的函数，是客观存在但我们并不知道的，梯度下降和前向分步加法模型的目标都是求得$\hat{f}\approx f^{\ast}$
3. 当知道$f_{m-1}$时，前向分步需要求得$\beta_m\text{和}G_m(x)$；梯度下降需要计算出$\rho_{m},-g_m$.
4. 前向分步不知道如何求得$\beta_m\text{和}G_m(x)$；梯度下降计算不出来$\rho_{m},-g_m$（why?在函数空间，$g_m$也是一个函数，也是客观存在，但并不知晓，唯一知道的就是$g_m(x_i)$）,于是，我们可以用$G_m(x)$去拟合$-g_m(x)$,剩下的$\beta_m\text{或者}\rho_m$就是一个单变量优化问题了。

算法

Gradient Boosting 算法
:

1. $f_0(x) = \arg\min_\gamma \sum_{i=1}^nL(y_i,\gamma)$
2. $m = 1,\cdots,M:$
   a. $g_i^m = -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\Big|_ { f(x) = f_ {m-1}(x)},i=1,\cdots,n$
   b. $\theta_m = \arg\min_{\theta} \sum_{i=1}^n \left( G(x_i;\theta) - g^m_i\right)^2$
   c. $\beta_m = \arg\min_{\beta} \sum_{i=1}^n L\left( y_i,f_{m-1}(x_i)+\beta G(x_i;\theta_m) \right)$
   d. $f_m(x) = f_{m-1}(x) + \beta_mG(x;\theta_m)$

  当我们令回归树作为基学习器时，上面算法中的求解每一步学习器参数和步长（权重）可变为更具体的形式。回归树的决策函数为:
$$T(x;\theta) = \sum_{j}^J b_j I(x\in R_j),$$
$R_j$为叶子节点，$b_j = mean\lbrace{x \in R_j \rbrace},$ 在迭代生成第$m$棵树时，此时的目标函数变为
\begin{equation}
\begin{array}{c l}
\min & \sum_{i=1}^n L(y_i,f_{m-1}(x_i)+\beta_m T(x;\theta)) \
= \min & \sum_{i=1}^n L(y_i,f_{m-1}(x_i)+ \sum_{j}^J \beta_mb_j I(x\in R_j) \
= \min & \sum_{j=1}^J \sum_{x_i \in R_j} L(y_i,f_{m-1}(x_i)+\gamma_j)
\end{array}
\end{equation}
因此
$$\gamma_j = \arg\min_{\gamma} \sum_{x_i \in R_j} L(y_i,f_{m-1}(x_i)+\gamma).$$
所以可得到如下算法：

基于 Deciision Tree 的 Gradient Boosting 算法
:

1. $f_0(x) = \arg\min_\gamma \sum_{i=1}^nL(y_i,\gamma)$
2. $m = 1,\cdots,M:$
   a. $g_i^m = -\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\Big|_ { f(x) = f_ {m-1}(x)},i=1,\cdots,n$
   b. 基于$\lbrace{x_i,g_i^m \rbrace}_{i=1}^n$拟合一个回归树，得到$R_j,j=1,\cdots,J$
   c. $\gamma_j = \arg\min_{\gamma} \sum_{x_i \in R_j} L\left(y_i,f_{m-1}(x_i)+\gamma\right),j=1,\cdots,J$
   d. $f_m(x) = f_{m-1}(x) + \sum_{j}^J \gamma_j I(x\in R_j)$

简单来讲，为了求得第$m$棵树，我们需要做两步：第一，基于负梯度拟合出一个回归树；第二，根据损失函数求出回归树每个节点的最优取值，相当于线搜索。

应用

  不同的应用会有不同的损失函数，不同的损失函数会产生不同的梯度形式，以及每个叶子节点的最优取值，下面分别讨论。

回归任务

最小二乘回归

损失函数为
$$L(y,f) = \frac{1}{2}(y-f)^2$$
梯度为
$$g = y-f$$
事实上就是残差，每个叶子节点的取值为所有当前叶子节点样本因变量的均值。

LAD 回归

损失函数为
$$L(y,f) = \left| y-f \right|$$
梯度为
$$g = sign(y-f),$$
是残差的符号，每个叶子节点的取值为所有当前叶子节点样本因变量的中位数。

  绝对值作为损失函数比最小二乘有更好的鲁棒性，特别是对于长尾数据，最小二乘很容易受这些数据的影响。

分类任务

对率损失

损失函数为
$$L(y,f) = \log(1+\exp(-yf(x)))$$
梯度为
$$g = -\frac{y}{1+\exp(yf(x))},$$

指数损失

损失函数为
$$L(y,f) = \exp(-yf(x)))$$
梯度为
$$g = -y\exp(-yf(x)),$$

特征重要性

  实际应用时，除了关注模型对数据的预测能力外，往往还想知道究竟哪些特征对于模型的预测能力贡献比较大，比如在sklearn训练完模型后，我们能够直接输出特征的重要性排序，那么如何计算特征的重要性呢？

在单棵回归树中，一个特征的重要性是通过下面这个式子定义的：
$$\text{feature_importance}_ i^2(T) = \sum_ {t=1}^{J-1}\text{improve}_t^2I\left( v(t)=i \right)$$
具体来讲就是，在回归树T中，第$i$个特征的重要性等于那些以特征$i$作为划分节点时，划分前后损失函数的下降量的平方和。推广到GBDT时，假设有$M$次迭代，那么特征的重要性为
$$\text{feature_importance}_ i^2 = \frac{1}{M}\sum_ {m=1}^M\text{feature_importance}_i^2(T_m),$$
一般情况下，计算完所有的特征重要性后，把所有的值可以放缩到$[0,1]$

References

[1] Hastie, The Elements of Statistical Learning
[2] Friedman, Greedy Function Approximation: A Gradient Boosting Machine