XGBoost

Posted on

XGBoost

XGBoost是大规模并行Boosted Tree的工具，也是目前较为好用的开源Boosted Tree工具包，其计算速度比常见的算法要快约10倍左右。在数据科学方面，许多选手使用XGBoost进行数据挖掘比赛；在工业界，由于其分布式版本拥有广泛的可移植性，k恶意很好地解决工业界的实际问题。
XGBoost算法较为复杂，主要是针对于传统的GBDT算法进行了很多细节上的改进，包括损失函数、正则化项、防止过拟合方法、切分点查找算法优化、稀疏感知算法、并行化算法设计以及在系统设计方面的各种优化措施。
参考文献：XGBoost: A Scalable Tree Boosting System

1. 原理

1.1. 目标函数

给定训练数据集\(\mathscr{D} = \{(\pmb{x}_i,y_i)\} (|\mathscr{D}|=n,\pmb{x}_i \in \mathbf{R}^m, y\in \mathbf{R})\)，其中\(n\)为训练数据集包含的样例数，\(m\)为没个样例包含的特征数。我们使用Tree Ensemble，将模型写成 \[\hat{y}_i = \phi(\pmb{x}_i) = \sum_{k=1}^K f_k(\pmb{x}_i), \quad f_k \in \mathscr{F} \tag{1}\] 其中\(\mathscr{F} = \{f(\pmb{x}) = w_{q(\pmb{x})}\} (q: \mathbf{R}^m \to T,w \in \mathbf{R}^T)\)，\(\mathscr{F}\)为对应的回归树的假设空间。\(q\)代表每棵回归树的结构，并且将一个样例对应到一个相应的叶节点上。\(T\)表示回归树的叶节点个数。每棵回归树\(f_k\)对应于一个树结构\(p\)和叶节点权重\(w\)。由于回归树的叶节点包含连续值，所以用\(w_i\)表示第\(i\)个叶节点上的权重。当用所学模型对测试样例进行预测时，只需要每棵回归树根据规则将样例分类到对应的叶节点上，之后将叶节点对应的权重累加作为最终的预测值。
为了学习该模型，需要最小化正则化后的目标函数： \[\mathscr{L}(\phi) = \sum_{i} l(\hat{y}_i,y_i) + \sum_{k} \Omega (f_k) \tag{2}\] 其中\(\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2\)。\(l(\hat{y}_i,y_i)\)为可微的凸函数，表示将真实标记\(y_i\)预测为\(\hat{y}_i\)的损失代价。第二项\(\Omega\)表示对于模型复杂度的惩罚，附加的正则项可以平滑最终学习到的权重，并且避免过拟合。当正则化项的参数为0时，目标函数退化为传统的GBDT。

1.2. 梯度拟合

用\(\hat{y}_i^{(t)}\)表示模型在第\(t\)轮对第\(i\)个样例的预测结果，我们需要最小化下面的目标函数： \[\mathscr{L}^{(t)} = \sum_{i=1}^n l(y_i,\hat{y}_i^{(t-1)} + f_t(\pmb{x}_i)) + \Omega (f_t)\] 一般情况下，为了能够快速的优化目标函数，可以使用二级泰勒展开近似该目标函数： \[\mathscr{L}^{(t)} \simeq \sum_{i=1}^n [l(y_i,\hat{y}^{(t-1)}) + g_i f_t(\pmb{x}_i) + \frac{1}{2} h_i f_t^2 (\pmb{x}_i)] + \Omega (f_t)\] 其中，\(g_i = \partial_{\hat{y}^{(t-1)}} l(y_i,\hat{y}^{(t-1)})\)，\(h_i = \partial_{\hat{y}^{(t-1)}}^2 l(y_i,\hat{y}^{(t-1)})\)，\(g_i\)和\(h_i\)分别表示损失函数的一阶导数和二阶导数。移除常数项后，可以将第\(t\)轮学习的目标函数化简为 \[\tilde{\mathscr{L}}^{(t)} = \sum_{i=1}^n [g_i f_t(\pmb{x}_i) + \frac{1}{2} h_i f_t^2 (\pmb{x}_i)] + \Omega (f_t) \tag{3}\] 定义\(I_j = \{i | q(\pmb{x}_i) = j\}\)为叶节点\(j\)包含的样例集合。在第\(t\)轮中，当\(i \in I_j\)时，有\(f_t(\pmb{x}_i) = w_j\)。我们可以将正则项\(\Omega\)展开，将上述公式重写为 \[\begin{align} \tilde{\mathscr{L}}^{(t)} &= \sum_{i=1}^n [g_i f_t(\pmb{x}_i) + \frac{1}{2} h_i f_t^2 (\pmb{x}_i)] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \nonumber \\ &= \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 \nonumber \end{align} \tag{4}\] 为了构建最优的树结构，我们可以对上面的公式求导，计算叶节点\(j\)对应的最优的权重\(w_j^*\)： \[w_j^* = - \frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \tag{5}\] 对应的最优目标函数值为 \[\tilde{\mathscr{L}}^{(t)} (q) = - \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 \tag{6}\] 上述公式可以作为评分函数来衡量一个结构为\(q\)的树的质量，分数越低，树结构越好。

