xgboost, lightgbm原理

  • xgboost

决策树（下）xgboost、lightgbm
xgboost部分讲得很好

  • lightgbm

深入理解lightgbm

XGBoost、lightgbm的主要特点？

xgboost:

  • 目标函数
    • 基分类器：xgboost, lightgbm - 图1的基分类器不仅支持xgboost, lightgbm - 图2决策树，还支持线性分类器，此时xgboost, lightgbm - 图3相当于带xgboost, lightgbm - 图4和xgboost, lightgbm - 图5正则化项的xgboost, lightgbm - 图6回归（分类问题）或者线性回归（回归问题）。
    • 可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。
    • 导数信息：xgboost, lightgbm - 图7对损失函数做了二阶泰勒展开，可以更为精准的逼近真实的损失函数，xgboost, lightgbm - 图8只用了一阶导数信息，并且xgboost, lightgbm - 图9还支持自定义损失函数，只要损失函数一阶、二阶可导。
    • 正则项：xgboost, lightgbm - 图10的目标函数加了正则项， 相当于预剪枝，使得学习出来的模型更加不容易过拟合。
  • 特征选择
    • 列抽样：xgboost, lightgbm - 图11支持列采样，与随机森林类似，用于防止过拟合。
    • 缺失值处理：对树中的每个非叶子结点，xgboost, lightgbm - 图12可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
    • 块结构，并行化：注意不是树维度的并行，而是特征维度的并行。xgboost, lightgbm - 图13预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。
  • Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间；
  • 工程优化
    • 缓存访问优化算法: 特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，这样会造成缓存命中率低。为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。
    • “核外”块计算: 数据量过大时无法将数据全部加载到内存中。独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。

lightgbm:

  1. 直方图算法：采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度。lightgbm对遍历每个特征寻找最优分裂点时，将每个特征进行了分桶，比如可指定分为64个桶，那么该特征所有的值都落入这64个桶中，遍历这个特征时，最多只需要遍历64次，则每次分裂的复杂度为O(特征数桶数)，如果不分桶，则可能所有样本的值都不同，则复杂度为O(特征数样本数)。
    为什么能分桶：因为每棵树都是弱分类器，不需要非常精准，且分桶一定程度上提高了泛化能力，降低了误差。大规模LR、FM等模型对所有数值特征分桶也是一样的道理。
  2. 分枝模式为leaf-wise，即遍历当前所有待分枝节点，不需要一定在最下边一层，谁的分裂增益大就分谁。而XGBoost的分枝模式为level-wise，即分完一层再分下一层，可能一层中有些叶子分裂增益极小，但是仍然要花费时间和空间去分裂。
  3. 单边梯度抽样算法GOSS GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，减小计算量
  4. 互斥特征捆绑算法
  5. 可直接处理类别型特征
  6. 工程上：特征并行、数据并行、投票并行

xgboost如何处理类别特征？

Unlike CatBoost or LGBM, XGBoost cannot handle categorical features by itself, it only accepts numerical values similar to Random Forest. Therefore one has to perform various encodings like label encoding, mean encoding or one-hot encoding before supplying categorical data to XGBoost.

https://towardsdatascience.com/catboost-vs-light-gbm-vs-xgboost-5f93620723db

xgboost是否对共线特征敏感？

https://datascience.stackexchange.com/questions/12554/does-xgboost-handle-multicollinearity-by-itself
可以处理共线特征

XGBoost使用二阶泰勒展开的目的和优势

  • 精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数，使模型收敛更快

  • 可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。

    XGBoost如何选择最佳分裂点？

  • 贪心算法

寻找最佳分割点的大致步骤如下：

  • 遍历每个结点的每个特征；
  • 对每个特征，按特征值大小将特征值排序；
  • 线性扫描，找出每个特征的最佳分裂特征值；
  • 在所有特征中找出最好的分裂点（分裂后增益最大的特征及特征值）

上面是一种贪心的方法，每次进行分裂尝试都要遍历一遍全部候选分割点，也叫做全局扫描法。
但当数据量过大导致内存无法一次载入或者在分布式情况下，贪心算法的效率就会变得很低，全局扫描法不再适用。

  • 基于此，XGBoost提出了一系列加快寻找最佳分裂点的方案（近似、分位数算法）：

    • 特征预排序+缓存：XGBoost在训练之前，预先对每个特征按照特征值大小进行排序，然后保存为block结构，后面的迭代中会重复地使用这个结构，使计算量大大减小。
    • 分位点近似法：对每个特征按照特征值排序后，采用类似分位点选取的方式，仅仅选出常数个特征值作为该特征的候选分割点，在寻找该特征的最佳分割点时，从候选分割点中选出最优的一个。
    • 并行查找：由于各个特性已预先存储为block结构，XGBoost支持利用多个线程并行地计算每个特征的最佳分割点，这不仅大大提升了结点的分裂速度，也极利于大规模训练集的适应性扩展。

      XGBoost为什么可以并行训练

  • xgboost的并行不是说每棵树可以并行训练，xgboost, lightgbm - 图14本质上仍然采用xgboost, lightgbm - 图15思想，每棵树训练前需要等前面的树训练完成才能开始训练。

  • 是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

    XGBoost中的一棵树的停止生长条件

  • 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。

  • 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。
  • 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。

