XGBoost与GBDT(二)-算法推导 XGBoost与GBDT(二)-算法推导

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

这个公式如果改写成迭代形式,假设可以得到

其实回顾上文中梯度下降与牛顿法不难发现,梯度下降使用的是一阶泰勒展开,而牛顿法使用的是二阶泰勒展开,也就是两种最优化算法中的学习步长.
GBDT算法原理

从Gradient Boosting开始
可以认为GBDT=GB+DT, DT也就是常见的Decision Tree, 在这里其实是指基分类器, 一般选择的是cart回归数.那什么是GB?
GB=Gradient+Boosting.
Boosting的思想是通过学习多个弱分类器,并将这些分类器进行线性组合从而提高分类的性能.基本的算法思路就是
所以,GB也就是在生成时基于损失函数在函数空间的负梯度学习.
【XGBoost与GBDT(二)-算法推导】GBDT
这里我们特指Friedman在Greedy Function Approximation：A Gradient Boosting Machine这篇文章里最早提出的GBDT算法.其模型F定义为加法模型:
,其中是每棵树的权重.
通过最小化损失函数求解最优模型:

这个问题是NP难问题,通过贪心法迭代求局部最优解.
此处常用损失函数为:
，此处选择平方损失，可能的原因在于，平方损失函数在是凸函数，可以使用梯度下降法进行求解。
下面解释一下残差。
前文提到过，GBDT是使用梯度下降法在函数空间进行优化，那么在第i次迭代时，我们需要求解，也就是求解，也就是, 由上文关于boosting原理可以知道,此处的为本次迭代需要得到的学习器，代入（1）中可以得到，, 可以得到第i次迭代的学习器的学习目标为,也就是通常博客里提到的残差。
算法步骤
1. 初始化算法模型
2. 迭代过程
  2.1 计算伪残差
  
  2.2 学习弱分类器
  2.3 基于上一步学习到的弱分类器学习该分类器的权重
  2.4 更新模型
  网上有一张图片形象描述了算法的迭代过程
  
  文章图片
  GBDT迭代过程
一些理解
从每一步迭代弱分类器的学习过程可以看出,GBDT主要依靠一阶偏导的信息求解,也就提现了Gradient的特点.
优缺点
优点: 可分类可回归,可以处理非线性数据, 低维度数据下效果非常好,算法解释性较强, 可以辅助进行特征选择.
缺点: boost方法是串行过程,难以并行化,难以应付高维度稀疏数据.
此外:
2014年Facebook发表了一篇介绍将GBDT+LR模型用于其广告推荐系统的论文，之后，无论是Kaggle竞赛还是淘宝商品推荐，都有借鉴该论文中的GBDT+LR模型组合思想，即通过GBDT来发掘有区分度的特征和组合特征，来代替人工组合特征。

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

推导过程
与GBDT一致的是,二者都是Boosting方法,因此也都是一种启发式的算法,并且迭代过程都是:

区别也主要在于每一步求解的方法.下面推导过程来自陈天奇大神的ppt
对于一般的增量训练过程:
首先确定优化的目标函数:

迭代过程,带入上式得到

回顾下二阶的泰勒展开

带入上式将损失函数展开得到

其中,,很明显,上文中的常数项以及对于目标函数求解最优解的时候并无影响,所以,目标函数可以改写成

在这里使用平方损失函数得到:
,
此外引入正则化项:
, 其中T为叶子数,
(写一半忘了保存了,过了大半个月才发现....忧桑)
更新后的目标函数:
$XGBoost与GBDT(二)-算法推导$
文章图片

这里简化一下式子,假设那么
,此时求解极值点得到

根据这个式子,可以知道,在树结构确定的时候,就能得到该结构下最好的分数,那么如何确定树结构?
既然是树结构,那么还是用C4.5, 但是作者在这里定义了一个新的增益.
首先

以上就是XGBoost的基本原理,不过到这里为止,算法的并行效率很低,基本上就是单线程,因此作者在此基础之上做了一些优化,等以后理解透彻一些再补充把.