GBDT，XGBoost，LightGBM

参考文章：重要度从上至下
1、 GBDT详解上 + 下 + 后补 火光摇曳
2、Introduction to Boosted Trees XGBoost作者PPT 陈天奇
XGBOOST论文
3、GBDT算法原理与系统设计简介
4、Introduction to Boosted Trees的翻译 -XGBoost 与 Boosted Tree
5、Greedy Function Approximation:GBM第一篇提出GBM
6、通俗的将Xgboost的原理讲明白
7、XGBoost解读(2)--近似分割算法
8、xgboost如何处理缺失值

1、理解这三个算法的区别

和目标函数息息相关，也就是Rj和bj区别
抓住两个变量，输入空间划分Rj，对应输出值bj
对应两个步骤，怎么确定Rj和bj
分裂节点的标准也不同，GBDT是gini指数，而XGBoost是目标函数衍化而来的

GBDT，因为目标函数没有加入正则化项，bj=Rj内所有标签的平均值，所以一旦Rj确定，bj也确定了

XGBoost，目标函数复杂，所以先要确定Rj和bj的关系。
1、对目标函数求bj的偏导，得到bj与Rj的关系式
2、只要确定Rj，bj也随之确定了

2、GBDT和XGBoost的区别

(2)传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

(3)xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance trade-off角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

(4)删除，不算区别。Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率，这个不算区别）

(5)列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

(6)对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

(7)xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

(8)可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

Histogram算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

带深度限制的Leaf-wise的叶子生长策略

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

Leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

总结：2，3两点的改进是核心，对目标函数的改进，导致影响R和b的关系，属于算法改进
其他属于工程实现上的优化，加快运行速度
xgboost在工程上的优化

Lightgbm算法直方图解释得很好

3、Xgboost和LightGBM的区别

sklearn、XGBoost、LightGBM的文档阅读小记

核心点

1、目标函数不同

• GBDT用一阶导数近似（没有对目标函数进行展开），XGBoost用一阶导数和二阶导数近似（ GBDT 在函数空间中利用梯度下降法进行优化，XGBoost 在函数空间中用牛顿法进行优化）
• XGBoost有正则化项l2和树的复杂度
• 从而影响输入空间Rj和切分点bj的分裂标准
  2、学习率
• GBDT 直接为1
• XGBoost 为了削弱每棵树的影响，让后面有更大的学习空间
  3、工程的区别
• 树节点分裂方法：XGboost是预排序（精确分裂，或者二阶导数三分位数），GBDT没有，LightGBM是直方图

bagging

核心：随机有放回的采样，叫Bootstraping

分：训练t颗树，对所有样本采集出m个样本点（对于每个样本不被采集到的概率1-1/m，m趋于无穷。也就是说，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。对于这部分大约36.8%的没有被采样到的数据，我们常常称之为袋外数据）

＆：如果是分类预测，用投票法得到最后结果；回归，对所有结果做平均

随机森林：

bagging + 基分类器是cart决策树

改进了一点，还做了特征采样

Adaboost

Adaboost算法在分类问题中的主要特点：通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能

1、计算每个分类器的分类误差率

2、根据分类误差率，得到当前分类器的权重

3、根据当前分类器的权重，跟新训练样本的权重分布（误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小）

boosting

总结一句话：在函数空间进行梯度下降，LR的梯度下降是每次用梯度更新参数，GBDT是用负梯度产生一个决策树
1、初始化模型

2、循环生成k个决策树，求出残差，一阶导数或二阶导数

3、遍历所有特征和切分点，让误差最小，得到当前最优的树（本质是贪心算法）

4、得到回归提升树

• 目标函数不同，有无正则化，目标函数拆分成一阶导数、二阶导数

• 接下来的提升树，核心区别在于如何划分输入空间Rj和每个输入空间对应的输出值bj（也就是叶子节点的值）

• 学习率

基于残差的提升树

回归树+平方误差

利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中残差的近似值，拟合一个回归树。

步骤：

1、初始化模型

2、循环生成k个决策树，每个样本对应的标签，要被替换成残差，真实值减去上一轮的预测值

3、遍历所有特征和切分点，让当前平方误差最小，得到当前最近的树（本质是贪心算法）

bj等于输入空间所有样本标签的平均值，划分输入空间的标准是均方误差最小

4、得到回归提升树

基于梯度的提升树

回归树+所有损失函数

升级为一阶导来拟合回归树

步骤：

1、初始化模型

2、循环生成k个决策树，每个样本对应的标签，求当前对应的负梯度（一阶导数）

3、遍历所有特征和切分点，让当前误差函数最小，得到当前最近的树

4、得到回归提升树

XGBoost

步骤：

1、初始化模型

（2、将目标函数泰勒展开，展开到二阶导数；3、目标函数加入正则化，l2正则化和树的负责度；4、去掉常数项，合并同类项；5、对Rj求导，得到bj关于Gi和Hi的公式，也得到新的损失函数；6、根据损失函数，定义分裂后的增益gain）

3、遍历所有特征和切分点，让gain最大，Gain的值越大，分裂后 L 减小越多

4、得到回归提升树
xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
https://www.cnblogs.com/mata123/p/7440774.html

lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact 算法，histogram算法在内存和计算代价上都有不小优势。
1、-. 内存上优势：很明显，直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features* 4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。
2、-. 计算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)

3、直方图做差加速
-. 一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。

4、lightgbm支持直接输入categorical 的feature
-. 在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。

5、但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法，为什么xgboost的近似算法比lightgbm还是慢很多呢？
-. xgboost在每一层都动态构建直方图， 因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。
-. lightgbm做了cache优化？

6、lightgbm哪些方面做了并行？
lightgbm更好地处理了多进程（毕竟是微软）
-. feature parallel
一般的feature parallel就是对数据做垂直分割（partiion data vertically，就是对属性分割），然后将分割后的数据分散到各个workder上，各个workers计算其拥有的数据的best splits point, 之后再汇总得到全局最优分割点。但是lightgbm说这种方法通讯开销比较大，lightgbm的做法是每个worker都拥有所有数据，再分割？（没懂，既然每个worker都有所有数据了，再汇总有什么意义？这个并行体现在哪里？？）
-. data parallel
传统的data parallel是将对数据集进行划分，也叫 平行分割(partion data horizontally)， 分散到各个workers上之后，workers对得到的数据做直方图，汇总各个workers的直方图得到全局的直方图。 lightgbm也claim这个操作的通讯开销较大，lightgbm的做法是使用”Reduce Scatter“机制，不汇总所有直方图，只汇总不同worker的不同feature的直方图(原理？)，在这个汇总的直方图上做split，最后同步。