提升树

提升树模型

以决策树为基函数的提升方法称为提升树(boosting tree)。
对分类问题是二叉分类树，对回归问题是二叉回归树。
提升树可以表示为决策树的加法模型：
fM(x)=∑m=1MT(x;Θm)
其中，T(x;Θm)表示决策树；Θm为决策树的参数；M为树的个数。

提升树算法

提升树算法采用前向分步算法。首先确定初始提升树f0(x)=0，第m步的模型是
fm(x)=fm−1(x)+T(x;Θm)
其中，fm−1(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数Θm，
Θ^m=argminΘm=∑i=1NL(yi,fm−1(xi)+T(xi;Θm))
针对不同问题的提升树学习算法，主要区别在于使用的损失函数不同。回归问题使用平方误差损失函数，分类问题使用指数损失函数。一般决策问题使用一般损失函数。
回归问题提升树使用以下前向分步算法：

在前向分步算法的m步，给定当前模型fm−1(x)，需求解
Θ^m=argminΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm))
得到Θ^m，即第m棵树的参数。
当采用平方误差损失函数时，
L(y,f(x))=(y−f(x))2
其损失变为

这里，
r=y−fm−1(x)
是当前模型拟合数据的残差。
所以，对回归问题的提升树算法来说，只需简单地拟合当前模型（前面所有树学到的模型）的残差。

梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不那么容易。
Freidman提出了梯度提升算法。这是利用最速下降法的近似算法，其关键是利用损失函数的负梯度在当前模型的值
−[∂L(yi,f(xi))∂f(xi)]f(x)=fm−1(x)
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

GBDT

数学公式

Gradient Tree Boosting or Gradient Boosted Regression Trees(GBRT)是一种适用于具有任意阶可导损失函数的提升方法。
优点：
处理不同类型数据
预测力强
对异常点具有鲁棒性（通过鲁棒的损失函数）
缺点：
可伸缩性Scalability。每棵树按顺序生成，很难并行。
GBRT加性模型
F(x)=∑m=1Mγmhm(x)
前向分步算法：
Fm(x)=Fm−1(x)+γmhm(x)
计算梯度
Fm(x)=Fm−1(x)+γm∑i=1n∇FL(yi,Fm−1(xi))
步长γm通过线性搜索确定
γm=argminγL(yi,Fm−1(xi)−γ∂L(yi,Fm−1(xi))∂Fm−1(xi))
分类和回归问题的区别在于使用的损失函数。

损失函数

回归问题：

ls,最小二乘回归的损失函数，初始模型F0(x)为目标值的均值

分类问题：

deviance,逻辑回归的损失函数，适用于二分类和多分类。当用于多分类时，每一步构建n_classes个回归树。当类别较多时，效率降低。

exponential，指数损失函数，相当于二分类的Adaboost算法，仅用于二分类。

L(yi,Fm−1(xi))=e−yi∗Fm−1(xi)
损失函数的反向梯度为
−∂(yi,Fm−1(xi))∂Fm−1(xi)=yi∗e−yi∗Fm−1(xi)

步长缩减

经验表明使用较小的学习率可以获得更好的测试表现。
一般设置其为较小的常数（lr≤0.1），通过早停来选择基学习器的数量。更多内容可参考

Ridgeway, “Generalized Boosted Models: A guide to the gbm package”, 2007
。

参考资料

《统计学习方法》第8章
scikit-learn gradient-boosting
gbdt算法原理与系统设计简介 weapon