为什么XGBoost效果更好，速度更快

xgboost 是一种集成学习方法，通过构建多棵决策树来实现分类和回归任务。

本文记录了xgboost的公式推导和系统实现的一些trick。 具体内容参加原论文《XGBoost: A Scalable Tree Boosting System》

模型描述

对于一棵决策树，给定以下符号表示 $|T|$: 此棵树的叶子节点数 $q(\text{x})$: $\text{x}$将会被映射到的叶子节点， 故$q(x)$的取值范围是$[1,|T|]$ ${\text{w}}_j$: 第j个叶子节点的输出值。

如果将一棵决策树视为一个函数，则可以写成 $$f(\text{x})=w_{q(\text{x})}$$

由于xgboost是使用多棵决策树，并且每棵树学习的上一棵树的残差，故xgboost的输出公式为 $$\widehat{y_i}=\sum _{k=1}^K{f}_k({\text{x}}_i)$$

其中第$f_k$表示第k棵决策树，xgboost会在每一次迭代中生成一棵新的决策树。

目标函数

xgboost的目标函数 $$L=\sum _{i}l({\hat{y}}_i,y_i)+\sum _k\Omega (f_k)$$

$$\Omega (f)=\gamma T+\frac{1}{2}\lambda \Vert w{\Vert }^2$$

第一项用来衡量模型的分类的错误率,这里用来描述$\hat{y},y$之间的距离函数$l$, 并没有指定，可以使用平方差或者其他的损失函数。第二项用于控制模型的复杂度

梯度提升算法

由于$f$是一棵树，无法用梯度下降或者牛顿法这种方法进行优化，所以xgboost采用前向分步算法。这种算法是一种贪心算法，具体做法是从前向后，每一步只学习一个基函数及其系数，逐渐优化目标函数，也就是说xgboost每次迭代会产生一个新的决策树，并保持之前的决策树不变。

令$y_i^{(t)}$ 表示第 $i$ 个样本在第 $t$ 次迭代时的输出结果，则： $$y_i^{(t)}=y_i^{(t-1)}+f_t({\text{x}}_i)$$ 则第t次迭代时，目标函数可以写成如下形式: $$L^{(t)}=\sum _{i=1}^{n}l(y_i,{\hat{y}}_i^{(t-1)}+f_t(\text{x}))+\Omega (f_t)$$

xgboost的优化方法是需要用到泰勒二阶展开，要求损失函数 $l$ 具有二阶导数，泰勒公式如下 $$f(x-x_0)=f(x_0)+(x-x_0)f^{\prime }(x_0)+\frac{(x-x_0{)}^2}{2}{f}^{\prime \prime }(x_0)+...+\frac{(x-x_0{)}^n}{n!}{f}^n(x_0)$$

将损失函数在$\hat y^{(t-1)} $泰勒二阶展开后， $$L^{(t)}\simeq \sum _{i=1}^n[l(y_i,{\hat{y}}_i^{(t-1)})+g_i{f}_t(\text{x})+\frac{1}{2}{h}_i{f}_i^2({\text{x}}_i)]+\Omega (f_t)$$ 其中$g_i,h_i$分别表示损失函数在$\hat y^{(t-1)} $的一阶导数和二阶导数。

在t轮迭代中，$\hat y^{(t-1)} $是确定的，而 $y$ 是样本对应的真实标签，也是确定的，故$l(y_i,{\hat{y}}_i^{(t-1)})$ 在上述损失函数中，是常数项，移除常数项后，得到如下损失函数：

$$L^{(t)}=\sum _{i=1}^n[g_i{f}_t(\text{x})+\frac{1}{2}{h}_i{f}_t^2({\text{x}}_i)]+\Omega (f_t)$$

令$I_j=\{i|q({\text{x}}_i)=j\}$, 也就是所有被分类到第 $j$ 个叶节点的样本集合。

