社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  机器学习算法

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

深度传送门 • 4 年前 • 332 次点击  

前言

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

你点的每个“在看”,我都认真当成了喜欢
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/110108
 
332 次点击