什么是梯度提升(Gradient Boosting)
可以认为 Gradient Boosting = Gradient Descent + Boosting
在AdaBoost中，我们通过每一步添加一个弱分类器来最终得到一个由若干弱分类器线性组合成的强分类器。每一步训练弱分类器时都更关注之前误分类的样本。将误分类样本看成总模型的缺陷，则算法每一步都是通过添加一个弱分类器来试图减小总模型的缺陷。
和 AdaBoost 一样，Gradient Boosting 也是一个步进算法，每一步添加一个弱分类器。不同的是，在 Gradient Boosting中，用来刻画缺陷的是梯度，通过梯度下降，来逐渐提高总模型的预测能力。
一个小例子
给定了一组数据点 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$，要求给出一个模型 $F(x)$ 使得平方误差最小。
假设你已经得到了一个模型：有 $F(x_1)=0.8$，$y_1=0.9$，$F(x_2)=1.4$，$y_2=1.3$ …… 现在想改进这个模型，要怎么做？
最简单的办法就是添加一个模型 $h$，即新的预测值由 $F(x)+h(x)$ 给出。
我们希望改进后满足$$\begin{array}{c}
F(x_1)+h(x_1)=y_1 \\
F(x_2)+h(x_2)=y_2 \\
\cdots \\
F(x_n)+h(x_n)=y_n
\end{array}$$
等价地，我们希望$$\begin{array}{c}
h(x_1)=y_1-F(x_1) \\
h(x_2)=y_2-F(x_2) \\
\cdots \\
h(x_n)=y_n-F(x_n) \\
\end{array}$$
所以我们可以训练出来一个模型 $h$ 来拟合数据 $(x_1,y_1-F(x_1)),(x_2,y_2-F(x_2)),\cdots,(x_n,y_n-F(x_n))$。如果添加 $h$ 后，我们对总模型仍不满意，可以继续添加新的模型。
与梯度下降的关系
上述的内容看起来与梯度下降没有关系，实则不然。回顾梯度下降的含义：通过向负梯度方向移动来最小化函数，即$$\theta_i:=\theta_i-\rho\cfrac{\partial J}{\partial \theta_i}$$
在上面的例子中，损失函数是 $L(y,F(x))=(y-F(x))^2/2$，我们想要通过调整 $F(x_1),\cdots,F(x_n)$ 来最小化 $J\left(\sum_{i=1}^n L(y_i,F(x_i))\right)$。则
$$\cfrac{\partial J}{\partial F(x_i)}=\cfrac{\partial \sum_{i=1}^n L(y_i,F(x_i))}{\partial F(x_i)}=\cfrac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=F(x_i)-y_i$$
所以
$$\begin{array}{c,l}
F(x_i)&:=&F(x_i)+h(x_i) \\
&:=&F(x_i)+y_i-F(x_i) \\
&:=&F(x_i)-1\cfrac{\partial J}{\partial F(x_i)}
\end{array}$$
梯度提升回归（Gradient Boosting for Regression）
总结一下上面的算法。负梯度为
$$-g(x_i)=-\cfrac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=y_i-F(x_i)$$
从一个最初的模型开始，比方说，$F(x_i)=\cfrac{\sum_{i=1}^n y_i}{n}$
重复下面过程直到收敛：
- 计算负梯度 $-g(x_i)$
- 对负梯度 $-g(x_i)$ 拟合一个模型 $h$（比如一个回归树）
- $F:=F+\rho h$，其中 $\rho=1$
这样描述算法有助于我们通过改变损失函数来推导出其他类似的算法。
其他损失函数
在上面，我们使用的是平方误差作为损失函数
- 优点：在数学上易于处理
- 缺点：对离群值很敏感（离群值会被很严重地惩罚，因为误差被平方放大了）
举个例子：
| $y_i$ | 0.5 | 1.2 | 2 | 5 |
|---|---|---|---|---|
| $F(x_i)$ | 0.6 | 1.4 | 1.5 | 1.7 |
| $L=(y-F)^2/2 $ | 0.005 | 0.02 | 0.125 | 5.445 |
这样的后果是给予了离群值过多的关注，过于努力地想把离群值纳入到模型中，从而使得模型地整体性能变差。
我们可以考虑其他的损失函数，比如下面这两个：
- 绝对值损失（不易受离群值影响）
$$L(y,F)=|y-F|$$ - Huber损失（不易受离群值影响）
$$L(y,F)=\begin{cases}
\frac{1}{2}(y-F)^2&|y-F|\le \delta \\
\delta(|y-F|-\delta/2)&|y-F|>\delta
\end{cases}$$
| $y_i$ | 0.5 | 1.2 | 2 | 5 |
|---|---|---|---|---|
| $F(x_i)$ | 0.6 | 1.4 | 1.5 | 1.7 |
| Square Loss | 0.005 | 0.02 | 0.125 | 5.445 |
| Absolute Loss | 0.1 | 0.2 | 0.5 | 3.3 |
| Huber Loss ($\delta=0.5$) |
0.005 | 0.02 | 0.125 | 1.525 |
更多的损失函数选择可参见参考资料2
Regression with Absolute Loss
负梯度为
$$-g(x_i)=-\cfrac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=\text{sign}(y_i-F(x_i))$$
从一个最初的模型开始，比方说，$F(x_i)=\cfrac{\sum_{i=1}^n y_i}{n}$
重复下面过程直到收敛：
- 计算负梯度 $-g(x_i)$
- 对负梯度 $-g(x_i)$ 拟合一个模型 $h$（比如一个回归树）
- $F:=F+\rho h$，其中 $\rho=1$
Regression with Huber Loss
负梯度为
$$-g(x_i)=-\cfrac{\partial L(y_i,F(x_i))}{\partial F(x_i)}=\begin{cases}
y_i-F(x_i)&|y_i-F(x_i)|\le \delta \\
\delta \text{sign}(y_i-F(x_i))&|y_i-F(x_i)|> \delta
\end{cases}$$
从一个最初的模型开始，比方说，$F(x_i)=\cfrac{\sum_{i=1}^n y_i}{n}$
重复下面过程直到收敛：
- 计算负梯度 $-g(x_i)$
- 对负梯度 $-g(x_i)$ 拟合一个模型 $h$（比如一个回归树）
- $F:=F+\rho h$，其中 $\rho=1$
梯度提升分类（Gradient Boosting Classification）
我们以一个具体的例子为场景：识别手写的大写字母。这是一个多分类问题。和回归不同的是，我们现在有26个模型函数 $F_A,F_B,F_C,\cdots,F_Z$，其中每个模型用来计算出样本属于该类别的分数，比如 $F_A(x)$ 表示这个字母是A的分数（分数越高，越可能属于这一类），然后将分数转换成概率：
$$\begin{array}{c}
P_A(x)=\cfrac{e^{F_A(x)}}{\sum_{c=A}^Ze^{F_c(x)}} \\
P_B(x)=\cfrac{e^{F_A(x)}}{\sum_{c=A}^Ze^{F_c(x)}} \\
\cdots \\
P_Z(x)=\cfrac{e^{F_A(x)}}{\sum_{c=A}^Ze^{F_c(x)}} \\
\end{array}$$
最终的预测结果即是概率最高的那一类
以 $y_5=G$ 为例，真实的概率分布为
我们逐渐调整 $F_A(x),\cdots,F_Z(x)$，使得预测的概率分布和真实的概率分布之间的差别逐渐缩小
用KL散度来刻画两个分布之间的差别，我们的目标就是最小化总的散度。
分类和回归的区别
- $F_A,F_B,\cdots,F_Z$ vs $F$
- 优化的参数是一个矩阵 vs 优化的目标是一个向量
$$\begin{matrix}
F_A(x_1)&F_B(x_1)&\cdots&F_Z(x_1) \\
F_A(x_2)&F_B(x_2)&\cdots&F_Z(x_2) \\
\cdots&\cdots&\cdots&\cdots \\
F_A(x_n)&F_B(x_n)&\cdots&F_Z(x_n)
\end{matrix}$$ - 计算的是一个梯度矩阵 vs 计算的是一个梯度向量
算法过程
从一组初始模型开始：$F_A,F_B,\cdots,F_Z$
重复下列步骤直到收敛：
- 对类A计算负梯度：$-g_A(x_i)=Y_A(x_i)-P_A(x_i)$
- 对类B计算负梯度：$-g_B(x_i)=Y_B(x_i)-P_B(x_i)$
$\cdots$ - 对类Z计算负梯度：$-g_Z(x_i)=Y_Z(x_i)-P_Z(x_i)$
- 训练一个模型（回归树）$h_A$ 来拟合负梯度 $-g_A(x_i)$
- 训练一个模型（回归树）$h_B$ 来拟合负梯度 $-g_B(x_i)$
$\cdots$ - 训练一个模型（回归树）$h_Z$ 来拟合负梯度 $-g_Z(x_i)$
- $F_A:=F_A+\rho_Ah_A$
- $F_B:=F_B+\rho_Bh_B$
$\cdots$ - $F_Z:=F_Z+\rho_Zh_Z$
选择步长
在预测过程中，我们每次添加一个弱分类器，但过多的分类器会导致过拟合，所以要对分类器的个数 $M$ 加以限制。另一方面，有人发现使用收缩技术可以很好地防止过拟合，一个简单的收缩技术就是在每一步中加入步长参数 $v$，即
$$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+v\cdot\rho_mh(\mathbf{x}),\quad 0<v\le 1$$
我们现在有两个参数可以来约束模型：$M$ 和 $v$。它们之间互相影响，理想情况是从两个参数的联合分布中选出最合适的取值。不过，增大 $M$ 也会同时增大计算量。下图是在某个数据集上做的测试，四条曲线分别代表 $v\in\{1.0,0.25,0.125,0.06\}$。
可以看出：
- 当 $v$ 比较大时，可以看到很明显的过拟合：$M$ 增大到一定程度时模型达到最优解，再增大 $M$，模型会变差。
- $v$ 值越小，收缩得越慢
- $v$ 值越小，过拟合越不明显