理解GBDT、XGBOOST

参考 https://www.csuldw.com/2019/07/12/2019-07-12-an-introduction-to-gbdt/

GBDT三大核心：

1. 提升方法（加法模型+前向分步算法）；
2. 梯度提升：梯度与残差；
3. 决策树：CART回归树。

为什么GBDT会引入gradient的概念？

• 回归损失MSE:
  
  的一阶导数就是残差的形式，残差正好就是损失函数的负梯度

GBDT的缺点？

对异常值过于敏感

参考https://zhuanlan.zhihu.com/p/29765582
解决方法：用绝对值损失或者huber损失（设置了outlier阈值）

XGBOOST的生长策略（跟GBDT相似，只不过这里是二阶导+正则项）

参考https://zhuanlan.zhihu.com/p/29765582

XGBOOOST目标函数：

G为叶子节点上各个样本的一阶导之和，H为二阶导之和

a、从深度为0的树开始，对每个叶节点枚举所有的可用特征

b、 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
分裂收益为： 分裂收益推导

c、 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该节点生长出左右两个新的叶节点，并为每个新节点关联对应的样本集

d、回到第1步，递归执行到满足特定条件为止

为什么选取最佳分割点时要对样本特征值进行排序？

In order to do so efficiently, the algorithm must first sort the data according to feature values and visit the data in sorted order to accumulate the gradient statistics for the structure score in Eq7.

为了更高效地枚举所有分割方案.(比如样本在某特征为6,3,7,8,2，那么我们分割点取x，需要对每个样本进行判断是否大于x，然后决定分配到左节点还是右节点。而排序后，样本特征为2,3,6,7,8,则直接知道，x左边的分配到左结点，右边的分配到右节点。这样只需要从左到右一遍线性扫描即可。

XGBOOST的生长策略是level-wise的

参考https://www.zhihu.com/question/51644470/answer/146321804
XGBoost 采用 Level-wise 的增长策略，不加区分的分裂每一层的所有节点，可以实现并行计算，提高了训练速度，便于控制模型复杂度，不容易过拟合，但同时也因为节点增益过小增加了很多不必要的分裂，增加了计算量；LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。