原文链接

GBDT算法综述

GBDT的全称为(Gradient Boosting Decision Tree)，是一种广泛应用于分类、回归和推荐系统中排序任务的机器学习算法，属于Boosting算法族。GBDT中的树都是回归树而不是分类树，GBDT的迭代更新过程即不断缩小残差的过程。

Boosting加法模型和前向分布算法

令输入空间是，输出空间是，不妨假设含有m个数据样本

其中。GBDT算法的假设函数可以看成是由棵树组合而成的加法模型：

其中，为所有树组合而成的函数空间，该模型的待求决策树函数为：，因此可以定义上述加法模型的目标函数为：，通过前向分布算法来优化该目标函数：

所以，迭代更新到第步时，目标函数可改写为：

最优化即可求得该轮需要学习的决策树函数。

Gradient Boosting算法

Gradient Boosting以负梯度代替残差来求解，对于任意可导函数来说，总是存在如下关系：

Gradient Boosting算法利用损失函数的负梯度在当前模型的值作为之前残差的近似值来拟合回归树

泰勒公式： 设是一个正整数，如果定义在包含的区间上的函数在点处次可到，那么对于这个区间上的任意都有： 等号右边的多项式称为函数在处的泰勒展开式，是泰勒公式的余项，且是的高阶无穷小。

为了求在处的一阶展开，不妨先对在处进行一阶展开可得：

令式子(6)中的，且记为，则有：

故最终目标函数形式为

XGBoost算法

XGBoost算法是GBDT算法的改进版本，其目标函数为

同理为了求损失函数在处的二阶展开，不妨先对在处进行二阶展开可得：

令式子(10)中的，和则有：

又因为在第步其实是已知的，所以是一个常数函数，故对优化目标函数不会产生影响，将上述结论带入目标函数即可得到：

优化目标函数

以XGBoost算法的目标函数为例，对于任意决策树，假设其叶子节点个数，该决策树是由所有节点对应的值组成的向量，以及能够把特征向量映射到叶子节点的函数构造而成的，且每个样本数据都存在唯一的叶子节点上，因此决策树可以定义为。决策树的复杂度可以由正则项来定义，该正则表达项表明决策树模型的复杂度可以由叶子结点的数量和叶子结点对应值向量的范数来定。定义集合为划分到叶子结点的所有训练样本的集合，即之前训练样本的集合，现在都改写成叶子结点的集合，因此XGBoost算法的目标函数可以改写为：

令，则有

分析可知当更新到第步时，此时决策树结构固定的情况下，每个叶子结点有哪些样本是已知的，那么和也是已知的；又因为和是第步的导数，那么也是已知的，因此和都是已知的。令目标函数的一阶导数为，即可求得叶子节点对应的值为：

因此针对于结构固定的决策树，最优的目标函数为：

上面的推导是建立在决策树结构固定的情况下，然而决策树结构数量是无穷的，所以实际上并不能穷举所有可能的决策树结构，什么样的决策树结构是最优的呢？通常使用贪心策略来生成决策树的每个结点， XGBoosting算法的在决策树的生成阶段就对过拟合的问题进行了处理，因此无需独立的剪枝阶段，具体步骤可以归纳为：

1. 从深度为0的树开始对每个叶子结点穷举所有的可用特征；
2. 针对每一个特征，把属于该结点的训练样本的该特征升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并采用最佳分裂点时的收益；
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该结点生成出左右两个新的叶子结点，并为每个新结点关联新的样本集；
4. 退回到第一步，继续递归操作直到满足特定条件。

因为对某个结点采取的是二分策略，分别对应左子结点和右子结点，除了当前待处理的结点，其他结点对应的 值都不变，所以对于收益的计算只需要考虑当前结点的 值即可，分裂前针对该结点的最优目标函数为：

分裂后的最优目标函数为：

那么对于该目标函数来说，分裂后的收益为：

故可以用上述公式来决定最有分裂特征和最优特征分裂点。