xgboost目标函数推导

作者: 文一休 | 来源:发表于2019-01-08 22:56 被阅读0次

xgboost目标函数推导
xgboost公式推导
11 集成学习 - XGBoost案例 - 波士顿房价进行预测
spark xgboost损失函数和评价函数的修改
09 集成学习 - XGBoost公式推导
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
logistic 线性回归函数推导过程
Xgboost原理及推导
Logistic Regression
xgboost复合直觉的推导

一说明

xgboost是boosting算法的其中一种，该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。具体的目标函数如下：

$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$ 来优化这一目标函数，使得最终结果足够小。下面对该函数进行推导化简。

二目标函数化简

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

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

2、推导过程：

$Obj{(t)} = \sum_{i=1}^n[l(y_i, \hat{y_i}^{(t-1)})+\partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})*f_t(x_i) +\partial_{\hat{y}^{(t-1)}}^{2}l(y_i, \hat{y}^{(t-1)})*\frac{f_t(x_i)}{2} + Ω(f_t) + constant\tag {3}$ $\approx{ \sum_{i=1}^n[g_i*f_t(x_i) + h_i*\frac{f_t(x_i)}{2}] + Ω(f_t) + constant}\tag {4}$

$=\sum_{i=1}^n[g_i*w_{q(x_i)} + \frac{1}{2}h_i*w_{q(x_i)}^2] + \gamma{T} + \lambda{\sum_{j=1}^T\omega_j^{2}} \tag {5}$

$=\sum_{j=1}^T[(\sum_{i\in{I_j}}g_i) w_j+ \frac{1}{2}((\sum_{i\in{I_j}}h_i + \lambda) w_j^2)] + \gamma{T}\tag {6}$ $=\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落到那个叶子结点上，取该结点的值。
  image
- 正则化项目选择了数据树的叶子个数，以及叶子权值大小平方。为了防止树在训练过程中过度复杂。当然这不是唯一的一种定义方式，不过这一定义方式学习出的树效果一般都比较不错。下图还给出了正则化项目计算的一个例子。 image
式(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个样本，三个叶子结点，计算的目标函数如下，最终的目标是得到最小值：

image

三分支

image

如何找到最佳的分支切割点，如上图所示。如何选取合适的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最小的切割点进行分支。

写在最后

关注公号:

AI成长社
学习机器学习，深度学习知识，了解最新技术进展，一块成长。
知乎专栏：ML与DL成长之路

xgboost目标函数推导
一说明 xgboost是boosting算法的其中一种，该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵...
xgboost公式推导
xgboost公式推导基本构成 boosted tree作为有监督学习算法有几个重要部分：模型、参数、目标函数、...
11 集成学习 - XGBoost案例 - 波士顿房价进行预测
08 集成学习 - XGBoost概述09 集成学习 - XGBoost公式推导10 集成学习 - XGBoost...
spark xgboost损失函数和评价函数的修改
spark xgboost自定义损失函数和评价函数一、spark xgboost自定义损失函数 xgboost定...
09 集成学习 - XGBoost公式推导
08 集成学习 - XGBoost概述根据上面的知识对XGBoost公式推导回顾: 第t次迭代后，模型的预测值...
超详细白板推导：从模型和优化 2 个角度详解 SVM 核函数
在 SVM 白板推导| 由最大间隔化目标演化的损失函数推导过程中白板手推了 SVM 的原理，并介绍了硬间隔核函数...
logistic 线性回归函数推导过程
sigmod 函数image.png sigmod 求导推导sigmoid推导.jpeg 代价函数推导logist...
Xgboost原理及推导
Xgboost无论是工业界还是kaggle比赛效果都很好，学习过程中看了很多博客依然理解的不是很好，自己比较菜，看...
Logistic Regression
推导 sigmoid 推导LR损失函数推导LR梯度下降 Softmax原理 softmax 损失函数 softm...
xgboost复合直觉的推导
https://towardsdatascience.com/boosting-algorithm-xgboost...