XGBoost笔记

Posted by mudux on March 3, 2020

  XGBoost是大规模并行boosting tree工具,是GBDT的一种高效实现,两者在目标函数定义,工程实现上有些差别。这里总结下相关知识。

1. XGBoost损失函数

  XGBoost求解的是由$k$个基模型组成的一个加法模型

  其中$f_k$是第$k$个基模型,$\widehat{y}_i$为第$i$个样本的预测值。
  在GBDT中求解每个基模型的过程为:

  • 对样本$i=1,2,\cdots,N$,计算负梯度

  • 利用$(x_i,r_{ti}),\ i=1,2,\cdots,N$,拟合一棵CART回归树,得到第$t$棵回归树,其对应的叶子结点区域为$R_{tj},j=1,2,\cdots,J$。其中$J$为回归树$t$的叶子结点的个数。
  • 对叶子区域$j=1,2,\cdots,J$,计算最佳拟合值

  • 更新学习器

  上面第一步是得到负梯度,即泰勒展开式一阶导数的负。第二步为第一个优化求解,即基于残差拟合一棵CART回归树,得到$J$个叶子结点区域。第三步是第二个优化求解,在第二步得到的每个叶子结点进行一次线性搜索,得到每个叶子结点的最优取值。第四步更新强学习器。
  从上面可以看出,要求解这个问题,需要求解当前决策树最优的所有$J$个叶结点区域和每个叶结点区域的最优解$c_{tj}$。GBDT分两步解决这个问题。而在XGBoost中,把2,3步合在一起,即一次求出决策树最优的所有$J$个叶结点和每个叶结点的最优解$c_{tj}$。
  XGBoost的损失函数为:

  上式中正则化项

  其中$J$是叶结点个数,$w_{tj}$是第$j$个叶结点的最优值,这里的$w_{tj}$和GBDT中$c_{tj}$是一个意思。
  需要极小化上面的损失函数,得到第$t$个决策树最优的$J$个叶结点区域和每个叶结点区域的最优解$w_{tj}$。XGBoost用损失函数的二阶泰勒展开求解(GBDT只用了一阶)。二阶泰勒展开为

  方便起见,把第$i$个样本在第$t$个弱学习器的一阶和二阶导数记为

  损失函数现在可以表示为

  对这个公式的理解也挺简单:因为需要最小化损失函数,最小化这个函数只能通过改变拟合值来优化,所以$\widehat{y}$相当于自变量,损失函数求导也是对$\widehat{y}$求导,而$f_t$就是自变量的增量。
  这个模型是加法模型,损失函数里面对当前第$t$步优化无影响,相当于常数,可以去掉,同时由于每个决策树的第$j$个叶结点的取值最终会是同一个值$w_{tj}$,因此损失函数可以简写为

  把每个叶结点区域样本的一阶导数和二阶导数的和表示为

  最终损失函数可以表示为

2. XGBoost损失函数优化求解

  关于如何一次求解出决策树最优的所有$J$个叶子结点和每个叶结点的最优解$w_{tj}$,可以拆分成2个问题:

  • 如果已经求出了第$t$个决策树的$J$个最优叶结点区域,如何求出每个叶结点的最优解$w_{tj}$
  • 对当前决策树做子树分裂决策时,应该如何选择哪个特征和特征值进行分裂,使得损失函数$L_t$最小

  对于第一个问题,第一节的损失函数对$w_{tj}$求导并令导数为0即可得到

  代入损失函数表达式,得到化简的损失函数

  其实在之前介绍GBDT时,在二分类问题中采用对数损失函数时

  叶结点近似解为

  损失函数一阶导

  二阶导

  所以$c_{tj}=-\frac{g_i}{h_i}$,两者只差一个正则化项$\lambda$。
  第二个问题,选择哪个特征和特征值进行分裂,使最终的损失函数$L_t$最小。
  在GBDT里面是直接拟合CART回归树,树节点分裂使用的是均方差。XGBoost不使用均方差,使用贪心法,即每次分裂都期望最小化损失函数。
  上面得到了化简的损失函数,每次做左右子树分裂时,最大程度的减少损失函数就行。假设当前结点左右子树的一阶导和二阶导和为$G_L,H_L,G_R,H_R$,希望最大化下式

  化简得到

3. XGBoost算法

  总结下XGBoost算法流程,基于决策树弱分类器,不涉及运行效率的优化和健壮性优化。
  输入:训练集,最大迭代次数$T$,损失函数$L$,正则化系数$\lambda, \gamma$。
  输出:强学习器$\widehat{y}(x)$。
  对迭代次数$t=1,2,\cdots,T$,有:

  1. 计算第$i$个样本$(i=1,2,\cdots,m)$在当前迭代损失函数$L$对于的一阶导数$g_{ti}$,二阶导数$h_{ti}$
  2. 基于当前结点样本分裂决策树,默认分数score=0 计算当前结点一阶导数和$G_t=\sum\limits_{i=1}^m g_{ti}$,二阶导数和$H_t=\sum\limits_{i=1}^m h_{ti}$ 对特征序号$k=1,2,\cdots,n$:
    • $G_L=0,H_L=0,G_R=G_t,H_R=H_t$
    • 将样本特征$k$从小到大排列,依次取出第$i$个样本,依次计算当前样本放入左子树后,左右子树的一阶和二阶导数和:

    • 更新最大分数

    如果有更新,记录对应的特征和特征值。

  3. 基于最大score对应特征和特征值分裂子树
  4. 如果最大score为0,则当前决策树建立完毕,计算所有叶结点的$w_{tj}$,得到弱学习器$f_t(x)$,更新强学习器$\widehat{y}(x)$,进入下一轮弱学习器迭代。如果最大score不为0,则转到第2步继续分裂,同时更新结点样本。

