机器学习面试 ｜ 结合论文理解XGBoost推导过程

前言

XGBoost是一个可扩展的提升树模型，论文“XGBoost: A Scalable Tree Boosting System”发表在2016年的KDD会议上。文章包括了XGBoost的原理以及对其的优化。本文主要分享XGBoost的推导过程，包含论文内容2.1-2.2部分，这里假设你已掌握决策树、GBDT的相关知识。

本文约2.7k字，预计阅读10分钟。

XGBoost原理

XGBoost最关键的思想就是采用二阶导来近似取代一般损失函数。整个推导过程分为以下几个步骤（问题）：

1. 目标函数的构造；
2. 目标函数难以优化，如何近似？
3. 将树的结构（参数化，因为模型的学习参数在树中）融入到目标函数；
4. 如何构造最优（局部）二叉树？采用贪心算法；

目标函数定义

首先我们假设一个数据集中包含个样本以及每个样本有个特征，因此数据集可以定义为：

对于提升树模型来说，我们假设共有个叠加函数（additive functions，即决策树），那么整个模型可以表示为：

其中：

• ：表示模型对样本的预测值；
• ：模型函数；
• ：表示单个样本；
• ：表示第决策树；
• ；表示决策树的空间集合；

我们要学习上述集成模型函数（也称加法模型），则需要最小化正则化后的损失函数（即目标函数，正则化是对复杂决策树的惩罚）：

表示第个决策树的复杂度，这里我们先不去参数化和。

梯度提升算法

问题1： 对于上述的目标函数，其实很难在欧氏空间中使用传统的优化方法。

因此，提升树模型采用前向分步的学习方法。假设表示在第次迭代时对第个样本的预测，那么我们可以将目标函数转化为以下形式（这里假设你已掌握提升树算法的知识）：

其中， 表示第次迭代时，集成模型对样本的预测，表示第个决策树。为常数，所以我们只需要学习，当然对于决策树复杂度的刻画，前的决策树的复杂度此时为常数，所以目标函数并没有包括。

【注】：为一个常数，我们当然尽可能希望其与真实值更近，为两者之间的一个「残差」，希望尽可能的趋于0，所以这就是为什么后面我们可以将看成。

问题2： 此时，目标函数变得更为简单，但是仍然无法描述损失函数，因为并不知道其类型，一般的复杂函数也很难刻画。

所以，我们需要一个近似函数来表示损失函数。论文中提到，采用在一般设定下，二阶近似法（Second-order approximation）可用于快速优化目标。论文这里引用了一篇参考文献，其实就是通过泰勒公式用函数在某点的信息描述其附近取值。

首先可以了解微分（微分是函数在一点附近的最佳线性近似）来近似表示一般函数【从几何的角度讲，就是在某点的切线来近似于原函数附近的曲线，二阶近似则是采用抛物线】：

为高阶无穷小，所以：

所以附近的值可以用上述线性近似来表示，「而GBDT就是采用线性近似（微分）来描述一般的损失函数。」 对于XGBoost来说，采用二阶近似（二阶泰勒公式）来描述损失函数：

那么如何应用在我们定义的损失函数？其实可以对应于，对应于，所以可以得到近似的损失函数：

我们令，因此近似目标函数化简为

并且为一个常数，所以可以去掉：

【注】：一阶导和二阶导是已知的，因此需要学习的参数包含在中。

问题3：如何参数化【将需要学习的参数在目标函数中显示】表示和决策树的复杂度？

对于，文章给出定义：

其中表示表示单个树的结构，即样本对应的叶子结点的索引。表示叶子结点的值。【某个样本的预测值对应于某个叶子结点的值，这样就能描述清楚决策树上对应每个样本的预测值】。但是下标依旧带有参数，所以最终作者用：

表示「决策树中分配到第个叶子结点中的样本集合」，这样，所有的叶子结点集合就能描述整个决策树。

而决策树的复杂度与叶子结点的数量和叶子结点的值（学习参数）相关，所以一般表示为：

所以，我们将目标函数表示为：

可以看到，这其实是关于的一个二次函数，我们可以使用中学的知识，最优解为，即：

计算对应的目标函数为：

以上便是XGBoost的梯度提升算法的推导过程。

寻找分割点（决策树构造）

上述近似目标函数可以作为一个决策树的评价分数，但是我们之前对于最小化目标函数来优化决策树的值是「假定决策树的结构是已知的」。简单来说，就是目前我们可以做到给定一个决策树的结构，我们可以将它的叶子结点的值进行优化，并且可以达到一个评价它性能的分数。

问题4：如何构造决策树？

最简单的方法是将所有决策树的结构全部罗列出来，然后优化，计算他们的目标函数值，进行比较，选择最小目标函数值的决策树。但是如果决策树深度过深，那么所有决策树的数量太多，很难完成上述步骤。

所以，文章采用了一种贪心算法（greedy algorithm）的策略，从单个叶子结点开始，迭代的增加分治进行比较。

假设，当前有样本，目前决策树为：

其目标函数值可以表示为：

我们对右下叶子结点增加新的分支：

此时目标函数值为：

我们将两者相减，得到：

如果，则说明可以进行分支，所以我们可以推导出，

其中与指代分割叶子结点后的新的左右叶子结点。通过以上分割方法，就可以分步的找到基于贪心的局部最优决策树。

总结

上述是我结合论文的2.1和2.2部分内容进行总结、解释与扩展，并不包括后续的各种优化方法。