Vgbhfive's Blog
  1. XGBoost
  2. XGBoost与GBDT有什么不同
  3. RF和GBDT的区别
  4. 比较LR和GBDT，说说什么情景下GBDT不如LR
  5. XGBoost为什么可以并行训练
  6. XGBoost为什么快？
  7. XGBoost中如何处理过拟合的情况？
  8. XGBoost的优缺点
  9. XGBoost和LightGBM的区别
  10. XGBoost使用二阶泰勒展开的目的和优势
  11. LightGBM
  12. 概述SVM
  13. SVM为什么采用间隔最大化
  14. SVM的优缺点
  15. SVM对缺失数据敏感
  16. LR、GBDT、SVM之间的区别

XGBoost

XGBoost 是大规模、分布式的通用梯度提升(GBDT)库，它在GB框架下实现了GBDT和一些广义线性ML算法。
XGBoost 是一种集成学习算法，属于3类常用的集成方法(Bagging，Boosting，Stacking)中的Boosting算法类别。它是一个加法模型，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。
XGBoost 对 GBDT 进行了一系列优化，比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行、默认缺失值处理等，在可扩展性和训练速度上有了巨大的提升，但其核心思想没有大的变化。

XGBoost与GBDT有什么不同

1. 基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的LR回归（分类问题）或者线性回归（回归问题）。
2. 导数信息：XGBoost对损失函数做了二阶泰勒展开，可以更为精准的逼近真实的损失函数，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导。
3. 正则项：XGBoost的目标函数加了正则项， 相当于预剪枝，使得学习出来的模型更加不容易过拟合。
4. 列抽样：XGBoost支持列采样，与随机森林类似，用于防止过拟合。
5. 缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支。
6. 并行化：注意不是树维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。
7. 可扩展性：损失函数支持自定义，只需要新的损失函数二阶可导。

RF和GBDT的区别

相同点：
都是由多棵树组成，最终的结果都是由多棵树一起决定。

不同点：
1. 集成学习：RF属于Bagging思想，而GBDT是Boosting思想
2. 偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差
3. 并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)
4. 最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合
5. 数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感
6. 泛化能力：RF不易过拟合，而GBDT容易过拟合

比较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拟合到了这个规律，这也是我们常说的过拟合。
因为现在的模型普遍都会带着正则项，而 LR 等线性模型的正则项是对权重的惩罚，也就是 w_1 一旦过大，惩罚就会很大，进一步压缩 w_1 的值，使他不至于过大。但是，树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种`case`，树只需要一个节点就可以完美分割9990和10个样本，一个结点，最终产生的惩罚项极其之小。
这也就是为什么在高维稀疏特征的时候，线性模型会比非线性模型好的原因了：带正则化的线性模型比较不容易对稀疏特征过拟合。

XGBoost为什么可以并行训练

不是说每棵树可以并行训练，XGBoost本质上仍然采用Boosting思想，每棵树训练前需要等前面的树训练完成才能开始训练。

而是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为`block`结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个`block`结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个`block`并行计算。
注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。
xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。
这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

XGBoost为什么快？

1. 分块并行：训练前每个特征按特征值进行排序并存储为`block`结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点
2. `block` 处理优化：`block`预先放入内存；`block`按列进行解压缩；将`block`划分到不同硬盘来提高吞吐
3. 候选分位点：每个特征采用常数个分位点作为候选分割点
4. CPU cache 命中优化： 使用缓存预取的方法，对每个线程分配一个连续的`buffer`，读取每个`block`中样本的梯度信息并存入连续的`buffer`中。

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

目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的 L2 模的平方，控制树的复杂度。
设置目标函数的增益阈值：如果分裂后目标函数的增益小于该阈值，则不分裂。
设置最小样本权重和的阈值：当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。
设置树的最大深度：XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝。
shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间
子采样：每轮计算可以不使用全部样本，使算法更加保守
列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）

XGBoost的优缺点

