此文是本人学习林轩田老师教授的机器学习技法第十一课—— Gradient Boosted Decision Tree ——的笔记。这节课会讲两个模型：Adaptive Boosted Decision Tree 和 Gradient Boosted Decision Tree (GBDT)。本质上讲，两者同属 boosting 方法结合 Decision Tree，只是他们的 error function 不同，训练方法稍有差别。（这节课有许多证明，因为太笨没懂就没详述 :-) ）
参考
Adaptive Boosted Decision Tree
Adaptive Boosted，即 AdaBoost，与 Decision Tree 已经在前面课程做过介绍，Adaptive Boosted Decision Tree 以 AdaBoost 为框架，以 Decision Tree 为弱模型，整合成一个模型。而在 机器学习技法第八课——Adaptive Boosting 中，弱模型简单地选取 Decision Stump，这也算 Adaptive Boosted Decision Tree 的一个特例，老师称之为 AdaBoost-Stump。
模型训练
在训练过程中，应该注意两点。
一、决策树应该剪枝。一方面为了正则化，另一方面，完全决策树的误差为零，这使得以修正误差为中心的 AdaBoost 难以进行。
二、从整个训练集中抽样出每次迭代的训练数据，每笔数据的选中概率正比于 AdaBoost 所计算的权重，替代了原来（第八课）将权重直接用于 error function 的方式。一方面与剪枝目的相同，避免将所有数据输入完全树导致误差为零。另一方面，权重不仅能通过抽取概率体现数据的重要程度，同时又能避免对弱模型 error function 的修改。
训练过程可参考第八课，改动的只有：在训练弱模型时，根据权重随机抽取训练数据，并训练出剪枝的决策树。
AdaBoost 与梯度下降
课上，老师详细证明了 AdaBoost 的训练过程是在最小（优）化函数，所谓的 loss function ：
$$ loss = \frac{1}{N} \sum_{n=1}^N \exp (-y_n s_n^{(T)}) $$
其中 $N$ 表示数据量， $T$ 表示迭代次数， $s_n^{(T)}$ 表示 $T$ 次迭代后模型估计值：
$$ sn^{(T)} = \sum{t=1}^T\alpha_t g_t(\mathbf{x}_n) $$
类似梯度下降，AdaBoost 的每次迭代都向最优点靠近，最终到达最优点。AdaBoost 的正向推导可参考：AdaBoost - wikipedia。
Gradient Boosted Decision Tree
简称 GBDT，它的思想与 AdaBoost 是相同的，只是 loss function 被替换成其他函数。流行用残差平方函数替换 AdaBoost 中的 $\exp$ 函数，以下只介绍这种 GBDT。
$$ loss=\frac{1}{N} \sum_{n=1}^N (s_n^{(T)} - y_n)^2 $$
模型训练
GBDT 的训练流程与 AdaBoost 稍有不同。
每次迭代根据上次估计值与实际值的残差（residual）训练决策树，不断减小残差使估计值逼近实际值。参考博文 Gbdt 迭代决策树入门教程，它详细介绍了 GBDT 所隐含的直觉。
每次迭代的权重计算公式：
$$ \alphat = \frac{\sum{n=1}^N g_t(\mathbf{x}_n)(y_n-sn^{(t-1)})}{\sum{n=1}^N g_t^2(\mathbf{x}_n)} $$
其中 $s_n^{(t-1)}$ 表示 $t-1$ 次迭代（前次迭代）后模型估计值。
- $s_1=s_2=…=s_n$
- for t=1,2,…,T
- 根据数据集 ${(\mathbf{x}_n, y_n-s_n)}$，训练出决策树 $g_t$
- 根据数据集 ${(g_t(\mathbf{x}_n),y_n-s_n)}$ 计算权重 $\alpha_t$
- 更新 $s_n \leftarrow s_n + \alpha_t g_t(\mathbf{x}_n)$
- 返回模型 $G(\mathbf{x})=\sum\alpha_t g_t(\mathbf{x}_n)$
注，在一些实现中，权重 $\alpha_t$ 直接设定为 1，没有经过计算。