XGBoost (eXtreme Gradient Boosting) 算法是在 CART 基础上对 Boosting 算法的一个改进,内部决策树采用回归树。由于 Boosting 算法在损失函数选择时有较大区别,例如选择平方损失函数,就是 Boosting Tree 的方式,每轮拟合残差。对于使用一般损失函数而言,可以采用 Gradient Boosting 的方式,根据梯度下降来拟合伪残差的近似值。

1. Prerequisites

  回顾一下,当我们谈及训练决策树的时候,其实是启发式的,然而这些启发式的操作却有对应的意义:

  • 根据划分指标(信息增益、增益率、基尼系数)划分属性:降低训练误差
  • 剪枝:可以看成通过节点数定义的归一化方式
  • 最大深度:在函数空间上的约束条件
  • 平滑叶节点取值平滑:实际是叶节点权重的 L2 归一化

  回归树不光可以做回归,主要看你如何利用预测结果,实际上可以用来做:分类、回归和排名等。主要依赖于你怎么定义目标函数,像之前用平方误差就构成了最基本的 Gradient Boosting 方法,我们可以总结如下:

  我们在考虑一个模型的目标函数时,强调有两个部分:

  其中:

  • $L ( \Theta )$ 代表损失函数的部分,衡量模型在训练集上拟合的好坏程度;
  • $\Omega ( \Theta )$ 代表正则化部分,衡量模型的复杂度。

2. XGBoost 算法

  在前面我们可以看到,损失函数的选取对 Gradient Boosting 方法来说有较大的影响。而对于除了平方误差的损失函数,其他损失函数处理起来依然很是复杂,于是陈天奇就想出了利用泰勒展开来拟合目标函数的方法。

  对于给定的数据集,$n$ 个实例,$m$ 个特征,

  树集成模型(下图所示)使用 $K$ 个函数的累加和来预测输出(加法模型)。

  其中

  是所有回归树(CART)的函数空间,里面的

  • $q$ 表示每颗树的结构,它将实例映射到相应的叶子节点的索引;
  • $T$ 表示一棵树的叶子节点个数;
  • 每一个 $f_k$ 对应于一个独立的树结构 $q$ 和叶子节点权重 $w$。

  每一个回归树在每一个叶子节点上的预测值 $w_i$ 表示第 $i$ 个叶子节点的得分。在上图例子中,我们使用树的决策规则来将小男孩分类到对应的叶子节点,然后将所有分到的叶子节点所对应的分值相加,最后得到小男孩的最终得分 $2.9$,因此,相较于老爷爷,小男孩玩电脑游戏的可能性更大。

  在上述例子中,我们学习到了两棵树,并且每颗树的决策变量不同,且他们具有决策先后顺序,那么这些决策(函数)是如何学习到的呢?我们通过最小化下面的目标函数来学习的:

  其中:

  可微的凸损失函数 $l$ 测量预测值和目标值的不同程度。$\Omega$ 是 $k$ 颗树的正则项,用于抑制模型的复杂度防止过拟合。当正则项的参数是 $0$ 时,上述目标函数就是一个传统的梯度树提升模型。

  至此,我们会有几个问题需要注意:

  1. 每一颗树的分支依据是如何确定的?(比如先分 age,再分性别)
  2. 每一颗树的分支分到哪里为止?(比如is male?下面还要不要分支?)
  3. 每棵树的叶子节点的权重分值是如何确定的?(为什么有的是2,有的是0.9,有的是-1)
  4. 树的颗数是如何确定的,多少颗树是最合适的?

  模型的训练是采用加法的形式来训练的,形式上,使用 $\hat{y}^{(t)}_i$ 作为第 $i$ 个实例在第 $t$ 次迭代中的预测值,我们需要添加 $f_t$ 来最小化下面的目标函数:

  对于上式,XGBoost 使用泰勒二阶展开目标函数:

  其中一阶导数 $g_i$ 和二阶导数 $h_i$ 如下:

  另外,$l\left(y_{i}, \hat{y}^{(t-1)}\right)$ 是一个常数,最小化时可以不考虑,那么优化目标简化为:

  定义 $I_{j}=\{i \vert q\left(x_{i}\right)=j\}$ 作为叶子节点 $j$ 上面的实例集合,我们可以重写上式,因为预测的结果就是落到叶节点的输出,这里每个叶节点都有一个权重,即输出 $w_j$:

  对于固定的树结构 $q(x)$,我们可以求导令零的操作结算得到叶子节点 $j$ 的最优权重 $w_{j}^{*}$:

  计算这棵树的最优值:

  这个公式能视作衡量函数来测量树结构 $q$ 的质量,类似不纯度(基尼系数)的衡量指标,来衡量一棵树的优劣程度。下图展示了如何计算一棵树的分值

  一棵树在该衡量指标下分值越低,说明这个树的结构越好(表示的是损失)。训练数据可能有很多特征,构建一棵树可能有许多种不同的构建形式,我们不可能枚举所有可能的树结构 $q$ 来一一计算它的分值。所以主要采用贪心算法来解决这个问题,贪心算法从一个单独树叶开始,迭代地增加分支,直到最后停止。(如何更快地生成树是关键)

  假设 $I_L$ 和 $I_R$ 是分割之后节点的左侧和右侧实例集合,令 $I=I_{L} \cup I_{R}$,那么在节点分割前-后的损失减少量为:

  这个公式的计算结果,通常用于在实践中评估候选分裂节点是不是应该分裂的划分依据,我们尽量找到使之最大的特征值划分点。

