决策树（三）- GBDT
上一篇我们所说的随机森林其实是一种Bagging技术，而GBDT是一种Boosting技术。 Bagging技术对于不同的分类器可以通过并行训练而获得，且每个分类器的权重相等。但Boosting则是在前面已训练获得的分类器基础上加以调整（更关心之前分类器分错的样本）而获得新的分类器，因此Boosting中的分类器权重并不相等，其权重值代表该分类器在上一轮迭代中的成功度。
此外，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成；Bagging主要关注降低方差，因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。
GBDT使用的树为分类回归树CART。我们假设CART分类回归树的输出结果为： \(f(x)=c_m \quad \text{若}x\in R_m\) 则我们可以将提升树GBDT表示为多个CART的和： \(f_N(x)=\sum_{n=1}^N T(x;\theta_n)\) $T(x;\theta_n)$表示第n棵CART $\theta_n$为第n棵决策树的参数, N为CART的棵树, $f_N$表示最终由N个CART树组成的GBDT模型。
对于分类问题，GBDT实质上仍把它转化为回归问题：
对于有k个类别的分类问题，GBDT每轮迭代对应构建了k棵树，对样本x的预测值可以表示为： \(f_{t_1}(x),f_{t_2}(x),...,f_{t_k}(x)\) 然后使用softmax便可以得到每一个类别的概率。这样处理的好处是，无论对于回归或者分类问题，GBDT都可以对$f(x)$计算出一个梯度，进而计算当前轮的残差，供下一轮迭代学习。
GBDT采用前向分布算法：
- 确定一棵初始CART树 f_0(x)
- 根据前一步的模型$f_{n-1}(x)$：
$f_n(x)=f_{n-1}(x)+T(x;\theta_n)$
第n棵决策树的参数$\theta_n$可通过经验风险最小化得到： \(\hat{\theta_n}=\arg\min\sum_{i=1}^{S}L(y_i, \quad f_{n-1}(x_i)+T(x_i;\theta_n))\) S为样本的数量。当L为平方误差时： \(L(y_i, \quad f_{n-1}(x_i)+T(x_i;\theta_n)) = \langle y_i - f_{n-1}(x_i)-T(x_i;\theta_n)\rangle ^2 = \langle r_i - T(x_i;\theta_n)\rangle^2\) 很明显，$r_i=y_i-f_{n-1}(x)$是模型n-1步时对样本i的残差。即每一轮产生的残差作为下一轮回归树的输入，下一轮回归树的目的就是尽可能的拟合这个输入残差：$\hat{c_m}=average(r_i|x_i \in R_m)$
上述算法最大问题是，模型的迭代依赖残差，cost function一般固定为反映残差的均方差，因此很难处理纯回归问题之外的问题。 我们可以利用梯度来代替残差，使用梯度提升算法来迭代模型，这样只要可求导的cost function都可以使用。
利用损失函数的负梯度在n-1模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树：
\(r_{ni} = -[\frac{\partial{L(y_i, f_{n-1}(x_i))}}{\partial f_{n-1}(x_i)}]\)
具体算法如下（与上方描述相反，下面算法的m/M为树的下标/个数，n/N为样本的下标/数量）：
GBDT对于分类的算法过程blog：http://www.cnblogs.com/leftnoteasy/archive/2011/03/07/random-forest-and-gbdt.html 已说的非常清楚了。
参考资料
【1】GBDT：梯度提升决策树
