论文笔记 | KDD2016 | XGBoost: A Scalable Tree Boosting System

xgb-title.jpg

一为什么读这篇

虽然几年前xgb刚出来时就有开始用，各种解读，教程也读了不少，惭愧的是原始论文居然从来没读过。正好最近在做搜索的事，很多地方都用到了lightgbm，按脉络上来讲xgb是lightgbm的前辈，借此机会通过论文这个第一手资料重温下xgb的实现原理，后面接着再去看lightgbm。

二相关背景介绍

搞机器学习，数据挖掘的相关从业人员对xgb和陈天奇应该很熟悉了，无需多言，截止阅读时这篇论文的引用次数为5644。

三关键词及主要贡献

关键词：gbdt，xgb

1 提供xgboost这个大杀器，横扫各大数据挖掘比赛

2 对gbdt工程上的，算法上的优化

四详细解读

0 摘要

本文针对稀疏数据和加权分位数缩略图提出了一种新的稀疏感知算法，用于近似树学习。更重要的是，本文提供了对缓存访问模式，数据压缩和分片的见解，以构建一个可扩展的树提升系统。

1 介绍

梯度提升树（GBM，GBRT）在分类任务上，其变种LambdaMART在排序任务上都取得了SOTA。Facebook的GBDT+LR也用在了真实生产环境上。2015年期间，29个kaggle比赛的winner有17个用了XGBoost。

XGBoost的可扩展性源于几个重要的系统和算法优化：一种创新的用于处理稀疏数据的树学习算法；一种理论上得到保证的加权分位数缩略图程序，可以在近似树学习中处理样本权重；并行和分布式计算可以使学习更快，从而使模型探索速度更快。

本文的主要贡献如下：

设计并构建了一个高度可扩展的端到端树提升系统
提出了理论上合理的加权分位数缩略图，用于高效的候选计算
介绍了一种新型的稀疏感知算法，用于并行树学习
提出了一种有效的缓存感知块结构，用于外存上的树学习

除了这些主要贡献外，也通过提出的正则化学习目标做出了额外的提升。

2 提升树概要

2.1 带正则化的学习目标

给定n个样本，m个特征的数据集： $\mathcal{D}=\left\{\left(\mathbf{x}_{i}, y_{i}\right)\right\}\left(|\mathcal{D}|=n, \mathbf{x}_{i} \in \mathbb{R}^{m}, y_{i} \in \mathbb{R}\right)$ ，一个融合树模型（如图1所示）使用K个加法函数来预测输出：
$\hat{y}_{i}=\phi\left(\mathbf{x}_{i}\right)=\sum_{k=1}^{K} f_{k}\left(\mathbf{x}_{i}\right), \quad f_{k} \in \mathcal{F}$

xgb-fig1.jpg

其中 $\mathcal{F}=\left\{f(\mathbf{x})=w_{q(\mathbf{x})}\right\}\left(q: \mathbb{R}^{m} \rightarrow T, w \in \mathbb{R}^{T}\right)$ 是回归树（CART）的空间。这里的 $q$ 表示每棵树的结构，它把一个样本映射为相应的叶子索引。 $T$ 是树中叶子的个数。每个 $f_{k}$ 对应着独立的树结构 $q$ 和叶子权重 $w$ 。与决策树不同的是，每个回归树在每个叶子上包含一个连续的分数，用 $\boldsymbol{w}_{i}$ 表示第i个叶子的分数。给定一条样本，使用树（由 $q$ 得到）的决策规则来将它分到叶子上，同时通过累加在相应叶子的分数（由 $w$ 得到）来计算最终预测。为了学习模型中使用的函数集合，需要最小化如下的带正则化的目标
$\begin{array}{l} \mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right) \\ \text { where } \Omega(f)=\gamma T+\frac{1}{2} \lambda\|w\|^{2} \end{array}$
这里的 $l$ 是一个可微凸损失函数，它用来衡量预测值 $\hat{y}_{i}$ 和目标值 $y_{i}$ 的差异。第二项 $\Omega$ 对模型的复杂性进行惩罚。增加的正则项有助于平滑最终学习到的权重以避免过拟合。

2.2 梯度树提升

