Boosting原理

385 阅读4分钟
原文链接: www.jianshu.com
xgboost xgboost

集成学习

集成学习是什么?集成学习通过训练多个分类器,然后将其组合起来,从而达到更好的预测性能,提高分类器的泛化能力。

集成学习 集成学习

目前集成学习主要有3个框架:bagging,boosting,stacking。

先看第一个bagging:bagging的时候每个分类器都随机从原样本中做有放回的采样,训练基模型,最后根据多个基模型的预测结果产出最终的结果。bagging的一种常见方法是我们训练好多模型:SVM, 决策树,DNN等,然后将最后再用一个lr做组合。

bagging bagging

第二个boosting:boosting每次对训练集进行转换后重新训练出基模型,最后再综合所有的基模型预测结果。主要算法有 AdaBoost 和 GBDT。


boosting boosting

第3个stacking:stacking的思想是将每个基模型的输出组合起来作为一个特征向量,重新进行训练。


stacking stacking

在学习集成学习中,我们需要知道一个非常重要的概念:Diversity,我们希望每个基模型都不尽相同,这样子最后的预测结果才能好。

xgboost详解

假设我们最后的预测函数形式如下:

ensembleensemble
最终的预测结果由K颗树集成所成,接着我们定义要优化的目标函数:
loss loss
目标函数由两部分组成:第一部分是训练损失,第二部分则是每颗树的复杂度,复杂度的衡量有多种方法:树的深度,内部节点个数,叶子节点个数(T),叶节点分数(w),xgboost使用了:
正则 正则
我们将预测函数稍微做个展开:
predict predict
第t次迭代后,模型的预测等于前t-1次的模型预测加上第t棵树的预测,此时的目标函数:
目标函数 目标函数
此时我们将目标函数做二阶泰勒展开:
泰勒展开 泰勒展开
此时第一项是一个常数项,重新整理目标函数得到:
整理后 整理后
上式中误差函数和正则项分别是:
image_1c0anp25fcq81ptv8kr102sm8c16.png-20.5kB image_1c0anp25fcq81ptv8kr102sm8c16.png-20.5kB
将其带入目标函数,并整理得到:
image_1c0anptuh1bf31t8e15i711ir1hji1j.png-40.5kB image_1c0anptuh1bf31t8e15i711ir1hji1j.png-40.5kB
此时我们考虑将对样本的累加和对叶子节点的累加统一到节点的累加,定义下面的函数:
image_1c0ans58m15bo13m7cofcdqhvo20.png-63kB image_1c0ans58m15bo13m7cofcdqhvo20.png-63kB

此处我们假设了树的结构是固定的,于是对目标函数求导后可得:


image_1c0anuli27rp1g6hjn4so316bb2d.png-29.8kB image_1c0anuli27rp1g6hjn4so316bb2d.png-29.8kB

到这一步:我们已经推导出其最优的叶节点分数以及对应的最小损失值,下一步需要解决的问题是:怎么确定树结构。

我们尝试着计算分裂后树的增益,选择增益最大的点进行分裂,在计算增益上,ID3算法采用信息增益,C4.5算法采用信息增益比,CART采用Gini系数,xgboost采用:


image_1c0ao4v6i1flg10ms1nbc1k37ecq2q.png-8.4kB image_1c0ao4v6i1flg10ms1nbc1k37ecq2q.png-8.4kB

分裂前后的增益定义:


image_1c0ao5hfrgkm1occ12n75qf1h1937.png-15.1kBimage_1c0ao5hfrgkm1occ12n75qf1h1937.png-15.1kB

再有的优化就是对于怎么快速计算树结构了,网上内容很多,不再详述了。

adaboost 推导

adaboostadaboost

此时我们对损失函数对参数beta求导,可得


image_1c0d3m16a1i191gc4te81hsqho141.png-44.9kB image_1c0d3m16a1i191gc4te81hsqho141.png-44.9kB

gbdt

梯度提升算法:首先给定一个损失函数L(y,F(x)),其输入是训练对:(x1,y1),(x2,y2),...,(xn,yn),目标是找到最优的F(x),使得损失函数L最小,按照传统梯度下降的方法,我们会将训练数据(xi,yi)带入,然后求L对参数的偏导,再用负梯度进行参数更新:

image_1c0fndee91aoh1blp7nsq2pupi4e.png-51.2kB image_1c0fndee91aoh1blp7nsq2pupi4e.png-51.2kB
这么做的一个前提是我们需要保证损失函数对F可微,F对参数 $\theta$可微,第二个可微可以说比较困难,于是我们退而求此次直接求对于F的梯度(函数空间):
image_1c0fo4iuf153a1pl0i021f2f15u19.png-18.5kB image_1c0fo4iuf153a1pl0i021f2f15u19.png-18.5kB
此时f可以用梯度下降的方法,求损失函数在$F_{m-1}$的导数,可得到:
image_1c0fo70ng15ph1924lmfmkh1a1fm.png-12.9kB image_1c0fo70ng15ph1924lmfmkh1a1fm.png-12.9kB
此时我们假设$F_{m-1}$和$y_i$都是已知的,则只有$\gamma_m$是未知的,通过一维的线性搜索就可以找到最优的值:
image_1c0fo9ndt16o44m719h8mip173113.png-16.2kBimage_1c0fo9ndt16o44m719h8mip173113.png-16.2kB

通过上面的讲述,我们将通过(x,y)来求未知参数$\theta$,转换为通过$(x,\nabla_f(y_i,F_{m-1}))$来预估第m颗树$f$,整个过程总结如下:


image_1c0fp3vem14b1vot1un2k21p712d.png-91.3kB image_1c0fp3vem14b1vot1un2k21p712d.png-91.3kB

下一篇将通过代码来详细介绍本篇的算法,尽请期待。

参考

使用 sklearn 进行集成学习——理论
GBDT算法原理与系统设计简介
小象学院《机器学习》课程