【推荐收藏】带你读一遍 XGBoost论文（上）

Sam Gor

发布于 2019-07-08 23:09:56

1.9K0

发布于 2019-07-08 23:09:56

文章被收录于专栏：SAMshareSAMshare

XGBoost作为一个非常常用的算法，我觉得很有必要了解一下它的来龙去脉，于是抽空找了一些资料，主要包括陈天奇大佬的论文以及演讲PPT，以及网络上的一些博客文章，今天在这里对这些知识点进行整理归纳，论文中的一些专业术语尽可能保留不翻译，但会在下面写出自己的理解与解释。

? Index

XGBoost介绍
XGBoost亮点
梯度增强树算法介绍
分裂查找算法介绍
XGBoost的系统设计

? XGBoost介绍

在Paper中，作者定义XGBoost：

a scalable machine learning system for tree boosting.

XGBoost为“Extreme Gradient Boosting”的缩写，里面包含了关键字'Boosting'，意味着它是一个boosting集成算法，所以它的主要思路是将成百上千个树模型组合起来成为一个准确率很高的模型，此模型通过不断迭代生成新的树。

XGBoost我们常用于监督学习，即建立一个数据模型，输入相关特征从而预测出目标，而这一过程，需要我们找到训练数据最好的参数，所以我们需要定义一个目标函数，通常由训练损失（traning loss）和正则项（regularization term）组成。

训练损失评估了预测模型的效果，例如常用的训练损失指标是均方误差或是逻辑回归的logistic loss。正则项则是控制着模型的复杂度，避免模型不被过度拟合。这两个互相博弈（tradeoff）的指标保证了模型的预测效果以及简洁程度。

? XGBoost亮点

We design and build a highly scalable end-to-end tree boosting system.
We propose a theoretically justified weighted quantile sketch for efficient proposal calculation.
We introduce a novel sparsity-aware algorithm for par- allel tree learning.
We propose an effective cache-aware block structure for out-of-core tree learning.

翻译来说，就是它设计并构建了适用于大规模的 end-to-end 的Boosting系统（end-to-end指的是端到端，就是只关心输入和输出，中间过程都不care），而且实现特征选择的并行处理，正则使用L2的稀疏感知算法，而且也提出了有效的缓存结构，加大训练效率

另外，其他博文也有一些总结：

相对GBDT来说，XGB在增加二阶梯度有更高的精度；
XGB的节点划分策略带有进行预排序，利用样本在损失函数上面的二阶梯度作为权值；
XGB对稀疏的特征划分方式；
在处理特征的粒度上进行多线程的优化；
使用近似算法替代每个样本逐个判断最佳分裂点的Exact Greedy Algorithm算法。

? 梯度增强树算法介绍

XGBoost还是采用属于gradient tree boosting algorithms，推导过程和已有的算法理论类似，但这里有了一些创新，比如正则化学习目标、样本子采样、特征子采样、近似算法等等。

3.1 Regularized Learning Objective

给定一个n X m维的数据集D，通过训练D，得到K棵树，而这K棵树累加的值作为我们的预测值。

其中，

是CART的空间，q表示每个树的结构，其可以将每个样本映射到对应的叶节点中，T是树中叶子节点的个数。

有了上面的预测值，我们可以代入loss function，得到我们的损失函数：

可以看出损失函数由两部分组成，Training Loss和Regularization。

3.2 Gradient Tree Boosting

这一节是对损失函数的推导求解，这里不是采取传统的优化方法进行优化，而是采用了Additive Training训练，我们将Training Loss部分，展开成K棵树叠加的形式，开始于一个常数，每次增加一个新的函数学习当前的树，贪婪地利用误差函数改善当前模型，而这里创新的点在于对误差函数进行二阶泰勒近似展开。

具体公式推导就不展开了，建议查阅：

XGBoost原理介绍：https://blog.csdn.net/yinyu19950811/article/details/81079192

3.3 Shrinkage and Column Subsampling

这一节讲到了两种防止过拟合的tricks，Shrinkage和Column Subsampling。

Shrinkage：权值收缩，主要针对叶子节点，在每一次的Tree Boosting后，收缩叶子节点的权重，降低了每棵独立树的影响，为将来的优化留出一些空间。
Column Subsampling：这种技术出现在RF中，这种做法不仅可以防止过拟合，还能提升一部分训练效率。

? 分裂查找算法介绍

4.1 Basic Exact Greedy Algorithm

这个是常见的基础贪心算法，即对所有的特征进行遍历处理，这就要求对计算资源要求比较高，因为需要对每个特征计算其信息增益，选择增益最大的作为分裂点，当然是需要比较多的时间和算力。

4.2 Approximate Algorithm

顾名思义，近似算法就是可能效果或者原理和Exact Greedy Algorithm差不多的算法，它的原理是根据特征分布的百分位数进行采样，选择待分裂点，然后，该算法将连续特征映射到由这些候选点分割的桶中，汇总统计信息并根据汇总的信息找到最佳解决方案，这里选择分裂点的方式有global和local：