GBDT拾遗
GBDT（Gradient Boosting Decision Tree）是我工作中常用的模型。但是，我在现有的资料中，没有找到一个介绍得比较全面的文章。很多博客说了自己的理解，都是浅尝辄止，其中也有一些错误（我会专门指出这些常见的错误）；李航的《统计学习方法》给出了比较好的数学解释，但是对于没有基础的初学者，他写的东西比较理论和晦涩，不易看懂（我也是后来才看懂他说的）；国外的一些论文等资料介绍得比较好，但是也缺乏全面的总结，对中文读者也有一定门槛。我总结一下我所有的知识，结合前人的各种文章，尝试写一篇GBDT的综述，希望大家轻拍。
要介绍GBDT，就不能不介绍其他相关的算法，比如Adaboost、随机森林等。我会简要说明这些算法，重点从这些算法和GBDT的区别上来说明GBDT。我还会介绍我理解的GBDT各种演变、参数的含义和使用建议。
一、集成学习
GDBT、Adaboost、随机森林等，都属于集成学习（ensemble learning）的范畴。集成学习的含义是，通过结合多个学习器（或者说预测方法），来产生新的预测方法。
所谓三个臭皮匠顶上一个诸葛亮。
一个最简单的例子，我需要预测一只股票会不会上涨，有10个朋友有不同的意见。结合他们的意见我的决策可能是：
1 取多数意见
2 给平时会炒股的人更高的意见权重，最后是的结果是一个加权值
又比如说，决定要不要给一个人发信用卡，有年龄、收入两个维度
其中，组合成最后的预测方法的单位称为个体学习器（比如每个同事的意见、在年龄维度上的阈值分割）。另外，如果集成方法要求个体学习器为“同质的”，则个体学习器也被称为基学习器（base learner）
集成学习的关键和核心：如何产生“好而不同”的个体学习器
二、Boosting的含义和Adaboost
Boost，提升。指的是如何将比较弱的个体学习器增强的方案。比如，个体学习器都是在一个维度上用一个阈值来划分样本（一刀切）。Boost通过迭代，找到样本的划分阈值，成为一个个体学习器，重复T轮后组合这些个体学习器，得到最后的增强的结果。
常用的迭代方法：
1 重赋权法（re-weighting）：适用于可以接受带权样本的基学习器（损失函数对样本加权计算）
2 重采样法（re-sampling）：适用于无法接受带权样本的基学习器（抽样时不同样本抽中的概率不同）
Adaboost，是一种十分常见的boost算法。它的核心思想是，通过迭代，给错误的样本更高的权重来不断更新个体学习器，最后加权组合每一步的个体学习器来实现预测。
关于Adaboost的介绍很多，它的常用算法流程我简要叙述如下：
1 初始，给予每个样本相同的权重1/n，其中n为样本个数
2 进行多轮迭代m=1，2，3…
a）找到在这个权重下的一个最佳的个体学习器。
这里，个体学习器可以是一个维度上的划分，称为Adaboost-Stump。比如，单从年龄上划分群体，得到一个年龄的阈值。
个体学习器也可以是一棵决策树，称为Adaboost-DecisionTree。但是需要有几点注意：
1 用重采样法来代替赋权
2 每个决策树不能完全长成。如果数深度=1，即退回原始Adaboost
b） 计算基于当前样本权重的个体学习器的分类错误率Em
c) 计算该个体学习器的权重取值Wm
d）更新样本权重
3 最后的分类器为各个个体学习器关于Wm的加权
三、Adaboost的另外一种解释：
Adaboost是把损失函数定义为指数函数的一种梯度下降的迭代方法。李航在《统计学习方法》中，命名为：
加法模型+前向分布算法+指数损失函数
四、GBDT的基本算法
注意，我这里说的算法，是GBDT的一种类型，具体而言，是将最小化平方误差作为拟合目标，用回归树拟合当前残差的方案（后面一章会介绍其他方案）。
在这种算法中，GBDT是回归树，而不是分类树（但是并不意味着GBDT不能用于二分类问题，其他方案的GBDT可以用分类树！这个问题上很多博客都抄来抄去，一直犯错）
1 初始回归拟合值为当前样本平均值f1
2 进行多轮迭代m=1，2，3…：
a 计算当前残差rm=y-fm
b 用回归数拟合当前残差（最小化当前残差的平方值）
c fm = fm-1 + 当前回归数残差
3 最后的分类器即为当前fm的拟合
五、从另一个角度看GBDT，GBDT的其他变种
和Adaboost的两种解释类似，GBDT也有对应的数学解释。GBDT可以看做：
线性加法模型+前向分布算法+损失函数
利用损失函数的负梯度来作为当前树的拟合目标。损失函数为平方函数时，失函数的负梯度恰好就是上面说的残差
它和Adaboost的区别是：
1 通过加法模型组合各个单步模型时，加权系数是1，即不按照和当前分类错误率相关的权重来组合，而是简单加和。
2 Adaboost限定了误差函数为指数误差。
但是，一般的GBDT，损失函数是不限于平方函数的。
损失函数是平方函数时，问题是对Outlier敏感。
常用的两种损失函数有：
绝对值差（Absolute loss）
Huber差（Huber loss）
总结：
1 任何一种损失函数，我们都能定义出一个GBDT。那么也可以仿照逻辑回归定义Log损失函数，定义相应的二分类GBDT
2 误差函数为平方误差时，每一步最小化的恰好是残差，但是这对异常点敏感
很多博客引用了以下的图。但是这个图有一些错误，或者说可能让人混淆的地方：
问题1：Adaboost的Ada，是体现在对每一步的结果，需要用当前误差加权，即f*上
问题2：Gradient boosting是一个总称，并不限于绝对误差。
六、GBDT的变形和参数建议
“Shrinkage”：每次迭代时，不直接加上当前的残差，而是乘以一个系数
“Bagging”：每次迭代单步的树时，随机选一些样本
七、GBDT和Random Forest的区别
我们再简要说明一下另外一类集成学习的方法，Bagging
Bagging，装袋。但是这名字其实是由Bootstrap Aggregating（加速聚合）而来。指的是用并行的方案生成各个各个学习器的方案。
1 简单的Bagging方案
2 随机森林–一种Bagging基础上的变体
Random Forest的每棵树都是完全长成的。虽然在各个点上有随机选取特征，但是最后还是要求每棵树尽可能的预测所有样本，然后综合各个树的结果来对全量进行预测。
Boosting方法，每棵树是。个人认为，这特别适合解决这类问题：部分样本就用部分特征就能描述，而另外的样本可能需要其他的特征来描述。我们目前的主要工作，恰好满足这个条件。
八、多说几句感想
并不是你掌握了看似很高大上的工具，就牛逼了。能成事，解决实际的问题，需要吃透每一个点，了解每一种工具、每一个算法的由来、含义。
学习时，真正把一个问题吃透，才有兴趣往下走。如果只是半桶水，似懂非懂，再往下会遇到很多麻烦，因为后面的知识往往依赖于前面的知识，后面的理解学习过程也会很慢。如果一个人前面没有完全吃透，后面学习花的时间会更多。在一个时间内没有达到预期的效果，没有正向反馈，就会对齐失去兴趣。
所以，只有把每个问题吃透，不漏疑点，才能保持兴趣。
什么算吃透？
任何一个公式的由来，含义。公式从来不用记住，只是靠脑子里的理解就能写出来。
但是吃透一个问题，谈何容易！
有3点：
1、根据人智力的不同，难度也不同，花的时间也不同。这一点几乎毫无办法，如果智力不够，只能靠时间积累，勤能补拙。
但是人与人之间的智力差别，其实是指数级的。且不说牛顿、爱因斯坦这类无双的天才，能发明微积分，能从光速不变就想出广义相对论，就是我高中、大学身边的出现的各种天才，就有口算思维数乘法的，有从来不上课考前翻翻书就接近满分的，没办法。
2、由于各种原因，包括一个开小差，一点懒惰没有弄清原理，在一个点上没有理解，那么结果往往是滚雪球。
3、老师讲课水平。如果你足够聪明，不需要老师，看一遍书就懂了。但是如果稍微弱一点，那么好的老师确实能够帮你节约理解的时间。一个好的老师在以下方面会让你很有收获：
A 这个知识点的的总体全貌是怎样的，它解决了什么问题，在整个大体系中发挥了什么作用。
B 这知识点的细节
C 对其他知识点的影响
一个真的好的老师，可以把一个问题讲解到非常通俗易懂
根据我的观察（包括学生和老师），高中能做到所有知识点都能融汇贯通的一般都能去985大学，大学里更是只有极少数人能做到这一点。包括所谓的教授，30-50%都是一知半解。（他可能只对自己科研的方向比较熟悉，但我认为这不是合格的教授）
参考文档：
南京大学 周志华《机器学习》第8章 集成学习
李航《统计学习原理》
国立台湾大学 林轩田 《机器学习技法》相关课程视频资料
http://blog.csdn.net/dark_scope/article/details/24863289