一、模型介绍

提升树模型是以分类树或回归树为基本分类器的提升方法，其采用加法模型和前向分布算法。基于处理过程中所使用的损失函数的不同，我们有用平方误差损失函数的回归问题，使用指数损失函数的分类问题，以及一般损失函数的一般决策问题。

GDBT（Gradient Descent Boosting Tree），梯度提升树，是以回归树为基本分类器的提升方法。是一种基于残差的处理方法，常用来处理回归类问题。

提升树模型可以表示为决策树的加法模型：

$f_M(x) = \sum_{m=1}^MT(x;\Theta_m)$

其中，$ T(x;\Theta_m)$ 表示第m颗决策树，$ \Theta_m$ 表示决策树的参数，$ M$ 表示树的个数。

在GDBT中采用的损失函数为平方差损失函数：

$L(y,f(x)) = (y-f(x))^2$

1、算法思想

GBDT的前向分布算法为：

$\begin{equation} \begin{split} f_0(x) &= 0 \\ f_m(x) &= f_{m-1}(x)+T(x;\Theta_m),m=1,2,...,M \\ f_M(x) &= \sum_{m=1}^MT(x;\Theta_m) \end{split} \end{equation}$

在前向分布算法的第m步，给定当前模型$ f_{m-1}(X)$ ，我们要求解：

$\Theta_m = argmin_{\Theta} \sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))$

当我们采用平方误差损失函数是，我们要求求解的目标为：

$\begin{equation} \begin{split} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)) &= [y-f_{m-1}(x)-T(x;\Theta_m)]^2 \\ &= [r-T(x;\Theta_m)]^2 \\ \end{split} \end{equation}$

这里，我们记$ r=y-f_{m-1}(x)$ ，就是当前模型拟合数据的残差，所以，对于回归问题的提升树算法来说，我们只需要简单的拟合当前模型的残差就行。那么回归问题的提升树算法叙述如下：

首先初始化$ f_0(x)=0$ ，初始化第一个残差数据集$ r_i=y_i-f_0(x_i)$ （原数据集），根据原数据建立一颗回归树$ T(x;\Theta_0)$ ，根据回归树得到的结果，再次计算残差，将这次得到的残差作为下一颗回归树的数据集，得到回归树$ T(x;\Theta_m)$ ，并且更新$ f_m(x) = f_{m-1}(x)+T(x;\Theta_m)$ ，不断地迭代，我们就能够得到最终的集成模型：

2、GDBT对提升树的优化

上面我们所提到的其实只是提升树在回归问题的求解过程而已，并不是真正的GDBT，对于提升树而言，当损失函数是平方损失或指数损失函数时，每一步的优化是很简单的，但是对于一般的损失函数而言，他的优化过程就比较难，我们很难找到最优的$ \Theta_m$ ，此时，我们就是用梯度下降的近似方法来近似其最优解。修改后的算法过程如下：

首先初始化$ f_0(x) =c$ ，即初始化它为能够使损失函数最小的一个常数值。第二步，将损失函数的负梯度作为当前模型的值，将它作为残差的估计，拟合一个树。得到这棵树的叶节点区域$ R_{mj}$ ，之后利用线性搜索来估计叶节点区域的值$ c_{mj}$，使损失函数最小化（这一步的意思就是，给叶子节点分配合适的值，使得损失函数最小化）。然后更新回归树$ f_m(x)$ ，不断地迭代，直到输出最终模型。