由模型定义可知，对任意${\text{x}}_i\in I_j$, 有$f({\text{x}}_i)={\text{w}}_j$， 损失函数可以写成如下形式。 $$\begin{array}{rl}{L}^{(t)}& =\sum _{j=1}^T[(\sum _{i\in I_j}{g}_i)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i)w_j^2]+\gamma T+\lambda \sum _{i=1}{w}_j^2\\ & =\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\end{array}$$ 这是个关于$w_j$的二次函数， 可以直接求出最优解 $$w_j^{\ast }=-\frac{{\sum }_{i\in I_j}{g}_i}{{\sum }_{i\in I_j}{h}_i+\lambda }$$ 最优损失函数为： $$L=-\frac{1}{2}\sum _{j=1}^T\frac{({\sum }_{i\in I_j}{g}_i{)}^2}{{\sum }_{i\in I_j}{h}_i+\lambda }+\gamma T$$ 上面对于损失函数的推导，建立在了$I_j$确定的基础上，也就是说，上面的损失函数表示的是，在根据某种划分依据确定了每个样本所属的叶节点后，通过调整每个叶节点的输出值，使得这种划分得到的树结构可以达到的最优值。

但是有没有可能，不划分的效果反而更好呢？答案是有的，损失函数对叶节点的个数有个惩罚项，用于控制树的复杂度，那就有可能划分后在准确率上的收益低于增加节点所带来的惩罚。既然上述的损失函数可以用来计算某种树结构的评分，那么就可以用它来计算划分后的树结构对于当前树结构的增益。 $$gain=\frac{1}{2}[\frac{({\sum }_{i\in I_L}{g}_i{)}^2}{{\sum }_{i\in I_L}{h}_i+\lambda }+\frac{({\sum }_{i\in I_R}{g}_i{)}^2}{{\sum }_{i\in I_R}{h}_i+\lambda }-\frac{({\sum }_{i\in I}{g}_i{)}^2}{{\sum }_{i\in I}{h}_i+\lambda }]-\gamma$$

节点划分

精确法

这种节点划分方式类似于CART，遍历数据集中每个特征，并将其每个取值作为切分点，选取最优的切分点，这种方式被称为精确贪心法（Exact Greedy Algorithm）。这种方式的效率很低，并且在数据量巨大的时候，不能一次加载到内存时会变得特别耗时。

近似法

切分点选择

精确法将特征的每个取值作为切分点效率很低，所以论文就提出了近似法，选取特征的若干取值作为切分点。

定义集合 $${\mathcal{D}}_k=\{(x_{1k},h_1),(x_{2k},h_2),...(x_{nk},h_n)\}$$ ${\mathcal{D}}_k$ 包含每个样本第 k 个特征的值和二阶导数（参考上文）。

定义排序函数 $$r_k(z)=\frac{1}{{\sum }_{(x,h)\in \mathcal{D}}h}\sum _{(x,h)\in \mathcal{D},x<z}h$$ 如果令所有的 $h$ 都为1，则$r_k(z)$表示数据集中所有第 $k$ 个特征的值小于 $z$ 的样本所占的比例，这里 $h$ 可以视为加权系数，下文将会解释原因。

在训练xgboost时，可以设置超参数 $ϵ$, 继而生成若干近似切分点$\{s_{k1},s_{k2}...s_{kn}\}$，这些切分点满足如下关系： $$|r_k(s_{k,j})-r_k(s_{k,j+1})|<ϵ$$

也就是说，每两个切分点直接包含 $nϵ$ 个样本，$n$ 表示样本总数。也可以看出，大概共有 $1/ϵ$ 个切分点。

接下分析为什么 $h_i$ 可以作为加权系数，损失函数可以写成如下形式： $$\begin{array}{rl}{L}^{(t)}& =\sum _{i=1}^n[g_i{f}_t(\text{x})+\frac{1}{2}{h}_i{f}_i^2({\text{x}}_i)]+\Omega (f_t)\\ & =\sum _{i=1}^n\frac{1}{2}{h}_i[f_t^2({\text{x}}_i)+2\frac{g_i}{h_i}{f}_t({\text{x}}_i)+(\frac{g_i}{h_i}{)}^2-(\frac{g_i}{h_i}{)}^2]+\Omega (f_t)\\ & =\sum _{i=1}^n\frac{1}{2}{h}_i[f_t({\text{x}}_i)+\frac{g_i}{h_i}{]}^2+\sum _{i=1}^n(\frac{g_i}{h_i}{)}^2+\Omega (f_t)\\ & =\sum _{i=1}^n\frac{1}{2}{h}_i[f_t({\text{x}}_i)-(-\frac{g_i}{h_i}){]}^2+\Omega (f_t)+constant\end{array}$$

