XGB原理知识点总结

根据知乎上的优秀文章，对XGB进行全面总结，便于后续复习

主要内容包括：

  1. 什么是XGB？
  2. XGB的基学习器是什么？
  3. XGB的模型如何定义？
  4. XGB如何学习？
  5. XGB的树如何生成？
  6. 如何寻找最佳分裂点？
  7. XGB在工程角度上做了哪些优化？
  8. XGB的优缺点总结
  9. Xgboost的参数学习
  10. XGB与GBDT的区别？
  11. XGB与LGB的区别？

什么是XGB？

XGB是Exterme Gradient Boosting的缩写，XGB是基于决策树和梯度提升的 机器学习算法。我们可以简单粗暴的认为，XGB是GBDT的优化版本，同样的，XGB也是利用加法模型和前向分步学习算法实现的优化过程。
但是XGB和GBDT还是存在区别的，具体区别后文给出。

XGB的基学习器是什么？

XGB可以使用Regression Tree（CART）作为基学习器，也可以使用线性分类器作为基学习器。其实基学习器的选择在 xgboost 第三方库中可以通过参数booster来设置。后文会有xgboost的参数详解。如果选择使用CART作为基学习器，那么xgboost的决策规则便和决策树一致。并且CART的每一个叶子结点具有一个权重，即叶子结点的预测值。CART如图所示：
image.png
当一个样本进行预测时，按照内部的决策规则，当样本落到具体的叶子结点时，完成决策，同时该叶子结点的权重就是该样本的预测输出值。

XGB的模型如何定义？

我们刚刚提过，XGB也是属于集成学习范围中的，同GBDT一样，XGB的模型构建也是基于加法模型的。具体看下例子：
给定一个n个样本m个特征的数据集：
image.png
XGB的输出预测形式为：
image.png
其中fk表示基学习器，一般多为树模型。K表示基学习器的个数。最终样本的预测值为K个基学习器预测值的累加和。可以看到，其实XGB在模型定义上还是与经典的集成学习模型类似的。
那有了模型，如何学习呢？

XGB如何学习？

我们说通常情况下，模型的学习基本遵循以下两个步骤：

  1. 定义目标函数，即损失函数或者损失函数和正则项的组合
  2. 使用优化算法优化目标函数

那我们首先来看一下，XGB的目标函数如何定义？
image.pngimage.png
首先XGB的目标函数由两个部分组成，一个是损失函数，另外一个是惩罚项（正则项）。
损失函数是用来度量预测值和真实值之间的差距。惩罚项中包含了两个子部分，一个是树的所有叶子结点数，另外一个是每颗树叶子结点输出分数的平方和，即L2范数。那么XGB对模型的复杂度不仅考虑到了每棵树的叶子结点数量，还考虑到了每棵树叶子结点输出值的平方和。
对于XGB的目标函数推导过程，本文不做详细归纳。XGB的目标函数的推导主要用到了前向分布算法和泰勒公式的展开。
最终的目标函数：
image.png
可以看出，XGB的目标函数主要依赖于数据点的一阶导数和二阶导数，这一点在使用上很灵活。
复习的时候还是需要看此篇文章：https://zhuanlan.zhihu.com/p/75217528，里面有详细的推导过程。

XGB对应的树如何生成？

首先我们给出XGB的特征选择以及切分点选择的指标：
image.png
我们把此式子称为切分增益，Gain值越大，说明再此结点进行切分时获得的收益最大。其中中括号中的第一项表示在当前节点分裂之后左结点的得分，第二项表示分裂之后右结点的得分，第三项表示的是分裂之前的得分。最后的y表示的是分裂之后模型复杂度的增加量。
好，在有了上文中的目标函数和分裂标准之后，要想生成一个树并完成训练，我们还需要理解XGB如何查找最有特征以及最有切分点。

XGB的分裂查找算法

XGB对于最优特征和最优切分点的选取提供了两个算法。

  1. 精确贪心算法
  2. 近似算法

    精确贪心算法

