我们对Boosting家族的Adaboost算法做了总结，本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。GBDT有很多简称，有GBT（Gradient Boosting Tree）, GTB（Gradient Tree Boosting ）， GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其实都是指的同一种算法，本文统一简称GBDT。GBDT在BAT大厂中也有广泛的应用，假如要选择3个最重要的机器学习算法的话，个人认为GBDT应该占一席之地。
我们先来看看提升树：
提升树模型实际是将多个决策树简单的叠加起来，用数学模型可表示为
$$ f_M(x) = \sum_{m=1}^M T(x;\Theta_m) $$
其中，$T(x;\Theta_m)$表示决策树，$\Theta_m$ 表示决策树的参数；$M$ 为树的个数。
针对样本$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，提升树模型的训练就是，选择决策树的参数$\Theta=\{\Theta_1,\Theta_2,...,\Theta_M\}$以最小化损失函数 $\sum L(y_i,f_M(x_i))$，即
$$ \arg \min_\Theta \sum_{i=1}^N L(y_i,f_M(x_i)) = \arg \min_\Theta \sum_{i=1}^N L\left(y_i, \sum_{m=1}^M T(x;\Theta_m)\right) $$
这里，损失函数用来反应“样本标签 $y_i$ ”与提升树的输出 $f_M(x_i)$ 之间的差别，这里可以选择平方误差损失函数：
$$ L(y, f(x))=\left( y-f(x) \right)^2 $$
提升树模型也可以表示为迭代过程
$$ f_m(x)=f_{m-1}(x)+T(x;\Theta_m),~ m=1,2,...,M $$
因此，提升树的训练也可以按照迭代的过程来完成，在 $m$次迭代中，生成一个新的决策树$T(x;\Theta_m)$
具体而言，首先初始化提升树 $f_0(x)=0$，第 $m$ 步确定第 $m$ 个决策树$T(x;\Theta_m)$，即选择合适的决策树参数 $\Theta_m$，使损失函数最小，即
$$ \hat{\Theta}_m = \arg \min_{\Theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i;\Theta_m)) $$
对于上式的求解，即为提升树的关键所在。如果采用平方损失函数，则有
$$ \begin{eqnarray*} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)) &=& \left[\,y_i - f_{m-1}(x_i) - T(x_i;\Theta_m)\right]^2 \\ &=& \left[\,r_{m,i} - T(x_i;\Theta_m)\right]^2 \end{eqnarray*} $$
这里， $r_{m,i}=y_i-f_{m-1}(x_i)$ 表示模型$f_{m-1}(x)$拟合数据 $(x_i,y_i)$ 的残差。
就变成了选择合适的决策树参数$\Theta_m$，使得决策树的输出 $T(x_i;\Theta_m)$与 残差 $r_{m,i}$ 的误差尽可能小。因此，可以使用 $\{(x_i,r_{m,i})\}_{i=1,2,...,N}$来作为决策树$T(x;\Theta_m)$的样本集，按照常规的决策树生成过程获得参数的最优值$\hat{\Theta}_m$。
综上，我们可以得到提升树算法如下：
上面我们讲了提升树，在某些时候不方便求残差，梯度提升树则是用损失函数的负梯度方向值来近似拟合残差，下面来看看具体细节：
二元GBDT分类算法
对于二分类问题，比较常用的损失函数为
$$ L(y,f(x))=\log (1+\exp (-y \cdot f(x))) \tag{12} $$
其中 $y∈{−1,+1}$，此时的负梯度误差为
$$ r_{m,i} = -\left[ \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1}(x)} = \frac{y_i}{1+\exp (y_i f_{m-1}(x_i))} $$
对于生成决策树，其叶子节点的输出值为
$$ c_{m,j} = \arg \min_c \sum_{x_i\in R_{m,j}} \log (1+\exp (-y_i (f_{m-1}(x_i) + c))) $$
由于上式比较难优化，我们一般使用近似值代替
$$ c_{m,j} =\left. \sum_{x_i\in R_{m,j}} r_{m,i} \middle / \sum_{x_i\in R_{m,j}} |r_{m,i}|(1-|r_{m,i}|) \right. $$
多元GBDT分类算法
对于多分类问题，假设类别为$ K$，一般采用的损失函数为
$$ L(y,f(x)) = - \sum_{k=1}^K y_k log p_k(x) $$
其中，如果样本输出类别为 $k$ ，则 $y_k=1$ ；$p_k(x)$ 表示模型 $f(x)$判定 $x$属于第$k$ 类的概率，其表达式为
$$ p_k(x) = \frac{\exp (f_k(x))}{ \sum_{l=1}^K \exp(f_l(x))} $$
注意此处，对于多分类问题，回归树训练时，会为每一个类别训练一个决策树。
由此，我们可以计算出第 $m$ 轮的第$i$个样本对应类别$ l$的负梯度误差为
$$ r_{m,i,l} = -\left[ \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1,l}(x)} = y_{i,l} - p_{m,l}(x_i) $$
观察上式可以看出，其实这里的误差就是样本$i$对应类别$l$ 的真实概率和$m−1$ 轮预测概率的差值。
对于生成的决策树，对应第$l$类别的决策树的叶节点输出为
$$ c_{m,l,j} = \arg \min_c \sum_{x_i \in R_{m,l,j}} L(y_{i,l}, f_{m-1,l}(x_i) + c) $$
类似的，我们用近似值代替
$$ c_{m,l,j} = \frac{K-1}{K} \frac{\sum\limits_{x_i \in R_{m,l,j}}r_{m,i,l}}{ \sum\limits_{x_i \in R_{m,l,j}} |r_{m,i,l}|(1-|r_{m,i,l}|) } $$
GBDT 的正则化
- 第一种是和Adaboost类似的正则化项，即使用步长(learning rate)，定义为 αα 。常规的提升回归树的迭代为
$$ f_m(x) = f_{m-1}(x) + T(x;\Theta_m) $$
引入正则化后，其迭代过程为
$$ f_m(x) = f_{m-1}(x) + \alpha T(x;\Theta_m) $$
其中，$0<α≤1$。对于同样的训练集学习效果，较小的 αα 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
- 第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。 - 第三种称为 Regularized Learning Objective，将树模型的复杂度作为正则项显式地加进优化目标里，这也是XGBoost实现的独到之处。其具体实现可以参考文献[7]，在这里列出其加入正则化后的优化目标
$$ L_{r}(y,f(x)) = L(y,f(x)) + \sum_{m} \Omega(T(x;\Theta_m)) \\ \mathrm{where} ~~ \Omega(T(x;\Theta_m)) = \gamma T_{leaf} + \frac12 \lambda \| w \|^2 $$
其中，$L(y,f(x))$ 为常规的损失函数；$\Omega(T(x;\Theta_m))$表示决策树的复杂度，$T_{leaf}$为树叶节点个数，$w$ 为叶节点的固定输出值$c_m$组成的向量；$γ,λ$为相应的系数。
- 最后还有一种就是类 似DeepLearning 的 Dropout ，其具体可以参考文献[8]。通俗地讲，每次新加一棵树，这棵树要拟合的并不是之前全部树ensemble后的残差，而是随机抽取的一些树ensemble。
