7.梯度提升树 - 二、xgboost - 《AI算法工程师手册》

二、xgboost

二、xgboost

xgboost 也是使用与提升树相同的前向分步算法。其区别在于：xgboost 通过结构风险极小化来确定下一个决策树的参数：

其中：
- 为第个决策树的正则化项。这是xgboost 和GBT的一个重要区别。
- 为目标函数。
定义：

即：
- 为在的一阶导数。
- 为在的二阶导数。
对目标函数执行二阶泰勒展开：

提升树模型只采用一阶泰勒展开。这也是xgboost 和GBT的另一个重要区别。
对一个决策树，假设不考虑复杂的推导过程，仅考虑决策树的效果：
- 给定输入，该决策树将该输入经过不断的划分，最终划分到某个叶结点上去。
- 给定一个叶结点，该叶结点有一个输出值。
因此将决策树拆分成结构部分，和叶结点权重部分，其中为叶结点的数量。
- 结构部分的输出是叶结点编号。它的作用是将输入映射到编号为的叶结点。
- 叶结点权重部分就是每个叶结点的值。它的作用是输出编号为的叶结点的值。
因此决策树改写为：。

2.1 结构分

定义一个决策树的复杂度为：。

其中：为叶结点的个数；为每个叶结点的输出值；为系数，控制这两个部分的比重。
- 叶结点越多，则决策树越复杂。
- 每个叶结点输出值的绝对值越大，则决策树越复杂。
该复杂度是一个经验公式。事实上还有很多其他的定义复杂度的方式，只是这个公式效果还不错。
将树的拆分、树的复杂度代入的二阶泰勒展开，有：

对于每个样本，它必然被划分到树的某个叶结点。定义划分到叶结点的样本的集合为：。则有：
定义：。
- 刻画了隶属于叶结点的那些样本的一阶偏导数之和。
- 刻画了隶属于叶结点的那些样本的二阶偏导数之和。
偏导数是损失函数关于当前模型的输出的偏导数。

则上式化简为：。

假设与与无关，对求导等于0，则得到：。

忽略常数项，于是定义目标函数为：
在推导过程中假设与与无关，这其实假设已知树的结构。

事实上是与相关的，甚至与树的结构相关，因此定义为结构分。

结构分刻画了：当已知树的结构时目标函数的最小值。

2.2 分解结点

现在的问题是：如何得到最佳的树的结构，从而使得目标函数全局最小。

2.2.1 贪心算法

第一种方法是对现有的叶结点加入一个分裂，然后考虑分裂之后目标函数降低多少。
- 如果目标函数下降，则说明可以分裂。
- 如果目标函数不下降，则说明该叶结点不宜分裂。
对于一个叶结点，假如给定其分裂点，定义划分到左子结点的样本的集合为：；定义划分到右子结点的样本的集合为：。则有：
定义叶结点的分裂增益为：

其中：
- 表示：该叶结点的左子树的结构分。
- 表示：该叶结点的右子树的结构分。
- 表示：如果不分裂，则该叶结点本身的结构分。
- 表示：因为分裂导致叶结点数量增大1，从而导致增益的下降。
每次分裂只一个叶结点，因此其它叶结点不会发生变化。因此：
- 若，则该叶结点应该分裂。
- 若，则该叶结点不宜分裂。
现在的问题是：不知道分裂点。对于每个叶结点，存在很多个分裂点，且可能很多分裂点都能带来增益。

解决的办法是：对于叶结点中的所有可能的分裂点进行一次扫描。然后计算每个分裂点的增益，选取增益最大的分裂点作为本叶结点的最优分裂点。
最优分裂点贪心算法：
- 输入：
  - 数据集，其中样本。
  - 属于当前叶结点的样本集的下标集合。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 初始化：。
  - 遍历各维度：
    - 初始化：
    - 遍历各拆分点：沿着第维：
      - 如果第维特征为连续值，则将当前叶结点中的样本从小到大排序。然后用顺序遍历排序后的样本下标：
      - 如果第维特征为离散值，设当前叶结点中第维取值样本的下标集合为，则遍历：
  - 选取最大的对应的维度和拆分点作为最优拆分点。
分裂点贪心算法尝试所有特征和所有分裂位置，从而求得最优分裂点。

当样本太大且特征为连续值时，这种暴力做法的计算量太大。

2.2.2 近似算法

近似算法寻找最优分裂点时不会枚举所有的特征值，而是对特征值进行聚合统计，然后形成若干个桶。

然后仅仅将桶边界上的特征的值作为分裂点的候选，从而获取计算性能的提升。
假设数据集，样本。

对第个特征进行分桶：
- 如果第个特征为连续特征，则执行百分位分桶，得到分桶的区间为：，其中。
  
  分桶的数量、分桶的区间都是超参数，需要仔细挑选。
- 如果第个特征为离散特征，则执行按离散值分桶，得到的分桶为：，其中为第个特征的所有可能的离散值。
  
  分桶的数量就是所有样本在第个特征上的取值的数量。
最优分裂点近似算法：
- 输入：
  - 数据集，其中样本。
  - 属于当前叶结点的样本集的下标集合。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 对每个特征进行分桶。假设对第个特征上的值进行分桶为：。
    
    如果第个特征为连续特征，则要求满足。
  - 初始化：。
  - 遍历各维度：
    - 初始化：
    - 遍历各拆分点，即遍历：
      - 如果是连续特征，则设叶结点的样本中，第个特征取值在区间的样本的下标集合为，则：
      - 如果是离散特征，则设叶结点的样本中，第个特征取值等于的样本的下标集合为，则：
    - 选取最大的对应的维度和拆分点作为最优拆分点。