大体思想就是，通过遍历每个特征下的每个可能的特征值作为切分点取值，并对数据进行切分，然后按照上文中的收益指标计算切分前后的收益，并选择获得最大收益的特征和特征值作为最优特征和最优切分点。具体的算法流程如下：
image.png
但是精确贪心算法的时间复杂度太高了，每次进行切分都需要遍历所有数据，对内存和运算都有压力。所以才有了近似算法。

近似算法

近似算法并不像前者那样需要遍历所有数据来选择最优切分点，近似算法首先根据每一个特征的特征值分布进行了分箱操作，箱体的边界值也就是候选切分点值。那么也就是对连续数据进行了离散化处理。然后便可以在每个桶内部计算一阶导和二阶导和，最后计算收益，选择收益最高的特征作为最优特征和最优切分点。
image.png
同时，近似算法还提出了两种分箱机制。

  1. Global
  2. Local

这两者并没有太大的区别，只是定义了提取候选切分点也就是分箱的时机。前者是在生成树之前为整棵树做一次分箱，后续的步骤中每次都直接使用这次的分箱结果。
而Local则是在每次节点划分之前，进行分箱。

Local和Global对比

  • Global只需要在初始化的时候进行一次切分，而Local则需要多次切分
  • Local每分裂之前都会进行分箱，可以理解反复的对数据进行细分。那么local方式更适合于树深度较大的情况。
  • Global如果想达到Local的性能，则必须在分箱时候提出更多的候选切分点。因为Global没有反复的数据进行细化。

    加权分位数略图

    略，详细可参考https://zhuanlan.zhihu.com/p/75217528

XGB在工程角度上做了哪些优化？

稀疏值处理（稀疏感知算法）

数据中难免会存在nan值，这可能是由于天然的数据缺失、或者onehot编码之后导致的数据稀疏问题。那么稀疏感知算法对于稀疏值的处理默认可以总结为一句话：让模型去学习缺失值的划分方向。具体的算法流程：
image.png
其实就是在每次的切分时，让缺失值分别被分到左结点和右结点，然后依次计算各自的收益，收益大的方向自然就是缺失值的最优划分方向。

分块并行

在树生成的过程中，需要花费大量的时间在特征选择和切分点选择上，并且这些时间大多数花费在对特征值的排序上面。
分块并行的做法就是按照特征进行分块，并且在每个块内部进行排序。块内部保存的是特征值及其对应的样本的梯度信息的索引，便于快速访问。如下图左部分所示。
image.png

这样的优点就是每个特征都会被隔离开来，对于每个块都可以分配一个线程，从而并发的去处理特征，也就是特征选择的并行化处理。从而提高运算效率。

缓存优化

基于分块的隔离性和块内特征值存储位置的连续性，使得访问特征值的速度大大提高。但是对于块内的特征值对应的样本梯度索引在内存上并不一定是连续的，这就造成了缓存命中率较低的问题。
缓存优化的解决办法就是将非连续转为连续，其实就是为每个线程在分配个buffer区域，用于存储需要到的梯度信息。也是一种动态加载的方式。

核外块计算

当数据量非常大的时候，没有办法将所有数据全部存储到内存中，这就需要现将数据存储在硬盘上，然后用到的时候到硬盘上去读取。但是这样会受限于硬盘的IO操作速度远远小于内存的处理速度。核外块计算的解决办法是，将数据分成多个块存储在硬盘上，然后用一个独立的线程专门去读取和加载。
为了高效读取和加载数据，减少硬盘读取的开销，作者还给出了两个方法。

  • 块压缩
    • 对每一个block按列压缩，读取的时候在进行解压
  • 块分区
    • 将每个block存储到不同的硬盘上，增加硬盘读取的吞吐性

XGB的优缺点总结

优点：

  • 精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
  • 灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，（使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题））。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
  • 正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合；
  • Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间；
  • 列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算；
  • 缺失值处理：XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度；
  • 可以并行化操作：块结构可以很好的支持并行计算。

    缺点：

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

Xgboost的参数学习

XGB和GBDT、LGB的比较后续在补充