(四) 梯度提升

1. 如何学习

目标函数： $Obj = \sum_{i=1}^{n}l(y_i, \hat{y_i}) + \sum_{k=1}^{K}\Omega(f_k)，f_k\in \mathcal{F}$

此时，我们不能使用诸如SGD（随机梯度下降）的方法，去得到f。因为它们是多颗树，而非数值向量。

解决方法：加法训练 Additive Training (Boosting) ，即，从常量开始，每次增加一个新函数。

该过程如下图所示，每轮在上一轮的基础上，累加一颗树，直至t轮共累加K颗树为止。

加法训练 Additive Training 过程

2. 加法训练 Additive Training

如何决定每轮增加的f：
以优化目标函数为导向。即，选取一个f，使得目标函数尽可能大地降低。

详细说明如下：

t轮的预测值为： $\hat{y_i}^{(t)} = \hat{y_i}^{(t-1)} + f_t(x_i)$ ，那么t轮的目标函数可化简为：

其中，为t轮中需要决定的f，以最小化目标函数。

假设损失函数为平方损失，那么，目标函数可进一步表示为：

3. 损失的泰勒展开近似

t轮的目标函数为： $Obj = \sum_{i=1}^{n}l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i)) + \Omega(f_k)+constant$

若损失函数为更加一般的形式（非平方损失），计算较为复杂。因此，利用泰勒展开式来近似化简。

泰勒展开式：

定义：

那么，t轮的目标函数可近似为：

4. 新的目标函数

不考虑常数项，从上一节的泰勒展开近似，可得t轮新的目标函数为：

为何简化目标函数，而非纯粹进行树的累加：
从理论的角度，更加明确学习、收敛的部分。
从工程的角度，囊括监督学习的所有成分。
$g_i$ 和 $h_i$ 用来定义损失函数，使得机器学习工具的实现可以更为通用。

5. 提炼树的定义

我们通过「叶节点评分构成的向量」和「能将实例映射到叶节点的叶节点索引映射函数」来定义树，前者为叶节点的权重序列，后者为树的结构。公式为： $f_t(x) = w_{q(x)}$ 。

以下图为例，该颗树的定义包含两部分：
一是，由w1=+2、w2=0.1、w3=-1三个叶节点的评分构成的向量；
二是，表示树结构的，叶节点索引映射函数 $q(x)$ 。对于单个实例而言，将“男生”映射到叶节点1。

树的定义

6. 定义一颗树的复杂度

我们可以通过如下公式，来定义一颗树的复杂度：
$\Omega(f_t) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_j^2$

其中， $\Omega$ 为树的复杂度， $T$ 为叶节点数量， $\sum_{j=1}^Tw_j^2$ 为叶节点评分的第二范数。
值得注意的是，以上并非唯一的定义方式。

如下图所示，该颗树共有三个叶节点，每个叶节点有相应的评分。因此，可代入上述公式，求得树的复杂度。

树的复杂度

7. 新的目标函数

从第4小节可知，若不考虑常数项，t轮的目标函数可近似为：

其中，

代入第5小节、第6小节中，树的定义公式和树的复杂度公式，目标函数可进一步化为：

若将叶节点 $j$ 的实例定义为： $I_j = \{i|q(x_i) = j\}$ （即，所有能通过叶节点索引映射函数q(x)映射到叶节点 $j$ 的，实例 $i$ 的集合 $I$ 。），那么，目标函数可进一步化为：

因此，目标函数可理解为， T个独立的二次函数的和。

8. 结构分

定义：
$G_j = \Sigma_{i\in I_j}\ g_i$

$H_j = \Sigma_{i\in I_j}\ h_i$

则，目标函数可进一步化为：

假设树的结构 $q(x)$ 是固定的，求目标函数的最小值，即为：求二次函数 $G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2$ 的最小值。

已知，对于单变量的二次函数而言： $H>0$ 时，使得二次函数 $Gx+\frac{1}{2}Hx^2$ 最小的 $x$ 等于 $-\frac{G}{H}$ ，此时，该二次函数的值为 $-\frac{1}{2}\frac{G^2}{H}$ 。即，有如下表示：

$argmin_x\ Gx + \frac{1}{2}Hx^2= -\frac{G}{H}，H > 0$

$min_x\ Gx + \frac{1}{2}Hx^2 = -\frac{1}{2} \frac{G^2}{H}$

那么类似地，有使得上述目标函数达到最小的权重：

$w^{\ast}_{j} = -\frac{G_j}{H_j + \lambda}$

此时，目标函数的最小值为：

$Obj = -\frac{1}{2}\sum_{j=1}^{T}\frac{G^2_j}{H_j + \lambda} + \gamma T$

具体举例如下：

