[关闭]
@chanvee 2015-09-10T12:52:11.000000Z 字数 2136 阅读 4861

Boosting 和 GBDT简介

数据挖掘 算法


GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree),是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力(generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。在正式介绍GBDT之前,我想先简单的介绍一下boosting算法。


Boosting

Boosting算法是一种把若干个分类器整合为一个分类器的方法,在boosting算法产生之前,还出现过两种比较重要的将多个分类器整合为一个分类器的方法,即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。

1)bootstrapping方法的主要过程:

  i)重复地从一个样本集合D中采样n个样本

  ii)针对每次采样的子样本集,进行统计学习,获得假设Hi

  iii)将若干个假设进行组合,形成最终的假设Hfinal

  iv)将最终的假设用于具体的分类任务

2)bagging方法的主要过程:

  i)训练分类器,从整体样本集合中,抽样n* < N个样本 针对抽样的集合训练分类器Ci

  ii)分类器进行投票,最终的结果是分类器投票的优胜结果

但是,上述这两种方法,都只是将分类器进行简单的组合,实际上,并没有发挥出分类器组合的威力来。到了1995年,Freund and schapire提出了现在的adaboost算法,其主要框架可以描述为:

i)循环迭代多次

ii)更新样本分布

iii)寻找当前分布下的最优弱分类器

iv)计算弱分类器误差率

v)聚合多次训练的弱分类器

数学上,如下表达:

给定样本集: (x1,y1),(x2,y2)...(xm,ym), 其中 xiX, yiY={1,1}
初始化: D1(i)=1/mDt(i)表示每个样本的权重, Dt(i)越大,表明该样本越可能被分错$
For t = 1...T:

具体实例见这篇博文


GBDT

目前GBDT有两个不同的描述版本,两者各有支持者,读文献时要注意区分。残差版本把GBDT说成一个残差迭代树,认为每一棵回归树都在学习前N-1棵树的残差,可以参见这篇博客Gradient版本把GBDT说成一个梯度迭代树,使用梯度下降法求解,认为每一棵回归树在学习前N-1棵树的梯度下降值,之前leftnoteasy的博客中介绍的为此版本(准确的说是LambdaMART中的MART为这一版本,MART实现则是前一版本)。

总的来说两者相同之处在于,都是迭代回归树,都是累加每颗树结果作为最终结果(Multiple Additive Regression Tree),每棵树都在学习前N-1棵树尚存的不足,从总体流程和输入输出上两者是没有区别的;两者的不同主要在于每步迭代时,是否使用Gradient作为求解方法。前者不用Gradient而是用残差----残差是全局最优值,Gradient是局部最优方向*步长,即前者每一步都在试图让结果变成最好,后者则每步试图让结果更好一点。

两者优缺点。看起来前者更科学一点--有绝对最优方向不学,为什么舍近求远去估计一个局部最优方向呢?原因在于灵活性。前者最大问题是,由于它依赖残差,cost function一般固定为反映残差的均方差,因此很难处理纯回归问题之外的问题。而后者求解方法为梯度下降,只要可求导的cost function都可以使用,所以用于排序的LambdaMART就是用的后者。

Markdown原文

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注