下图说明了该分数如何计算：

通常情况下，很难枚举出所有可能的树结构，而是使用一种贪心的算法从一个单一的叶节点迭代的增加分支。假设\(I_L\)和\(I_R\)分别表示切分后左节点包含的样例和右节点包含的样例，令\(I = I_L \cup I_R\)，切分后的损失函数可写为 \[\mathscr{L}_{split} = \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 \tag{7}\] 这个公式通常用来选择用于切分的特征。

2. Shrinkage和Column Subsampling

2.1. Shrinkage

Shrinkage（衰减）类似于学习率，在每一步学习得到的tree boosting上增加一个参数\(\eta\)，类似于随机梯度下降法中的学习率，通过这种方法减小每棵树的影响力，对接下来需要学习的树模型提供空间去优化模型。

2.2. Column Subsampling

Column Subsampling（特征子采样），这个技术通常用于随机森林中，但之前一直未用于tree boosting中。根据用户的反馈，使用特征自采样避免过拟合的效果通常优于传统的训练数据集下采样，并且对后续的并行化处理算法的速度有所提高。

3. 切分点查找算法

3.1. Exact Greedy算法

一个关键的问题是如何根据公式（7）在回归树的学习阶段选取最优切分点。
exact greedy算法思想：枚举所有特征的所有可能的切分点，根据公式寻找最优切分点。
一般在单机版的工具包中都有实现该算法，如sklearn等，为了提高效率，通常会先根据特征值对训练集数据进行排序，并按照顺序累加计算公式（7）中需要的梯度统计值。
算法如下：

3.2. 近似算法

exact greedy算法非常有效，但是当数据不能完全存入内存中时，想要高效地运行此算法是不可能的，同样的问题也会出现在分布式的环境中。为了应对这两种情况，下面给出一种近似算法。

算法总结：

  • 该算法会根据特征分布的分位数获得候选切分点，即按照分布式加权直方图算法确定一组候选切分点，再通过遍历寻找最优切分点；
  • 在寻找切分点时，不会枚举所有特征值，而是对特征值进行聚合统计，将连续的特征值映射到不同的buckets中，整合统计信息，只有在buckets边界上的特征值才会作为候选切分点。

根据候选切分点获取的时间段，该算法有两种变体：

  • global：在模型构建的初始阶段获取候选的切分点，并且在之后算法中使用的候选切分点不会改变；
  • local：在每次切分之后更新候选切分点列表。

通常情况下，global方法比local方法需要更少的执行步骤，但是需要更多的候选切分点，因为在每次切分后，global方法不会改善候选切分点。local方法需要在每次切分之后改善候选切分点，所以更适用于更深的树结构的构造。

下图是对不同方法的比较：

3.3. 加权Quantile Sketch

