XGBoost与GBDT(二)-算法推导

2019-03-28 本文已影响0人 MashoO

前言

XGBoost跟GBDT是两种应用非常广泛的树模型,之前在几种最优化方法对比中,简单回顾了一下几种常见的最优化方法,算是对这篇内容的简单铺垫. 形象地来说, XGBoost与GBDT都是基于Boost方法的树模型, 是类似的算法模型, 都是函数优化问题. 二者最根本的区别就在于最优化的方法不同,GBDT在函数空间中利用梯度下降法进行优化, 而XGBoost在函数空间中用牛顿法进行优化 同时XGBoost有一些防止过拟合的策略.下面简单地从数学原理的角度给出两种算法的推导以及二者的对比.
实际上GBDT泛指所有的梯度提升树算法,也包括XGBoost, 这里特指Greedy Function Approximation：A Gradient Boosting Machine这篇文章提出的算法.

从泰勒公式说起

泰勒公式是一个用函数在某点的信息描述其附近取值的公式.
$f(x)=\sum_{n=0}^{\infty}\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$
这个公式如果改写成迭代形式,假设 $x^t=x^{t-1}+\Delta t$ 可以得到
$f(x^t)= \sum_{n=0}^{\infty}\frac{f^{(n)}(x^{t-1})}{n!}{\Delta t}^n$
其实回顾上文中梯度下降与牛顿法不难发现,梯度下降使用的是一阶泰勒展开,而牛顿法使用的是二阶泰勒展开, $\Delta t$ 也就是两种最优化算法中的学习步长.

GBDT算法原理

从Gradient Boosting开始
可以认为GBDT=GB+DT, DT也就是常见的Decision Tree, 在这里其实是指基分类器, 一般选择的是cart回归数.那什么是GB?
GB=Gradient+Boosting.
Boosting的思想是通过学习多个弱分类器,并将这些分类器进行线性组合从而提高分类的性能.基本的算法思路就是 $1\leqslant m \leqslant M; F_{m+1}(x)=F_m(x)+h(x)$
所以,GB也就是在生成 $h(x)$ 时基于损失函数在函数空间的负梯度学习.
GBDT
这里我们特指Friedman在Greedy Function Approximation：A Gradient Boosting Machine这篇文章里最早提出的GBDT算法.其模型F定义为加法模型:
$F(x;w)=\sum_{t=0}^{T}\alpha_th_t(x;w_t)=\sum_{t=0}^{T}f_t(x;w_t)$ ,其中 $\alpha$ 是每棵树的权重.
通过最小化损失函数求解最优模型:
$F^*=\underset{F}{argmin\sum_{i=0}^{N}L(y_i,F(x_i;w))}$
这个问题是NP难问题,通过贪心法迭代求局部最优解.
此处常用损失函数为:
$L(y_i,F(x_i;w))=\frac{1}{2}(y_i-F(x_i,w))^2$ ，此处选择平方损失，可能的原因在于，平方损失函数在是凸函数，可以使用梯度下降法进行求解。
下面解释一下残差。
前文提到过，GBDT是使用梯度下降法在函数空间进行优化，那么在第i次迭代时，我们需要求解 $min L$ ，也就是求解 $\frac{\partial L}{\partial F} = 0$ ，也就是 $\frac{\partial L}{\partial F} = y-F_i=0（1）$ , 由上文关于boosting原理可以知道 $F_i=F_{i-1}+h_i$ ,此处的 $h_i$ 为本次迭代需要得到的学习器，代入（1）中可以得到， $y-F_{i-1}-h_i=0$ , 可以得到第i次迭代的学习器的学习目标为 $h_i=y-F_{i-1}$ ,也就是通常博客里提到的残差。
算法步骤
1. 初始化算法模型
  $F_0(x)=\underset{\gamma}{argmin\sum_{i=1}{n}L(y_i, \gamma)}$
2. 迭代过程
  2.1 计算伪残差
  $r_{im}=- \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}, for\; i=1,2,...n$
  2.2 学习弱分类器 $h_m(x)$
  2.3 基于上一步学习到的弱分类器学习该分类器的权重 $\gamma_m$
  2.4 更新模型 $F_m(x)=F_{m-1}(x)+\gamma _{m}h_m(x)$
  网上有一张图片形象描述了算法的迭代过程
  GBDT迭代过程