XGBoost如何评价特征的重要性？

常用的三种方法来评判模型中特征的重要程度：

  • weight ：该特征在所有树中被用作分割样本的特征的总次数。
  • gain ： 增益意味着相应的特征对通过对模型中的每个树采取每个特征的贡献而计算出的模型的相对贡献。与其他特征相比，此度量值的较高值意味着它对于生成预测更为重要。
  • cover ：覆盖度量指的是与此功能相关的观测的相对数量。例如，如果您有100个观察值，4个特征和3棵树，并且假设特征1分别用于决定树1，树2和树3中10个，5个和2个观察值的叶节点;那么该度量将计算此功能的覆盖范围为xgboost, lightgbm - 图16个观测值。这将针对所有4项功能进行计算，并将以17个百分比表示所有功能的覆盖指标。

    XGBoost如何处理缺失值？（稀疏感知法

xgboost模型的一个优点就是允许特征存在缺失值：

  • xgboost在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。
  • 如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。

  • 树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。
    原因就是：一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。

    为什么XGBoost相比某些模型对缺失值不敏感

    一些模型如SVM和KNN，其模型原理中涉及到了对样本距离的度量，如果缺失值处理不当，最终会导致模型预测效果很差。
    而树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。原因就是，一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂，完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。
    而且xgboost有相应的缺失值处理方法。

    XGBoost如何处理不平衡数据？

    XGBoost有两种自带的方法来解决：

  • 如果你在意AUC，采用AUC来评估模型的性能，那你可以通过设置scalepos_weight来平衡正样本和负样本的权重。例如，当正负样本比例为1:10时，scale_pos_weight可以取10；源码到底是怎么利用scale_pos_weight来平衡样本的呢，if (info.labels[i] == 1.0f) w *= param.scale_pos_weight

可以看出，应该是增大了少数样本的权重。

  • 如果你在意概率(预测得分的合理性)，你不能重新平衡数据集(会破坏数据的真实分布)，应该设置max_delta_step为一个有限数字来帮助收敛（基模型为LR时有效）。

    XGBoost中如何处理过拟合的情况？

  • 目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的xgboost, lightgbm - 图17模的平方，控制树的复杂度。

  • 设置目标函数的增益阈值：如果分裂后目标函数的增益小于该阈值，则不分裂。
  • 设置最小样本权重和的阈值：当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。
  • 设置树的最大深度：xgboost, lightgbm - 图18 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
  • shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间
  • 子采样：每轮计算可以不使用全部样本，使算法更加保守

  • 列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）

  • 调参：

    • 第一类参数：用于直接控制模型的复杂度。包括max_depth，min_child_weight，gamma 等参数
    • 第二类参数：用于增加随机性，从而使得模型在训练时对于噪音不敏感。包括subsample，colsample_by树
    • 还有就是直接减小learning rate，但需要同时增加estimator 参数。

      XGBoost中如何对树进行剪枝

  • 在目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的L2模的平方，控制树的复杂度。

  • 在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益小于该阈值，则不分裂。
  • 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。

  • XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。

    XGBoost的Scalable性如何体现？

  • 基分类器的scalability：弱分类器可以支持cart决策树，也可以支持LR。

  • 目标函数的scalability：支持自定义loss function，只需要其一阶、二阶可导。有这个特性是因为泰勒二阶展开，得到通用的目标函数形式。

  • 学习方法的scalability：block结构支持并行化，支持 Out-of-core计算。

    XGBoost为什么快？

  • 分块并行：训练前每个特征按特征值进行排序并存储为block结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点

  • 候选分位点：每个特征采用常数个分位点作为候选分割点
  • **block** 处理优化：block预先放入内存；block按列进行解压缩；将block划分到不同硬盘来提高吞吐

  • CPU cache 命中优化： 使用缓存预取的方法，对每个线程分配一个连续的buffer，读取每个block中样本的梯度信息并存入连续的buffer中。

    XGBoost的缺点

  • 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；

  • 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

    others

    XGBoost和LightGBM的区别

  • 树生长策略

    • XGB采用level-wise的分裂策略：XGB对每一层所有节点做无差别分裂，但是可能有些节点增益非常小，对结果影响不大，带来不必要的开销。
    • LGB采用leaf-wise的分裂策略：Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的，但是很容易出现过拟合问题，所以需要对最大深度做限制 。

  • 分割点查找算法

    • XGB使用特征预排序算法，LGB使用基于直方图的切分点算法，其优势如下：
      • 减少内存占用，比如离散为256个bin时，只需要用8位整形就可以保存一个样本被映射为哪个bin(这个bin可以说就是转换后的特征)，对比预排序的exact greedy算法来说（用int_32来存储索引+ 用float_32保存特征值），可以节省7/8的空间。
      • 计算效率提高，预排序的Exact greedy对每个特征都需要遍历一遍数据，并计算增益。而直方图算法在建立完直方图后，只需要对每个特征遍历直方图即可。
    • LGB还可以使用直方图做差加速，一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算
  • 直方图算法
    • XGB 在每一层都动态构建直方图， 因为XGB的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图。
    • LGB中对每个特征都有一个直方图，所以构建一次直方图就够了
  • 支持离散变量
    • XGB无法直接输入类别型变量因此需要事先对类别型变量进行编码（例如独热编码），
    • LGB可以直接处理类别型变量。
  • 缓存命中率
    • XGB用block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的，这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率。
    • LGB是基于直方图分裂特征的，梯度信息都存储在一个个bin中，所以访问梯度是连续的，缓存命中率高。
  • 并行策略-特征并行
    • XGB每个worker节点中仅有部分的列数据，也就是垂直切分，每个worker寻找局部最佳切分点，worker之间相互通信，然后在具有最佳切分点的worker上进行节点分裂，再由这个节点广播一下被切分到左右节点的样本索引号，其他worker才能开始分裂。
    • LGB特征并行的前提是每个worker留有一份完整的数据集，但是每个worker仅在特征子集上进行最佳切分点的寻找；worker之间需要相互通信，通过比对损失来确定最佳切分点；然后将这个最佳切分点的位置进行全局广播，每个worker进行切分即可。
  • 并行策略-数据并行
    • LGB中先对数据水平切分，每个worker上的数据先建立起局部的直方图，然后合并成全局的直方图，采用直方图相减的方式，先计算样本量少的节点的样本索引，然后直接相减得到另一子节点的样本索引，这个直方图算法使得worker间的通信成本降低一倍，因为只用通信以此样本量少的节点
    • XGB中的数据并行也是水平切分，然后单个worker建立局部直方图，再合并为全局，不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引

  • 投票并行（LGB）：当数据量和维度都很大时，选用投票并行，该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大，尤其是当特征维度很大时。大致思想是：每个worker首先会找到本地的一些优秀的特征，然后进行全局投票，根据投票结果，选择top的特征进行直方图的合并，再寻求全局的最优分割点。

    RF和GBDT的区别

    相同点：

  • 都是由多棵树组成，最终的结果都是由多棵树一起决定。

