Boosting 系列算法——6. XGBoost_6db boosting

1. 算法导出

在XGBoost中，使用的目标函数相比于GBDT，添加一个新的正则项，主要目的是衡量模型的复杂程度，直接在损失函数中直接控制树的复杂度。
$$Obj=\sum _{i=1}^N\underset{\text{训练损失}}{\underbrace{L\left(y_i,F({\mathbf{x}}_i)\right)}}+\sum _{m=1}^M\underset{\text{树的复杂度}}{\underbrace{\Omega \left(h_m\right)}},$$
$$\Omega (h)={\lambda }_{J}J+\frac{1}{2}{\lambda }_w\Vert w{\Vert }^2.$$
其中，${\lambda }_J$与${\lambda }_w$为惩罚项系数，$J$为叶子数。我们定义每个叶子节点都会有一个权重得分$w_j$（可以理解为前文所述的${\rho }_{jm}$），$\Vert w{\Vert }^2$为叶子得分的L2范数。目标函数所加的正则化帮助平滑最终学习的权重避免过拟合。正则化对象将倾向于挑选出一个简单、可预测的函数。我们的目标函数和相应的学习算法更为简单，更容易并行化。当正则化参数设置为0时，目标函数将变为传统的GBDT框架。

下面我们考虑二阶Taylor展开近似估计损失函数。首先回忆二阶泰勒展开：当函数$f(x)$在点$x$处可导时，在其邻域内，恒有：
$$f(x+\Delta x)\approx f(x)+f^{\prime }(x)\Delta x+\frac{1}{2}{f}^{\prime \prime }(x)\Delta x^2.$$
我们的损失函数又可写为下述形式，
$$Ob{j}^{(m)}=\sum _{i=1}^{N}L\left(y_i,F_{m-1}({\mathbf{x}}_i)+h_m({\mathbf{x}}_i)\right)+\Omega \left(h_m\right).$$
对上式进行泰勒展开，可得：
$$Ob{j}^{(m)}\approx \sum _{i=1}^n\left[L\left(y_i,F_{m-1}({\mathbf{x}}_i)\right)+f_{i,m-1}{h}_m\left({\mathbf{x}}_i\right)+\frac{1}{2}{g}_{i,m-1}{h}_m^2\left({\mathbf{x}}_i\right)\right]+\Omega \left(h_m\right),$$
其中
$$f_{i,m-1}=\frac{\partial L\left(y_i,F_{m-1}({\mathbf{x}}_i)\right)}{\partial F_{m-1}({\mathbf{x}}_i)},g_{i,m-1}=\frac{{\partial }^{2}L\left(y_i,F_{m-1}({\mathbf{x}}_i)\right)}{\partial F_{m-1}^2({\mathbf{x}}_i)}.$$
若使用平方损失，则：
$$f_{i,m-1}=\frac{\partial {\left(y_i-F_{m-1}({\mathbf{x}}_i)\right)}^2}{\partial F_{m-1}({\mathbf{x}}_i)}=2\left(F_{m-1}({\mathbf{x}}_i)-y_i\right),$$
$$g_{i,m-1}=\frac{{\partial }^2{\left(y_i-F_{m-1}({\mathbf{x}}_i)\right)}^2}{\partial F_{m-1}^2({\mathbf{x}}_i)}=2.$$

下面我们移除常数项$L\left(y_i,F_{m-1}({\mathbf{x}}_i)\right)$，并且定义$I_j$为叶子节点$j$里面的所有样本，进行函数化简：
O b j ~ ( m ) = ∑ i = 1 n [ f i , m − 1 h m ( x i ) + 1 2 g i , m − 1 h m 2 ( x i ) ] + Ω ( h m ) = ∑ i = 1 n [ f i , m − 1 h m ( x i ) + 1 2 g i , m − 1 h m 2 ( x i ) ] + λ J J + 1 2 λ w ∑ j = 1 J w j 2 = ∑ j = 1 J [ ( ∑ i ∈ I j f i , m − 1 ) w j + 1 2 ( ∑ i ∈ I j g i , m − 1 + λ w ) w j 2 ] + λ J J .