$h_i,g_i$ 是损失函数对上一次迭代输出值的导数，对于当前迭代来说是常数，所以损失函数是系数为$h_i$ 的平方函数。

顺便提一句，上面公式里标红的符号，原论文里写错了，应该是作者笔误吧，我在推导公式的时候，怎么都得不到和论文一样的结果，就去查了一下。参考stackchange

产生切分点的时间

产生切分点的时间可以分为全局和局部两种，全局法是指在构建决策树的初始阶段生成所有的候选切分点，在后续的建树过程中使用相同的候选切分点。局部法是在每次分割数据集后重新生成候选切分点。

上图是论文中给的对比图，可以看出当使用全局法并且选取较多的切分点时效果和精确法是差不多的，而使用局部法则不需要那么多的切分点，但是局部法在每次分割后都需要计算候选切分点。

防止过拟合

学习速率（收缩率，shrinkage）

$${\hat{y}}_i^t={\hat{y}}_i^{(t-1)}+\eta f_t({\text{x}}_i)$$ 设置学习速率可以给后续训练留取更多的学习空间，可以有效的防止过拟合，通常设置为0.1

列、行采样

行采样是指样本抽样 列采样是指在每次分裂中对特征抽样

缺失值处理

现实世界中的很多数据集是非常稀疏的，造成数据集稀疏的原因一般有以下几个：

数据中的缺失值统计出现的大量0值认为的one-hot编码

xgboost处理缺失值的方法很简单也很有效。将数据缺失的样本视为同一类，然后：

将缺失样本放到左子树，然后对非缺失的样本进行分割。

将却是样本放到右子树，然后对非缺失的样本进行分割。

这样在选取最优切分点的时候，也就选择了把缺失数据放到哪边。

这种算法的时间复杂度和非缺失样本的数量呈线性关系，因此效率很高，下图是在Allstate-10K和基础算法（算法1,2）的对比，快了50倍。

Column Block

在构建决策树的过程中，比较费时的是寻找最优切分点（包括特征选择和切分点的值），这个过程比较费时的是对数据进行排序 。论文提出了一种Block结构存储数据。Boloc中的数据按照CSC（一种稀疏矩阵的压缩存储方式）存储，这种格式有个好处，就是可以对只对特征进行一次排序，在后面的切分过程中直接使用排序好的数据。

由图可以看出，在构建树的初始阶段将特征排序后，在后面分裂时可以直接查询其梯度信息。

在Exact Greedy Algorithm 中，由于只需要排序一次，时间复杂度可以由$O(Kd\Vert \text{x}{\Vert }_{0}logn)$ 降低到 $O(Kd\Vert \text{x}{\Vert }_0+\Vert \text{x}{\Vert }_{0}logn)$ ， $(\Vert \text{x}{\Vert }_{0}logn)$ 表示一次排序的时间。

在近似法中，使用多个Block，每个Block对应着数据集的一个子集，多个Block之间可以并行计算。

缓存优化

文章中提到，在建树的初始阶段进行排序，会大大提高算法的效率，但同时会让对数据集的访问由连续的转化成非连续的，这会使得CPU的缓存命中率降低。为了解决这一问题，可以建立一个缓冲区。具体的分为两种策略：

对于Exact Greedy Algorithm，给每个线程创建一个缓冲区，将梯度信息提前放入缓冲区，然后从缓冲区中读取。

对于近似算法，可以通过设置不同的Block size（Block 中包含的样本数量）来提高CPU命中率

过小的Block size 不能高效的并行，过大的Block size 可能会因为缓存未命中而导致训练速度下降。

总结

xgboost相比于一般的GBDT，有以下的改进：

将损失函数泰勒二阶展开，考虑了二阶导数提出了近似算法，在数据集规模很大的时候可以大幅提高学习速率在损失函数中加入了正则系数，对决策树进行预剪枝

为什么xgboost运行效率很高：

在数据集规模很大的时候使用近似算法使用Column Block，在特征粒度上并行计算是从CSC存储数据，建立索引，在构建树的时候，对数据集只需要一次排序缓存优化，使用缓冲区提高cpu的chche命中率