一文读懂XGBoost背后的数学原理（原理讲解篇）

XGBoost自2014推出以来，一直被誉为机器学习黑客马拉松（ML Hackathon）和竞赛的圣杯。从预测广告点击率到对高能物理事件进行分类，XGBoost在性能和速度方面证明了自己的实力。

在任何ML Hackathon中，XGBoost总是我的第一个算法选择。它一贯给出的精度和节省的时间都在表明它是多么有用。但它实际上是如何工作的呢？是什么样的数学方法使得XGBoost变得如此强大？我们很快就会找出这些问题的答案。

XGBoost的共同创建者之一陈天琦（在2016年）宣布，XGBoost的创新系统特性和算法优化使其比大多数机器学习解决方案快10倍。一个真正惊人的技术！

在本文中，我们将首先研究XGBoost的强大功能，然后深入研究这种流行而强大的技术的内部工作原理。能够用Python或R语言实现它是件好事，但是理解算法的基本内容将帮助您成为一个更好的数据科学家。

注意：我们建议阅读下面的文章，并充分理解本文中提到的各种术语和概念：

集成建模的综合指南（附Python代码）

目录表

1.XGBoost的威力

2.为什么集成学习？

• bagging
• boosting

3.论证boosting潜力

4.用梯度下降法优化损失函数

5.XGBoost的几大特性

1.XGBoost的威力

这种强大算法的优点在于它的可扩展性，它通过并行和分布式计算驱动快速学习，并提供高效的内存使用。

难怪欧洲核子研究中心（简称“CERN”）承认它是将来自大型强子对撞机（Large Hadron Collider）的信号分类的最佳方法。CERN提出的这一特殊挑战需要一种解决方案，该解决方案能够以每年3千兆字节的速度处理正在生成的数据，并在复杂的物理过程中有效地将极其罕见的信号与背景噪声区分开。XGBOOST成为最有用、最直接和最稳健的解决方案。

现在，让我们深入研究XGBoost的内部操作。

2.为什么集成学习？

XGBoost是一种集成学习方法。有时，仅仅依赖一个机器学习模型的结果可能是不够的。集成学习提供了一种系统的解决方案，结合多个学习者的预测能力。所得结果是一个单一模型，它给出了来自多个模型的聚合输出。

形成集成的模型，也称为基学习器（Base Learner），可以来自相同的学习算法或不同的学习算法。Bagging和Boosting是两种被广泛使用的集合学习器。虽然这两种技术可以与几个统计模型一起使用，但最主要的使用还是决策树。

让我们简单讨论一下Bagging，然后更详细地了解Boosting的概念。

Bagging

决策树虽然是最容易解释的模型之一，但是也表现出高度可变的行为。考虑一个单一的训练数据集，我们随机分成两部分。现在，让我们使用每个部分来训练决策树，以获得两个模型。

当我们拟合这两种模型时，它们会产生不同的结果。决策树被认为与高方差相关，由于这种行为。Bagging或Boosting集成有助于减少任何学习器的差异。并行生成的多个决策树构成了Bagging技术的基学习器。替换采样的数据被馈送给这些学习器进行训练。最后的预测是所有学习者的平均输出。

Boosting

在Boosting中，树是按顺序构建的，这样每个后续树的目的是减少前一棵树的错误。每个树从它的前辈学习并更新残余误差。因此，序列中生长的树将从残差的更新版本中学习。

Boosting的基学习器是偏向性高的弱学习器，其预测能力比随机猜测略好。这些弱学习器中的每一个都为预测结果贡献了一些重要的信息，使得boosting技术能够通过有效地结合这些弱学习器来产生强学习器。最终的强学习器会降低偏见和差异。

与诸如随机森林（Random Forest）等最大限度地种植树木的Bagging技术相比，boosting利用了劈裂较少的树木。这样的小树，不是很深，是高度可解释的。诸如树或迭代的数量、梯度提升学习的速率以及树的深度之类的参数可以通过诸如k次交叉验证之类的验证技术来最佳地选择。有大量的树可能会导致过度拟合。因此，有必要仔细选择Boosting的停止标准。

Boosting由三个简单步骤组成：

• 初始模型F0被定义为预测目标变量y。该模型将与残差（y-F0）相关联。
• 一个新的模型h1适合于前一步的残差。
• 现在，F0和h1被组合以给出F1，即F0的boosting版本。F1的均方误差将低于F0：

为了改善F1的性能，我们可以对F1的残差进行建模，并建立一个新的模型F2：

这可以对“m”迭代进行，直到残差尽可能地最小化为止：

这里，添加学习器不会干扰前面步骤中创建的函数。相反，他们传授他们自己的信息来减少错误。

3.论证boositing潜力

