一、如何在不改变原有模型的结构上提升模型的拟合能力

假设现在有样本集，然后用一个模型，用去拟合这些数据，使得这批样本的平凡损失函数（即）最小。但是你发现虽然模型的拟合效果很好，但仍然有一些差距，比如预测值，而真实值等等。另外不允许更改原来模型的参数，那么有什么办法进一步提高模型的拟合能力？
既然不能更改原来模型的参数，就意味着必须在原来模型的基础上做改善，直观的做法就是建立一个新的模型来拟合未完全拟合真是样本的残差，即。所以对于每个样本来说，拟合的样本集就变成了：


图1. GBDT提出原因

二、基于残差的GBDT

在第一部分，被称为残差，这一部分也就是前一模型未能完全拟合的部分，所以交给新的模型来完成。
我们知道GBDT的全称是Gradient Boosting Decision Tree，其中Gradient是梯度，更一般的理解，可以认为是一阶导。这里的梯度和残差是什么关系呢？在第一部分，我们提到了一个叫做平方损失函数的东西，其具体形式为，熟悉其他算法的原理应该知道，这个损失函数主要针对回归类型的问题，分类则是用熵值类的损失函数。具体到平方损失函数的例子，它的一阶导数其实就是残差的形式，所以基于残差的GBDT是一种特殊的GBDT模型，它的损失函数是平方损失函数，常用来处理回归类的问题。具体形式可以如下表示：

损失函数的一阶导：

正好残差就是损失函数一阶导的负数，即负的梯度

三、为什么基于残差的GBDT不是一个好的选择

基于残差的GBDT在解决回归问题上不算是一个好的选择，一个比较明显的缺点就是对于异常值过于敏感。通过下面的例子来看一下：

图2. 残差过大的例子
很明显后续的模型会对第4个关注过多，这不是一个好的现象，所以一般会归类的损失函数会用绝对损失或者Huber损失函数来代替平方损失函数：

• 绝对值损失(Absolute loss)，对噪声更加稳定

• Huber损失函数，对噪声更加稳定

下面看一下他们的损失对比：

图3. 损失函数对比

四、Boosting的加法模型

如前面所述，GBDT模型可以认为是由个基模型组成的一个加法运算式：

其中是指所有基模型组成的函数空间。
那么一般化的损失函数是预测值与真实值之间的关系，如我们前面的平方损失函数，那么对于个样本来说，则可以写成：

更一般的，我们知道一个好的模型，在偏差和方差上有一个较好的平衡，而算法的损失函数正式代表了模型的偏差面，最小化损失函数，就相当于最小化模型的偏差，但平时我们也需要兼顾模型的方差，所以目标函数还包括模型复杂度的正则项，因此目标函数可以写成：

其中代表了基模型的复杂度，若基模型是树模型，则树的深度、叶子节点数等指标可以反映树的复杂程度。
对于Boosting来说，它采用的是前向优化算法，及从前往后，逐渐建立基模型来优化逼近目标函数，具体过程如下：

那么，在每一步，如何学习一个新的模型呢？答案的关键还是在于GBDT的目标函数上，即新模型的加入总是以优化目标函数为目的的。
我们以第步的模型拟合为例，在这一步，模型对个样本的预测为：

其中，就是我们这次需要加入的新模型，即需要拟合的模型，此时，目标函数就可以写为：

即此时最优化目标函数，就相当于求得了

五、什么是GBDT的目标函数

我们知道在泰勒公式中，若很小时，我们只保留二阶导是合理的(GBDT是一阶导，xgBoost是二阶导，我们以二阶导为例，一阶导可以自己推一下)，即：

我们将公式(11)中的看成是公式(12)中的，看成是，因此公式(11)可以写成：

其中为损失函数的一阶导数，为损失函数的二阶导数，注意这里的导数是对求导。我们以平方损失函数为例：，则

由于在第步 其实是一个已知的值，所以 是一个常数，其对函数优化不会产生影响，因此，公式(15)可以写成：

所以我么只要求出每一步损失函数的一阶和二阶导的值（由于前一步的 是已知的，所以这两个值就是常数）代入公式(16)，然后最优化目标函数，就可以得到每一步的 ，最后根据加法模型得到一个整体模型。

六、如何用决策树来表示上一步的目标函数

假设我们boosting的基模型用决策树来实现，则一颗生成好的决策树，即结构确定，也就是说树的叶子结点其实是确定了的。假设这棵树的叶子结点有 片叶子，而每片叶子对应的值 。熟悉决策树的同学应该清楚，每一片叶子结点中样本的预测值都会是一样的，在分类问题中，是某一类，在回归问题中，是某一个值（在gbdt中都是回归树，即分类问题转化成对概率的回归了），那么肯定存在这样一个函数
即将 中的每个样本映射到每一个叶子结点上，当然 和 我们都是不知道的，但我们也不关心，这里只是说明一下决策树表达数据结构的方法是怎么样的，不理解也没有问题。
那么 就可以转成 ，这里的 代表了每个样本在哪个叶子结点上，而 则代表了哪个叶子结点取什么 值，所以 就代表了每个样本的取值 （即预测值）。
如果决策树的复杂度可以由正则项来定义 ，即决策树模型的复杂度由生成的树的叶子节点数量和叶子节点对应的值向量的L范数决定。

我们假设 为第 个叶子节点的样本集合，则公式(16)根据上面的一些变换可以写成：

即我们之前样本的集合，现在都改写成叶子结点的集合，由于一个叶子结点有多个样本存在，因此才有了和 这两项。
定义则公式(18)可以写成：

如果树的结构是固定的，即是确定的，或者说我们已经知道了每个叶子结点有哪些样本，所以和是确定的，但不确定（ 其实就是我们需要预测的值），那么令目标函数一阶导为0，则可以求得叶子结点对应的值：

目标函数的值可以化简为：

七、如何最优化目标函数

那么对于单棵决策树，一种理想的优化状态就是枚举所有可能的树结构，因此过程如下：

1. 首先枚举所有可能的树结构，即；
2. 计算每种树结构下的目标函数值，即公式(21)的值；
3. 取目标函数最小（大）值为最佳的数结构，根据公式(20)求得每个叶子节点的 取值，即样本的预测值。

但上面的方法肯定是不可行的，因为树的结构千千万，所以一般用贪心策略来优化：

1. 从深度为0的树开始，对每个叶节点枚举所有的可用特征
2. 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集
4. 回到第1步，递归执行到满足特定条件为止

那么如何计算上面的收益呢，很简单，仍然紧扣目标函数就可以了。假设我们在某一节点上二分裂成两个节点，分别是左（L）右（R），则分列前的目标函数是，分裂后则是，则对于目标函数来说，分裂后的收益是（这里假设是最小化目标函数，所以用分裂前-分裂后）：

公式(22)计算出来的收益，也是作为变量重要度输出的重要依据。
所以gbdt的算法可以总结为：

1. 算法在拟合的每一步都新生成一颗决策树；
2. 在拟合这棵树之前，需要计算损失函数在每个样本上的一阶导和二阶导，即 和 ；
3. 通过上面的贪心策略生成一颗树，计算每个叶子结点的的 和 ，利用公式(20)计算预测值 ；
4. 把新生成的决策树 加入，其中为学习率，主要为了抑制模型的过拟合。

   八、参考链接

   参考链接1：机器学习-一文理解GBDT的原理-20171001