$$\begin{aligned} \widetilde{Obj}^{(m)} &= \sum_{i=1}^{n}\left[f_{i,m-1} h_{m}\left(\mathbf{x}_{i}\right)+\frac{1}{2} g_{i,m-1} h_{m}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(h_{m}\right) \\ &=\sum_{i=1}^{n}\left[f_{i,m-1} h_{m}\left(\mathbf{x}_{i}\right)+\frac{1}{2} g_{i,m-1} h_{m}^{2}\left(\mathbf{x}_{i}\right)\right] +\lambda_J J+\frac{1}{2} \lambda_w \sum_{j=1}^{J} w_{j}^{2} \\ &=\sum_{j=1}^{J}\left[\left(\sum_{i \in I_{j}} f_{i,m-1}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} g_{i,m-1}+\lambda_w\right) w_{j}^{2}\right]+\lambda_J J. \end{aligned}$$ Obj ​(m)​=i=1∑n​[fi,m−1​hm​(xi​)+21​gi,m−1​hm2​(xi​)]+Ω(hm​)=i=1∑n​[fi,m−1​hm​(xi​)+21​gi,m−1​hm2​(xi​)]+λJ​J+21​λw​j=1∑J​wj2​=j=1∑J​⎣⎡​⎝⎛​i∈Ij​∑​fi,m−1​⎠⎞​wj​+21​⎝⎛​i∈Ij​∑​gi,m−1​+λw​⎠⎞​wj2​⎦⎤​+λJ​J.​
由于上述中括号内是关于叶子节点权值$w_j$的开口向上的二次方程，因此有最小值，我们可以计算每个叶子节点$j$的最优权重$w_j^{\ast }$：
$$w_j^{\ast }=-\frac{{\sum }_{i\in I_j}{f}_{i,m-1}}{{\sum }_{i\in I_j}{g}_{i,m-1}+{\lambda }_w},$$
而后将其代入原目标函数，得到：
$${\widetilde{Obj}}^{(m)}=-\frac{1}{2}\sum _{j=1}^J\frac{{\left({\sum }_{i\in I_j}{f}_{i,m-1}\right)}^2}{{\sum }_{i\in I_j}{g}_{i,m-1}+{\lambda }_w}+{\lambda }_{J}J.$$
上式可以作为一个评估方程去评价一棵树的结构。这个打分就像评估决策树的不纯度得分，不同的是它是为了更广泛的目标函数所导出。但通常来说我们不可能枚举出所有的树结构，而是使用贪心算法，从一个叶子节点开始分裂，反复给树添加分支。假设$I_L$和$I_R$是一个叶子节点分裂后左右节点中包含的样本集合，满足叶子节点的样本集合$I=I_L\cup I_R$。我们可以类似决策树的分裂，定义一个收益函数，用于评价候选分裂节点的好坏：
$$\text{Gain}=\frac{1}{2}\left[\frac{{\left({\sum }_{i\in I_L}{f}_i\right)}^2}{{\sum }_{i\in I_L}{g}_i+{\lambda }_w}+\frac{{\left({\sum }_{i\in I_R}{f}_i\right)}^2}{{\sum }_{i\in I_R}{g}_i+{\lambda }_w}-\frac{{\left({\sum }_{i\in I}{f}_i\right)}^2}{{\sum }_{i\in I}{g}_i+{\lambda }_w}\right]-{\lambda }_J.$$

---

2. 训练算法

XGBoost中的一个关键问题在于寻找每个分裂时的最优划分点。一种最简单的方法是寻找所有特征的所有划分点，也就是精确贪心算法（Exact Greedy Algorithm）。其需首先对所有样本的所有变量进行排序，而后再进行遍历搜索。

当数据量过大时，传统算法便不再适用，这是由于需要遍历每个分割点，其需要大的内存，以及耗费大量的时间。因此，XGBoost中提出了另外一种近似算法，其在几乎不影响算法精度的前提下，能加快运行的时间。

此算法主要思想为：枚举所有特征，根据特征的分布情况，（例如：第$k$个特征的分布的分位数来决定出$l$个候选切分点），根据候选切分点将相应的样本映射到对应的桶中，进行分桶（一个桶为一个区间段），而后对每个桶的 $\nu ,\xi$ 进行累加，最后在候选切分点集合上按照前文所述算法进行贪心查找。

