前言
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也就是在生成时基于损失函数在函数空间的负梯度学习.GBDT
这里我们特指Friedman在Greedy Function Approximation:A Gradient Boosting Machine这篇文章里最早提出的GBDT算法.其模型F定义为加法模型:
,其中是每棵树的权重.
通过最小化损失函数求解最优模型:
这个问题是NP难问题,通过贪心法迭代求局部最优解.
此处常用损失函数为:
,此处选择平方损失,可能的原因在于,平方损失函数在是凸函数,可以使用梯度下降法进行求解。
下面解释一下残差。
前文提到过,GBDT是使用梯度下降法在函数空间进行优化,那么在第i次迭代时,我们需要求解,也就是求解,也就是, 由上文关于boosting原理可以知道,此处的为本次迭代需要得到的学习器,代入(1)中可以得到,, 可以得到第i次迭代的学习器的学习目标为,也就是通常博客里提到的残差。-
算法步骤
- 初始化算法模型
- 迭代过程
2.1 计算伪残差
2.2 学习弱分类器
2.3 基于上一步学习到的弱分类器学习该分类器的权重
2.4 更新模型
网上有一张图片形象描述了算法的迭代过程
- 初始化算法模型
一些理解
从每一步迭代弱分类器的学习过程可以看出,GBDT主要依靠一阶偏导的信息求解,也就提现了Gradient的特点.优缺点
优点: 可分类可回归,可以处理非线性数据, 低维度数据下效果非常好,算法解释性较强, 可以辅助进行特征选择.
缺点: boost方法是串行过程,难以并行化,难以应付高维度稀疏数据.
此外:
2014年Facebook发表了一篇介绍将GBDT+LR模型用于其广告推荐系统的论文,之后,无论是Kaggle竞赛还是淘宝商品推荐,都有借鉴该论文中的GBDT+LR模型组合思想,即通过GBDT来发掘有区分度的特征和组合特征,来代替人工组合特征。
XGBoost
XGBoost是一种高效的梯度提升树实现,相对于GBDT,最大的区别在于, 学习过程使用了二阶偏导信息,并且把树模型复杂度作为正则项加到优化目标从而避免了过拟合.
- 推导过程
与GBDT一致的是,二者都是Boosting方法,因此也都是一种启发式的算法,并且迭代过程都是:
区别也主要在于每一步求解的方法.下面推导过程来自陈天奇大神的ppt
对于一般的增量训练过程:
首先确定优化的目标函数:
迭代过程,带入上式得到
回顾下二阶的泰勒展开
带入上式将损失函数展开得到
其中,,很明显,上文中的常数项以及对于目标函数求解最优解的时候并无影响,所以,目标函数可以改写成
在这里使用平方损失函数得到:
,
此外引入正则化项:
, 其中T为叶子数,
(写一半忘了保存了,过了大半个月才发现....忧桑)
更新后的目标函数:
这里简化一下式子,假设那么
,此时求解极值点得到
根据这个式子,可以知道,在树结构确定的时候,就能得到该结构下最好的分数,那么如何确定树结构?
既然是树结构,那么还是用C4.5, 但是作者在这里定义了一个新的增益.
首先
以上就是XGBoost的基本原理,不过到这里为止,算法的并行效率很低,基本上就是单线程,因此作者在此基础之上做了一些优化,等以后理解透彻一些再补充把.