1. 前言

如果读了我之前的几篇集成学习的博文，相信读者们已经都对集成学习大部分知识很有了详细的学习。今天我们再来一个提升，就是我们的集大成者GBDT。GBDT在我们的Kaggle的比赛中基本获得了霸主地位，大部分的问题GBDT都能获得异常好的成绩。

2. GBDT原理

GBDT的中文名叫梯度提升树，GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是\(f_{t-1}(x)\), 损失函数是\(L(y,f_{t-1}(x))\)，我们本轮迭代的目标是找到一个CART回归树模型的弱学习器\(h_t(x)\)，让本轮的损失函数\(L(y,f_t(x)=L(y,f_{t-1}(x)+h_t(x))\)最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。即梯度提升树是用CART树去拟合前一个弱模型的损失函数的残差，使得本轮的损失更小。

3. 提升树

回归问题提升树的前向分步算法：

假设第\(m\)个模型是\(f_m(x)\)，则有以下公式
\[
f_0(x)=0
\]
\[
f_m(x)=f_{m-1}(x)+T(x,\theta_m)
\]
\[
f_M(x)=\sum_{m=1}^MT(x,\theta_m)
\]
有了模型函数后，我们就得到了损失函数：
\[
L(y,f_m(x))=L(y,f_{m-1}(x)+T(x,\theta_m))=L(r_{m-1},T(x,\theta_m))
\]
其中的\(T(x,\theta)\)需要用CART树去拟合，而\(r_{m-1}\)是上一个学习器的损失的残差。
\[
r_{m-1}=L(y,f_{m-1}(x))
\]
我们举个例子，假设损失函数是平方损失函数：
\[
L(y,f(x))=(y-f(x))^2
\]
则第\(m\)个模型的损失函数
\[
L(y,f_m(x))=L(y,f_{m-1}(x)+T(x,\theta_m))=L(r_{m-1},T(x,\theta_m))=(r_{m-1}-T(x,\theta_m))^2
\]

4. 梯度提升树

前面的提升树利用加法模型和前向算法进行，当损失函数是平方损失或者指数损失的时候，很好推算，但是对于一般的损失函数，就比较难处理。这时候我们可以利用最速下降法来近似，关键是利用了损失函数的负梯度在当前模型的值：

\[
r_{ti} \approx -\bigg[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;(x)}
\]

输入：是训练集样本\(T={(x_1,y_1),(x_2,y_2),...(x_N,y_N)}\)，最大迭代次数\(M\), 损失函数\(L\)。

输出：强学习器\(f_M(x)\)

初始化弱学习器

\[
f_0(x) = arg min_{c}\sum\limits_{i=1}^{N}L(y_i, c)
\]

对迭代轮数\(m=1,2,...M\)有：
1. 对样本\(i=1,2,...,N\)，计算负梯度\(r_{mi} \approx -\bigg[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;(x)}\)
2. 利用\((x_i,r_{mi})(i=1,2,..N)\), 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为\(Rmj,(j=1,2,...,J)\)。其中\(J\)为回归树t的叶子节点的个数。
3. 对叶子区域\(j=1,2,...,J\)计算最佳拟合值\(c_{mj} = arg min_{c}\sum\limits_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i) +c)\)
4. 更新强学习器\(f_{m}(x) = f_{m-1}(x) + \sum\limits_{j=1}^{J}c_{mj}I(x \in R_{mj})\)
得到强学习器f(x)的表达式\(f(x) = f_M(x) =f_0(x) + \sum\limits_{m=1}^{M}\sum\limits_{j=1}^{J}c_{mj}I(x \in R_{tj})\)

5. GBDT的正则化

和Adaboost类似的正则化项，即步长(learning rate)。
正则化的方式是通过子采样比例（subsample）。
对于弱学习器即CART回归树进行正则化剪枝。

6. 总结

GBDT也是需要正则化的过程，
最后总结下GBDT的优缺点。

GBDT主要的优点有：

可以灵活处理各种类型的数据，包括连续值和离散值。
在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

GBDT的主要缺点有：

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

巴特西

5. 集成学习（Ensemble Learning）GBDT

1. 集成学习（Ensemble Learning）原理

2. 集成学习（Ensemble Learning）Bagging

3. 集成学习（Ensemble Learning）随机森林（Random Forest）

4. 集成学习（Ensemble Learning）Adaboost

5. 集成学习（Ensemble Learning）GBDT

6. 集成学习（Ensemble Learning）算法比较

7. 集成学习（Ensemble Learning）Stacking