考虑下面的数据，经验年限是预测变量，薪水（单位：千美元）是目标。使用回归树作为基学习器，我们可以创建一个模型来预测工资。为了简单起见，我们可以选择平方损失作为我们的损失函数，我们的目标是最小化平方误差。

第一步，用函数F0（x）初始化模型。F0（x）应该是最小化损失函数或均方误差（MSE）的函数，在这种情况下：

利用上述方程关于γ的第一个微分，可以看到函数在平均i=1nyin处最小化。因此，可以通过以下方式启动促进模式：

F0（x）给出了从我们的模型的第一阶段的预测。现在，每个实例的残差是（$y_i$ -F0（x））。

我们可以使用F0（x）的残差来创建h1（x）。h1（x）将是一个回归树，它将尝试减少前一步的残差。h1(x)的输出将不是$y$ 的预测，相反，它将有助于预测将降低残差的连续函数F1(x)。

附加的模型h1（x）计算树的每个叶的残差（$y$ -F0）的平均值。通过求F0（x）和h1（x）求出boosted函数F1（x）。这样，h1（x）就从F0（x）的残差中学习并在F1（x）中抑制它。

这可以重复2次迭代来计算h2（x）和h3（x）。这些附加学习器hm（x）中的每一个都将利用前一函数$Fm-1(x)$ 的残差。

F0（x）、F1（x）和F2（x）的MSE分别为875, 692和540。令人惊讶的是，这些简单的弱学习器能大幅地减少误差！

注意，每个学习器hm（x）都是在残差上进行训练的。在每个步骤中的残余误差建模后，对boosting的所有附加学习器进行建模。可以直观地观察到boosting学习器使用的是残差中的方式。在通过boosting达到最大精度的阶段，残差看起来是随机分布的，没有任何模式。

FN和HN的作图

4.用梯度下降法优化损失函数

在上面讨论的情况下，MSE是损失函数，是平均最小误差。当平均绝对误差（MAE）是损失函数时，中值将被用作F0（x）来初始化模型。$y$ 中的单位变化也会导致MAE中的单位变化。

对于MSE，观察到的变化大致是指数的。代替在残差上拟合hm(x)，在损失函数的梯度上拟合它，或者沿着损失发生的步骤进行拟合，将使得该过程具有通用性，并且适用于所有损失函数。

梯度下降有助于我们最小化任何可微函数。早些时候，hm(x)的回归树预测树的每个终端节点的平均残差。在梯度提升中，将计算平均梯度分量。

对于每个节点，有一个因子γ与hm（x）相乘。这就解释了分裂的每个分支的影响差异。梯度增强有助于预测附加模型的最佳梯度，这与经典的梯度下降技术不同，后者减少了每次迭代时的输出误差。

在梯度提升中涉及以下步骤：

F0（x）-我们用它初始化Boosting算法——将被定义：

损失函数的梯度迭代计算：

每个hm（x）适合于在每一步获得的梯度。

推导了每个终端节点的乘法因子γm，并定义了提升模型FM（x）：

5.XGBoost几大特性

XGBoosting是一种流行的梯度boosting实现。让我们来讨论让XGBoost变得如此有趣的一些特性。

正则化：XGBoost可以通过L1和L2正则化惩罚复杂模型。正则化有助于防止过度拟合。

处理稀疏数据：缺失值或数据处理步骤（如一个热编码）使数据稀疏。XGBoost结合了稀疏感知的分割查找算法来处理数据中的不同类型的稀疏模式。

加权分位数素描：当数据点具有相等的权重时（使用分位数素描算法），大多数现有的基于树的算法都可以找到分裂点。然而，它们不具备处理加权数据的能力。XGBoost有一个分布式加权分位数草图算法来有效地处理加权数据。

并行学习的块结构：为了更快的计算，XGBoost可以在CPU上使用多个内核。这是可能的，因为它的系统设计中有块结构。数据被排序并存储在被称为块的内存单元中。与其他算法不同，这使得数据布局可以在随后的迭代中重复使用，而不是再次计算。此特征也适用于分裂查找和列次采样等步骤。

高速缓存意识：在XGBoost中，通过行索引获取梯度统计信息是非连续内存访问所必需的。因此，XGBoost已经被设计用于优化硬件的使用。这是通过在每个线程中分配内部缓冲区（可以存储梯度统计信息）来完成的。

核外计算：该特性优化了可用磁盘空间，并在处理不适合内存的大型数据集时最大化了它的使用。

6.小结：

这就是关于流行的XGBoost算法的数学。如果你的基础是扎实的，这篇文章对你来说一定是微不足道的。它是如此强大的算法，尽管有其他技术从它衍生而来（如CATBoost），XGBoost仍然是机器学习社区中的游戏改变者。

原文链接：An End-to-End Guide to Understand the Math behind XGBoost

翻译：隐山君