gbdt&xgboost小结

对gbdt和xgboost做一下总结

一、前言 #

GBDT最原始的版本一般是指Friedman在1999年发表那篇GBM[1]，xgboost[3]是陈天奇等人对GBDT的一种高效实现。

二、GBM(Gradient Boosting Machine) #

模型 #

GBM在模型上是一个加法模型，由M个函数累加得到最后结果，beta是每个函数的权重，h是函数。在GBM文章中，这里的h使用是regression tree。

目标函数 #

GBM里面没有加正则项

学习算法 #

学习的算法实际上是在函数空间上做梯度下降 1.Fo(x)可以随机初始化，或者根据样本统计初始化化 2.M是树的总个数 3.基于损失函数计算当前对F(x)的梯度，这个梯度被称为pseudo-response 4.学习树内部的参数alpha和beta，去拟合这个response 5.在学到树参数后，做line search，寻找最优的p,使得损失函数最小 6.更新F(x)

三、xgboost #

模型 #

加法模型，树模型使用CART。q表示树的结构，把输入映射到一个叶子节点。T表示叶子节点个数。w表示第i个叶子节点的score。

对于一个输入x，把每个叶子节点的score相加，就得到预测的y

目标函数 #

加上了正则项，防止过拟合。另外xgboost也支持shrinkage和feature subsampling的方法来防止过拟合。

学习算法 #

如何评估分裂效果 #

新学习ft(x)的目的是使得损失函数L最小

将损失函数在ft(x)这个点进行二阶泰勒展开，得到如上情况，g和h分别是一阶和二阶偏导数

去掉常数项

将公式进行改写成跟参数w和q相关

对于固定的树结构q，可以求得最优参数w使得Loss最小，将w带入得到最优Loss。

选择一个特征分裂点后，可以计算分裂前后Loss和改变情况，以此作为评估分裂效果的标准。这个跟决策树里的基尼系数、信息熵等分裂评估标准类似，不同的是这种方式可以支持多种目标函数（通过求g和h就行）

选择分裂点 #

Basic Exact Greedy Algorithm #

选择分裂点，最基础的方式是贪心的遍历每个分类点，计算score，找最大的。但是这种方式计算开销太大。

Approximate Algorithm #

当数据量太大，无法完成放到内存时，Exact Greedy Algorithm就不太管用了，因此需要设计一种近似求解的方法。首先特征的分布分位设计分裂点，将特征划分到不同的bucket里面，聚合统计bucket里的信息，在不同bucket之间找分类点。更具体的看划分为global方式和local方式:

global方式在最初始阶段做全局的分裂点划分，总体上需要更少的统计次数，但是通常需要统计的候选集量更多。
local方式在每次分裂之后做一遍。每次分裂后会调整候选集，所以最后需要处理的候选集可能少一点。可能更适合deeper trees。

在有足够多候选集的情况下，global和local的精确度相似。也可以使用其他分箱的方式来划分，在xgboost中实现是一种weighted quantile方法。

Sparsity-aware Split Finding #

xgboost对于missing value会有一个分裂的default direction。这个默认分裂方向是基于non-missing数据集进行学习的，分别向左和向右分裂，计算哪个方向带来的收益最大，记为默认方向，预测时使用。

四、其他 #

gbdt与xgboost的区别和联系 #

总的来说，两者之间的区别和联系可以总结成以下几个万面。

GBDT 是机器学习算法，XGBoost是该算法的工程实现。
在使用CART作为基分类器时，XGBoost显式地加入了正则来控制模型的复杂度，有利于防止过拟台，从而提高模型的泛化能力。
GBDT在模型训练时只使用了Loss func的一阶导数信患，XGBoost对Loss func进行二阶泰勒展开（并不是XGBOOST首次提出），可以同时使用一阶和二阶导数。
传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。
传统的GBDT在每轮迭代时使用全部的数据， XGBoost则采用了与随机森林相似的策略，支持对数据（行和列）进行采样。
传统的GBDT没有设计对缺失值进行处理，XGBoost 能够自动学习出缺失值的处理策略。

Reference #

[1] Greedy function approximation a gradient boosting machine J.H. Friedman First paper about gradient boosting [2] Additive logistic regression a statistical view of boosting. J.H. Friedman T. Hastie R. Tibshirani Uses second-order statistics for tree splitting, which is closer to the view presented in this slide [3] XGBoost: A Scalable Tree Boosting System