一些理解
从每一步迭代弱分类器的学习过程可以看出,GBDT主要依靠一阶偏导的信息求解,也就提现了Gradient的特点.
优缺点
优点: 可分类可回归,可以处理非线性数据, 低维度数据下效果非常好,算法解释性较强, 可以辅助进行特征选择.
缺点: boost方法是串行过程,难以并行化,难以应付高维度稀疏数据.
此外:
2014年Facebook发表了一篇介绍将GBDT+LR模型用于其广告推荐系统的论文，之后，无论是Kaggle竞赛还是淘宝商品推荐，都有借鉴该论文中的GBDT+LR模型组合思想，即通过GBDT来发掘有区分度的特征和组合特征，来代替人工组合特征。

XGBoost

XGBoost是一种高效的梯度提升树实现,相对于GBDT,最大的区别在于, 学习过程使用了二阶偏导信息,并且把树模型复杂度作为正则项加到优化目标从而避免了过拟合.

推导过程
与GBDT一致的是,二者都是Boosting方法,因此也都是一种启发式的算法,并且迭代过程都是:
$1\leqslant m \leqslant M; F_{m+1}(x)=F_m(x)+f_m(i)$
区别也主要在于每一步求解 $f_m(i)$ 的方法.下面推导过程来自陈天奇大神的ppt
对于一般的增量训练过程:
首先确定优化的目标函数:
$Obj^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y_i}) + \sum_{i-1}^{t}\Omega(f_i)$
迭代过程 $\hat{y_i}^t=\hat{y_i}^{t-1} + f_t(x_i)$ ,带入上式得到
$Obj^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y_i}^{t-1}+ f_{t}(x_i))+\Omega(f_t)+constant$
回顾下二阶的泰勒展开
$f(x+\Delta x) \approx f(x) + {f}'(x)\Delta x+ \frac{1}{2}{f}''(x)\Delta x^2$
带入上式将损失函数展开得到
$Obj^{(t)}\approx \sum_{i=1}^{n}[l(y_i,\hat{y_i}^{(t-1)})+g_i f_t(x_i) + \frac{1}{2}h_i {f_t}^2(x_i)]+\Omega (f_t)+const$
其中 $g_i=\partial _{\hat{y}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)})$ , $h_i=\partial^{2} _{\hat{y}^{(t-1)}}l(y_i,\hat{y_i}^{(t-1)})$ ,很明显,上文中的常数项以及 $l(y_i,\hat{y_i}^{t-1})$ 对于目标函数求解最优解的时候并无影响,所以,目标函数可以改写成
$Obj^{(t)} \approx \sum_{i=1}^{n}[g_if_t(x_i)+\frac{1}{2}h_i f_t^2(x_i)] + \Omega(f_t)$
在这里使用平方损失函数得到:
$g_i=2(\hat{y}^{(t-1)}-y_i)$ , $h_i=2$
此外引入正则化项:
$\Omega (f_t)=\gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} {\omega _j}^2$ , 其中T为叶子数,
(写一半忘了保存了,过了大半个月才发现....忧桑)
更新后的目标函数:
$Obj^{(t)}=\sum_{i=1}^{n}[g_if_t(x_i)+\frac{1}{2}h_i f_t^2(x_i)] + \gamma T+\frac{1}{2}\lambda \sum_{j=1}^{T}w_j^2=\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$
这里简化一下式子,假设 $G_j=\sum_{i\in I_j}^{}g_i, H_j=\sum_{i\in I_j}^{}h_i$ 那么
$Obj^{(t)}=\sum_{j=1}^{T}[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T$ ,此时求解极值点得到
$W_j^*=-\frac{G_j}{H_j+\lambda}, Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j + \lambda} + \gamma T$
根据这个式子,可以知道,在树结构确定的时候,就能得到该结构下最好的分数,那么如何确定树结构?
既然是树结构,那么还是用C4.5, 但是作者在这里定义了一个新的增益.
首先 $Obj_{split}=-\frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}]+\gamma T_{split}$
$Obj_{nosplit}=\frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\gamma T_{nosplit}$
$Gain=Obj_{split}-Obj_{nosplit}$
以上就是XGBoost的基本原理,不过到这里为止,算法的并行效率很低,基本上就是单线程,因此作者在此基础之上做了一些优化,等以后理解透彻一些再补充把.

XGBoost与GBDT(二)-算法推导

前言

从泰勒公式说起

GBDT算法原理

XGBoost

猜你喜欢

热点阅读