分桶有两种模式：
- 全局模式：在算法开始时，对每个维度分桶一次，后续的分裂都依赖于该分桶并不再更新。
  - 优点是：只需要计算一次，不需要重复计算。
  - 缺点是：在经过多次分裂之后，叶结点的样本有可能在很多全局桶中是空的。
- 局部模式：除了在算法开始时进行分桶，每次拆分之后再重新分桶。
  - 优点是：每次分桶都能保证各桶中的样本数量都是均匀的。
  - 缺点是：计算量较大。
全局模式会构造更多的候选拆分点。而局部模式会更适合构建更深的树。
分桶时的桶区间间隔大小是个重要的参数。

区间间隔越小，则桶越多，则划分的越精细，候选的拆分点就越多。

2.3 加权分桶

假设候选样本的第维特征，及候选样本的损失函数的二阶偏导数为：

定义排序函数：

它刻画的是：第维小于的样本的之和，占总的之和的比例。
xgboost 的作者提出了一种带权重的桶划分算法。定义候选样本的下标集合为，拆分点定义为：

其中表示样本的第个特征。即：
- 最小的拆分点是所有样本第维的最小值。
- 最大的拆分点是所有样本第维的最大值。
- 中间的拆分点：选取拆分点，使得相邻拆分点的排序函数值小于（分桶的桶宽）。
  - 其意义为：第维大于等于，小于的样本的之和，占总的之和的比例小于。
  - 这种拆分点使得每个桶内的以为权重的样本数量比较均匀，而不是样本个数比较均匀。
上述拆分的一个理由是：根据损失函数的二阶泰勒展开有：

对于第个决策树，它等价于样本的真实标记为、权重为、损失函数为平方损失函数。因此分桶时每个桶的权重为。

2.4 缺失值

真实场景中，有很多可能导致产生稀疏。如：数据缺失、某个特征上出现很多 0 项、人工进行 one-hot 编码导致的大量的 0。
- 理论上，数据缺失和数值0的含义是不同的，数值 0 是有效的。
- 实际上，数值0的处理方式类似缺失值的处理方式，都视为稀疏特征。
  
  在xgboost 中，数值0的处理方式和缺失值的处理方式是统一的。这只是一个计算上的优化，用于加速对稀疏特征的处理速度。
- 对于稀疏特征，只需要对有效值进行处理，无效值则采用默认的分裂方向。
  
  注意：每个结点的默认分裂方向可能不同。
在xgboost 算法的实现中，允许对数值0进行不同的处理。可以将数值0视作缺失值，也可以将其视作有效值。

如果数值0是有真实意义的，则建议将其视作有效值。
缺失值处理算法：
- 输入：
  - 数据集，其中样本。
  - 属于当前叶结点的样本的下标集合。
  - 属于当前叶结点，且第维特征有效的样本的下标集合。
- 输出：当前叶结点最佳分裂点。
- 算法：
  - 初始化：。
  - 遍历各维度：
    - 先从左边开始遍历：
      - 初始化：
      - 遍历各拆分点：沿着第维，将当前有效的叶结点的样本从小到大排序。
        
        这相当于所有无效特征值的样本放在最右侧，因此可以保证无效的特征值都在右子树。
        
        然后用顺序遍历排序后的样本下标：
    - 再从右边开始遍历：
      - 初始化：
      - 遍历各拆分点：沿着维，将当前叶结点的样本从大到小排序。
        
        这相当于所有无效特征值的样本放在最左侧，因此可以保证无效的特征值都在左子树。
        
        然后用逆序遍历排序后的样本下标：
  - 选取最大的对应的维度和拆分点作为最优拆分点。
缺失值处理算法中，通过两轮遍历可以确保稀疏值位于左子树和右子树的情形。

2.5 其他优化

2.5.1 正则化

xgboost 在学习过程中使用了如下的正则化策略来缓解过拟合：
- 通过学习率来更新模型：。
- 类似于随机森林，采取随机属性选择。

2.5.2 计算速度提升

xgboost 在以下方面提出改进来提升计算速度：
- 预排序pre-sorted 。
- cache-aware 预取。
- Out-of-Core 大数据集。

2.5.2.1 预排序

xgboost 提出column block 数据结构来降低排序时间。
- 每一个block 代表一个属性，样本在该block 中按照它在该属性的值排好序。
- 这些block 只需要在程序开始的时候计算一次，后续排序只需要线性扫描这些block 即可。
- 由于属性之间是独立的，因此在每个维度寻找划分点可以并行计算。
block 可以仅存放样本的索引，而不是样本本身，这样节省了大量的存储空间。

如：block_1 代表所有样本在feature_1 上的从小到大排序：sample_no1,sample_no2,.... 。

其中样本编号出现的位置代表了该样本的排序。

2.5.2.2 预取

由于在column block 中，样本的顺序会被打乱，这会使得从导数数组中获取时的缓存命中率较低。

因此xgboost 提出了cache-aware 预取算法，用于提升缓存命中率。
xgboost 会以minibatch 的方式累加数据，然后在后台开启一个线程来加载需要用到的导数。

这里有个折中：minibatch 太大，则会引起cache miss ；太小，则并行程度较低。

2.5.2.3 Out-of-Core

xgboost 利用硬盘来处理超过内存容量的大数据集。其中使用了下列技术：
- 使用block 压缩技术来缓解内存和硬盘的数据交换IO ：数据按列压缩，并且在硬盘到内存的传输过程中被自动解压缩。
- 数据随机分片到多个硬盘，每个硬盘对应一个预取线程，从而加大”内存-硬盘”交换数据的吞吐量。