↓Skip to main content

重读XGBoost

·7 mins
Paper Machine Learning Xgboost
Table of Contents

在使用xgboost方法调参时，对其中个别参数不是特别理解。故重新读了一遍原论文。

1. 引言 #

阐述机器学习和数据驱动的方法应用时两个重要的因素：

  • 能捕捉数据间复杂依赖关系的模型
  • 可扩展的学习系统，可以从大量数据中学习

在目前常用的方法中，梯度提升树（gradient tree boosting）在许多场景中效果都不错，作者列举了一些。提出xgboost方法在比赛以及各类问题中的应用。

叙述XGBoost的优点：运行更快、拓展性更好。创新点包括：

  • 高度可拓展的端到端提升树（tree boosting）系统
  • 用于高效计算的加权分位数图（weighted quantile sketch）
  • 新颖的稀疏感知算法（sparsity-aware algorithm），用于并行树学习
  • 有效的缓存优化以及块（cache-aware block）结构用于外存（out-of-core）树学习 关于以上几点在正文中详解。

论文结构：

  1. 提升树（tree boosting）简介以及目标函数正则化
  2. 分裂点寻找的方法
  3. 系统设计，包括为每个优化提供量化支持的结果
  4. 相关工作
  5. 详细的端到端评估
  6. 总结

2. 提升树（Tree Boosting）简介 #

首先需要了解CART（Classification And Regression Tree）算法，对于cart分类树和回归树分别采用了：Gini系数、和方差度量方式来划分节点[1]。例如回归树，对于划分特征A, 划分点s使两边数据集D1和D2,求出使 D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小。 $$\underline{min}_{\text{A,s}}[\underline{min}_{\text{c1}}\sum_{x_i\in{D1(A,s)}}(y_i - c1)^2+\underline{min}_{\text{c2}}\sum_{x_i\in{D2(A,s)}}(y_i - c2)^2]$$ 其中，c1为D1的样本输出均值，c2为D2的样本输出均值, 回归树采用叶子节点的均值或者中位数来预测输出结果，$y_i$即样本的label，此时的输出值即下文中用到的$w_{q(x)}$。

2.1 正则化目标函数 #

对于这种类型的集成树模型，用K棵树的结果来预测最后的结果（式1），那么问题来了我们怎么来求这些树的参数，每棵树都可以看做一个函数$f_i$包含树的结构以及最后叶节点权重，集成模型不像传统优化问题一样通过简单用梯度下降可以对所有的树进行学习求解，所以，在这里用到了加法策略，即固定已经学习到的，每次加一棵树来进行学习（式3）。 $$\hat{y_i} = \phi(x_i) = \sum_{k = 1}^{K} f_k(x_i)\tag1$$ 其中$f(x) = w_{q(x)}$，每个$f_k$对应一个独立的树结构q以及其叶节点权重w，为了学习模型中的参数，最小化下面正则化的目标函数。 $$L(\phi) = \sum_i l(\hat{y_i}, y_i) + \sum_k \Omega(f_k)\tag2$$

$$\Omega(f_k) = \gamma T + \frac{1}{2}\lambda||w||^2$$ T是树的叶节点数

2.2 梯度提升树（Gradient Tree Boosting） #

