先进树模型库学习

本文介绍 XGBoost、LightGBM、CatBoost 等树模型库，他们考虑到许多实际运用中的需求和限制。 因为这些库的使用场景距离自己比较遥远未必会用到，本文不会太多的讨论技术细节，仅以了解为主，日后若有需要再深度更新。

本文大面积参考这篇文章： 【机器学习】决策树（下）——XGBoost、LightGBM（非常详细） - 阿泽的文章 - 知乎

XGBoost

XGBoost 是大规模并行 boosting tree 的工具。 XGBoost 和 GBDT 两者都是 boosting 方法，除了工程实现、解决问题上的一些差异外，最大的不同就是目标函数的定义。 GBDT 仅针对一阶导数，而 XGBoost 对一阶导数和二阶导数都进行了优化，此外 XGBoost 还加入了正则项，防止过拟合。 XGBoost 不止支持决策树，还支持线性模型，此处我们主要介绍决策树。

基础知识

目标函数可以写作：

$$\begin{aligned} Obj^{(t)} & =\sum_{i=1}^n l\left(y_i, \hat{y}_i^t\right)+\sum_{i=1}^t \Omega\left(f_i\right) \\ & =\sum_{i=1}^n l\left(y_i, \hat{y}_i^{t-1}+f_t\left(x_i\right)\right)+\sum_{i=1}^t \Omega\left(f_i\right) \end{aligned}$$

其中，$\hat{y}_i^t$ 是第 $t$ 次迭代的预测值，$f_t$ 是第 $t$ 次迭代的模型，$\Omega$ 是正则项。 对该式求解可以利用到泰勒展开 $f(x)=\sum_{i=0}^n \frac{f^{(i)}\left(x_0\right)}{i !}\left(x-x_0\right)^i+R_n(x)$。 那么对于一个函数在 $x$ 处的二阶展开可以写作 $f(x+\Delta x) \approx f(x)+f^{\prime}(x) \Delta x+\frac{1}{2} f^{\prime \prime}(x) \Delta x^2$。 那么目标函数可以重写为：

$$O b j^{(t)}=\sum_{i=1}^n\left[l\left(y_i, \hat{y}_i^{t-1}\right)+g_i f_t\left(x_i\right)+\frac{1}{2} h_i f_t^2\left(x_i\right)\right]+\sum_{i=1}^t \Omega\left(f_i\right)$$

其中，$g_i$ 和 $h_i$ 分别是损失函数 $l$（而不是目标函数）关于 $\hat{y}_i^{t-1}$ 的一阶和二阶导数。 又由于 $l\left(y_i, \hat{y}_i^{t-1}\right)$ 是一个常数，不会对优化目标产生影响，所以

$$Obj^{(t)} \approx \sum_{i=1}^n\left[g_i f_t\left(x_i\right)+\frac{1}{2} h_i f_t^2\left(x_i\right)\right]+\sum_{i=1}^t \Omega\left(f_i\right)$$

所以我们只需要求出每一步损失函数的一阶导和二阶导的值（两个值就是常数），然后优化目标函数，就可以得到每一步的 $f_t$。

与决策树一起使用

定义决策树为 $f_t\left(x\right)= w_{q(x)}$, 其中 $q(x)$ 是叶子节点的索引，$w_j$ 是叶子节点的取值（权值）。 对于决策树来说，复杂度可以用叶子节点的个数 $T$ 来表示，此外叶子结点的权重 $w_j$ 也是需要优化的参数，所以正则项可以写作

$$\Omega\left(f_t\right)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^T w_j^2$$

那么，目标函数可以写作

$$\begin{aligned} O b j^{(t)} & \approx \sum_{i=1}^n\left[g_i f_t\left(x_i\right)+\frac{1}{2} h_i f_t^2\left(x_i\right)\right]+\Omega\left(f_t\right) \\ & =\sum_{i=1}^n\left[g_i w_{q\left(x_i\right)}+\frac{1}{2} h_i w_{q\left(x_i\right)}^2\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\ & =\sum_{j=1}^T\left[\left(\sum_{i \in I_j} g_i\right) w_j+\frac{1}{2}\left(\sum_{i \in I_j} h_i+\lambda\right) w_j^2\right]+\gamma T & =\sum_{j=1}^T\left[G_j w_j+\frac{1}{2}\left(H_j+\lambda\right) w_j^2\right]+\gamma T \end{aligned}$$

其中，$I_j$ 是叶子节点 $j$ 中的样本索引集合, $G_j$ 和 $H_j$ 分别是 $I_j$ 中样本的一阶导数和二阶导数之和。 此时是一个二次规划问题，将目标函数对 $w_j$ 求导，并令其为 0，可以得到

$$\begin{aligned} &w_j^*=-\frac{G_j}{H_j+\lambda} \end{aligned}$$

所以目标函数可以简化为以下形式，这个值越小，代表这个树的结构越好。

$$\begin{aligned} &Obj=-\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda}+\gamma T \end{aligned}$$