3. 分支节点分裂算法

3.1 暴力枚举(Basic Exact Greedy Algorithm)

  在树学习中,一个关键问题是如何找到每一个特征上的分裂点,比如在本文的例子中,age 的分裂节点是 15 岁,而不是其他年纪。为了找到最佳分裂节点,分裂算法枚举特征上所有可能的分裂点,然后计算得分,这种算法称为 Exact Greedy Algorithm,单机版本的XGBoost 支持这种 Exact Greedy Algorithm,算法如下所示:

  为了有效率的找到最佳分裂节点,算法必须先将该特征的所有取值进行排序,之后按顺序取分裂节点计算 $L_{s p l i t}$。时间复杂度是 $O(N_u)$, $N_u$ 是这个特征不同取值的个数。

3.2 近似算法(Approximate Algo for Split Finding)

  Exact Greedy Algorithm 使用贪婪算法非常有效地找到分裂节点,但是当数据量很大时,数据不可能一次性的全部读入到内存中,或者在分布式计算中,这样不可能事先对所有值进行排序,且无法使用所有数据来计算分裂节点之后的树结构得分。为解决这个问题,近似算法被设计出来。近似算法首先按照特征取值中统计分布的一些百分位点确定一些候选分裂点,然后算法将连续的值映射到 buckets 中,接着汇总统计数据,并根据聚合统计数据在候选节点中找到最佳节点。

  XGBoost 采用的近似算法对于每个特征,只考察分位点,减少复杂度,主要有两个变体:

  • Global variant:学习每棵树前就提出候选切分点,并在每次分裂时都采用这种分割
  • Local variant:每次分裂前将重新提出候选切分点

  具体算法如上,这里按照三分位点举例:

  找到其中最大的信息增量的划分方法:

  然而,这种划分分位点的方法在实际中可能效果不是很好,所以 XGBoost 实际采用的是加权分位数的方法做近似划分算法。

