1. N问GBDT

• 怎样设置单棵树的停止生长条件？
• 如何评估特征的权重大小？
• 如何人工去干预某列特征的权重？
• 当增加样本数量时，训练时长是线性增加吗？
• 当增加树的棵树时，训练时长是线性增加吗？
• 当增加一个棵树叶子节点数目时，训练时长是线性增加吗？
• 每个节点上都保存什么信息？
• 常见的衡量分裂loss的指标都有哪些？
• 分类问题还说，决策树DT如何来做回归的？
• 如何防止过拟合？
• boosting的本意是是什么？跟bagging，random forest,adaboost,gradient boosting有什么区别？
• gbdt中哪些部分可以并行？
• 树生长成畸形树，会带来哪些危害，如何预防？
• feature sample ratio = 1.0会怎么样？跟特征数量的多少有联系么？
• 每个点分裂收益是如何计算的？
• 使用gbrank时，pair的正逆序比和权重有什么关系？正逆序比越大权重就一定高么？
• 如何选择特征和相应的分裂点？
• 假如某些特征是稀疏特征，在特征选择的时候会吃亏，怎么办？
• 通过更改指定样本sample和label来达到调整权重的目的，会有什么缺点和不足?
• G所表示的gradient在哪里体现的？
• 通过前N棵树已经正确分类的数据，在第N+1棵树上是会被怎样处理的？
• 既然在实际应用的过程中是residuals(残差)，为何还称其为GBDT，而不是称其为RBDT？
• 每棵树赋权重是怎样体现的？
• GBDT可以解决分类、回归问题，若是面对rank问题，该怎么处理？
• 对于rank问题，优化的目标函数是什么样的？怎么样优化这种非凸函数？
• 为什么大多数场景都选择square loss作为loss function？它有什么优缺点？
• boosting和bagging之间的比较？
• gbdt不适合于那些场景，或是说哪些场景下线性模型反而更好，或是差不多？
• 选择损失函数时，squareloss和logloss的适用场景？
• 当前很火热的xgboost和一般的gbdt相比，有哪些区别？
• xgboost采用了二阶导，这样会带来哪些缺点？
• xgboost节点分裂选取特征和特征分裂值时，为什么要先sort by one feature？
• 对于Nfeature，构建一棵深度为d的树，时间复杂度是什么样的？
• 若是添加一个冗余特征会怎么样？
• gbdt涉及到了哪些主要参数，是怎样来调参的？
• 如何处理非均衡数据？
• xgboost中booster有三个选项，gblinear，gbtree，dart，三者的区别与适用场景？
• 简述xgboost中提及的近似直方图算法。
• 如何为gbdt设计正则项？
• 对于指定的某数据集，在其上建立最优决策树，复杂度是多少？（仔细想想）
• 假如数据量过大，在分裂特征的时候不能一次性的加载到内存中，怎么处理？
• 如何处理缺省值，或稀疏数据？
• 怎么剪枝？
• 假设已经有个已经训好的gbdt model，此时又设计了一个新的特征，若不重训模型，怎样来做？（实践中，dump数据和数据准备可能会很麻烦，不想重新model，有什么trick？）

2. GBDT总结

GBDT（Gradient Boosting Decision Tree）是我自己工作中常用的模型，在实际工程中的运用也十分广泛。但是，我在现有的资料中，没有找到一个介绍得比较全面的文章。很多博客说了自己的理解，都是浅尝辄止，更有甚者是不加思考的抄袭，其中不乏错误（我会专门指出这些常见的错误）；李航的《统计学习方法》给出了比较好的数学解释，但是对于没有基础的初学者，他写的东西比较理论和晦涩，不易看懂（我也是后来才完全明白）；国外的一些论文等资料介绍得比较好，但是也缺乏全面的总结，另外这些文章对中文读者也有一定门槛。这里我总结一下我所有的知识，结合前人的各种文章，尝试写一篇GBDT的综述，希望大家轻拍。

要介绍GBDT，就不能不介绍其他相关的算法，比如Adaboost、随机森林等。我会简要说明这些算法，重点从这些算法和GBDT的区别上来说明GBDT。我还会介绍GBDT各种演变、参数的含义和我理解的这类模型的使用场景和相关参数的建议。

一、集成学习

