机器学习算法二：详解Boosting系列算法三XGboost及总结

XGboost

XGboost 是eXtreme Gradient Boosting ，他是在GBM基础上的改进，内部同样采用决策树作为基学习器，XGboost（下文称为XGB）与GBM的区别在于损失函数更新的方式，GBM利用的是梯度下降法的近似方法，而XGB方法则引入了牛顿法进行损失函数的寻优，因为牛顿法使用到了二阶导，这就是为什XGB要叫做极端梯度法。
接下来讲解XGB方法前先介绍一些基础的内容。

牛顿法
牛顿法是求解无约束最优化问题的常用方法，有收敛速度快的特点。牛顿法采用的是迭代算法，每一步需要求解目标函数的海森矩阵（Hessian Matrix）的逆矩阵。假设一个无约束优化问题

,求x最小值点，假设f(x)$f(x)$具有二阶连续偏导数，若第m次迭代值为x(m)$x^{(m)}$，则将f(x)$f(x)$在x(m)$x^{(m)}$附近进行泰勒二阶展开： Δθ=x−x(m)$\mathrm{\Delta }\theta =x-x^{(m)}$，为了方便分析将一阶导数和二阶倒数做简化推广如下 gm$g_m$为函数在当前点的梯度向量，Hm$H_m$称为当前点的海森矩阵
牛顿法利用的是函数有极值的必要条件是在极值点一阶导数为0的理论，所以有 ,最后可知将上面第二个公式作为迭代更新公式的方法就是牛顿法。

XGB

该算法就建立在boosting方法上，利用牛顿法来求解损失函数的最小值。
计算步骤如下：

第一步，定义boosting方法的目标函数
第二步，建立循环
第三步，求解第m步迭代的损失函数的梯度向量gm(xi)$g_m(x_i)$
第四步，求解第m步迭代的海森矩阵hm(xi)$h_m(x_i)$
第五步，利用牛顿法求解损失函数最小化的决策树参数θm${\theta }_m$
第六步，结合每个基学习器的权值η$\eta$,得到基学习器模型fm(x)=ηθm(x)$f_m(x)=\eta {\theta }_m(x)$
最后将所有循环得到的基学习器模型相加f(x)=∑mMfm(x)$f(x)=\sum _m^M{f}_m(x)$

boosting方法总结

最近将boosting类算法三大方法都学习了：adaboost、GBM以及XGB。现在来做一个总结：
boosting系列算法是利用很多串联的基学习器，通过改变每个基学习器的输入数据的分布得到不同的弱学习模型，对这些模型进行线性组合最终得到一个强学习模型。最常用的基学习器是决策树，也是目前认为表现最好的基学习器。
所有的boosting算法都有可以看做是一个前向加法模型,对于每个模型求经验风险最小化

T$T$为每次学习到的树模型，α$\alpha$对应不同树模型的权重系数，经过多个不同的模型迭代相加使最终结果逼近最优参数。比如梯度下降boost（GBM）
从参数空进到函数空间，我们都可以看到不断用负的梯度向量相加，类似于梯度下降的效果，最终参数的累加会趋近于最优解。同样的道理来看XGB
只是梯度下降的参数增量改变了而已，实质还是一样的。

那为什么会先后提出adaboost、GBM以及XGB算法呢？

GBM算法得提出是为了弥补adaboost无法自定义损失函数的缺点，因为当损失函数是平方损失或指数损失时，每步的残差很好求，但是对于一般的损失函数就不方便求解了，为弥补adaboost的不足，于是就利用损失函数的负梯度向量来求取残差的近似值。
XGB的提出是认为利用二阶偏导估计残差会比GBM只利用了一阶导数估计更准确，但实际上差距并不会那么明显，只要影响性能的是:超参数、正则化项。随机参数等。

项了解更多详细的知识点，请参考以下资料：
1.Tree Boosting With XGBoost Why Does XGBoost Win “Every” Machine Learning Competition?. Didrik Nielsen
这个资料很详尽的解释了tree boosted 以及对比了GBM和XGB，非常适合深入的学习。
2.Introduction to Boosted Trees.Tianqi Chen
这是相对于前一个要简单易懂一些，适合入门和建立总体概念。
3.GBDT算法原理与系统设计简介.wepon.http://wepon.me
这个资料有助于提高一些理解，可以最后来看。