XGboost原理基础之梯度提升树

胖友们好，有好一段时间没有更新了。之前写了两篇的内容，表达了一些粗浅的理解，其实主要也是想跟大家探讨互相学习。上次也有胖友反映第一篇文章，回归树那部分能不能讲得更深入点？后面我们也考虑过原理方面比较多，希望每部分讲得细一点，所以这次的文章先讲比较重要的点，梯度提升树和梯度提升树和的关系。

从提升方法到梯度提升树

我们先从GBDT中的梯度提升树原理讲起，讲到梯度提升树就先从提升树开始讲起。提升树起源于提升方法，什么是提升方法呢？参考李航的《统计学习方法》，首先是有强可学习和弱可学习的概念。强可学习的意思是，如果一个概念即我们建模的对象，可以有一个正确率很高很强的模型去学习它，那么它就是强可学习的。如果这个概念只能通过一个仅比随即猜测略好的模型去学习它，那么它就是弱可学习。事实上，已经证明，可以通过提升方法去把弱可学习模型提升为强可学习模型。很当然地，求一个比较即弱分类器要比求一个强分类器容易得多。提升方法就是不断学习弱学习器，最后把这些学习器组合成强学习器。提升树就是是以分类树或者回归树为基分类器的一种提升方法。假设有n个训练样本，特征为X，分类标签为y，最初的弱分类器为F(X),那么对任意一个样本，残差ri=yi-F(Xi)。那么下一轮拟合的目标就不是y而是残差ri，拟合完ri得到h(X)。从刚才的过程看，我们现在应该比较清楚，提升树拟合的其实必须是回归树。现在我们希望在数学上把它推广一下，我们可以不可以不拟合残差，因为如果损失函数比较复杂，继续用残差拟合是不合适的。所以针对其他的损失函数，参考梯度下降法，提出了梯度提升决策树模型，把残差推广为上一轮损失函数的负梯度，而残差其实是上一轮损失函数的负梯度的特例。下图来自于书本统计学习基础，可以看出当损失函数为均方误差时，损失函数的负梯度就是残差。它的算法流程如下：

1.初始化一棵树，使F0等于y的平均值。因为要估计使损失函数极小化的常数值，那么这个常数值即F0等于y的平均值，就最小了。

2.计算上一轮损失函数的负梯度，作为残差的估计。

3.拟合上一轮损失函数的负梯度。

4.更新回归树知道误差减少到约定阈值。

梯度提升树与梯度下降法

有胖友会问，之前我们写的一篇文章提到的梯度下降法跟这种梯度提升树算法很像，区别是怎样的？其实应该说，我们理解的是梯度提升树算法借鉴了梯度下降法的思想，但它们有这些区别：提升方法包括这里提到的梯度提升树是加法模型，包含了多个分类器，适用于决策树这种包含非常多参数的非参数模型。而梯度下降法是只有一个模型，整个过程变化的是里面的参数，不像梯度提升树是多个分类器累加的过程。

从GBDT到

讲了那么多，梯度提升树其实就是我们经常听到的算法GBDT，而实际上是借鉴了梯度提升法的思想。但两者的拟合目标应该是不一样的，GBDT拟合上一轮损失函数的负梯度

拟合的直接就是当前一轮损失函数，但是作了泰勒展开。下面是陈天奇大神课件的一部分，目标函数先不看正则化的部分，第t轮的目标就是拟合第t轮的损失函数，然后我们发现也是加法模型，当前轮的模型是上一轮模型加上这次拟合的基分类器。先解释下图，看图里面的泰勒展开式，把

当成

，把

当成

就得到：

，

其实聪明的胖友们就看到，我们已经得到上一轮的模型，关键就是求当前这一轮的基分类器

。先去掉常数项

，那么目标函数就变成

这次我们先不讨论模型复杂度

，只先知道

，

那么得到，

把每个样本都分组到每个叶子节点得到

，因为肯定有多个样本分到同一个叶子节点，这里解释一下

是什么回事？q代表样所在叶子的序列号，看下图得到：

，看下图输出结果

就可以看到

这个结果了。

下面开始求，陈天奇大神说让我们定义：

，可得：

延续上一步，要求极小值，根据以下过程，得到：

，就是我们要求的基分类器。

所以小结一下，本次文章主要讲了提升方法，从提升方法又衍生得到提升树，提升树又推广得到梯度提升树，而又存在与梯度提升树的联系与区别。