第t次预测值等于t-1加上第t棵树的结果 $$\hat{y_i} = \hat{y_i}^{t-1} + f_t(x_i)\tag3$$ 此时目标函数(式2)可以写成 $$L^{(t)} = \sum_{i=1} ^n l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i)) + \Omega(f_t)\tag4$$ 该式子的二阶近似可以表达为(式5），可以参考补充中二阶泰勒展开的一般形式 $$L^{(t)} \approx \sum_{i=1} ^n [l(y_i, \hat{y_i}^{(t-1)}) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\tag5$$ 其中 $g_i=\partial_{\hat{y}^{(t-1)}}{l(y_i, \hat{y_i}^{(t-1)})}， h_i=\partial_{\hat{y}^{(t-1)}}^2{l(y_i, \hat{y_i}^{(t-1)})}$

式5中去掉常数项，即label与第t-1次结果的损失函数，可以得到：

$$\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)\tag6$$

式6即对新树的优化目标函数，进一步合并可以写为：

$$obj^{t} \approx \sum_{i=1}^{n}[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T+ \frac{1}{2}\lambda \sum _{j=1}^T w_j^2$$

定义$I_j = {i|q(x_i)=j}$即叶节点j上的实例。

$$obj^{t} \approx \sum_{j=1}^T[(\sum_{i\in{I_j}}g_i)w_j+\frac{1}{2}(\sum_{i\in{I_j}}h_i+\lambda)w_j^2]+\gamma T\tag7$$

上式7对$w_j$求导即可求出w最优值

$$w_j^* = -\frac{\sum_{i\in{I_j}}g_i}{\sum_{i\in{I_j}}h_i+\lambda} $$

令$G_j = \sum_{i\in{I_j}}g_i，H_j=\sum_{i\in{I_j}}h_i$

此时，对应的最小值为: $$obj^* = -\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T$$ $\color{red}\frac{G_j^2}{H_j+\lambda}$越大，loss越小，所以对叶节点进行分裂，分裂后增益定义为 $$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma\tag8$$

2.3 缩减和列抽样（Shrinkage and Column Subsampling） #

除了在目标函数中引入正则项，在防止过拟合方面xgboost还运用了两项技术，给每一步tree boosting得到的结果一个权重$\eta$，来降低每一步的影响从而给后面树的形成留下空间，比喻成优化问题中的学习率缩减；同时还用到随机森林中的列抽样，即随机特征筛选。

3. 分裂点寻找算法 #

3.1 精确贪婪算法（Basic Exact Greedy Algorithm） #

即按照2.2中式8来寻找分裂点 pythonscikit-learn，Rgbm，单机的xgboost都支持。

3.2 近似算法（Approximate Algorithm） #

精确贪婪算法由于列举了所有可能的分裂点，在数据量很大不能全部写入内存时会导致不是那么高效。所以提出近似算法。对于每个特征，只考察分位点，减少计算复杂度。 近似算法存在两个变种：

  • global: 学习每棵树前，提出候选分裂点
  • local: 每次分裂前，重新提出候选分裂点

3.3 加权分位数图（Weighted Quantile Sketch） #

近似算法中最重要一点即提出候选分裂点，xgboost不是简单的按照样本个体进行分位，而是以损失函数二阶导数值作为权重进行分位数分裂。如何寻找二阶导数分位点，首先是利用权重计算排序函数，然后相邻相减值作为判断依据。问题是为什么会想到利用损失函数二阶导数值作为权重来划分。 文中给出式6可以变形为 $$\sum_{i=1}^n\frac{1}{2}h_i(f_t(x_i)-g_i/h_i)^2 + \Omega(f_t) + constant\tag9$$ 指出该式恰好是权重平方差损失函数，权重$h_i$以及label $g_i/h_i$ 自己从式6变不到式9，觉得中间符号是+还差不多。 看有人理解说变成式10才对。是否作者真的是这样想的，不得而知。欢迎指正。 $$\sum_{i=1}^n\frac{1}{2}h_i(f_t(x_i)-(-g_i/h_i))^2 + \Omega(f_t) + constant\tag{10}$$ stackexchange上关于理解xgboost近似分裂点

3.4 稀疏值感知分裂（Sparsity-aware split finding） #

造成稀疏值的原因：1）缺失值 2）统计过程中频繁的0值输入 3）one-hot编码以及其他特征工程 所以让算法注意数据中稀疏规律很重要，遍历所有特征，在划分子节点时，统一将该特征的缺失值划分到右支或者左支，计算最大的gain。

$\color{red}这里也有个疑问就是为什么排序第一次是升序，第二次是降序$

4. 系统设计 #

4.1 分块并行（Column Block for Parallel Learning） #

基于树学习过程中最耗时的是将数据排序，为了减少排序的时间成本，提出基于内存的block结构。

  • 在Exact greedy算法中，将整个数据集存放在一个Block中
  • 在近似算法中，使用多个Block，每个Block对应原来数据的子集。不同的Block可以在不同的机器上并行计算

4.2 缓存优化 #

这里指利用CPU缓存对算法进行优化。

4.1中column block按特征大小顺序存储，相应的样本的梯度信息是分散的，造成内存的不连续访问，降低CPU cache命中率。 优化方法：

  • 对于精确贪婪算法，预取数据到buffer中（非连续->连续），再统计梯度信息。
  • 对于近似算法，调节block的大小，设置过大则容易导致命中率低，过小则容易导致并行化效率不高。

4.3 外存计算 #

除了处理器以及内存，利用磁盘空间来处理不能进入内存的数据也十分重要，数据划分为多个Block并存放在磁盘上。计算的时候，使用独立的线程预先将Block放入主内存，因此可以在计算的同时读取磁盘。在减少计算资源开销以及提高磁盘输入输出方面主要用到以下技术：

  • Block压缩，按列压缩，加载到主内存时由独立线程动态解压缩。具体压缩技术参看原文。
  • Block Sharding，将数据划分到不同硬盘上，提高磁盘吞吐率。

5. 端到端评估 #

利用4个数据集对xgboost评估：

  • 分类问题
  • 排序问题
  • 外存计算实验
  • 分布计算实验

这几个方面进行评估，详细结果见论文。

ref #

  1. CART分类树与回归树
  2. Markdown数学公式
  3. Mathjax应用在网页
  4. XGBoost.ppt
  5. readthedocs xgboost tutorials推荐
  6. gbdt.ppt
  7. xgboost原文

补充 #

  1. 文中很多术语翻译可能有不恰当的地方，欢迎指出。
  2. 二阶泰勒展开的一般形式： $$f(x^t) = f(x^{t-1}+\Delta x)\approx{f(x^{t-1})+ f^{\prime}(x^{t-1})\Delta{x}+f^{\prime\prime}(x^{t-1})\frac{\Delta x^2}{2}}$$
  3. 式4中加入loss function是mean squared error(MSE)，可以求出相应的gi， hi作为一个特例来验证该做法。
  4. 基于树的算法理解时带着这几个问题去理解每一步是用来做什么的：选择哪个特征进行分裂？在特征什么点位进行分裂？分裂后叶节点取什么值？

    分别对应：遍历每个特征，加权分位数图，$w_j$

  5. 对于系统设计中应用到的技术理解不是十分深刻，对应一个算法如何从计算机硬件的方方面面考虑去优化对非专业领域研究者还是比较难