梯度提升决策树(GBDT)

Boosting 属于集成学习的一种方法，算是传统机器学习的大杀器之一了。本文介绍 GBDT 的相关知识。

关于 Boosting 的知识，我在之前的一篇文章机器学习之 Bootstrap、Bagging、Boosting 介绍中介绍了很多了。本文开门见山，直接介绍 GBDT 了，本文的很多内容都是 GBDT 和 XGBoost 融合，因为二者本来就很像。

GBDT 介绍

GBDT 全称为 Gradient Boosting Decision Tree，是一种用于回归、分类和排序任务的机器学习技术，属于 Boosting 方法族的一部分。Boosting 方法通过分步迭代（stage-wise）的方式来构建模型，在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足。

GBDT 和 AdaBoost

Boosting 族算法的著名代表是 AdaBoost，AdaBoost 算法通过给已有模型预测错误的样本更高的权重，使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。与 AdaBoost 算法不同，梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失（steepest-descent）的学习器来弥补已有模型的不足。经典的 AdaBoost 算法只能处理采用指数损失函数的二分类学习任务，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking 等），应用范围大大扩展。

另一方面，AdaBoost 算法对异常点（outlier）比较敏感，而梯度提升算法通过引入 Bagging 思想、加入正则项等方法能够有效地抵御训练数据中的噪音，具有更好的健壮性。这也是为什么梯度提升算法（尤其是采用决策树作为弱学习器的 GBDT 算法）如此流行的原因，甚至有种观点认为 GBDT 是性能最好的机器学习算法，这当然有点过于激进又固步自封的味道，但通常各类机器学习算法比赛的赢家们都非常青睐 GBDT 算法，由此可见该算法的实力不可小觑。

GBDT 的优劣点

基于梯度提升算法的学习器叫做 GBM(Gradient Boosting Machine)。理论上，GBM 可以选择各种不同的学习算法作为基学习器。现实中，用得最多的基学习器是决策树。为什么梯度提升方法倾向于选择决策树（通常是 CART 树）作为基学习器呢？这与决策树算法自身的优点有很大的关系。

• 决策树可以认为是 if-then 规则的集合，易于理解，可解释性强，预测速度快。
• 决策树算法相比于其他的算法需要更少的特征工程，比如可以不用做特征标准化，可以很好的处理字段缺失的数据，也可以不用关心特征间是否相互依赖等。
• 决策树能够自动组合多个特征，它可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分（举个例子，决策树能轻松处理好类别 $A$ 在某个特征维度 $x$ 的末端，类别 $B$ 在中间，然后类别 $A$ 又出现在特征维度 $x$ 前端的情况）。

不过，单独使用决策树算法时，有容易过拟合缺点。所幸的是，通过各种方法，抑制决策树的复杂性，降低单颗决策树的拟合能力，再通过梯度提升的方法集成多个决策树，最终能够很好的解决过拟合的问题。由此可见，梯度提升方法和决策树学习算法可以互相取长补短，是一对完美的搭档。至于抑制单颗决策树的复杂度的方法有很多，比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收 bagging 的思想对训练样本采样（subsample），在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。现在主流的 GBDT 算法实现中这些方法基本上都有实现，因此 GBDT 算法的超参数还是比较多的，应用过程中需要精心调参，并用交叉验证的方法选择最佳参数。

加法模型

GBDT 听起来很厉害，看上去很复杂，实际算法模型却很简单，可以简单的认为是由 $K$ 棵树组成的加法模型：

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

从上面公式可以看出，GBDT 预测的结果就是多个串联的树的预测结果的和。那么这些树是如何训练学习的呢？

首先定义目标函数为： $Obj=\sum{i=1}^n l(y_i, \hat{y}_i) + \sum{k=1}^K \Omega(f_k)$，其中 $\Omega$ 表示决策树的复杂度（树的复杂度可以考虑树的节点数量、树的深度或者叶子节点所对应的分数的L2范数等等），作为参数正则化项，前一部分就是我们熟悉的损失函数。和大多数机器学习的任务一样，我们训练的目标就是使得目标函数最小化。

解这一优化问题，可以用前向分布算法（forward stagewise algorithm）。因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数（结构），逐步逼近优化目标函数，那么就可以简化复杂度。这一学习过程称之为 Boosting。具体地，我们从一个常量预测开始，每次学习一个新的函数，过程如下：

$$\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}$$

那么，在每一步如何决定哪一个函数 $f$ 被加入呢？指导原则还是最小化目标函数。

在第 $t$ 步，模型对于 $x_i$ 的预测为：$\hat{y}_i^t= \hat{y}_i^{t-1} + f_t(x_i)$，其中 $f_t(x_i)$ 为这一轮中我们要学习的函数（一颗决策树）。这个时候，目标函数可以表示为：

$$\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}$$

举例说明，假设损失函数为平方损失（square loss），则目标函数为：

$$\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}$$

其中，$(\hat{y}_i^{t-1} - y_i)$ 称之为残差（residual）。因此，使用平方损失函数时，GBDT算法的每一步在生成决策树时只需要拟合前面的模型的残差。

等式 (1) 为什么能够写成等式 (2) 呢？下面我们用泰勒展开来解释这个损失函数。