4. XGBoost算法优化

4.1 切分点查找算法

  决策树生成的关键在于查找最优切分点,XGBoost支持贪心算法和近似算法。

4.1.1 贪心算法

  贪心算法如下图所示:

4.1

  贪心算法其实就是对每个特征的每个可能的切分点进行遍历,找到最好的切分特征和特征值。贪心算法肯定是比较耗时,而且需要在内存中把特征排序。单机版的XGBoost支持贪心算法。

4.1.2 近似算法

  当数据大到不能加载到内存中或者分布式情况下就无法使用贪心算法,论文提出了近似算法。近似算法提出候选切分点,并把特征映射到相应的桶中,然后寻找最优切分点。

4.3   有两个版本的近似算法:

  • global: 在初始化就提出所有的候选切分点,在当前迭代中一直使用这些候选切分点
  • local: 每次切分时都重新提出候选切分点

  自然地,全局版本需要更多的候选切分点,局部版本在切分时重新提出候选点,在树深度大时更精确。
  几种方法对比如下:

4.2

  可以看出,分位切分点可以达到和贪心策略同样的精确度。

4.2 加权分位数(Weighted Quantile Sketch)

  XGBoost在提出切分点候选点时不是按照特征值的分位数来选取,而是以二阶导数$h_{ti}$为权重确定分位点。如下图所示: 4.4

  因为在损失函数中每个样本是以二阶导数为权值的:

  注意这里除$f_t$外都是常数。
  可以看出每个样本的损失是以二阶导数为权重的。

4.3 稀疏感知算法(Sparsity-aware Split Finding)

  在实际应用中,输入数据是稀疏的情况普遍存在,如1)缺失值;2)统计上的0值;3)特征工程如one-hot编码导致等。在CART树种,在寻找切分点和切分时针对缺失值做了某些固定处理。而在XGBoost中,缺失值缺省方向是从数据中学得的。把缺失值分别分到左子结点和右子结点,再对非缺失值样本进行遍历找最优切分点。因为要考虑两个方向,所以这里有两次遍历。算法如下图所示:

4.5

5. XGBoost工程优化

5.1 块结构设计

  决策树学习最耗时的在于数据排序以搜索最优切分点。为了加快搜索,XGBoost把数据存储在块结构(block)中。每个块中的数据以压缩列格式存储(compressed column format),即每个列按照对应的特征值排序,这一块结构仅需在训练前计算一次,后面迭代也可以重复使用,因为迭代改变的是梯度值,而特征值不会改变,同时也需要存储指向梯度值的索引。

5.1

  • 每个块结构包括一个或多个已经排序好的特征;
  • 缺失特征值将不进行排序;
  • 每个特征会存储指向样本梯度统计值的索引,方便计算一阶和二阶导数值;

  块结构带来两个好处:

  • Boosting算法的弱学习器是没法并行迭代的。但XGBoost把特征存储在快结构,所以针对每个特征的扫描可以并行运行,这也是XGBoost能够实现分布式或多线程计算的原因;
  • 块结构支持列采样;

5.2 缓存访问优化

  块结构的涉及可以减少结点分裂时的计算量,但特征值通过索引访问样本梯度统计值的设计导致访问操作的内存空间不连续,造成缓存命中率低,从而影响算法的效率。
  为了解决缓存命中率低的问题:

  • 针对贪心算法,XGBoost为每个线程分配一个连续的缓存区,将需要的梯度信息存放在缓存区中;
  • 针对近似算法,选择合适的块大小。块太小导致每个线程负载低,并行化效率低。块太大容易导致命中率低。

5.3 “核外”计算块结构

  当数据量太大无法加载到内存中时,需要利用硬盘存储数据,当需要时再读进来。XGBoost把数据分为多个块,然后把每个块存入硬盘。为了缓解内存和硬盘读取速度的差异,XGBoost用一个独立的线程预先把预期读取到缓存。
  尽管如此还是不能解决问题,因为硬盘读取占用了很多时间。XGBoost提出了两个方法:

  • 块压缩(Block Compression),对块按列压缩后在存储,读取是再进行解压缩,用解压时间换取硬盘读取成本;
  • 块拆分(Block Sharding),在有多个硬盘可用时,把数据拆分到多个硬盘,对每个硬盘分配一个预读取线程,训练线程从这些线程的缓存区中依次读取数据。

6. XGBoost总结

  优点:

  • 精度更高:GBDT只用了一阶泰勒展开,XGBoost是二阶泰勒展开。XGBoost引入二阶导一方面是为了增加精度,另一方面也是为了能够自定义损失函数,二阶泰勒展开可以近似大量损失函数。
  • 灵活性更强:GBDT以CART作为基分类器,XGBoost不仅支持CART还支持线性分类器。
  • 不容易过拟合:XGBoost损失函数有正则化项,用于控制模型的复杂度;而且有Shrinkage,当前弱学习器迭代完后,加入强分类器时有一个缩减(学习速率),使后面的弱分类器有更大的空间;列抽样,和随机深林同样的做法。
  • 缺失值处理:稀疏感知算法极大的加快结点分裂速度。
  • 可以并行化:块结构支持并行化。

  缺点:

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

7. Reference

1 XGBoost-paper
2 XGBoost算法原理小结-刘建平
3 决策树(下)- 阿泽