模型通过递增地方式训练。通常，定义 $\hat{y}_{i}^{(t)}$ 为第i个样本在第t次迭代的预测，需要增加 $f_{t}$ 来最小化如下的目标
$\mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right)$
这意味着通过等式2，可以贪婪地添加最能改善模型的 $f_{t}$ 。二阶近似可以用来快速优化目标：
$\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)$
其中 $g_{i}=\partial_{\hat{y}(t-1)} l\left(y_{i}, \hat{y}^{(t-1)}\right)$ 和 $h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)$ 分别是损失函数的一阶，二阶梯度。可以移除常数项来得到在第t步的简化的目标：
$\tilde{\mathcal{L}}^{(t)}=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)$
定义 $I_{j}=\left\{i | q\left(\mathbf{x}_{i}\right)=j\right\}$ 为叶子 $j$ 的样本集合。这样可以通过扩展 $\Omega$ 重写上式：
$\begin{aligned} \tilde{\mathcal{L}}^{(t)} &=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\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 \end{aligned}$
对于固定的结构 $q(\mathbf{x})$ ，可以通过下式计算叶子 $j$ 的优化权重 $w_{j}^{*}$ ：
$w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}$
同时也可通过下式计算相应的优化值：
$\tilde{\mathcal{L}}^{(t)}(q)=-\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T$
上式可以作为一个评分函数，用于衡量树结构 $q$ 的质量。该分数类似于评估决策树的杂质分数，不同之处在于它是通过更广泛的目标函数得到的。图2说明了该分数是如何计算的。

xgb-fig2.jpg

迭代所有可能的树结构 $q$ 通常是不可能的，因此用一种贪婪算法来替代，它从单个叶子开始，然后迭代地向树中添加分支。定义 $I_{L}$ 和 $I_{R}$ 分别为分割后左节点和右节点的样本集合。令 $I=I_{L} \cup I_{R}$ ，之后分割后的损失减少量通过下式得到：
$\mathcal{L}_{s p l i t}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma$
在实践中该式也用于评估分割候选。

2.3 收缩和列采样

除了正则化之外，还有两种方法也可以阻止过拟合。一种是Friedman于2002提出的shrinkage（收缩）。在每一步树提升之后，收缩通过因子 $\eta$ 按比例新增权重。类似于随机优化中的学习率，缩放减少了每个独立树的影响，给后来的树留下空间以提升模型。另一种是用于随机森林的列采样。据用户反馈，使用列采样比行采样更能阻止过拟合，同时也加速了计算。

3 分割查找算法

3.1 基础的精确贪婪算法

树学习的一个关键问题就是找到最佳分割点。为了达到该目的，在全部特征上枚举所有可能分割的发现算法称之为精确贪婪算法，该算法如图所示：

xgb-alg1.jpg

对于连续特征，它的计算要求枚举所有可能的分割点。为了有效的实现这一目标，该算法必须首先根据特征值对数据进行排序，并以排序的顺序访问数据，以便累加公式7中的结构化分数的累积梯度统计量。

3.2 近似算法

精确贪婪算法有个问题是当数据不能都装进内存时便失效了。近似框架如算法2所示：

xgb-alg2.jpg

总结一下，该算法首先根据特征分布百分比提出候选分割点（一种特殊的规范可见3.3节），之后通过这些候选点将连续特征映射为桶分割，将统计数据进行汇总，并根据汇总后的统计数据，在候选中找到最佳的方案。

该算法有两种变种，取决于什么时候提出候选。两种变种的效果如图3所示：

xgb-fig3.jpg

xgboost即支持精确贪婪算法，也支持全局和局部候选提出近似算法。

3.3 加权分位数缩略图