注意这里有两种分桶的方式，一种是全局的，一种是局部的。
\begin{itemize}
\item 全局的是在建树之前就构建相应的$S_k$，之后的每次分割都在全局的$S_k$中寻找划分点；
\item 局部的方法是在每次节点分裂之后重新更新$S_k$。
\end{itemize}

通常而言，全局选择$S_k$的方法需要设置更小的分位数间隔，才能取得比较好的效果，而局部的方法可以设置更大的分位数间隔，从而产生更少的桶.每次特征分裂查找基于较少的候选点，计算速度快，但是需要每次节点分裂后重新执行。

下面我们将介绍关于分位数的具体选取方式。首先我们继续用样本的方式对原本的目标函数进行分解。

O b j ~ ( m ) ≈ ∑ i = 1 n [ f i , m − 1 h m ( x i ) + 1 2 g i , m − 1 h m 2 ( x i ) ] + Ω ( h m ) = ∑ i = 1 N 1 2 g i , m − 1 ( 2 f i , m − 1 g i , m − 1 h m ( x i ) + h m 2 ( x i ) ) + Ω ( h m ) = ∑ i = 1 N 1 2 g i , m − 1 ( f i , m − 1 2 g i , m − 1 2 + 2 f i , m − 1 g i , m − 1 h m ( x i ) + h m 2 ( x i ) ) + Ω ( h m ) − f i , m − 1 2 2 g i , m − 1 = ∑ i = 1 N 1 2 g i , m − 1 ( h m ( x i ) − ( − f i , m − 1 g i , m − 1 ) ) 2 + Ω ( h m ) − f i , m − 1 2 2 g i , m − 1 = ∑ i = 1 N 1 2 g i , m − 1 ( h m ( x i ) − ( − f i , m − 1 g i , m − 1 ) ) 2 + Ω ( h m ) + constant 