泰勒公式：设 $n$ 是一个正整数，如果定义在一个包含 $a$ 的区间上的函数 $f$ 在点 $a$ 处 $n+1$ 次可导，那么对于这个区间上的任意 $x$ 都有：$\displaystyle f(x)=\sum{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^n+R n(x)$，其中的多项式称为函数在 $a$ 处的泰勒展开式，$R_n(x)$ 是泰勒公式的余项且是 $(x-a)^n$ 的高阶无穷小。

根据泰勒公式把函数在 $f(x+\Delta x)$ 点 $x$ 处二阶展开，可得到如下等式：

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

所以由等式 (1) 可知，目标函数是关于变量 $\hat{y}_i^{t-1} + f_t(x_i)$ 的函数（$y_i$ 表示 label，是已知量）。我们可以把变量 $\hat{y}_i^{t-1}$ 看成是等式 (3) 中的 $x$，把变量 $f_t(x_i)$ 看成是其中的 $\Delta x$，则等式 (1) 可转化为：

$$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$$

其中，$gi$ 定义为 损失函数 $l(x)$ 的一阶导数：$g_i=\partial{\hat{y}^{t-1}}l(yi,\hat{y}^{t-1})$。$h_i$ 定义为损失函数的二阶导数：$h_i=\partial{\hat{y}^{t-1}}^2l(yi,\hat{y}^{t-1})$。举个例子，假设损失函数为平方损失函数，则 $g_i=\partial{\hat{y}^{t-1}}(\hat{y}^{t-1} - yi)^2 = 2(\hat{y}^{t-1} - y_i)$，$h_i=\partial{\hat{y}^{t-1}}^2(\hat{y}^{t-1} - y_i)^2 = 2$。我们将 $g_i$ 和 $h_i$ 带入等式 (4) 就可以得到了基于平方损失函数的目标函数，也就是等式 (2)。

由于函数中的常量在函数最小化的过程中不起作用，因此我们可以从等式 (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$$

由于要学习的函数仅仅依赖于目标函数，从等式 (5) 可以看出只需为学习任务定义好损失函数，并为每个训练样本计算出损失函数的一阶导数和二阶导数，通过在训练样本集上最小化等式 (5) 即可求得每步要学习的函数 $f(x)，从而根据加法模型等式 (0) 可得最终要学习的模型。

GBDT 算法模型

了解了加法模型，我们再来看 GBDT 中怎么运用加法模型。对于一颗生成好的决策树，假设其叶子节点个数为 $T$，该决策树是由所有叶子节点对应的值组成的向量 $w \in R^T$，以及一个把特征向量映射到叶子节点索引（Index）的函数 $q:R^d \to {1,2,\cdots,T}$ 组成的。因此，策树可以定义为：$ft(x)=w{q(x)}$。

决策树的复杂度可以由正则项 $\Omega(ft)=\gamma T + \frac12 \lambda \sum{j=1}^T w_j^2$ 来定义，即决策树模型的复杂度由生成的树的叶子节点数量和叶子节点对应的值向量的L2范数决定。

定义集合 $I_j={ i \vert q(x_i)=j }$ 为所有被划分到叶子节点 $j$ 的训练样本的集合。上面的等式 (5) 可以根据树的叶子节点重新组织为 $T$ 个独立的二次函数的和：

$$\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$$

定义 $Gj=\sum{i \in Ij}g_i$，$H_j=\sum{i \in I_j}h_i$，则等式 (6) 可写为：

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

假设树的结构是固定的，即函数 $q(x)$ 确定，令函数的 $Obj^{(t)}$ 一阶导数等于0，即可求得叶子节点 $j$ 对应的值为：

$$w_j^*=-\frac{G_j}{H_j+\lambda} \tag 7$$

此时，目标函数的值为

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

综上，为了便于理解，单颗决策树的学习过程可以大致描述为：

1. 枚举所有可能的树结构 $q$
2. 用等式 (8) 为每个 $q$ 计算其对应的分数 $Obj$，分数越小说明对应的树结构越好
3. 根据上一步的结果，找到最佳的树结构，用等式 (7) 为树的每个叶子节点计算预测值

然而，可能的树结构数量是无穷的，所以实际上我们不可能枚举所有可能的树结构。通常情况下，我们采用贪心策略来生成决策树的每个节点。

1. 从深度为 0 的树开始，对每个叶节点枚举所有的可用特征
2. 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集
4. 回到第 1 步，递归执行到满足特定条件为止

在上述算法的第二步，样本排序的时间复杂度为 $O(n \log n)$，假设公用 $K$ 个特征，那么生成一颗深度为 $K$ 的树的时间复杂度为 $O(dKn\log n)$。具体实现可以进一步优化计算复杂度，比如可以缓存每个特征的排序结果等。

如何计算每次分裂的收益呢？假设当前节点记为 $C$，分裂之后左孩子节点记为 $L$，右孩子节点记为 $R$，则该分裂获得的收益定义为当前节点的目标函数值减去左右两个孩子节点的目标函数值之和：$Gain=Obj_C-Obj_L-Obj_R$，具体地，根据等式 (8) 可得：

$$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 \tag 9$$

其中，$-\gamma$ 项表示因为增加了树的复杂性（该分裂增加了一个叶子节点）带来的惩罚。

最后，总结一下 GBDT 的学习算法：

1. 算法每次迭代生成一颗新的决策树
2. 在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数 $g_i$ 和二阶导数 $h_i$
3. 通过贪心策略生成新的决策树，通过等式 (7) 计算每个叶节点对应的预测值
4. 把新生成的决策树 $f_t(x)$ 添加到模型中：$\hat{y}_i^t = \hat{y}_i^{t-1} + f_t(x_i)$

通常在第四步，我们把模型更新公式替换为：$\hat{y}_i^t = \hat{y}_i^{t-1} + \epsilon f_t(x_i)$，其中 $\epsilon$ 称之为步长或者学习率。增加 $\epsilon$ 因子的目的是为了避免模型过拟合。

关于 GBDT 的实际计算简单实例，可以参考我的另一篇文章：机器学习之分类与回归树(CART)

参考资料

• https://www.zybuluo.com/yxd/note/611571