优点：

  • 精度更高： GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
  • 灵活性更强： GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，使用线性分类器的 XGBoost 相当于带 和 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
  • 正则化： XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是XGBoost优于传统GBDT的一个特性。
  • Shrinkage（缩减）： 相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。传统GBDT的实现也有学习速率；
  • 列抽样： XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。这也是XGBoost异于传统GBDT的一个特性；
  • 缺失值处理： 对于特征的值有缺失的样本，XGBoost 采用的稀疏感知算法可以自动学习出它的分裂方向；
  • XGBoost工具支持并行： Boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是树粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第次迭代的代价函数里包含了前面次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为`block`结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个`block`结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
  • 可并行的近似算法： 树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似算法，用于高效地生成候选的分割点。

缺点：

  • 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
  • 预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

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`上的节点分裂时会单独计算子节点的样本索引。

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

XGBoost是以MSE为基础推导出来的，在MSE的情况下，XGBoost的目标函数展开就是一阶项+二阶项的形式，而其他类似Logloss这样的目标函数不能表示成这样形式，为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接定义损失函数了，只要二阶可导即可，增强了模型的扩展性
二阶信息能够让梯度收敛的更快，拟牛顿法比SGD收敛更快，一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。

LightGBM

LightGBM是一个梯度 boosting 框架，使用基于学习算法的决策树。 它可以说是分布式的，高效的。
从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。

LightGBM 是为解决GBDT训练速度慢，内存占用大的缺点，此外还提出了：

  • 基于Histogram的决策树算法
  • 单边梯度采样 Gradient-based One-Side Sampling(GOSS)
  • 互斥特征捆绑 Exclusive Feature Bundling(EFB)
  • 带深度限制的 Leaf-wise 的叶子生长策略
  • 直接支持类别特征(Categorical Feature)
  • 支持高效并行
  • Cache 命中率优化

概述SVM

SVM 是一种二类分类模型。

它的基本思想是在特征空间中寻找间隔最大的分离超平面使数据得到高效的二分类，具体来讲，有三种情况（不加核函数的话就是个线性模型，加了之后才会升级为一个非线性模型）：

  • 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
  • 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
  • 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

SVM为什么采用间隔最大化

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

SVM的优缺点

优点：

  • 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
  • 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
  • 拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，在某种意义上避免了“维数灾难”。
  • 理论基础比较完善(例如神经网络就更像一个黑盒子)。

缺点：

  • 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
  • 只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)

SVM对缺失数据敏感

这里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

LR、GBDT、SVM之间的区别

直观区别：

  • 逻辑回归：逻辑回归的决策边界总是一条直线（或者一个平面，在更高维度上是超平面），逻辑回归方法得到的决策边界总是线性的，并不能得到这里需要的环状边界。因此，逻辑回归适用于处理接近线性可分的分类问题。
  • 决策树：决策树是按照层次结构的规则生成的，决策规则只是用平行于轴线的直线将特征空间切分，如果边界是非线性的，并且能通过不断将特征空间切分为矩形来模拟，那么决策树是比逻辑回归更好的选择。
  • SVM：SVM是通过把特征空间映射到核空间，使得各个类别线性可分。先提升特征的维度，在高纬度用一个平面来分割数据（线性分类器），这个平面映射回原来的二维特征空间，就能得到一个环状的决策边界。
理论区别：
  • 模型复杂度：SVM 支持核函数，可处理线性非线性问题，既可以用于分类问题，也可以用于回归问题；LR 模型简单，训练速度快，适合处理线性问题，非线性问题需要转换，适用于二分类问题；决策树也能处理非线性特征，但容易过拟合，需要进行剪枝，适用于多分类问题。
  • 损失函数：SVM hinge loss; 带L2正则化的LR对应的是cross entropy loss，不带的是正则化的是log loss; 决策树的损失函数由叶节点上的经验熵决定。
  • 数据量：LR和决策树都适合用于数据量大的情况，SVM在样本数据量较大需要较长训练时间，因此更适用于数据量小的情况
  • 敏感度：LR对缺失值敏感，不能有缺失值；SVM噪声不能太多，对缺失数据敏感；决策树对缺失数据不敏感