3.3 加权分位数(Weighted Quantile Sketch)

  我们可以先令多集合

  表示第 $k$ 个特征的每个训练样本的二阶梯度统计,其中 $h_{ik}$ 可以看做第 $i$ 个样例的第 $k$ 个特征值的权重。我们可以定义一个排序函数 $r_{k}$:$\mathbb{R} \rightarrow[0,+\infty)$,根据这个 Rank 值来取值:

  表示特征值 $k$ 小于 $z$ 的实例比例。目标就是寻找候选分裂点集 $\{s_{k 1}, s_{k 2}, \dots s_{k l}\}$,因而:

  该 Rank 函数的输入为某个特征值 $z$,计算的是该特征所有可取值中小于 $z$ 的特征值的总权重占总的所有可取值的总权重和的比例,输出为一个比例值。

  其中:

  • $s_{k1}$ 是特征 $k$ 的取值中最小的值 $x_{ik}$,$s_{kl}$ 是特征 $k$ 的取值中最大的值 $x_{ik}$,这是分位数缩略图要求需要保留原序列中的最小值和最大值
  • 这里 $\epsilon$ 是近似因子或者说是扫描步幅,按照步幅 $\epsilon$ 挑选出特征 $k$ 的取值候选点,组成候选点集,这意味着有大概 $\frac{1}{\epsilon}$ 个候选点。这里每个数据点的权重为 $h_i$,从图上看可能更明显一些:

  至于为什么用 $h_i$ 加权,把目标函数整理成以下形式:

  最后的代价函数就是一个加权平方误差,权值为 $h_i$,label 为 $-\frac{g_i}{h_i}$,所以可以将特征 $k$ 的取值权重看成对应的 $h_{i}$。

3.4 稀疏感知分割(缺失值处理)

  在很多现实业务数据中,训练数据 $x$ 可能很稀疏。造成这个问题得原因可能是:

  1. 存在大量缺失值
  2. 太多 $0$ 值
  3. one-hot encoding 所致

  算法能够处理稀疏模式数据非常重要,XGBoost 在树节点中添加默认划分方向的方法来解决这个问题,如下图所示:

  当有缺失值时,系统将实例分到默认方向的叶子节点。每个分支都有两个默认方向,最佳的默认方向可以从训练数据中学习到。算法如下:

4. 系统设计

  XGBoost 的快还体现在良好的系统设计,体现在几个方面:

4.1 Column Block - 分块并行

  在建树的过程中,最耗时是找最优的切分点,Column Block 这个结构加速了 split finding 的过程,只需要在建树前排序一次,保存到块结构中,后面节点分裂时直接根据索引得到梯度信息,大大减少计算量。

  此过程值得注意的有以下几点:

  1. 特征进行预排序,以 Column Block 的结构存于内存中
  2. 每个特征会存储指向样本梯度统计值的索引,方便计算一阶导和二阶导数值(instance indices)
  3. block 的每个块结构中都采用了稀疏矩阵存储格式(Compressed Sparse Columns Format,CSC)进行存储,一个 block 存储一个或多个特征值
  4. 缺失特征值将不进行排序
  5. 对于列的 blocks,并行的 split finding 算法很容实现

  这种块结构存储的特征之间相互独立,方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂,这时各个特征的增益计算可以同时进行,这也是 XGBoost 能够实现分布式或者多线程计算的原因。

4.2 Cache Aware Access - 缓存优化

  虽然 Column Block 的设计可以减少节点分裂时的计算量,但其按特征大小顺序存储,相应的样本的梯度信息是分散的,造成内存的不连续访问,降低 CPU cache 命中率。解决办法是:为每个线程分配一个连续的缓存区,将需要的梯度信息存放在缓冲区中,这样就是实现了非连续空间到连续空间的转换,提高了算法效率。

  • 缓存优化方法
    • 预取数据到buffer中(非连续->连续),再统计梯度信息
    • 适当调整块大小,也可以有助于缓存优化。

4.3 “核外”块计算

  当数据量过大时无法将数据全部加载到内存中,只能先将无法加载到内存中的数据暂存到硬盘中,直到需要时再进行加载计算,而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题,XGBoost 独立一个线程专门用于从硬盘读入数据,以实现处理数据和读入数据同时进行。

  此外,XGBoost 还用了两种方法来降低硬盘读写的开销:

  • 块压缩:对 Block 进行按列压缩,并在读取时进行解压;
  • 块拆分:将每个块存储到不同的磁盘中,从多个磁盘读取可以增加吞吐量。

4.4 其他特性

  1. 列抽样(column sample) :XGBoost 借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算;
  2. Shrinkage(缩减):相当于学习速率。XGBoost 在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间;
  3. 支持自定义损失函数(需二阶可导)

