xgboost目标函数详细推导

qlmx
qlmx
qlmx
54
文章
2
评论
2020年8月25日03:16:18 评论 2,325阅读8分14秒

xgboost目标函数详细推导

一 说明

做机器学习相关工作,难免会接触到xgboost。尤其在面试中,经常会被问及到它的原理。今天主要从他的目标函数展开,通俗的讲解xgboost。xgboost是boosting算法的其中一种,boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为xgboost是一种提升树模型,所以它是将许多树模型集成在一起,形成一个很强的分类器。通俗的理解就是不断的进行特征分裂来生长一棵树,每次添加一个树,其实是学习一个新函数,去拟合上次预测的残差。具体的目标函数如下:

$$Obj{(t)} = \sum_{i=1}^nl(y_i, \hat{y_i}^{(t-1)} + f_t(x_i)) + Ω(f_t) + constant\tag {1}$$

​ 通过上面目标函数,可知主要就是找到\(f_t\)来优化这一目标函数。通过一个简单的例子来形象的理解该目标函数。例如我们需要建立一个决策系统来预测小明有多少糖,他真实有100个糖果。首先基于一些特征建立一个决策树1,此时预测一共有90个,这时得到一个残差,这个残差值就是100-90=10,表示预测和真实值差别是10。为了提高精度,可以在该决策系统中再添加一棵树,记为树2。树2就是为了弥补上一棵树存在的残差,假设它的预测结果是5,此时总体的残差值是10-5=5,即和真实值相差为5。符号化表示:之前的结果10表示为输出结果为\(\hat{y_1}\),即上一时刻的残差值,树2的值为\(f_2\),此时得到的值。接着可以再建立第三棵树,记为树3。假设它的预测值为3,此时总体的残差值是5-3=2,即和真实值相差为2。符号化表示:上一时刻输出结果5为\(\hat{y_2}\),即上一时刻的残差值,树3为\(f_3\),此时得到的值。xgboost的目标就是通过找到\(f_t\)来优化这一目标函数,使得最终结果足够小,模型实际输出值为几棵树预测值的输出。下面对该函数进行推导化简。

xgboost目标函数详细推导

二 目标函数化简

xgboost目标函数详细推导

1、预备知识,泰勒展开式。主要使用泰勒展开式来近似原来的目标函数

$$f(x + \nabla{x}) = f(x) + f^{’}(x)\nabla{x} + \frac{1}{2}f^{''}(x)\nabla{x}\tag {2}$$

2、推导过程:
xgboost目标函数详细推导

$$=\sum_{j=1}^T[G_jw_j + \frac{1}{2}{(H_j + \lambda)w_j^2}] + \gamma{T} \tag {7}$$

  • 式(3):它是在(2)的基础上推导出来,是将\(l(y_i, \hat{y_i}^{(t-1)})\)看着(2)中的x,\(f_t(x_i)\)记为\(\nabla{x}\)(注:这里的变换是近似变换。后面式中的t,表示时刻;i表示第i个样本。将\(g_i = \partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)}), h_i = \partial_{\hat{y}^{(t-1)}}^{2}l(y_i, \hat{y}^{(t-1)}) \);又因为\(l(y_i, \hat{y_i}^{(t-1)})\)是一个固定值,可以合并到后面的常数项中。式(3)变形为式(4)
  • 式(5):它是将\(f_t(x_i)\)z和后面的正则项目展开了。
    • 这里对于f的定义做一下细化,把树拆分成结构部分q叶子权重部分w。下图是一个具体的例子。结构函数q把输入映射到叶子的索引号上面去,即第几个叶子;而w给定了每个索引号对应的叶子分数是什么。通俗的理解就是样本x落到那个叶子结点上,取该结点的值。xgboost目标函数详细推导 
    • 正则化项目选择了数据树的叶子个数,以及叶子权值大小平方。为了防止树在训练过程中过度复杂。当然这不是唯一的一种定义方式,不过这一定义方式学习出的树效果一般都比较不错。下图还给出了正则化项目计算的一个例子。xgboost目标函数详细推导
  • 式(6)主要的变换是将对样本的遍历,转换为对树的叶子结点的遍历。(理解部分:假设一共5个样本,其中共有两个样本落在上图树中的leaf1,一个样本落在leaf2中,还有两个样本落在leaf3中。式(5)是直接统计各个样本的值,式(6)则是直接遍历叶子,遍历leaf1时可以取得统计2个样本的值,leaf2时可以取得统计1个样本的值, leaf3时可以取得统计2个样本的值,同样可以访问所有的样本。在叶子上遍历更加方便计算)。式(6)中就是统计落在每个叶子结点中所有的样本的一阶导数\(g_i\)和该叶子结点权值w的乘积,同时二阶导数\(h_i\)和该叶子结点权值w的乘积(每个样本的\(g_i和h_i\)都不一样)。
  • 使式中\(G_j\)表示当前叶子结点所有样本一阶导数的和,同理\(H_j\)表示当前样本所有二阶导数的和

3 目标函数转换

$$Obj^{(t)}=\sum_{j=1}^T[G_jw_j + \frac{1}{2}{(H_j + \lambda)w_j^2}] + \gamma{T} \tag {8}$$

使得式(8)最小,令

$$\frac{\partial{j(f_t)}}{\partial{w_j}} = G_j + (H_j + \lambda)w_j = 0\tag {9}$$

得到$$w_j = -\frac{G_j}{H_j +\lambda}\tag {10}$$

将(10)代入(9)得到:$$Obj = -\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j + \lambda} + \gamma{T}\tag {11}$$

举例说明:下图中有5个样本,三个叶子结点,计算的目标函数如下,最终的目标是得到最小值:

xgboost目标函数详细推导

三 分支

xgboost目标函数详细推导

如何找到最佳的分支切割点,如上图所示。如何选取合适的a点分割,使目标函数值变小。这里是基于式(11),得到分支增益的公式:

$$Gain = \frac{1}{2}[\frac{G_L^2}{H_L +\lambda} + \frac{G_R^2}{H_R +\lambda} + \frac{G_L^2 + G_R^2}{H_L +H_R +\lambda}] -\gamma\tag {12}$$

选取是Gain最小的切割点进行分支。

继续阅读
  • 我的微信小程序
  • 这是我的微信小程序扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin
qlmx
  • 本文由 发表于 2020年8月25日03:16:18
  • 除非特殊声明,本站文章均为原创,转载请务必保留本文链接
xgboost做二分类,多分类以及回归任务 机器学习

xgboost做二分类,多分类以及回归任务

1.简介 该部分是代码整理的第二部分,为了方便一些初学者调试代码,作者已将该部分代码打包成一个工程文件,包含简单的数据处理、xgboost配置、五折交叉训练和模型特征重要性打印四个部分。数据处理部分参...
推荐系统工业界召回论文调研 深度学习

推荐系统工业界召回论文调研

1. 2020_KDD_ComiRec 论文综述:主要是应用于召回,是序列化推荐的解决方案。提出一个新的序列化推荐模块-ComiRec 解决问题: 聚焦匹配问题,提升召回的性能,也就是候选物的精度 解...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: