GBDT:梯度提升决策树
？GBDT的树是回归树(不是分类树)。GBDT用于回归预测，也可用于调整后的分类。
？GBDT的思想赋予了它天然的优势，它可以找到多种区别特征和特征组合。在业界，脸书使用它来自动发现有效特征和特征组合作为LR模型中的特征，以提高CTR点击率预测的准确性(详见参考文献5和6)。GBDT在淘宝的搜索和预测业务中也发挥着重要作用(详见参考文献7)。
回归树的整体过程和分类树类似，不同的是回归树的每个节点都会得到一个预测值。以年龄为例，预测值等于属于这个节点的所有人的平均年龄。分支时，穷尽列出每个特征的每个阈值，寻找最佳分割点，但最佳度量不再是最大熵，而是最小平方误差。也就是说，预测犯错的人越多，错误越离谱，平方误差越大。通过最小化平方误差，可以找到最可靠的分支基。分支直到每个叶子节点上的人的年龄唯一或者达到预设的终止条件(比如叶子数的上限)。如果最终叶节点上的人的年龄不是唯一的，则该节点上所有人的平均年龄被作为该叶节点的预测年龄。(引自一篇博客，详见参考文献3)
？回归树算法如下图所示(截图由统计学习法5.5.1 CART生成):
提升树就是迭代多个回归树做出相同的决策。当使用平方误差损失函数时，每个回归树学习所有先前树的结论和残差，并且通过拟合获得当前残差回归树。残差的含义如下:残差=真实值-预测值。提升树是整个迭代过程生成的回归树的累积。
？例如，提到一个博客(参考。4)，本博客引用的例子更直观的展示了多个决策树的线性求和过程以及残差的显著性。
？训练提升树模型预测年龄；
？训练集中有四个人，A，B，C，D的年龄分别是14，16，24，26。样本具有购物金额、在线时间、经常去百度提问等特征。提升采油树的过程如下:
这个例子可以直观的看出，预测值等于所有树值的累加，比如A的预测值=树1左节点值15+树2左节点-1 = 14。
？因此，给定当前模型fm-1(x)，只需简单拟合当前模型的残差即可。现在回归问题的提升树算法描述如下:
提升树采用加法模型和正向逐步算法实现学习的优化过程。当损失函数为平方损失函数和指数损失函数时，每一步的优化都很简单，比如用平方损失函数学习残差回归树。
？但是对于一般的损失函数，往往不是那么容易优化每一步，比如上图中的绝对损失函数和Huber损失函数。针对这一问题，Freidman提出了梯度提升算法:利用最速下降的近似方法，即利用当前模型中损失函数负梯度的值作为回归问题中提升树算法残差的近似值，拟合出一棵回归树。(注:我个人认为残差是负梯度的特例而不是残差的近似值)算法如下(截图来自《统计学习的要素》):
算法步骤解释:
GBDT树推荐深度:6；(横向比较:决策树/RandomForest需要将树的深度调整到15或更高)
？以下摘自知乎的一个问答(详见参考文献8)。问答很好的解释了这个参数设置的数学原理。
？为什么xgboost/gbdt在调整参数时可以达到很高的精度？
？使用xgboost/gbdt将树的最大深度调整为6具有较高的准确性。但在使用DecisionTree/RandomForest时，需要将树的深度调整为15或更高。我可以理解为使用RandomForest需要的树的深度和决策树是一样的，因为它是通过装袋的方式组合决策树，相当于多次制作决策树。但是xgboost/gbdt只用梯度上升法就能达到6个节点深度的高预测精度，让我惊讶的怀疑是黑科技。xgboost/gbdt是怎么做到的？它的节点和一般的决策树有区别吗？
？回答
？这是一个非常好的问题，题主对每一个算法都研究的非常仔细和透彻，问的问题也和这两个算法的本质有关。这个问题其实不是一个很简单的问题。我试着用我浅薄的机器学习知识来回答这个问题。
？一句话的解释来自周志华的机器学习教材(Machine Learning-周志华):Boosting主要着眼于减少偏差，所以Boosting可以基于泛化性能差的学习者建立强集成；Bagging侧重于减少方差，因此在决策树和神经网络等学习器中更有效，无需修剪。
？随机森林和GBDT都属于集成学习的范畴。整合学习中有两个重要的策略:装袋和助推。
？Bagging算法是这样做的:每个分类器随机采样原始样本，然后分别在这些采样样本上训练分类器，再将这些分类器组合起来。简单多数票一般就够了。其代表算法是随机森林。Boosting就是他迭代训练一系列分类器，每个分类器采用的样本分布与上一轮的学习结果有关。其代表算法有AdaBoost和GBDT。
？其实就机器学习算法而言，它的泛化误差可以分解为两部分，偏差和方差。这可以从下图的公式推导出来(这里用的是概率公式D(X)= E(X ^ 2)-[E(X)]2)。偏差是指算法的预期预测与真实预测之间的偏差程度，反映了模型本身的拟合能力；方差度量相同规模的训练集变化引起的学习绩效的变化，描述数据扰动引起的影响。这是一个有点迂回，但你必须知道拟合。
？如下图所示，模型越复杂，拟合度越高，模型的训练偏差越小。但是这个时候如果你改变一组数据，模型可能会有很大的变化，就是模型的方差很大。所以当模型过于复杂时，就会导致过拟合。
？当模型更简单时，即使我们改变另一组数据，最终的学习者和之前的学习者之间的差异也没有那么大，模型的方差也很小。或者因为模型简单，偏差会很大。
？换句话说，我们在训练一个模型的时候，偏差和方差都要兼顾，一个都不能少。
？对于Bagging算法，因为我们会并行训练很多不同的分类器，目的就是降低这个方差，因为采用更多的独立基分类器后，h的值会自然趋近。所以对于每个基分类器，目标都是如何减少这种偏向，所以我们会采用深度很深甚至不剪枝的决策树。
？对于Boosting，我们会在每一步最后一轮的基础上更加拟合原始数据，这样可以保证偏倚。所以对于每个基分类器，问题是如何选择一个方差更小的分类器，也就是更简单的分类器，所以我们选择一个深度较浅的决策树。
最近，一种引起关注的梯度提升算法xgboost与GBDT相比，在计算速度和精度上有了明显的提高。xgboost的全称是极限梯度提升，是梯度提升机器的c++实现。作者是陈琦程·天齐，他正在华盛顿大学学习机器学习。xgboost最大的特点是可以自动使用CPU多线程进行并行，同时改进算法提高精度。其首次亮相的是Kaggle的希格斯子信号识别比赛，由于其出色的效率和较高的预测准确率，在比赛论坛上引起了参赛选手的广泛关注。GBDT值得我们进一步探索和研究。
参考
1、《统计学习原理》
2.统计学习方法
3 、/ 2010/12/an-introduction-to-tree link . html
8、问题/45487317