Gbdt（mart）概念简介

jopen 9年前

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种用于回归的机器学习算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。当把目标函数做变换后，该算法亦可用于分类或排序。

本文主要从高层明确几个GBDT概念，主要讲GBDT的两个版本以及GBDT是什么不是什么。详细介绍见文中的链接。

GBDT的两个不同版本

目前GBDT有两个不同的描述版本，两者各有支持者，读文献时要注意区分。残差版本把GBDT说成一个残差迭代树，认为每一棵回归树都在学习前N-1棵树的残差，之前我写的GBDT入门教程主要在描述这一版本，ELF开源软件实现中用的也是这一版本。Gradient版本把 GBDT说成一个梯度迭代树，使用梯度下降法求解，认为每一棵回归树在学习前N-1棵树的梯度下降值，之前leftnoteasy的博客中介绍的为此版本，umass的源码实现中用的则是这一版本（准确的说是LambdaMART中的MART为这一版本，MART实现则是前一版本）。

对GBDT无基础的朋友可以先分别看一下前面两篇博文教程。总的来说两者相同之处在于，都是迭代回归树，都是累加每颗树结果作为最终结果（Multiple Additive Regression Tree)，每棵树都在学习前N-1棵树尚存的不足，从总体流程和输入输出上两者是没有区别的；两者的不同主要在于每步迭代时，是否使用Gradient 作为求解方法。前者不用Gradient而是用残差----残差是全局最优值，Gradient是局部最优方向*步长，即前者每一步都在试图让结果变成最好，后者则每步试图让结果更好一点。

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

GBDT中的Tree是回归树，不是分类决策树。

详见GBDT入门教程

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。 GBDT除了描述的残差版本外还有另一种GBDT描述，两者大概相同，但求解方法（Gradient应用）不同。其区别和另一版本的介绍链接见： 由于另一版本介绍博客中亦有不少错误，建议大家还是先看本篇，再跳到另一版本描述，这个顺序当能两版本都看懂。 第1~4节：GBDT算法内部究竟是如何工作的？第5节：它可以用于解决哪些问题？第6节：它又是怎样应用于搜索排序的呢？ 比较推荐的两篇英文文献，喜欢英文原版的同学可直接阅读： Boosting Decision Tree入门教程 http://www.schonlau.net/publication/05stata_boosting…

GBDT中的Boost是样本目标的迭代，不是re-sampling的迭代，也不是Adaboost。

Adaboost中的boosting指从样本中按分类对错，分配不同的weight，计算cost function时使用这些weight，从而让“错分的样本权重越来越大，直到它们被分对”。Bootstrap也有类似思想，只不过它可以利用不同的 weight作为sample概率对训练样本集做re-sample，让错分的样本被进一步学习，而分类正确的样本就不用再学了。但GBDT中的 boost完全不同，跟上述逻辑没有任何关系，GBDT中每步boost的样本集都是不变的，变的是每个样本的回归目标值。详见之前我写的GBDT入门教程。

Shrinkage不是Gradient的步长

Shrinkage只是一种大步变小步的逐步求精方法。这点看起来和Gradient目标=Gradient单位方向*步长挺像，但其实很不同：

  1. shrinkage的处理对象不一定是Gradient方向，也可以是残差，可以是任何增量，即目标=任何东西*shrinkage步长。
  2. shrinkage决定的是最终走出的一步大小，而不是希望走出的一步大小。前者是对于已有的学习结果打折，后者是在决定学习目标时对局部最优方向上走多远负责。
  3. shrinkage设小了只会让学习更慢，设大了就等于没设，它适用于所有增量迭代求解问题；而Gradient的步长设小了容易陷入局部最优点，设大了容易不收敛。它仅用于用梯度下降求解。这两者其实没太大关系。LambdaMART中其实两者都用了，而外部可配的参数是shrinkage而不是Gradient步长。

GBDT中的Gradient不一定必须是Gradient

见第1部分的两个版本。

来自：http://suanfazu.com/t/gbdt-mart-gai-nian-jian-jie/133