$$\begin{aligned} \widetilde{O b j}^{(m)} & \approx \sum_{i=1}^{n}\left[f_{i,m-1} h_{m}\left(\mathbf{x}_{i}\right)+\frac{1}{2} g_{i,m-1} h_{m}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(h_{m}\right) \\ &=\sum_{i=1}^{N} \frac{1}{2} g_{i,m-1}\left(2 \frac{f_{i, m-1}}{g_{i, m-1}} h_{m}\left(\mathbf{x}_{i}\right)+h_{m}^{2}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(h_{m}\right) \\ &=\sum_{i=1}^{N} \frac{1}{2} g_{i,m-1}\left(\frac{f_{i,m-1}^{2}}{g_{i,m-1}^{2}}+2 \frac{f_{i,m-1}}{g_{i,m-1}} h_{m}\left(\mathbf{x}_{i}\right)+h_{m}^{2}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(h_{m}\right)-\frac{f_{i,m-1}^{2}}{2 g_{i,m-1}} \\ &=\sum_{i=1}^{N} \frac{1}{2} g_{i,m-1}\left(h_{m}\left(\mathbf{x}_{i}\right)-\left(-\frac{f_{i,m-1}}{g_{i,m-1}}\right)\right)^{2}+\Omega\left(h_{m}\right)-\frac{f_{i,m-1}^{2}}{2 g_{i,m-1}} \\ &=\sum_{i=1}^{N} \frac{1}{2} g_{i,m-1}\left(h_{m}\left(\mathbf{x}_{i}\right)-\left(-\frac{f_{i,m-1}}{g_{i,m-1}}\right)\right)^{2}+\Omega\left(h_{m}\right)+\text {constant } \end{aligned}$$ Obj ​(m)​≈i=1∑n​[fi,m−1​hm​(xi​)+21​gi,m−1​hm2​(xi​)]+Ω(hm​)=i=1∑N​21​gi,m−1​(2gi,m−1​fi,m−1​​hm​(xi​)+hm2​(xi​))+Ω(hm​)=i=1∑N​21​gi,m−1​(gi,m−12​fi,m−12​​+2gi,m−1​fi,m−1​​hm​(xi​)+hm2​(xi​))+Ω(hm​)−2gi,m−1​fi,m−12​​=i=1∑N​21​gi,m−1​(hm​(xi​)−(−gi,m−1​fi,m−1​​))2+Ω(hm​)−2gi,m−1​fi,m−12​​=i=1∑N​21​gi,m−1​(hm​(xi​)−(−gi,m−1​fi,m−1​​))2+Ω(hm​)+constant ​

上式可视为标签为$-\frac{f_{i,m-1}}{g_{i,m-1}}$，权重为二阶梯度$g_{i,m-1}$的平方误差。我们将权重$g_{i,m-1}$引入$S_k$的选取中，使用加权分位数的方式来确定$S_k$。

下面考虑另一个问题，当数据为稀疏的情形。许多真实世界中的问题，数据可能是稀疏的，主要原因如：存在缺失值、大量的0项、特征工程中one-hot等编码。因此，对于数据的稀疏模式感知（Sparsity-aware）非常重要。本文算法提出了在每个树节点提添加一个默认方向。即当一个实例值是缺失时，该实例会被分类到默认方向，当一个值是缺失值时，我们就把他分类到默认方向，每个分支有两个选择，具体的选择需要通过枚举向左和向右的情况，根据score的大小进行确定。

---

3. 系统设计

3.1 列块并行学习（Column Block for Parallel Learning）

利用树进行学习的一些模型算法，大多数时间消耗在获取数据的排序上。为了降低排序成本，我们将数据存储在内存单元中，称为block。每个block的数据以列压缩CSC形式存储，每列通过对应的特征值排序。输入数据仅需要在训练之前计算一次，之后的迭代中可以重复使用。

在精确贪心中，我们存储整个数据集在一个block中，通过对预排序的样本线性扫描运行分割搜索算法。我们对所有的叶子节点做分割点查找，因此对block的一次扫描可以收集所有叶子分支上分裂候选点的统计信息。

block结构对近似算法也是有帮助的。可以使用多个block，每个block对应数据集中行的子集，不同的block可以分布在不同的机器上或者核外硬盘上。使用排序结构，分位数查找步骤变成对排序后的列进行线性查找。这对局部近似变体是非常有价值的，因为该变体在每个分支频繁的产生候选点。

搜集每列的统计信息也可以是并行化的，更重要的是，列block结构支持列采样，其可使在每个block中搜集列子集的统计信息变得非常容易。

---

3.2 支持缓存访问（Cache-aware Access）

虽然提出的block结构能够帮助优化划分查找的计算复杂度，但由于在顺序访问特征值时，访问的是一块连续的内存空间。需要间接通过行索引获取样本梯度信息，这并不是连续的内存空间。

对于精确贪心算法，我们使用缓存预取算法来进行优化。即我们在每个线程中分配一个缓存，读取梯度信息存储在其中。这种预取策略能够有效降低当数据量过大时的程序运行时间。

而在近似算法中，XGBoost对block的大小进行了合理的设置，其为block中最多的样本数。设置合适的大小非常重要，设置过大则容易导致缓存丢失，因为梯度统计数据没有进入CPU缓存；过小则会导致并行化效率不高。经过实验，发现​比较好。

---

3.3 用于核外计算的块（Blocks for Out-of-core Computation）

系统目标在于充分利用机器资源进行可扩展的学习。除了处理器和内存之外，利用磁盘空间处理不能放入内存的数据是很重要的。为了确保核外计算，我们将数据划分为多个block，并将block存入磁盘。在计算中使用独立线程预读取block到缓存。因此计算和磁盘读取可以同步进行。但是由于磁盘读取耗时过长，降低开销和增加磁盘IO的吞吐量非常重要。XGBoost主要使用两种技术来改进核外计算。

• 数据块压缩：对数据块按列压缩，在将数据传输到内存中，最后再由独立的线程解压缩。即将磁盘的读取消耗转换为解压缩所消耗的计算资源。

• 数据块分区：将数据分片到多个磁盘，每个磁盘分配一个预取线程，将数据拿到in-memory 缓存，再从各个缓存中读取数据。训练线程交替读取多块缓存的同时，计算任务也在运转，提升了硬盘总体的吞吐量。

---

传送门

• 下一篇：Boosting 系列算法——7. LightGBM
• Boosting 系列算法