GBDT

GBDT 的全称是 Gradient Boosting Decision Tree，先要理解GBDT中的Gradient Boosting 和Decision Tree分别是什么？

GBDT中的Decision Tree是CART回归树（不是分类树），无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

GBDT的损失函数是误差平方和：
$L(y_i,f(x_i))=\frac{1}{2}\sum_{i=1}^n(\hat y_i-y_i)^2=\frac{1}{2}\sum_{i =1}^n(f(x_i)-y_i)^2$
我们对 $f(x_i)$ 求偏导:
$\frac{∂L(y_i,f(x_i)}{∂f(x_i)}=\sum_{i=1}^nf(x_i)-y_i$
其中 $f(x_i)-y_i$ 表示的是残差，也就是梯度值，所以说GBDT拟合的是残差。

GBDT算法步骤：
1、确定超参数：学习率、迭代次数、树的深度；
2、对每一个特征，根据其值，确定划分点；
3、划分点划分后的两个子数据集（因为是二叉的）；
4、按照该划分点进行预测的结果，与真实标签之间的残差，进而计算残差平方和；
5、将两个子集的残差平方和相加，得到该划分点的残差平方和；
6、重复步骤2-5，确定每一个特征下所有划分点的残差平方和，并从中选择最小的残差平方和对应的特征的划分点，作为本次的划分点；
7、如果未达到设定的树的深度，对步骤6划分后的子集应用步骤2-6进行划分；
8、树的深度达到设定值后，完成一棵树桩；
9、根据该树桩预测的结果与真实标签之间的残差，作为下一次迭代的标签；
10、重复2-9进行迭代，直到达到设定迭代次数；
11、最终学习器为学习率与各个基学习器线性之和。初始基学习器可以不应用学习率。

我们通过例子来说明什么叫拟合残差？

GBDT例1

训练集

$x \in [1,10]$ , $y \in [5,10]$ ，学习这个回归问题，考虑只用树桩作为基函数。
1、第1步求第一棵树桩 $T_1(x)$ ，
要先找到训练数据集的切分点：根据数据集中的 $x$ ，考虑如下切分点: $\{1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5 \}$
对于第1个切分点有子集 $R_1 = \{5.56 \}$ ， $R_2 = \{5.7,5.91, 6.4,6.8,7.05,8.9,8.7,9,9.05\}$
分别求 $S_1$ 的平均数 $μ_1=5.56$ ， $S_2$ 的平均数 $μ_2=7.5$
那么该切分点产生的残差为两个集合残差之和： $R=\sum_{y1 \in S_1}(y_1-μ_1)^2+\sum_{y2 \in S_2}(y_2-μ_2)^2$ =0+15.72=15.72
同理，我们可以求出各个切分点对应的残差：

显然，当切分点为

x=6.5

时，其产生的残差最小，此时有集合：

R_1 = \{5.56,5.7,5.91,6.4, 6.8,7.05 \}

，

μ_1=6.24

R_2 = \{8.9, 8.7, 9, 9.05 \}

，

μ_2=8.91

有残差表：

以第一个残差为例：5.56-6.24=-0.68
那么有树 $f(x)=T_1(x)=\left\{ \begin{aligned} 6.24 , x \lt 6.5 \\ 8.91, x \geq6.5 \end{aligned} \right.$
该树桩 $T_1(x)$ 你和训练数据的平方误差损失为： $L=\sum_{i=1}^{10} r_i^2=1.93$

2、求第2个树桩 $T_2(x)$ ，然后这个残差表就层楼我们“新的数据集”，同样考虑划分点: $\{1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5 \}$ ，并求出各个划分点对应的残差，选择残差最小的作为最终划分点，此时有划分点 $x=3.5$ ，那么其将残差数据集分成两部分
$S_1 = \{-0.68, -0.54, -0.33 \}$ ， $μ_1=-0.52$
$S_2 = \{0.16, 0.56, 0.81,-0.01, -0.21, 0.09, 0.14\}$ ， $μ_2=0.22$
那么有树桩 $T_2(x)=\left\{ \begin{aligned} -0.52 , x \lt 3.5 \\ 0.22, x \geq 3.5 \end{aligned} \right.$

由切分点$x=3.5又可以更新残差表：

至此，有树 $f(x)=T_1(x)+T_2(x)=\left\{ \begin{aligned} 5.72 , x \lt 3.5 \ \ \ \ \ \ \ \ \ \ \\ 6.46 , 3.5 \leq x \lt 6.5 \\ 9.13, x \geq6.5 \ \ \ \ \ \ \ \ \ \ \end{aligned} \right.$
此时，用树 $f(x)$ 拟合训练数据得到平方损失误差为0.79.

3、由更新后的残差表，求第3棵树桩，每获得一个树桩，残差表更新一次，依次可求得多个树桩，直到树桩达到指定数目或残差小于某个设定值，停止迭代。将所有树桩串联起来即可得到训练后的结果 $f(x)=T_1(x)+T_2(x)+...+T_n(x)$

GBDT例2

我们要根据年龄和体重预测身高，那么身高就是我们的标签列。第4条为我们要预测的。

1、参数设置：
学习率：learning_rate=0.1
迭代次数：n_trees=5
树的深度：max_depth=3，上面的例子中我们没有考虑树的深度，因为我们就一个特征。
2、第1棵树桩: $T_0(x)=\frac{1.1+1.3+1.7+1.8}{4}=1.475$
这个意思就是说我们把第1个基分类器设置为要拟合的均值，即给出任何年龄和体重该基分类器预测的都是1.475。我们难道不能对图1的数据集直接构建CART树吗？——显然是可以的，使用平均值更简单。

此时我们可以得到残差：

此时， $f(x)=T1=1.45$ ，其在训练集上的残差平方和为0.3275。

用T1的残差残差作为标签，产生了新的数据集：

2、迭代轮数m=1，2,…,M:
对图3的数据集构建CART回归树:
对年龄属性选择划分点[7,21,30]
age<7， $S_1 = \{-0.375 \}$

age>=7，

S_2 = \{ -0.175, 0.225, 0.325 \}

该划分点的残差为：

r=0+0.09+0.01+0.04=0.14

同理，我们可以得到各个特征下各个划分点对应的残差平方和，如下表：

选择残差平方和最小的即0.025，对应两个划分点，age=21和weight=60，我们随机选一个作为划分点，这里选择age=21。有树如下：

第1棵树

我们设定的树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分：

此时我们得到
$T_1(x)=η*\sum_{j=1}^4y_iI(x)$
$=0.1*(-0.375+(-0.0175)+0.0225+0.0325)$
那么 $f(x)=T_0(x)+T_1(x)$

为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。
所以，可以更新残差，作为下一类迭代的标记。
重复此步骤，直到 m>5 结束，最后生成5棵树。（加上 $f_0(x)$ 一共是6个基学习器）

第2棵树

第3棵树

第4棵树

第5棵树

得到最后的强学习器：
$f(x)=T_0(x)+T1(x)+...+T_6(x)$

当我们输入年龄=25，体重=65给 $T_0$ ，得到值1.475；
当我们输入年龄=25，体重=65给 $T_1$ ，得到值0.225；
当我们输入年龄=25，体重=65给 $T_2$ ，得到值0.2025；
...
最终预测结果： $f(x)=1.475+0.1∗(0.225+0.2025+0.1823+0.164+0.1476)=1.56714$

推荐阅读更多精彩内容