5. 总结

XGBoost 优点

  1. 利用了二阶梯度来对节点进行划分,相对其他 GBM 来说,精度更加高。
  2. 利用局部近似算法对分裂节点的贪心算法优化,取适当的 eps 时,可以保持算法的性能且提高算法的运算速度。
  3. 在损失函数中加入了 L1/L2 项,控制模型的复杂度,提高模型的鲁棒性。
  4. 提供并行计算能力,主要是在树节点求不同的候选的分裂点的 Gain Infomation(分裂后,损失函数的差值)。
  5. 可以找到精确的划分条件

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

XGBoost 缺点

  • 每次迭代训练时需要读取整个数据集,耗时耗内存;每轮迭代时,都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小;如果不装进内存,反复地读写训练数据又会消耗非常大的时间。
  • 使用 Basic Exact Greedy Algorithm 计算最佳分裂节点时需要预先将特征的取值进行排序,排序之后为了保存排序的结果,费时又费内存;需要pre-sorted,这个会耗掉很多的内存空间(2 * #data * # features)。
  • 计算分裂节点时需要遍历每一个候选节点,然后计算分裂之后的信息增益,费时;数据分割点上,由于 XGBoost 对不同的数据特征使用 pre-sorted 算法而不同特征其排序顺序是不同的,所以分裂时需要对每个特征单独做依次分割,遍历次数为 (#data * #features) 来将数据分裂到左右子节点上。
  • 由于 pre-sorted 处理数据,在寻找特征分裂点时(level-wise),会产生大量的cache随机访问。生成决策树是 level-wise 级别的,也就是预先设置好树的深度之后,每一颗树都需要生长到设置的那个深度,这样有些树在某一次分裂之后效果甚至没有提升但仍然会继续划分树枝,然后再次划分….之后就是无用功了,耗时。
  • 尽管使用了局部近似计算,但是处理粒度还是太细了。
  • 计算量巨大
  • 内存占用巨大
  • 易产生过拟合
  • 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量,但在节点分裂过程中仍需要遍历数据集;
  • 预排序过程的空间复杂度过高,不仅需要存储特征值,还需要存储特征对应样本的梯度统计值的索引,相当于消耗了两倍的内存。

6. Q & A

6.1 XGBoost 与 GBDT 有什么不同?

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

6.2 XGBoost 为什么使用泰勒二阶展开

  • 精准性:相对于 GBDT 的一阶泰勒展开,XGBoost 采用二阶泰勒展开,可以更为精准的逼近真实的损失函数。可以想象成一阶导数只知道当前情况下往哪个方向跨多少是比较好的,二阶导数可以知道当前跨的这一步能够如何影响后续的路程(好像有人已经告诉你后面路程的规划)。
  • 可扩展性:损失函数支持自定义,只需要新的损失函数二阶可导。

6.3 XGBoost 为什么可以并行训练

  • XGBoost 的并行,并不是说每棵树可以并行训练,XGBoost 本质上仍然采用 boosting 思想,每棵树训练前需要等前面的树训练完成才能开始训练。
  • XGBoost 的并行,指的是特征维度的并行:在训练之前,每个特征按特征值对样本进行预排序,并存储为 Block 结构,在后面查找特征分割点时可以重复使用,而且特征已经被存储为一个个 block 结构,那么在寻找每个特征的最佳分割点时,可以利用多线程对每个 block 并行计算。

6.4 XGBoost 为什么快

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

6.5 XGBoost 防止过拟合的方法

  XGBoost在设计时,为了防止过拟合做了很多优化,具体如下:

  1. 目标函数添加正则项:叶子节点个数 + 叶子节点权重的 L2 正则化
  2. 列抽样:训练的时候只用一部分特征(不考虑剩余的 Block 块即可)
  3. 子采样:每轮计算可以不使用全部样本,使算法更加保守
  4. Shrinkage: 可以叫学习率或步长,为了给后面的训练留出更多的学习空间

6.6 XGBoost 如何处理缺失值

XGBoost 模型的一个优点就是允许特征存在缺失值。对缺失值的处理方式如下:

  1. 在特征 $k$ 上寻找最佳 split point 时,不会对该列特征 missing 的样本进行遍历,而只对该列特征值为 non-missing 的样本上对应的特征值进行遍历,通过这个技巧来减少了为稀疏离散特征寻找 split point 的时间开销。
  2. 在逻辑实现上,为了保证完备性,会将该特征值 missing 的样本分别分配到左叶子结点和右叶子结点,两种情形都计算一遍后,选择分裂后增益最大的那个方向(左分支或是右分支),作为预测时特征值缺失样本的默认分支方向。
  3. 如果在训练中没有缺失值而在预测中出现缺失,那么会自动将缺失值的划分方向放到右子结点。

.7. XGBoost 中叶子结点的权重如何计算出来

  具体查看第二节。

6.8 XGBoost 中的一棵树的停止生长条件

  • 当新引入的一次分裂所带来的增益 Gain < 0 时,放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。
  • 当树达到最大深度时,停止建树,因为树的深度太深容易出现过拟合,这里需要设置一个超参数 max_depth。
  • 当引入一次分裂后,重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值,也会放弃此次分裂。这涉及到一个超参数:最小样本权重和,是指如果一个叶子节点包含的样本数量太少也会放弃分裂,防止树分的太细。

6.9 XGBoost 如何处理不平衡数据

  对于不平衡的数据集,例如用户的购买行为,肯定是极其不平衡的,这对 XGBoost 的训练有很大的影响,XGBoost有两种自带的方法来解决:

  1. 如果你在意 AUC,采用 AUC 来评估模型的性能,那你可以通过设置 scale_pos_weight 来平衡正样本和负样本的权重。例如,当正负样本比例为1:10时,scale_pos_weight 可以取10;

  2. 如果你在意概率(预测得分的合理性),你不能重新平衡数据集(会破坏数据的真实分布),应该设置 max_delta_step 为一个有限数字来帮助收敛(基模型为 LR 时有效)。

  那么,源码到底是怎么利用 scale_pos_weight 来平衡样本的呢,是调节权重还是过采样呢?请看源码:

if (info.labels[i] == 1.0f)  w *= param_.scale_pos_weight

  可以看出,应该是增大了少数样本(?)的权重。

  除此之外,还可以通过上采样、下采样、SMOTE 算法或者自定义代价函数的方式解决正负样本不平衡的问题。

6.10 XGBoost 中如何对树进行剪枝

  1. 在目标函数中增加了正则项:使用叶子结点的数目和叶子结点权重的L2模的平方,控制树的复杂度。
  2. 在结点分裂时,定义了一个阈值,如果分裂后目标函数的增益小于该阈值,则不分裂。
  3. 当引入一次分裂后,重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值(最小样本权重和),也会放弃此次分裂。
  4. XGBoost 先从顶到底建立树直到最大深度,再从底到顶反向检查是否有不满足分裂条件的结点,进行剪枝。

6.11 XGBoost 如何选择最佳分裂点

  XGBoost 在训练前预先将特征按照特征值进行了排序,并存储为 block 结构,以后在结点分裂时可以重复使用该结构。

  因此,可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点,根据每次分裂后产生的增益,最终选择增益最大的那个特征的特征值作为最佳分裂点。

  如果在计算每个特征的最佳分割点时,对每个样本都进行遍历,计算复杂度会很大,这种全局扫描的方法并不适用大数据的场景。XGBoost 还提供了一种直方图近似算法,对特征排序后仅选择常数个候选分裂位置作为候选分裂点,极大提升了结点分裂时的计算效率。

6.12 XGBoost 的 Scalable 性如何体现

  1. 基分类器的 scalability:弱分类器可以支持 CART 决策树,也可以支持 LR 和 Linear。
  2. 目标函数的 scalability:支持自定义 loss function,只需要其一阶、二阶可导。有这个特性是因为泰勒二阶展开,得到通用的目标函数形式。
  3. 学习方法的 scalability:Block 结构支持并行化,支持 Out-of-core 计算。

6.13 XGBoost 如何评价特征的重要性

  我们采用三种方法来评判 XGBoost 模型中特征的重要程度:

  1. weight :该特征在所有树中被用作分割样本的特征的总次数。
  2. gain :该特征在其出现过的所有树中产生的平均增益。
  3. cover :该特征在其出现过的所有树中的平均覆盖范围。

  注意:覆盖范围这里指的是一个特征用作分割点后,其影响的样本数量,即有多少样本经过该特征分割到两个子节点。

6.14 XGBooost 参数调优的一般步骤

  首先需要初始化一些基本变量,例如:

  • max_depth = 5
  • min_child_weight = 1
  • gamma = 0
  • subsample, colsample_bytree = 0.8
  • scale_pos_weight = 1

(1) 确定learning rate和estimator的数量

  learning rate 可以先用 0.1,用 cv 来寻找最优的 estimators

(2) max_depth和 min_child_weight

  我们调整这两个参数是因为,这两个参数对输出结果的影响很大。我们首先将这两个参数设置为较大的数,然后通过迭代的方式不断修正,缩小范围。

  • max_depth,每棵子树的最大深度,check from range(3,10,2)。

  • min_child_weight,子节点的权重阈值,check from range(1,6,2)。

  如果一个结点分裂后,它的所有子节点的权重之和都大于该阈值,该叶子节点才可以划分。

(3) gamma

  也称作最小划分损失 min_split_loss,check from 0.1 to 0.5,指的是,对于一个叶子节点,当对它采取划分之后,损失函数的降低值的阈值。

  • 如果大于该阈值,则该叶子节点值得继续划分
  • 如果小于该阈值,则该叶子节点不值得继续划分

(4) subsample, colsample_bytree

  • subsample 是对训练的采样比例

  • colsample_bytree 是对特征的采样比例

  • both check from 0.6 to 0.9

(5) 正则化参数

  • alpha 是L1正则化系数,try 1e-5, 1e-2, 0.1, 1, 100

  • lambda 是L2正则化系数

(6) 降低学习率

  降低学习率的同时增加树的数量,通常最后设置学习率为0.01~0.1

6.15 XGBoost模型如果过拟合了怎么解决

  当出现过拟合时,有两类参数可以缓解:

  1. 第一类参数:用于直接控制模型的复杂度。包括 max_depth, min_child_weight, gamma 等参数
  2. 第二类参数:用于增加随机性,从而使得模型在训练时对于噪音不敏感。包括subsample, colsample_bytree

  还有就是直接减小 learning rate,但需要同时增加 estimator 参数。

6.16 为什么 XGBoost 相比某些模型对缺失值不敏感

  对存在缺失值的特征,一般的解决方法是:

  • 离散型变量:用出现次数最多的特征值填充;
  • 连续型变量:用中位数或均值填充;

  一些模型如SVM和KNN,其模型原理中涉及到了对样本距离的度量,如果缺失值处理不当,最终会导致模型预测效果很差。

  而树模型对缺失值的敏感度低,大部分时候可以在数据缺失时时使用。原因就是,一棵树中每个结点在分裂时,寻找的是某个特征的最佳分裂点(特征值),完全可以不考虑存在特征值缺失的样本,也就是说,如果某些样本缺失的特征值缺失,对寻找最佳分割点的影响不是很大。

  XGBoost对缺失数据有特定的处理方法,详情参考上面问 6.6。

  因此,对于有缺失值的数据在经过缺失处理后:

  • 当数据量很小时,优先用朴素贝叶斯
  • 数据量适中或者较大,用树模型,优先XGBoost
  • 数据量较大,也可以用神经网络
  • 避免使用距离度量相关的模型,如KNN和SVM

6.17 XGBoost 和 LightGBM 的区别

(1)树生长策略:XGB采用level-wise的分裂策略,LGB采用leaf-wise的分裂策略。XGB对每一层所有节点做无差别分裂,但是可能有些节点增益非常小,对结果影响不大,带来不必要的开销。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的,但是很容易出现过拟合问题,所以需要对最大深度做限制 。

(2)分割点查找算法:XGB使用特征预排序算法,LGB使用基于直方图的切分点算法,其优势如下:

  • 减少内存占用,比如离散为256个bin时,只需要用8位整形就可以保存一个样本被映射为哪个bin(这个bin可以说就是转换后的特征),对比预排序的exact greedy算法来说(用int_32来存储索引+ 用float_32保存特征值),可以节省7/8的空间。
  • 计算效率提高,预排序的Exact greedy对每个特征都需要遍历一遍数据,并计算增益,复杂度为 $O(\text{#} feature × \text{#}data)$。而直方图算法在建立完直方图后,只需要对每个特征遍历直方图即可,复杂度为𝑂(#𝑓𝑒𝑎𝑡𝑢𝑟𝑒×#𝑏𝑖𝑛𝑠)。
  • LGB还可以使用直方图做差加速,一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到,从而加速计算

但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法,为什么xgboost的近似算法比lightgbm还是慢很多呢? xgboost在每一层都动态构建直方图, 因为xgboost的直方图算法不是针对某个特定的feature,而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图,而lightgbm中对每个特征都有一个直方图,所以构建一次直方图就够了。

(3)支持离散变量:无法直接输入类别型变量,因此需要事先对类别型变量进行编码(例如独热编码),而LightGBM可以直接处理类别型变量。

(4)缓存命中率:XGB使用Block结构的一个缺点是取梯度的时候,是通过索引来获取的,而这些梯度的获取顺序是按照特征的大小顺序的,这将导致非连续的内存访问,可能使得CPU cache缓存命中率低,从而影响算法效率。而LGB是基于直方图分裂特征的,梯度信息都存储在一个个bin中,所以访问梯度是连续的,缓存命中率高。

(5)LightGBM 与 XGboost 的并行策略不同:

  • 特征并行 :LGB特征并行的前提是每个worker留有一份完整的数据集,但是每个worker仅在特征子集上进行最佳切分点的寻找;worker之间需要相互通信,通过比对损失来确定最佳切分点;然后将这个最佳切分点的位置进行全局广播,每个worker进行切分即可。XGB的特征并行与LGB的最大不同在于XGB每个worker节点中仅有部分的列数据,也就是垂直切分,每个worker寻找局部最佳切分点,worker之间相互通信,然后在具有最佳切分点的worker上进行节点分裂,再由这个节点广播一下被切分到左右节点的样本索引号,其他worker才能开始分裂。二者的区别就导致了LGB中worker间通信成本明显降低,只需通信一个特征分裂点即可,而XGB中要广播样本索引。

  • 数据并行 :当数据量很大,特征相对较少时,可采用数据并行策略。LGB中先对数据水平切分,每个worker上的数据先建立起局部的直方图,然后合并成全局的直方图,采用直方图相减的方式,先计算样本量少的节点的样本索引,然后直接相减得到另一子节点的样本索引,这个直方图算法使得worker间的通信成本降低一倍,因为只用通信以此样本量少的节点。XGB中的数据并行也是水平切分,然后单个worker建立局部直方图,再合并为全局,不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引,因此效率贼慢,每个worker间的通信量也就变得很大。

  • 投票并行(LGB):当数据量和维度都很大时,选用投票并行,该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大,尤其是当特征维度很大时。大致思想是:每个worker首先会找到本地的一些优秀的特征,然后进行全局投票,根据投票结果,选择top的特征进行直方图的合并,再寻求全局的最优分割点。

References

  1. Boosted Tree by Tianqi Chen
  2. Loss function Approximation With Taylor Expansion
  3. Tree Boosting With XGBoost
  4. Introduction to Boosted Trees
  5. Newton Boosting Tree 算法原理:详解 XGBoost
  6. 机器学习竞赛大杀器XGBoost–原理篇
  7. Gradient Boosting梯度提升-GBDT与XGBoost解析及应用
  8. 视频讲解
  9. gbdt-xgboost
  10. 数据竞赛利器XGBoost常见面试题集锦
  11. 集成学习(三)XGBoost