不同点：

  • 集成学习：xgboost, lightgbm - 图19属于xgboost, lightgbm - 图20思想，而xgboost, lightgbm - 图21是xgboost, lightgbm - 图22思想
  • 偏差-方差权衡：xgboost, lightgbm - 图23不断的降低模型的方差，而xgboost, lightgbm - 图24不断的降低模型的偏差
  • 并行性：xgboost, lightgbm - 图25的树可以并行生成，而xgboost, lightgbm - 图26只能顺序生成(需要等上一棵树完全生成)
  • 最终结果：xgboost, lightgbm - 图27最终是多棵树进行多数表决（回归问题是取平均），而xgboost, lightgbm - 图28是加权融合
  • 数据敏感性：xgboost, lightgbm - 图29对异常值不敏感，而xgboost, lightgbm - 图30对异常值比较敏感
  • 泛化能力：xgboost, lightgbm - 图31不易过拟合，而xgboost, lightgbm - 图32容易过拟合

比较LR和GBDT，说说什么情景下GBDT不如LR

先说说LR和GBDT的区别：

  • LR是线性模型，可解释性强，很容易并行化，但学习能力有限，需要大量的人工特征工程
  • GBDT是非线性模型，具有天然的特征组合优势，特征表达能力强，但是树与树之间无法并行训练，而且树模型很容易过拟合；

当在高维稀疏特征的场景下，LR的效果一般会比GBDT好。原因如下：

先看一个例子：

假设一个二分类问题，label为0和1，特征有100维，如果有1w个样本，但其中只要10个正样本1，而这些样本的特征 f1的值为全为1，而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。 我们都知道在这种情况下，树模型很容易优化出一个使用f1特征作为重要分裂节点的树，因为这个结点直接能够将训练数据划分的很好，但是当测试的时候，却会发现效果很差，因为这个特征f1只是刚好偶然间跟y拟合到了这个规律，这也是我们常说的过拟合。

因为现在的模型普遍都会带着正则项，而 xgboost, lightgbm - 图33 等线性模型的正则项是对权重的惩罚，也就是 xgboost, lightgbm - 图34一旦过大，惩罚就会很大，进一步压缩 xgboost, lightgbm - 图35的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种case，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小。

这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合。
[

](https://zhuanlan.zhihu.com/p/99069186)

xgboost paper Lightgbm如何处理类别特征： https://blog.csdn.net/anshuai_aw1/article/details/83275299 LightGBM 直方图优化算法：https://blog.csdn.net/jasonwang_/article/details/80833001 https://zhuanlan.zhihu.com/p/73045333