浅谈 GBDT

在 Xgboost 那篇文章 (Kaggle 神器 xgboost) 中提到了 Gradient Boosted Decision Trees，今天来仔细看看 GBDT。

本文结构：

• 什么是 GBDT ？
• GBDT 与 Adaboost 的区别与联系是什么 ？
• GBDT 与 Xgboost 的区别是什么？

什么是 GBDT？

GBDT（Gradient Boosting Decision Tree，梯度提升决策树），由名字可以看出涉及到三点：

1. 首先是 Boosting：

前面写过一篇 Adaboost 算法，里面简单介绍了 Boosting 的思想:

给定初始训练数据，由此训练出第一个基学习器；
根据基学习器的表现对样本进行调整，在之前学习器做错的样本上投入更多关注；
用调整后的样本，训练下一个基学习器；
重复上述过程 T 次，将 T 个学习器加权结合。

简单讲，就是每次训练单个弱学习器时，都将上一次分错的数据权重提高一点再进行当前单个弱学习器的学习。这样越往后执行，训练出的单个弱学习器就会越在意那些容易分错（权重高）的点。当执行 M 次后，通过加权求和的方式组合成一个最终的学习器。

2. 接着是 Gradient Boosting：

Gradient boosting 是 boosting 的其中一种方法，它主要的思想是，每一次建立单个学习器时，是在之前建立的模型的损失函数的梯度下降方向。

我们知道损失函数(loss function)越大，说明模型越容易出错，如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。

接下来看算法具体细节：

最终模型 F 是多个弱学习器的加权组合：

整体损失函数，其中 P 为模型的参数：

我们要求使损失函数达到最小的参数：

或者写成梯度下降的方式，就是我们将要得到的模型 fm 的参数 {αm,βm} 能够使得 fm 的方向是之前得到的模型 Fm-1 的损失函数下降最快的方向：

因为 Fm-1 的损失函数下降最快的方向为：

那我们可以用最小二乘法来得到 αm：

在此基础上，可以得到 βm：

最终得到整体：

完整算法：

3. 然后是 Decision Tree：

GBDT 是 GB 和 DT 的结合，就是当 GB 中的单个学习器为决策树时的情况，此处 DT 使用的是回归树。

下面两个图分别表示 DT 和 由 100 棵树组合成的 GB 在树的深度为 0，3，6 时的效果，0 时就是要拟合的函数的图像，可以看到 GB 可以在有限的深度就能得到比较光滑的的拟合：

Decision Tree

Gradient Boosting

既然都是 boosting 方法，那么 GBDT 与 Adaboost 的区别与联系是什么？

它们都属于 boosting 提升方法：

adaboost 可以表示为 boosting 的前向分布算法(Forward stagewise additive modeling)的一个特例。

在上图中，如何选择损失函数决定了算法的名字。不同的损失函数和极小化损失函数方法决定了 boosting 的最终效果，下面是几个常见的 boosting：

AdaBoost 是通过提升错分数据点的权重来定位模型的不足，

而 Gradient Boosting是通过算梯度（gradient）来定位模型的不足。

GBDT 与 Xgboost 的关系又是什么？

在 Kaggle 神器 xgboost 这篇文章中简单地提了一下 xgboost 的特点，除了很多优化外它与 GBDT 的区别有：

• Xgboost 是 GB 算法的高效实现，xgboost 中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。
• xgboost在目标函数中显示的加上了正则化项：

• GB 中使用 Loss Function 对 f(x) 的一阶导数计算出伪残差用于学习生成fm，xgboost 不仅使用到了一阶导数，还使用二阶导数：

• CART 回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost 寻找分割点的标准是最大化，lamda，gama 与正则化项相关：

参考：

统计学习方法

A Gradient Boosting Machine－Jerome H. Friedman

http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

http://blog.csdn.net/yangtrees/article/details/7506052

http://blog.csdn.net/shenxiaoming77/article/details/51542982

http://blog.csdn.net/dark_scope/article/details/24863289

http://arogozhnikov.github.io/2016/06/24/gradient_boosting_explained.html