查看原文
其他

结合论文理解 XGBoost 推导过程

The following article is from 推荐算法的小齿轮 Author 潜心

前言

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部分内容进行总结、解释与扩展,并不包括后续的各种优化方法。

推荐阅读

贝叶斯学派与频率学派有何不同?

Toad:基于Pyhon的标准化评分卡模型

机器学习模型评估指标ROC、AUC详解

数据挖掘实战:个人信贷违约预测

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存