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)聚合多次训练的弱分类器

数学上，如下表达：

给定样本集: $(x_1, y_1), (x_2, y_2)... (x_m, y_m)$, 其中 $x_i \in X$, $y_i \in Y = \{1, -1\}$
初始化: $D_1(i) = 1/m$，$D_t(i)$表示每个样本的权重， $D_t(i)$越大，表明该样本越可能被分错$
For t = 1...T:

• 用分布$D_t$训练弱分类器
• 得到如分类器的假设函数 $h_t$: X -> (1, -1), 其误差为：$\epsilon_{t} = Pr_{i \in D_t}(h_t(x_i) \neq y_i)$
• 得到 $\alpha_t = \frac{1}{2}ln(\frac{1-\epsilon_{t}}{\epsilon_{t}})$, $\alpha_t$表示的即为该分类器的权重，$\epsilon_{t}$ 越大，误差越大，分类效果越差，那么该分类器对应的权重就会更小

• 更新：
  

  $$\begin{eqnarray}D_{t+1}(i) = \frac{D_t(i)}{Z_t} \begin{cases} e^{-\alpha_t}, & h_t(x_i) = y_i \cr e^{\alpha_t}, & h_t(x_i) \neq y_i \end{cases} \end{eqnarray}$$
  其中$Z_t$是归一化参数，这样每次迭代就能将被分错的样本增大权重，反之分错的样本权重减小

• 最后得到最终的强分类器：$H(x) = sign(\sum_{t=1}^{T}\alpha_t h_t(x))$

具体实例见这篇博文。

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原文