机器学习 - 梯度提升树（GBDT）算法-回归任务 - 《机器学习》

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，从名字中我们可以看出来它是属于 Boosting 策略。GBDT 是被公认的泛化能力较强的算法。

1 思想

GBDT 由三个概念组成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和 Shrinkage（一个重要演变）
1.1 回归树（Regression Decision Tree）
CART算法用于分类任务时，树的分裂准则采用基尼指数，用于回归任务时，树的分裂用MSE（均方误差）。
对于分类树而言，其值加减无意义（如性别），而对于回归树而言，其值加减才是有意义的（如说年龄）。
由于在GBDT中拟合的目标是一个梯度值，这个值是连续值或者实值，所以GBDT中的树都是回归树。

回归树在分枝时会穷举每一个特征的每个阈值以找到最好的分割点，衡量标准是最小化均方误差（这里注意和GBDT损失函数区分开，GBDT回归任务损失函数为平方差损失，分类任务损失函数为对数损失。但是在寻找最好分割点时的衡量标准都是最小化均方误差，因为CART回归算法使用的是MSE）。
1.2 梯度迭代（Gradient Boosting）
上面说到 GBDT 的核心在于累加所有树的结果作为最终结果，GBDT 的每一棵树都是以之前树得到的残差来更新目标值，这样每一棵树的值加起来即为 GBDT 的预测值。
模型的预测值可以表示为：
梯度提升树（GBDT）算法-回归任务 - 图3
梯度提升树（GBDT）算法-回归任务 - 图4 为基模型与其权重的乘积，模型的训练目标是使预测值梯度提升树（GBDT）算法-回归任务 - 图5 逼近真实值 y，也就是说要让每个基模型的预测值逼近各自要预测的部分真实值。由于要同时考虑所有基模型，导致了整体模型的训练变成了一个非常复杂的问题。所以研究者们想到了一个贪心的解决手段：每次只训练一个基模型。那么，现在改写整体模型为迭代式：
梯度提升树（GBDT）算法-回归任务 - 图6
这样一来，每一轮迭代中，只要集中解决一个基模型的训练问题：使梯度提升树（GBDT）算法-回归任务 - 图7 逼近真实值梯度提升树（GBDT）算法-回归任务 - 图8 。
举个例子：比如说 A 用户年龄 20 岁，第一棵树预测 12 岁，那么残差就是 8，第二棵树用 8 来学习，假设其预测为 5，那么其残差即为 3，如此继续学习即可。
那么 Gradient 从何体现？其实很简单，其残差其实是最小均方损失函数关于预测值的反向梯度(划重点)：
梯度提升树（GBDT）算法-回归任务 - 图9
也就是说，预测值和实际值的残差与损失函数的负梯度相同。

补充知识：为什么拟合负梯度值

图片.png
但要注意，基于残差 GBDT 容易对异常值敏感，举例：
很明显后续的模型会对第 4 个值关注过多，这不是一种好的现象，所以一般回归类的损失函数会用绝对损失或者 Huber 损失函数来代替平方损失函数。

GBDT 的 Boosting 不同于 Adaboost 的 Boosting，GBDT 的每一步残差计算其实变相地增大了被分错样本的权重，而对与分对样本的权重趋于 0，这样后面的树就能专注于那些被分错的样本。
1.3 缩减（Shrinkage）
Shrinkage 的思想认为，每走一小步逐渐逼近结果的效果要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它并不是完全信任每一棵残差树。
梯度提升树（GBDT）算法-回归任务 - 图13
Shrinkage 不直接用残差修复误差，而是只修复一点点，把大步切成小步。本质上 Shrinkage 为每棵树设置了一个 weight，累加时要乘以这个 weight，当 weight 降低时，基模型数会配合增大。

2 优缺点

2.1 优点

可以自动进行特征组合，拟合非线性数据；
可以灵活处理各种类型的数据。

2.2 缺点

对异常点敏感。

3 与 Adaboost 的对比
3.1 相同：
都是 Boosting 家族成员，使用弱分类器；
都使用前向分布算法；

3.2 不同：

迭代思路不同：Adaboost 是通过提升错分数据点的权重来弥补模型的不足（利用错分样本），而 GBDT 是通过算梯度来弥补模型的不足（利用残差）；
损失函数不同：AdaBoost 采用的是指数损失，GBDT 使用的是绝对损失或者 Huber 损失函数；
GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
补充知识：为什么梯度负方向下降最快

图片.png

4. 对梯度提升算法的若干思考

（1）梯度提升与梯度下降的区别和联系是什么？
GBDT使用梯度提升算法作为训练方法，而在逻辑回归或者神经网络的训练过程中往往采用梯度下降作为训练方法，二者之间有什么联系和区别呢？
下表是梯度提升算法和梯度下降算法的对比情况。可以发现，两者都是在每一轮迭代中，利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新，只不过在梯度下降中，模型是以参数化形式表示，从而模型的更新等价于参数的更新。而在梯度提升中，模型并不需要进行参数化表示，而是直接定义在函数空间中，从而大大扩展了可以使用的模型种类。
图片.png