其中， $I_1 = \{1 \}$ 表示：同时满足「年龄<15」和「性别为男」两个条件，分到叶节点1的实例，仅包含实例索引为1的“男孩”。

最终，目标函数的值越小，表示该树结构越好。

9. 单棵树的搜索算法

从第8小节的内容，可将单颗树的搜索算法概括如下：
1）枚举所有可能的树结构 $q(x)$
2）利用公式，计算固定树结构 $q(x)$ 下的结构分：
$Obj = -\frac{1}{2}\sum_{j=1}^{T}\frac{G^2_j}{H_j + \lambda} + \gamma T$

3）找到最优的树结构，使用最优的叶节点权重：
$w^{\ast}_{j} = -\frac{G_j}{H_j + \lambda}$

问题：可能的树结构有无限多个。

10. 树的贪心学习

鉴于第9小节所述「可能的树结构有无限多个，无法全部枚举」的局限性，实际中，树的生长采用贪心算法：
1）从深度为 0 的树开始
2）对于树的每一个叶节点，尝试增加一个分裂点。增加分裂点后，目标函数值的变化，即增益为：

那么，此时的问题是：如何找到最佳的分裂点？

11. 有效查找最佳分裂点

对于分裂规则 $x_j < a$ 而言，什么是分裂后的增益？
假如 $x_j$ 表示年龄，则有下图：

其中，左子树包含年龄小于a的“男孩”和“女孩”，分别对应实例索引1和4；右子树包含年龄大于等于a的“妈妈”、“爷爷”和“奶奶”，分别对应实例索引2、3和5。

因此，可分别求得左子树的一阶导数之和 $G_L$ 、二阶导数之和 $H_L$ ，以及右子树的一阶导数之和 $G_R$ 、二阶导数之和 $H_R$ ，从而代入第10小节的增益公式，得到Gain。

对于某个特征而言，对已排序的实例进行从左至右的线性扫描，能够决定最佳的分裂点。

12. 分裂点查找算法

从第11小节的内容，可将分裂点的查找算法，概括如下：
对于每一个叶节点，枚举所有的特征：
1）对于每一个特征，依据特征值，对所有实例排序
2）使用线性扫描来决定，该特征的最佳分裂点
3）使得所有特征，各自按照最佳分裂点进行分裂

13. 类别变量的处理

一些树的学习算法，是分开处理类别变量和数值变量的。
而xgboost，可以简单地使用之前推导的公式，计算基于类别变量的分裂分数，即，不必分开处理类别变量。

对于类别变量，我们可以使用独热编码（one-hot encoding），将类别变量编码为数值向量，即，分配一个维度为类别数量的向量：

$z_j = \begin{cases}0& \text{如果x在类别j中}\\1& \text{否则}\end{cases}$

若有很多类别变量，这个数值向量将是稀疏的，而xgboost学习算法是偏爱处理稀疏数据的。

14. 剪枝和正则化

鉴于增益的公式为：
$Gain = [\frac{G^2_L}{H_L + \lambda} + \frac{G^2_R}{H_R + \lambda} - \frac{(G_L+G_R)^2}{H_L + H_R + \lambda}] - \gamma$

其中，中括号内的部分，为训练损失的减少量； $\gamma$ 为正则化项。

若前者小于后者，分裂后的增益为负。
因此，需要在树的简化度（simplicity）和预测性能（predictiveness）之间进行权衡。

提前终止（Pre-stopping）：
若最佳分裂产生的增益为负，那么停止分裂。
但是，当前的一个分裂可能对未来的分裂有益。

后剪枝（Post-Prunning）：
生长一棵树到最大深度，再递归地修剪所有具有负增益的叶子分裂节点。

15. 回顾：树提升算法

1）每一轮迭代增加一颗新的树
2）每一轮迭代开始时，计算一阶导数 $g_i$ 和二阶导数 $h_i$ ：
$g_i = \partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})$

$h_i = \partial^2_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})$

3）贪心生长一颗树 $f_t(x)$ ：
$Obj = -\frac{1}{2}\sum_{j=1}^{T}\frac{G^2_j}{H_j + \lambda} + \gamma T$

4）添加树 $f_t(x)$ 至模型： $\hat{y_i}^{(t)} = \hat{y_i}^{(t-1)} + f_t(x)$

通常，实际令 ${y_i}^{(t)} = {y_i}^{(t-1)} + \epsilon f_t(x_i)$ 。
其中， $\epsilon$ 称为步长（step-size）或缩减系数（shrinkage），通常设置为 0.1左右。
这意味着，在每一步我们并不做完全优化，而是给未来的轮次保留机会，有助于防止过拟合。

Introduction to Boosted Trees: Tianqi Chen