本文介绍了提升树模型中的梯度提升树算法GBDT (Gradient Boosting Decision Tree) 。首先介绍了提升树通过拟合残差来提升学习器的设计思想。然后介绍了基于梯度提升的GBDT算法，核心在于学习器本身不再拟合残差，而是学习器拟合残差的一阶梯度，权重拟合残差的一阶系数。最后介绍了GBDT对应分类和回归场景的学习流程。
作者 | 文杰
编辑 | yuquanle
提升树
提升树GBDT同样基于最小化第个学习器和前个学习器累加起来损失函数最小，提升树采用残差的思想来最小化损失函数，将投票权重放到学习器上，使得基学习器的权重都为1。
GBDT将损失用一阶多项式拟合，基学习器拟合梯度，学习器的权重为一阶多项式的系数。
在前面的Adaboost中，我们需要学习个基学习器，赋予不同的权重组合得到最后的强学习器。它是基于个基学习器组合而成。而提升树中，直接将他们以“残差（损失函数的残差）”的形式累加起来，故也为加法模型，而且是逐步累加。
提升树模型如下：
其中，表示决策树，为决策树的参数，为树的个数。
提升树优化过程：
- 输入：训练集，损失函数
- 输出：提升树
- 初始化
- 对 2.1 计算残差: 2.2 拟合残差学习基学习器，训练集为 2.3 更新模型：
- 得到最终的强学习器:
可以看出，提升树本质与Adboost一致，也是最小化第个学习器和前个学习器组合的损失函数，不同的是提升树采用决策树作为基学习器，采用残差的思想使得每个决策树的投票权重为。
GBDT
GBDT是基学习器采用的Decision Tree的Gradient Boosting方法。Gradient Boosting模型与Adaboost的形式一致，采用个基学习器的线性组合得到最终模型：
首先确定初始模型，定义初始基学习器，当模型迭代到第步时：
通过最小化损失来确定参数θ的值：
这里有两种理解Gradient Boosting的方式，从优化角度可以理解是采用梯度下降算法，表示负梯度方向，为步长。从模型角度我们可以理解为损失函数一阶多项式展开，而表示一阶信息，为系数。
优化角度，保证损失函数在递减：
为了使得损失函数不断减少，即梯度下降：
将代入上式有：
所以Gradient Boosting 的算法流程如下：
- 输入：训练集，损失函数
- 输出：
- 初始化；
- 对： 2.1 计算梯度: 2.2 拟合梯度学习基学习器，训练集为； 2.3 根据梯度下降算法，计算学习器: 2.4 更新模型：
- 得到最终的强学习器：
可以看出Gradient Boosting 是一个不断基于残差弥补的模型，目标不断地减少Bais，而没有关注Variance。它不像随机森林的集成引入随机性减少Variance的思想。
下面考虑决策树为基学习器的Gradient Boosting的方法GBDT，其在GB基础上有两点值得一提：
- GBDT，采用决策树作为基函数将样本划分到固定数目个决策区间；
- 在决策树中决策函数采用指示函数，梯度与步长的积直接放到上。
下面给出GBDT回归和分类两个问题的算法流程
GBDT 回归
- 输入：训练集，，损失函数
- 输出：
- 初始时给出一个最优的偏置常数，：
- 对
a）计算梯度:
b）拟合梯度学习一个回归树，产生个决策区间；
c）对于决策区间，计算:
d）更新模型：
- 得到最终的强学习器：
GBDT分类
考虑分类问题，采用Softmax思想，将类映射到维。第个决策树的决策第维的值为，对输出进行Softmax归一化，可以得到类的概率为，类的概率和，分类损失函数采用交叉熵损失。
似然函数为：
对数损失函数为：
由于Softmax将分类映射到维，对应的基分类器和损失函数都是维。因此算法流程中负梯度方向也是一个维向量。
算法流程：
- 输入：训练集，，损失函数
- 输出：
- 初始时
- 对 2.1 对决策树进行Softmax归一化: 2.2 对: 2.2.1 计算梯度: 2.2.2 拟合梯度学习第个决策树在第维产生的个决策区间: 2.2.3 计算第颗树第维在区间的参数: 2.2.4 更新模型：
- 得到最终的强学习器：
GBDT到此，可以看出Boosting的这些方法，都是前向分步加法模型，分类回归采用不同的损失函数，加法模型都是考虑学习模型来不断地减小损失函数，即第个模型的学习是基于前个模型组合起来最小化损失函数。
Adboost是基于最小化损失函数在导数为处取到，针对二分类问题导出样本系数，决策器权重系数，决策树。
提升树是基于残差思想最小化损失函数，使得决策树的权重为。GBDT采用一阶多项式来拟合残差，进而导出梯度提升的思想。GBDT中存在冗余项，在GBDT中用决策树拟合梯度，来确定步长。
The End