近似算法中一个重要的步骤就是如何确定候选切分点。
令集合\(\mathscr{D}_k = \{(x_{1k},h_1),(x_{2k},h_2),\cdots,(x_{nk},h_n)\}\)表示数据集中各样例第\(k\)个特征值，并且按照二阶导的统计信息\(h_i\)进行排序，我们可以定义如下的排序公式： \[r_k (z) = \frac{1}{\sum_{(x,h) \in \mathscr{D}_k} h} \sum_{(x,h) \in \mathscr{D}_k,x<z} h \tag{8}\] 上式表示样例第\(k\)个特征值小于\(z\)在数据集中所占的比例，目标是找到候选切分点集\(\{s_{k1},s_{k2},\cdots,s_{kl}\}\)，有 \[|r_k(s_k,j) - r_k(s_k,j+1)| < \epsilon , \quad s_{k1} = \min_{i} x_{ik},s_{kl} = \max_{i} x_{ik}\] 这里\(\epsilon\)是一个近似参数，直观地可理解为大约有\(1/ \epsilon\)个候选切分点。
上述过程中样例\(\pmb{x}_i\)的权重为\(h_i\)，为了解释为什么用\(h_i\)表示权重，可将公式（3）重写为 \[\sum_{i=1}^n \frac{1}{2} h_i(f_t(\pmb{x}_i) - g_i/h_i)^2 + \Omega(f_t) + constant\] 上述公式可理解为计算平方误差的目标函数，其中每个样例的权重为\(h_i\)，标记为\(g_i/h_i\)。

3.4. 稀疏特征切分点查找

在现实任务中，训练数据很有可能是稀疏的，例如特征工程中的one-hot编码、数据缺失等，算法能够处理稀疏模式也是十分重要的。为了应对稀疏问题，XGBoost中在树中的每个节点处加入了一个默认方向，当节点对应的特征值缺失时，样例将会被分到默认方向。

由于每个节点有两个分支，所以默认方向有两种选择，最佳默认方向会从数据中学得。
算法如下：

该算法只会关注于那些在特征\(k\)上无缺失的样例，并会处理将特征\(k\)缺失的样例分到左分支和右分支两种情形，之后比较二者选取最优的默认方向。对于未出现过的特征值也可当作缺失值处理，用户可为缺失值指定值，该算法同样适用。

4.系统设计

XGBoost在系统设计方面同样设计了一些方法用于提升算法的速度和准确度，这里只介绍一下并行化处理，具体内容可参考原文。

4.1. 并行化处理

在树的生成阶段，大部分时间用来对数据集进行排序。为了减少排序时间，XGBoos把数据按照block结构存储于内存中，数据在每个block中存储为压缩列（compressed column，CSC）格式，每一列存储了对相应特征值的排序结果。所以输入数据的分布只需要在训练之前计算一次，并且在后续迭代中可以重复使用。

在决策树生成过程中需要选择增益最大的特征值作为切分点，而各个特征值增益的计算就可以通过block结构中不同的列并行处理，即采用多线程并行的方式寻找最优切分点。同样的，block结构也支持特征子采样，只需要选择一部分列去寻找最优切分点。除此之外，block结构也降低了算法的时间复杂度，这里就不具体分析了。

5. XGBoost使用

XGBoost的参数主要分为三类：

  • 通用参数：宏观函数控制；
  • Booster参数：控制每一步的Booster（tree/regression）；
  • 学习目标参数：控制训练目标的表现。

（1）通用参数

-w500

-w500

（2）Booster参数

通常情况下，tree booster的表现优于linear booster，所以linear booster很少用到。

（3）学习目标参数
控制优化目标和每一步结果的度量方法。 XGBoost工具支持自定义目标函数，只要函数可一阶和二阶求导。

-w600

-w600

6. XGBoost与传统GBDT的不同

XGBoost与传统GBDT的不同：

  • 传统GBDT以CART作为基分类器，XGBoost还支持线性分类器，此时XGBoost相当于带L1和L2正则化的logistic回归（分类问题）或线性回归（回归问题）；
  • 传统GBDT在目标函数的优化中只是用了一阶导数信息，而XGBoost对目标函数进行了二阶泰勒展开，同时用到一阶导数和二阶导数；
  • XGBoost在目标函数中加入了正则项，控制模型复杂度，避免出现过拟合，而传统GBDT的目标函数中没有正则项，依赖于决策树剪枝；
  • Shrinkage缩减，降低了每棵树的影响，为后续决策树的学习提供了空间；
  • 特征子采样，借鉴随机森林的方法，降低过拟合，减少运算量；
  • 对缺失值的处理，在决策树生成时构建默认方向；
  • 并行计算，在选取最优切分点时支持并行计算；
  • 可并行的近似直方图算法，用于高效地生成候选的切分点。

XGBoost目标函数中的加入正则项是否优于CART剪枝？