使用时的具体考虑

之后的问题就是如何找到最优的结构，使得 $Obj$ 最小。 需要考虑到的问题有：

1. 如何选取特征切分节点：一般来说有两种方法，一种是贪心算法（类似普通决策树，遍历特征和分裂点，记录收益），一种是近似算法（针对数据量过大无法读入内存的情况，对于每个特征只考察候选分位点可以减少计算复杂度）。
2. 加权分位数缩略图：不是简单地按照样本个数进行分位，而是以二阶导数值 $h_i$ 作为样本的权重进行划分。（$h_i$ 可以看作平方损失函数中样本的权重）
3. 稀疏感知算法：XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，同时为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上。（缺省方向可以从数据中学到，可以通过枚举特征缺省样本归为左右分支之后的增益。）

工程实现上的考虑：

1. 训练决策树时对特征的值排序十分耗时。XGBoost 在训练之前对根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。
2. 在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。
3. 每个特征会存储指向样本梯度统计值的索引，方便计算一阶导和二阶导数值。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问优化算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。
4. XGBoost 独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。

特性

1. 块结构：XGBoost 采用了块结构，可以大大减小计算量。
2. 精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。
3. 正则化：正则项有效的控制了模型的复杂度，防止过拟合。
4. 列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。
5. 缺失值处理：XGBoost 使用稀疏感知算法。
6. 可以并行化操作：块结构可以很好的支持并行计算。

LightGBM

LightGBM 是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。

模型训练：GOSS 算法

使用单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）对样本进行抽样，减少了大量梯度小的样本，极大的减少了计算量。 GOSS 保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。

我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a% 的梯度大的样本，和总体样本的 b%，在计算增益时，通过乘上 $\frac{1-a}{b}$ 来放大梯度小的样本的权重。 一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

特征离散化：直方图算法

将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。 利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。 虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。 同时对稀疏特征进行优化，仅使用非零特征构建直方图。

互斥特征捆绑算法

高维特征往往是稀疏的，而且特征间可能是相互排斥的，即两个特征不同时取零（非零）值。 可以用互斥率表示互斥程度。 互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。 则需要讨论，哪些特征可以绑定？以及绑定之后如何确定特征的值？

问题一可以用一个加权无向图表示，转化为一个图着色算法。 其中节点表示特征，边表示两个特征之间的互斥程度，边的权重表示互斥程度。 根据节点的度进行降序排序，度越大，与其他特征的冲突越大。 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，是的总体冲突最小。

问题二其关键在于原始特征能从合并的特征中分离出来。 （特征合并算法这里不详细展开）

基于最大深度的 Leaf-wise 的垂直生长算法

对于建树的策略而言，XGBoost 采用 Level-wise 的增长策略，方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，降低了计算量。 LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。

类别特征最优分割

决策树中对于类别特征通常不推荐 one-hot 编码，因为切分收益很少（在一个均匀的多分类中，只有少量为 1，多数为 0）。 此外在这些离散的小空间上统计信息可能不准确，学习效果变差。

LightGBM 原生支持类别特征，采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。 Many-vs-many 的切分方式是将类别特征的所有类别分为两个子集，然后计算每个子集的增益，最后选择增益最大的子集进行切分。 (具体选取子集的方式这里不详细展开）

特征并行和数据并行

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果（因为对数据进行垂直划分，每台机器所含数据不同）。 此处的通信增加了额外的复杂度。 LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点，这种数据开销过大。 LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

LightGBM 特点

1. 内存更小。
   1. 使用直方图将特征值离散化，减少了内存占用。
   2. 同时采用了互斥特征捆绑算法，减少了特征数量。
2. 速度更快。
   1. 遍历样本转化为便利直方图
   2. GOSS 过滤了梯度小的样本
   3. 采用了 Leaf-wise 的增长策略，减少了计算量。
   4. 使用了优化的特征并行和数据并行算法，减少了通信代价。
   5. 对缓存也进行了优化，提高了命中率。

Reference

1. 【机器学习】决策树（下）——XGBoost、LightGBM（非常详细） - 阿泽的文章 - 知乎
2. 大战三回合：XGBoost、LightGBM 和 Catboost 一决高低 - AI科技大本营的文章 - 知乎