梯度提升和梯度下降的区别（梯度下降与梯度上升）

梯度提升决策树（GBDT）由于准确率高、训练快速等优点，被广泛应用到分类、回归合排序问题中。该算法是一种additive树模型，每棵树学习之前additive树模型的残差。许多研究者相继提出XGBoost、LightGBM等，又进一步提升了GBDT的性能。

以决策树为基函数的提升方法称为提升树，其决策树可以是分类树或者回归树。决策树模型可以表示为决策树的加法模型。
$梯度下降决策树梯度提升决策树简介_机器学习$
其中， $梯度下降决策树梯度提升决策树简介_GBDT_02$ 表示决策树， $梯度下降决策树梯度提升决策树简介_提升树_03$ 表示树的参数， $梯度下降决策树梯度提升决策树简介_GBDT_04$ 为树的个数。

针对不同问题的提升树算法主要区别在于损失函数的不同。对于回归问题，使用的是平方损失函数；对于分类问题，使用的是指数损失函数；对二分类问题，提升树算法只需将AdaBoost的基分类器设置为二分类树即可，此时的提升树算法是AdaBoost算法的一个特例。以下主要关注回归问题的提升树算法。

对于回归问题的提升树算法，每一步拟合的是前一步的残差，具体为什么拟合的是残差看下面推导：
$梯度下降决策树梯度提升决策树简介_梯度下降决策树_05$
其中 $梯度下降决策树梯度提升决策树简介_机器学习_06$

回归问题中的提升树算法如下：

输入：训练数据集 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_07$ 其中$x_{i} in X subseteq R^{n} $梯度下降决策树梯度提升决策树简介_梯度下降决策树_08$

输出：提升树 $梯度下降决策树梯度提升决策树简介_机器学习_09$

初始化 $梯度下降决策树梯度提升决策树简介_GBDT_10$
对 $梯度下降决策树梯度提升决策树简介_机器学习_11$

计算每个数据的残差：

$梯度下降决策树梯度提升决策树简介_GBDT_12$

拟合残差学习一颗回归树，得到 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_13$
更新 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_13$

得到回归问题提升树
$梯度下降决策树梯度提升决策树简介_GBDT_15$

得到一颗提升树后，可以对输入数据进行预测。假设得到两棵树，下图给出预测过程：

梯度下降决策树梯度提升决策树简介_GBDT_16

梯度提升的思想借鉴与梯度下降法，回顾梯度下降法，对于优化问题：
$梯度下降决策树梯度提升决策树简介_梯度提升_17$
使用梯度下降法求解的基本步骤：

随机选择一个初始点 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_18$
重复以下过程：

求负梯度： $梯度下降决策树梯度提升决策树简介_机器学习_19$
选择步长 $梯度下降决策树梯度提升决策树简介_GBDT_20$
更新参数： $梯度下降决策树梯度提升决策树简介_梯度提升_21$

直到满足终止条件

由以上过程可以看出，对于最终的最优解 $梯度下降决策树梯度提升决策树简介_梯度提升_22$ ，是由初始值 $梯度下降决策树梯度提升决策树简介_机器学习_23$ 经过M次迭代后得到的。设 $梯度下降决策树梯度提升决策树简介_提升树_24$ ，则 $梯度下降决策树梯度提升决策树简介_梯度提升_22$ 为：
$梯度下降决策树梯度提升决策树简介_提升树_26$
在函数空间中，我们也可以借鉴梯度下降的思想，进行最优函数的搜索。关键是利用损失函数的负梯度在当前模型的值
$梯度下降决策树梯度提升决策树简介_机器学习_27$
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

对于模型的损失函数 $梯度下降决策树梯度提升决策树简介_机器学习_28$ ，为了能够求解出最优的函数 $梯度下降决策树梯度提升决策树简介_机器学习_29$ ，首先设置初始值为：
$梯度下降决策树梯度提升决策树简介_梯度下降决策树_30$
以函数 $梯度下降决策树梯度提升决策树简介_GBDT_31$ 为一个整体，与梯度下降法的更新过程一致，假设经过M代，得到最优的函数 $梯度下降决策树梯度提升决策树简介_机器学习_29$ 为：
$梯度下降决策树梯度提升决策树简介_提升树_33$
其中 $梯度下降决策树梯度提升决策树简介_梯度提升_34$ 为：
$梯度下降决策树梯度提升决策树简介_梯度提升_35$
可以看到这里梯度变量是一个函数，是在函数空间上求解；而以往的梯度下降是在N维的参数空间负梯度方向，变量是参数。在梯度提升中，这里变量是函数，通过当前函数的负梯度方向更新函数以修正模型，最后累加的模型近似最优函数。

GBDT的负梯度为什么近似于提升树的残差

对于损失函数 $梯度下降决策树梯度提升决策树简介_梯度提升_36$ ，我们将 $梯度下降决策树梯度提升决策树简介_机器学习_37$ 而不是 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_38$ 作为自变量。根据梯度下降定义，可以得到损失函数参数的更新公式：
$梯度下降决策树梯度提升决策树简介_GBDT_39$
同时提升树的定义为： $梯度下降决策树梯度提升决策树简介_梯度提升_40$ ，决策树拟合的值等于负梯度，为残差。

了解了GBDT的两个部分（提升树和梯度提升）后，我们以回归树为例，基模型为CART回归树，得到GBDT的实现思路如下

输入：训练数据集 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_07$ ，其中其中$x_{i} in X subseteq R^{n} $梯度下降决策树梯度提升决策树简介_梯度下降决策树_08$

输出：提升树 $梯度下降决策树梯度提升决策树简介_机器学习_09$

初始化 $梯度下降决策树梯度提升决策树简介_提升树_44$
对 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_45$

计算每个数据： $梯度下降决策树梯度提升决策树简介_梯度下降决策树_46$
拟合 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_47$ 学习一棵回归树，得到 $梯度下降决策树梯度提升决策树简介_梯度提升_48$ 。更详细一点，得到第 $梯度下降决策树梯度提升决策树简介_GBDT_49$ 棵树的叶节点区域 $梯度下降决策树梯度提升决策树简介_梯度下降决策树_50$ ，即一颗由 $梯度下降决策树梯度提升决策树简介_提升树_51$
计算每个区域的最优输出：
$梯度下降决策树梯度提升决策树简介_GBDT_52$
更新
$梯度下降决策树梯度提升决策树简介_梯度下降决策树_53$
得到回归问题梯度提升树
$梯度下降决策树梯度提升决策树简介_提升树_54$