GBDT

Gradient Boosting Decision Tree
GBDT是一种迭代的决策树算法，由多课决策树组成，分类的话是每棵树的结果投票决定，回归的话是每棵树的结果相加得到。

GBDT中的决策树指的是CART的回归树。回归树总体流程类似于分类树，区别在于，回归树的每一个节点都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化平方误差。因为分类的结果不好叠加，所以才用回归树。
为了防止过拟合，剪枝操作。有预剪枝和
C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值（熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1），按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

梯度提升指的是每棵树都是在上一棵树的残差上来继续训练的。所以才说，回归的最后结果是所有树结果的加和。
损失函数MSE，梯度迭代求到后正好是2倍的残差。

xgBoost

rf：https://xgboost.readthedocs.io/en/latest/model.html
https://www.jianshu.com/p/7467e616f227

GBM（Boosted trees）指通过不断地拟合去拟合出函数来。每次迭代都增加一棵树（一个new function）。
xgBoost本质也是一堆cart树，对于分类问题，由于CART树的叶子节点对应的值是一个实际的分数，而非一个确定的类别，这将有利于实现高效的优化算法。xgboost出名的原因一是准，二是快，之所以快，其中就有选用CART树的一份功劳。

迭代过程

第t棵树的优化目标函数是均方差损失函数+正则。当MSE作为损失函数时，目标函数包含残差和新一棵树预测结果的平方。

将迭代公式带入目标函数

泰勒二阶展开后的目标函数

二次展开的好处：

• gbdt只用到了一阶信息，如果按照上文中推导，相当于loss只进行了一阶泰勒展开。在没有复杂度项的情况下，无法确定步长，所以只能用常数步长根据一阶梯度方向去逼近。这就是牛顿下降法和梯度下降法的区别。由于二阶展开用二次函数去逼近函数，所以可以利用二阶信息确定更新步长，比只利用一阶信息的gdbt用更少的迭代获得更好的效果。cf.牛顿梯度法的二阶收敛性。
• 每个样本的gi, hi相关，可并行计算。
• gi和hi是不依赖于损失函数的形式的，只要这个损失函数二次可微就可以了。好处就是xgboost可以支持自定义损失函数，只需满足二次可微即可。

寻找最佳树结构：
对于第t棵树的优化目标函数，我们继续推导：

Ij代表一个集合，集合中每个值代表一个训练样本的序号，整个集合就是被第t棵CART树分到了第j个叶子节点上的训练样本。

继续简化

split点的评判标准：

LightGBM

分布式 GBDT。速度快！
它抛弃了大多数 GBDT 工具使用的按层生长
(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大(一般也是数据量最大)的一个叶子，然后分裂，如此循环。因此同 level-wise 相比，在分裂次数相同的情况下，leaf-wise 可以降低更多的误差，得到更好的精度。leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

• 缺失值（missing value）的自动处理
• 类别特征(Categorical Feature) 的进一步优化，不再使用类似one-hot coding的分割方式。对于类别数量很多的类别特征，使用one-vs-other的切分方式会长出很不平衡的树，不能实现较好的精度。这是树模型在支持类别特征的一个痛点。 LightGBM可以找出类别特征的最优切割，即many-vs-many的切分方式。并且最优分割的查找的时间复杂度可以在线性时间完成，和原来的one-vs-other的复杂度几乎一致。