（2）梯度提升和提升树算法的区别和联系？
提升树利用加法模型与前向分歩算法实现学习的优化过程。当损失函数是平方误差损失函数和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。针对这一问题，Freidman提出了梯度提升（gradient boosting）算法。这是利用损失函数的负梯度在当前模型的值梯度提升树（GBDT）算法-回归任务 - 图21 作为提升树算法中残差的近似值，拟合一个梯度提升模型。
（3）梯度提升和GBDT的区别和联系？

采用决策树作为弱分类器的Gradient Boosting算法被称为GBDT，有时又被称为MART（Multiple Additive Regression Tree）。GBDT中使用的决策树通常为CART。
GBDT使用梯度提升（Gradient Boosting）作为训练方法。

（4）梯度提升算法包含哪些算法？
Gradient Boosting是Boosting中的一大类算法，其中包括：GBDT（Gradient Boosting Decision Tree）、XGBoost（eXtreme Gradient Boosting）、LightGBM （Light Gradient Boosting Machine）和CatBoost（Categorical Boosting）等。
（5）对于一般损失函数而言，为什么可以利用损失函数的负梯度在当前模型的值作为梯度提升算法中残差的近似值呢？
我们观察到在提升树算法中，残差梯度提升树（GBDT）算法-回归任务 - 图22 是损失函数梯度提升树（GBDT）算法-回归任务 - 图23 的负梯度方向，因此可以将其推广到其他不是平方误差(分类或是排序问题)的损失函数。也就是说，梯度提升算法是一种梯度下降算法，不同之处在于更改损失函数和求其负梯度就能将其推广。即，可以将结论推广为对于一般损失函数也可以利用损失函数的负梯度近似拟合残差。

5.GBDT回归算法实例

图片.png

其中J为叶子节点的数量，梯度提升树（GBDT）算法-回归任务 - 图26 表示各个叶子节点的值

（1）数据集介绍
训练集如下表所示，一组数据的特征有年龄和体重，身高为标签值，共有4组数据。

测试数据如下表所示，只有一组数据，年龄为25、体重为65，我们用在训练集训练好的GBDT模型预测该组数据的身高值为多少。

（2）模型训练阶段
参数设置：

学习率：learning_rate = 0.1
迭代次数：n_trees = 5
树的深度：max_depth = 3
1）初始化弱学习器：

损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，导数等于零，得到。

令导数等于0：

所以初始化时，取值为所有训练样本标签值的均值。，此时得到的初始化学习器为。
2）对于建立M棵分类回归树：
由于我们设置了迭代次数：n_trees=5，且设置了M=5。
首先计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差，也就是与上一轮得到的学习器的差值：

现将残差的计算结果列表如下：

上一轮预测结果的残差作为当前数据集的标签值训练弱学习器 F1(x) = y-F0(x) ，即下表数据：

接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征值为5开始，到体重特征为70结束，分别计算分裂后两组数据的平方损失（Square Error），梯度提升树（GBDT）算法-回归任务 - 图42 为左节点的平方损失，梯度提升树（GBDT）算法-回归任务 - 图43 为右节点的平方损失，找到使平方损失和梯度提升树（GBDT）算法-回归任务 - 图44 最小的那个划分节点，即为最佳划分节点。
例如：以年龄7为划分节点，将小于7的样本划分为到左节点，大于等于7的样本划分为右节点。左节点包括梯度提升树（GBDT）算法-回归任务 - 图45 ，右节点包括样本梯度提升树（GBDT）算法-回归任务 - 图46 ，梯度提升树（GBDT）算法-回归任务 - 图47 ，梯度提升树（GBDT）算法-回归任务 - 图48 ，梯度提升树（GBDT）算法-回归任务 - 图49 。

计算过程详解：损失计算过程与CART回归方法一样，当以年龄7划分时，R1={0}，R2={1，2，3}
c1 = 1/1(-0.375)= -0.375，c1即为R1的预测值，此时损失为0.
c2 = 1/3(-0.175+0.025+0.325) = 0.125，c2即为R2的预测值，
SEr = 1/3*[(0.125-(-0.175))^2+(0.125-0.025)^2+(0.125-0.325)^2] = 0.14

所有可能的划分情况如下表所示：
以上划分点的总平方损失最小为0.025有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选年龄21。现在我们的第一棵树长这个样子：

我们设置的参数中树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分：
对于左节点，只含有0,1两个样本，根据下表结果我们选择年龄7为划分点（也可以选体重30）。

对于右节点，只含有2,3两个样本，根据下表结果我们选择年龄30为划分点（也可以选体重70）。

现在我们的第一棵回归树长下面这个样子：

3）叶子节点的值即为

此时可更新强学习器，需要用到参数学习率：learning_rate=0.1，用梯度提升树（GBDT）算法-回归任务 - 图57 表示。
梯度提升树（GBDT）算法-回归任务 - 图58
为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上拟合值梯度提升树（GBDT）算法-回归任务 - 图59 ，即学习率为1，很容易一步学到位导致GBDT过拟合。
重复此步骤，直到 梯度提升树（GBDT）算法-回归任务 - 图60 结束，最后生成5棵树。
下面将展示每棵树最终的结构，这些图都是我GitHub上的代码生成的，感兴趣的同学可以去运行一下代码。https://github.com/Microstrong0305/WeChat-zhihu-csdnblog-code/tree/master/Ensemble%20Learning/GBDT_Regression
第一棵树：

第二棵树：

第三棵树：