GDBT、Adaboost、随机森林等，都属于集成学习（ensemble learning）的范畴。集成学习的含义是，通过结合多个学习器（或者说预测方法），来产生新的预测方法。

所谓三个臭皮匠顶上一个诸葛亮。一个最简单的例子是，我需要预测一只股票会不会上涨，有10个朋友有不同的意见。结合他们的意见，我的决策可能是：

1. 简单地取多数意见
2. 给平时会炒股的人意见更高的权重（最后是的结果是一个加权值）

又比如说，决定要不要给一个人发信用卡，有年龄、收入、学历、消费水平、婚姻状况很多维度的数据，一个好的预测可能在单一维度上需要很多划分，再组合这些维度：比如25<年龄<50且收入大于某个阈值，加上22<年龄<25且学历是在读硕士，加上消费水平>1k且是已婚女性，等等。

其中，组合成最后的预测方法的单位称为个体学习器（比如每个同事的意见、在年龄这个维度上的阈值分割等）。另外，如果集成方法要求个体学习器为“同质的”，则个体学习器也被称为基学习器（base learner）。

集成学习的关键和核心：如何产生“好而不同”的个体学习器。即上述的维度都有一定的预测性，但是他们之间关注的角度或者说特征属性又不一致：如果你10个炒股的朋友都是你的大学同学，他们和你同样从事程序员工作，平常的对一个事物的看法也比较一致——那么，结合他们的意见，可能也没啥作用。

二、Boosting的含义和Adaboost

Boost，提升。指的是如何将比较弱的个体学习器增强的方案。比如：个体学习器都是在一个维度上用一个阈值来划分样本（一刀切，英文称stump），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. 每个决策树不能完全长成。如果完全长成，那么一次决策树的样本错误率就为0了，也就不需要迭代了。另外，如果决策树的深度等于1，即退回原始Adaboost-stump

• b) 计算基于当前样本权重的个体学习器的分类错误率Em

• c) 计算该个体学习器的权重取值Wm

• d) 更新样本权重

• 3. 最后的分类器为各个个体学习器关于Wm的加权

三、Adaboost的另外一种解释：

Adaboost除了按之前的解释方法以外，也可以解释为把损失函数定义为指数函数的一种梯度下降的迭代方法。李航在《统计学习方法》中，命名为：

加法模型+前向分布算法+指数损失函数

• 加法模型：指每一步产生的个体学习器（按权重）加法成为最后的预测方法
• 前向分布算法：每一次迭代用个体学习器极小化当前的损失函数的算法
• 指数损失函数：损失函数为指数函数，即e^(分类错误数)

我把书的那一页直接贴图了，这样读者能看得清楚一点。大家有条件可以直接参阅书籍。

李航《统计学习方法》 清华大学出版社 第一版p144

四、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）

The Elements of Statisic Learning

总结：

1. 任何一种损失函数，我们都能定义出一个GBDT。那么也可以仿照逻辑回归定义Log损失函数，定义相应的二分类GBDT
2. 误差函数为平方误差时，每一步最小化的恰好是残差，但是这对异常点敏感

很多博客引用了以下的图：

Machine Learning: A Probabilistic Perspective

但是这个图有一些错误，或者说可能让人混淆的地方：

• 问题1：Adaboost的Ada，是体现在对每一步的结果，需要用当前误差加权，即图中的f*
• 问题2：Gradient boosting是一个总称，并不限于绝对误差。

六、GBDT的变形和参数建议

GBDT的一个重要的参数就是每个DT（Decision Tree）的深度。类似于Adaboost，如果每次迭代时树都完全长成，那么其实就成为了一个基本的决策树，会导致过拟合，也失去了Boost算法的意义。在一些文章中，很多人推荐把树的深度设为4到8之间，并且认为6是个不错的数值。我觉得，这个也要看变量的个数、样本数、每次迭代的步长（后文会介绍）有关。这实际上是一个经验活，而且和每次的训练场景之间相关。

GBDT在实际运用时，常常有两种变体：

“Shrinkage”：事实上这是一种正则化（regularization）方法，为了进一步过拟合，在每次对残差估计进行迭代时，不直接加上当前步所拟合的残差，而是乘以一个系数。

即：fm = fm-1 + λ * 当前回归数残差

λ为1时，即为不加Shrinkage的一般GBDT。

有文章指出，10 < λ * 迭代次数（或者说数的数目）< 100，是一个比较合适的学习速率。但是一般这个速率常常被设成了0.1，或者0.05。

