提升树
提升树模型
以决策树为基函数的提升方法称为提升树(boosting tree)。
对分类问题是二叉分类树，对回归问题是二叉回归树。
提升树可以表示为决策树的加法模型：
<nobr> fM(x)=∑m=1MT(x;Θm) </nobr>
其中， <nobr> T(x;Θm) </nobr>表示决策树； <nobr> Θm </nobr>为决策树的参数；M为树的个数。
提升树算法
提升树算法采用前向分步算法。首先确定初始提升树 <nobr> f0(x)=0 </nobr>，第m步的模型是
<nobr> fm(x)=fm−1(x)+T(x;Θm) </nobr>
其中， <nobr> fm−1(x) </nobr>为当前模型，通过经验风险极小化确定下一棵决策树的参数 <nobr> Θm </nobr>，
<nobr> Θ^m=argminΘm=∑i=1NL(yi,fm−1(xi)+T(xi;Θm)) </nobr>
针对不同问题的提升树学习算法，主要区别在于使用的损失函数不同。回归问题使用平方误差损失函数，分类问题使用指数损失函数。一般决策问题使用一般损失函数。
回归问题提升树使用以下前向分步算法：
在前向分步算法的m步，给定当前模型 <nobr> fm−1(x) </nobr> ，需求解
<nobr> Θ^m=argminΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm)) </nobr>
得到 <nobr> Θ^m </nobr> ，即第m棵树的参数。
当采用平方误差损失函数时，
<nobr> L(y,f(x))=(y−f(x))2 </nobr>
其损失变为
这里，
<nobr> r=y−fm−1(x) </nobr>
是当前模型拟合数据的残差。
所以，对回归问题的提升树算法来说，只需简单地拟合当前模型（前面所有树学到的模型）的残差。
梯度提升
提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。
Freidman提出了梯度提升算法。这是利用最速下降法的近似算法，其关键是利用损失函数的负梯度在当前模型的值
<nobr> −[∂L(yi,f(xi))∂f(xi)]f(x)=fm−1(x) </nobr>
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
GBDT
数学公式
Gradient Tree Boosting or Gradient Boosted Regression Trees(GBRT)是一种适用于具有任意阶可导损失函数的提升方法。
优点：
处理不同类型数据
预测力强
对异常点具有鲁棒性（通过鲁棒的损失函数）
缺点：
可伸缩性Scalability。每棵树按顺序生成，很难并行。
GBRT加性模型
<nobr> F(x)=∑m=1Mγmhm(x) </nobr>
前向分步算法：
<nobr> Fm(x)=Fm−1(x)+γmhm(x) </nobr>
计算梯度
<nobr> Fm(x)=Fm−1(x)+γm∑i=1n∇FL(yi,Fm−1(xi)) </nobr>
步长 <nobr> γm </nobr>通过线性搜索确定
<nobr> γm=argminγL(yi,Fm−1(xi)−γ∂L(yi,Fm−1(xi))∂Fm−1(xi)) </nobr>
分类和回归问题的区别在于使用的损失函数。
损失函数
回归问题：
ls,最小二乘回归的损失函数，初始模型 <nobr> F0(x) </nobr>为目标值的均值
分类问题：
deviance,逻辑回归的损失函数，适用于二分类和多分类。当用于多分类时，每一步构建 <nobr> n_classes </nobr>个回归树。当类别较多时，效率降低。
exponential，指数损失函数，相当于二分类的Adaboost算法，仅用于二分类。
<nobr> L(yi,Fm−1(xi))=e−yi∗Fm−1(xi) </nobr>
损失函数的反向梯度为
<nobr> −∂(yi,Fm−1(xi))∂Fm−1(xi)=yi∗e−yi∗Fm−1(xi) </nobr>
步长缩减
经验表明使用较小的学习率可以获得更好的测试表现。
一般设置其为较小的常数（ <nobr> lr≤0.1 </nobr>），通过早停来选择基学习器的数量。更多内容可参考
Ridgeway, “Generalized Boosted Models: A guide to the gbm package”, 2007
。
参考资料
《统计学习方法》第8章
scikit-learn gradient-boosting
gbdt算法原理与系统设计简介 weapon
京公网安备 11010502036488号