- GBDT是Gradient Boosting Decision Tree的简写，中文为梯度提升决策树，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
GBDT中的GB
GB代表的是Gradient Boosting，意为梯度提升，梯度是一种数学概念，一个函数的梯度方向是函数上升最快的方向，相反的，负梯度方向是函数下降最快的方向。
- 这里的梯度提升其实是一种梯度下降的思想，和大多数boosting方法一样，总体上的思想它是将多个弱分类器结合起来得到强分类器的结果。不同于adaboost每次加大分错样本的权重，GB则是每次拟合上一预测的残差，例如在第m轮迭代中有：
image.png
为了找到h(x)，我们用每一轮预测的残差去近似它，即：
image.png
由于当我们的损失函数为平方损失函数时：
损失函数的负梯度正好为h(x):
- 因此GB是一种具有梯度下降思想的算法，我们马上联想到：如果损失函数的形式不是平方损失时，还能否使用残差来模拟损失函数下降最快的方向？答案是不能的，损失函数的形式多种多样，残差不一定总是损失函数下降最快的方向，因此我们迫切的需要统一一下，每轮迭代时我们需要用什么去拟合h(x)，也就是说我们需要找到损失函数下降最快的方向，去迭代减少它。
- 因此，Freidman提出了梯度提升算法：
利用最速下降的近似方法，即利用损失函数的负梯度在当前模型的值，作为回归问题中提升树算法的残差的近似值，拟合一个回归树。
算法步骤：
GBDT中的DT
这里的DT我们不要简单理解为广义的决策树，考虑到我们GB算法中需要将多个弱分类器的结果累加起来，然而如果是分类问题，结果是无法相加的，比如“男”+“女”等于什么？所以说GBDT中所有的树都是回归树，而不是分类树，也就是说DT独指Regression Decision Tree。
接着，我们对问题进行进一步细分，来分析具体的一棵回归树的运行流程。
作为对比，简要回顾下分类树的运行过程：以ID3为例，穷举每一个属性特征的信息增益值，每一次都选取使信息增益最大的特征进行分枝，直到分类完成或达到预设的终止条件，实现决策树的递归构建。
回归树的运行流程与分类树基本类似，但有以下两点不同之处：
第一，回归树的每个节点得到的是一个预测值而非分类树式的样本计数，假设在某一棵树的某一节点使用了年龄进行分枝（并假设在该节点上人数>1)那么这个预测值就是属于这个节点的所有人年龄的平均值。
第二，在分枝节点的选取上，回归树并没有选用最大熵值来作为划分标准，而是使用了最小化均方差，即
这很好理解，被预测出错的次数越多，错的越离谱，均方差就越大，通过最小化均方差也就能够找到最靠谱的分枝依据。image.png
GBDT中的Shrinkage
这个Shrinkage听上去好像比较复杂，其实很简单，就是类似于梯度下降中步长缩减的意思，但一般来说GBDT的迭代公式中会有两个缩减系数，一个超参—学习率，一个不是超参，是我们需要最优化的参数
这里面的gama就是我们需要去求出来的参数。
所以说要注意：Shrinkage所指的是超参数v,即学习率，不要将它和gama混为一谈。
一般来说，越小的学习率会导致迭代轮数的增多，一般取v = 0.01.
GBDT做分类
首先明确一点，gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为我们所选择的任务是分类任务就选用分类树，这里面的核心是因为gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。
如果选用的弱分类器是分类树，类别相减是没有意义的。上一轮输出的是样本 x 属于 A类，本一轮训练输出的是样本 x 属于 B类。 A 和 B 很多时候甚至都没有比较的意义，A 类- B类是没有意义的。
我们具体到分类这个任务上面来，我们假设样本 X 总共有 K类。来了一个样本 x，我们需要使用gbdt来判断 x 属于样本的哪一类。
- 第一步 我们在训练的时候，是针对样本 X 每个可能的类都训练一个分类回归树。举例说明，目前样本有三类，也就是 K = 3。样本 x 属于 第二类。那么针对该样本 x 的分类结果，其实我们可以用一个 三维向量 [0,1,0] 来表示。0表示样本不属于该类，1表示样本属于该类。由于样本已经属于第二类了，所以第二类对应的向量维度为1，其他位置为0。
- 针对样本有 三类的情况，我们实质上是在每轮的训练的时候是同时训练三颗树。第一颗树针对样本x的第一类，输入为（x,0）。第二颗树输入针对 样本x 的第二类，输入为（x,1）。第三颗树针对样本x 的第三类，输入为（x，0）
-
在这里每颗树的训练过程其实就是就是我们之前已经提到过的CATR TREE 的生成过程。在此处我们参照之前的生成树的程序 即可以就解出三颗树，以及三颗树对x 类别的预测值f1(x),f2(x),f3(x)。那么在此类训练中，我们仿照多分类的逻辑回归 ，使用softmax 来产生概率，则属于类别 1 的概率
image.png
并且我们我们可以针对类别1求出残差
类别2 求出残差
类别3 求出残差
然后开始第二轮训练 针对第一类输入分别为
-
所以当K =3。我们其实应该有三个式子
image.png
当训练完毕以后，新来一个样本 x1 ，我们需要预测该样本的类别的时候，便可以有这三个式子产生三个值，f1(x),f2(x),f3(x)。样本属于 某个类别c的概率为
image.png
总结
GBDT（Gradient Boosting Decison Tree）中的树都是回归树，GBDT用来做回归预测，调整后也可以用于分类（设定阈值，大于阈值为正例，反之为负例），可以发现多种有区分性的特征以及特征组合。GBDT是把所有树的结论累加起来做最终结论的，GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差(负梯度)，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。 Boosting的最大好处在于，每一步的残差计算其实变相地增大了分错instance的权重，而已经分对的instance则都趋向于0。这样后面的树就能越来越专注那些前面被分错的instance。
- 之后可能会补上GBDT的例子，如何选择特征等等。
参考链接http://www.cnblogs.com/ModifyRong/p/7744987.html