“Bagging”：每次迭代单步的树时，随机选一些样本的残差做拟合，而不是把所有样本的残差做拟合（常用的样本残差选取率为0.5-0.6）。这和随机森林的思想有类似之处，下一章详细介绍一下。

七、GBDT和Random Forest的区别简要

我们再简要说明一下另外一类集成学习的方法，Bagging

Bagging，装袋。但是这名字其实是由Bootstrap Aggregating（加速聚合）而来。指的是用并行的方案生成各个各个学习器的方案。

1. 简单的Bagging方案
2. 随机森林-一种Bagging基础上的变体

具体而言，Random Forest通过随机抽样、随机选取特征来产生一棵树，最后通过每棵树的结果做线性结合来产生最终的预测结果。由于每棵树的生成过程不依赖于其他树（和GBDT明显区别，GBDT每棵树的产生需要依赖上一层树的结果），所以树的生成是并行的（这也是其成为Bagging的原因）。在RF中，每棵树都是几乎完全长成（但是仅仅预测了部分样本），树的深度会很大。

Boosting方法，每棵树是不能完全长成的，只需要一部分特征就去完成残差的一个迭代降低。个人认为，这特别适合解决这类问题：部分样本就用部分特征就能描述，而另外的样本可能需要其他的特征来描述，比如股票的样本有很多类型的股票，我们有的朋友对一种类型比较擅长，另外的朋友对别的类型比较擅长。我们目前的主要工作，恰好满足这个条件。

八、多说几句感想

能成事，解决实际的问题，需要吃透每一个点，了解每一种工具、每一个算法的由来、含义，特别是工作中的算法，如果只是略知一二，是不能很好地解决问题的。

学习时，真正把一个问题吃透，才有兴趣往下走。如果只是半桶水，似懂非懂，再往下会遇到很多麻烦，因为后面的知识往往依赖于前面的知识，后面的理解学习过程也会很慢。如果一个人前面没有完全吃透，后面学习花的时间会更多。在一个时间内没有达到预期的效果，没有正向反馈，就会对齐失去兴趣。

所以，只有把每个问题吃透，不漏疑点，才能保持兴趣。

什么算吃透？

任何一个公式的由来，含义。公式从来不用记住，只是靠脑子里的理解就能写出来。

但是吃透一个问题，谈何容易！有三点：

1. 根据人智力的不同，难度也不同，花的时间也不同。这一点几乎毫无办法，如果智力不够，只能靠时间积累，勤能补拙。但是人与人之间的智力差别，其实是指数级的。且不说牛顿、爱因斯坦这类举世无双的天才，他们能发明微积分，能从光速不变就想出广义相对论；就是我高中、大学身边的出现的各种天才，就有口算四位数乘以四位数乘法几秒钟报答案的，有从来不上课，考前翻翻书就把我们受虐的课程考到接近满分的，没办法，天才的思维方式是常人不能理解的。

2. 由于各种原因，包括一个开小差，一点懒惰没有弄清原理，在一个点上没有理解，那么结果往往是滚雪球。

3. 老师讲课水平。如果你足够聪明，不需要老师，看一遍书就懂了。但是如果稍微弱一点，那么好的老师确实能够帮你节约理解的时间。一个好的老师在以下方面会让你很有收获（一个真的好的老师，可以把一个问题讲解到非常通俗易懂）：

4. 这个知识点的的总体全貌是怎样的，它解决了什么问题，在整个大体系中发挥了什么作用。

5. 这知识点的细节

6. 对其他知识点的影响

根据我的观察（包括学生和老师），高中能做到所有知识点都能融汇贯通的一般都能去985大学，大学里更是只有极少数人能做到这一点。包括所谓的教授，30-50%都是一知半解（他可能只对自己科研的方向比较熟悉，但我认为这不是合格的教授）。

参考文档

• 南京大学 周志华《机器学习》第8章 集成学习
• 李航《统计学习原理》
• 国立台湾大学 林轩田 《机器学习技法》相关课程视频资料
• Boosted Regression (Boosting) - An introductory tutorial and a stata plugin
• http://blog.csdn.net/dark_scope/article/details/24863289
• http://www.jianshu.com/p/005a4e6ac775
• http://blog.csdn.net/suranxu007/article/details/49910323