近似算法的一个重要步骤就是提出候选分割点。定义多个集合 $\mathcal{D}_{k}=\left\{\left(x_{1 k}, h_{1}\right),\left(x_{2 k}, h_{2}\right) \cdots\left(x_{n k}, h_{n}\right)\right\}$ 表示每个训练样本的第k个特征值和二阶导数统计量（总共n个训练样本）。定义排序函数 $r_{k}: \mathbb{R} \rightarrow[0,+\infty)$ 如下式表示：
$r_{k}(z)=\frac{1}{\sum_{(x, h) \in \mathcal{D}_{k}} h} \sum_{(x, h) \in \mathcal{D}_{k}, x<z} h$
该式表示特征值 $k$ 小于 $z$ 的样本的比例。目标是发现候选分割点 $\left\{s_{k 1}, s_{k 2}, \cdots s_{k l}\right\}$ ，如下所示：
$\left|r_{k}\left(s_{k, j}\right)-r_{k}\left(s_{k, j+1}\right)\right|<\epsilon, \quad s_{k 1}=\min _{i} \mathbf{x}_{i k}, s_{k l}=\max _{i} \mathbf{x}_{i k}$
此处 $\epsilon$ 是近似因子。直觉上看，这意味着有接近 $1 / \epsilon$ 个候选点。每个数据点的权重是 $h_{i}$ 。为什么 $h_{i}$ 可以表示权重，可以重写公式3得到：
$\sum_{i=1}^{n} \frac{1}{2} h_{i}\left(f_{t}\left(\mathbf{x}_{i}\right)-g_{i} / h_{i}\right)^{2}+\Omega\left(f_{t}\right)+\text { constant }$
恰好是带有标签 $g_{i} / h_{i}$ 和权重 $h_{i}$ 的加权平方损失。当每个样本有相同的权重时，一个称之为分位数缩略图（quantile sketch）的算法可以解这个问题。然而，当前没有针对加权数据的分位数缩略图算法。因此，当前大多数近似算法要么采取可能失败的随机子数据集进行排序，要么采用没有理论保证的启发式算法。

为了解这个问题，本文发明一种新的有理论保证的分布式加权分位数缩略图算法来处理加权数据。总体思路是提出一种支持合并和剪枝运算的数据结构，并证明每个运算都可以保持一定的准确性。具体细节可见附录。

3.4 稀疏感知分割查找

使算法能感知到数据中的稀疏模式是重要的，为了实现这一点，本文提出为每个树的节点加一个默认方向，如图4所示。

xgb-fig4.png

当在稀疏矩阵 $x$ 中的值缺失时，该实例会按默认方向进行分类。每个分支上有2个默认方向的选择，优化默认方向是从数据中进行学习，如算法3所示：

xgb-alg3.png

关键的改进是仅访问非缺失的 $I_{k}$ 。

本文方法利用稀疏性使计算复杂度与输入中的非缺失项的数量成线性关系。相比原始算法要快50倍，如图5所示

xgb-fig5.png

4 系统设计

4.1 用于并行学习的列块

树学习最耗时的地方在于把数据变为有序。为了减少排序的消耗，本文提出以内存为单位存储数据，称之为块。每一个快中的数据用压缩列（CSC）格式存储，每个列通过相应的特征值排序。此输入数据布局仅需在训练之前计算一次，即可在以后的迭代中重用。图6展示了如何把数据集变换为这种格式，并使用块结构来发现最优分割点。

xgb-fig6.png

4.2 缓存感知访问

xgb-fig8.png

xgb-fig7.png

xgb-fig9.png

4.3 用于内存外计算的块

块压缩

分块

5 相关工作

xgb-table1.png

6 端到端评估

6.1 系统实现

6.2 数据集和设置

xgb-table2.png

在全部实验中，树的最大深度通常设置为8，收缩率设置为0.1，没有列采样

6.3 分类

xgb-table3.png

这里列采样有负效果

6.4 LTR

xgb-table4.png

xgb-fig10.png

这里列采样又有效了。。

6.5 内存外实验

xgb-fig11.png

6.6 分布式实验

xgb-fig12.png

xgb-fig13.png

五小结

读完原文才知道，原来xgb的论文更偏工程化。讲了许多怎么提速的技术，反正就一个快字。实验部分效果上没啥亮眼的地方，不过速度是真的快，各种秒杀竞对。其实近似算法用来选择分割点的也是为了提速的目的。

论文笔记 | KDD2016 | XGBoost: A Scalable Tree Boosting System

论文笔记 | KDD2016 | XGBoost: A Scalable Tree Boosting System

一为什么读这篇

二相关背景介绍

三关键词及主要贡献

四详细解读

0 摘要