引言

上一节介绍了$\text{Boosting}$算法思想。并以加性模型的$\text{AdaBoost}$为例，介绍了理论推导过程。本节将继续介绍$\text{Boosting}$算法系列的另一个样例——$\text{Gradient Boosting}$。

回顾：$\text{Boosting}$算法思想与$\text{AdaBoost}$

关于$\text{Boosting}$算法思想可表示为：在迭代过程中，通过不断学习出新的基学习器$h_t(x)(t=1,2,\cdots ,\mathcal{T})$，使得它们能够更关注之前迭代过程中的基学习器预测误差较大的样本，最终使得基学习器融合的强学习器 能够覆盖更多的样本，并使得这些样本的预测偏差较小。

基于加性模型的$\text{AdaBoost}$算法描述表示如下：
这里仅描述的是‘二分类任务’，关于样本标签 y ( i ) ( i = 1 , 2 , ⋯   , N ) ∈ { − 1 , + 1 } y^{(i)}(i=1,2,\cdots,N) \in \{-1,+1\} y(i)(i=1,2,⋯,N)∈{−1,+1}.

输入$(\text{Input})$	训练集 D = { x ( i ) , y ( i ) } i = 1 N \mathcal D = \{x^{(i)},y^{(i)}\}_{i=1}^N D={x(i),y(i)}i=1N​；基学习算法$\mathcal{K}$；迭代次数$\mathcal{T}$
初始化($\text{Initialization}$)	$\begin{array}{r}{\mathcal{D}}_{init}=\frac{1}{N}\end{array}$
算法过程($\text{Algorithmic Process}$)	$1.$ for $t=1,2,\cdots ,\mathcal{T}$ do： $2.$   $h_t=\mathcal{K}(\mathcal{D},{\mathcal{D}}_t);$ $3.$   ${ϵ}_t={\mathcal{P}}_{x\sim {\mathcal{D}}_t}\left[h_t(x)\ne f(x)\right]$ $4.$   if ${ϵ}_t>0.5:$ $5.$      break $6.$   else $7.$      ${\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$ $8.$      D t + 1 = 1 Z t ⋅ D t ⋅ exp ⁡ { − f ( x ) ⋅ α t h t } \mathcal D_{t+1} = \frac{1}{\mathcal Z_t} \cdot \mathcal D_t \cdot \exp\{-f(x) \cdot \alpha_th_t\} Dt+1​=Zt​1​⋅Dt​⋅exp{−f(x)⋅αt​ht​} $9.$ end for
输出($\text{Output}$)	$\mathcal{H}(x)=\text{Sign}({\sum }_{t=1}^{\mathcal{T}}{\alpha }_t{h}_t)$

观察上述算法，对于学习出的基学习器$h_t=\mathcal{K}(\mathcal{D},{\mathcal{D}}_t)$，其中${\mathcal{D}}_t$表示样本的采样权重。也可以理解为样本被关注的程度。
以$5$个样本组成的数据集为例，初始状态下，它们各自的权重信息是相等状态：
$${\mathcal{D}}_{init}\Rightarrow \left[\frac{1}{5},\frac{1}{5},\frac{1}{5},\frac{1}{5},\frac{1}{5}\right]$$
经过$t$次迭代后，得到的权重结果可能是这个样子：
$${\mathcal{D}}_t\Rightarrow \left[\frac{1}{10},\frac{1}{10},\frac{2}{5},\frac{1}{5},\frac{1}{5}\right]$$
比较这两组权重，可以发现：对于样本的关注度转移了。可以想象：

• 对于$x^{(1)},x^{(2)}$两个样本，$t$次迭代之前学习的基学习器$h_1,\cdots ,h_{t-1}$相比之下能够较容易地将这两个样本预测正确；
• 相反，被分配权重较高的样本，如样本$x^{(3)}$，它就需要当前迭代的基学习器$h_t$进行学习。如果依然有$f(x^{(3)})\ne h_t(x^{(3)})$，只能再次分配权重，让$t+1$次迭代的基学习器$h_{t+1}$去学习$x^{(3)}$，以此类推。

通过上面的算法流程，可以发现：关于权重分布${\mathcal{D}}_t$，它并不是我们想要关注的对象。我们真正关注的对象只有${\alpha }_t$和$h_t$。它的更新顺序表示为：
$${\mathcal{D}}_{init}\Rightarrow h_1,{\alpha }_1\Rightarrow {\mathcal{D}}_1\Rightarrow \cdots \Rightarrow {\mathcal{D}}_{\mathcal{T}-1}\Rightarrow h_{\mathcal{T}},{\alpha }_{\mathcal{T}}\Rightarrow {\mathcal{D}}_{\mathcal{T}}$$

关于加性模型的$\text{AdaBoost}$，在每次迭代学习新的基学习器 过程中，我们只是对训练集$\mathcal{D}$进行重新赋权($\text{Re-Weighting}$)操作。那么对于不接受带权样本的基学习算法${\mathcal{K}}^{\prime }$，可以使用重采样($\text{Re-Sampling}$)实现。
机器学习(周志华著)P177.

• 不同于重新赋权操作，$t$次迭代过程中重采样操作产生的${\mathcal{D}}_t$不再是权重分布，而是真真正正的以$t-1$次迭代过程中未被学习正确的样本为主体的样本集合。

• 一般情况下，无论是重新赋权，还是重采样，两种方法没有优劣区别。但重新赋权方法中需要判别${ϵ}_t={\mathcal{P}}_{x\sim {\mathcal{D}}_t}\left[h_t(x)\ne f(x)\right]$的结果是否满足条件，如果不满足条件，会提前停止迭代。

  相反，如果是重采样方法，相当于每一次迭代均重新设置训练集，只要训练集内有样本，就不会出现停止迭代的情况。因而可以持续到预设的$\mathcal{T}$轮迭代完成。
  由于概率密度积分的约束，因而权重之和必然是1 -> 不会出现采不到样本的情况。

$\text{Gradient Boosting}$算法介绍

场景构建

依然假设数据集合$\mathcal{D}=\{(x^{(i)},y^{(i)}){\}}_{i=1}^N$，并且定义一个初始状态下预测模型${\mathcal{H}}_{init}(x)$，并初始化它的模型结果：
$${\mathcal{H}}_{init}(x^{(i)})=0i=1,2,\cdots ,N$$

算法过程

这里以第$t$次迭代为例，并且假设我们基于数据集$\mathcal{D}$处理一个回归任务：

• 在$t-1$次迭代后我们得到的数据集合${\mathcal{D}}_{t-1}$表示如下：
  $${\mathcal{D}}_{t-1}=\{(x^{(i)},y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})){\}}_{i=1}^N$$
  其中，样本特征$x^{(i)}(i=1,2,\cdots ,N)$未发生变化；而对应标签表示为真实标签$y^{(i)}$与$t-1$时刻预测模型${\mathcal{H}}_{t-1}(x)$关于对应样本$x^{(i)}$的预测结果${\mathcal{H}}_{t-1}(x^{(i)})$之间的残差信息($\text{Residuals}$)：
  当$t=1$时,${\mathcal{H}}_0(x^{(i)})={\mathcal{H}}_{init}(x^{(i)})=0$。这意味着‘初始时刻’就在原始的数据集合$\mathcal{D}$上进行训练。
  $$y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})$$

• 以${\mathcal{D}}_{t-1}$作为第$t$次迭代步骤的数据集，并通过学习算法$\mathcal{K}$从该数据集训练出一个新的基学习器($\text{Base Learner}$)$h_t$：
  $$h_t=\mathcal{K}({\mathcal{D}}_{t-1})$$
  这意味着：$h_t$作为学习的并不是关于真实标签的信息，而是$t-1$时刻的预测模型${\mathcal{H}}_{t-1}(x)$对于真实标签拟合不足的部分。也就是说，${\mathcal{H}}_{t-1}(x)$对于真实标签没有拟合的部分，由新训练的基学习器$h_t$去拟合。

• 按照上述逻辑，我们需要将$t-1$时刻预测模型${\mathcal{H}}_{t-1}(x)$与$t$时刻的基学习器$h_t$做融合，得到$t$时刻的预测模型${\mathcal{H}}_t(x)$：
  $${\mathcal{H}}_t(x)={\mathcal{H}}_{t-1}(x)+\eta \cdot h_t$$
  观察上式可以发现，多了一个学习率($\text{Learning Rate}$)$\eta$。它本质上式一个正则项，也被称作基学习器$h_t$的收缩($\text{Shrinkage}$)。从常规逻辑的角度，既然$h_t$能够对残差训练集${\mathcal{D}}_{t-1}$进行拟合，那么应该将$h_t$与${\mathcal{H}}_{t-1}(x)$直接融合即可。即$\eta =1$。

  但真实情况是，这种做法可能会导致过拟合$(\text{Overfitting})$。因为不断拟合残差的过程，最终可能导致：除去初始的若干次迭代之外，剩余的迭代中基学习器拟合的信息绝大多数是数据的噪声信息。因而使用学习率来约束基学习器$h_t$的拟合信息。

迭代过程与梯度下降法之间的关联关系

关于${\mathcal{H}}_t(x)$的迭代过程类似于梯度下降法($\text{Gradient Descent,GD}$)，不同于梯度下降法的点在于：直接对预测模型自身求解梯度，而不是对模型参数。针对回归任务的目标函数，我们选择均方误差($\text{Mean-Square Error,MSE}$)：
$$\mathcal{L}=\frac{1}{N}\sum _{i=1}^N{\left(y^{(i)}-y_{pred}^{(i)}\right)}^2$$

• 由于样本之间独立同分布($\text{Independent Identically Distribution,IID}$)这里仅观察某一个样本标签$y^{(i)}$的目标函数信息：
  $${\mathcal{L}}^{(i)}=\frac{1}{N}{\left(y^{(i)}-y_{pred}^{(i)}\right)}^2$$
• 假设迭代到$t$时刻停止，那么此时的预测模型就是${\mathcal{H}}_t(x)$。因而关于样本标签$y^{(i)}$的预测结果$y_{pred}^{(i)}$为：
  $$y_{pred}^{(i)}={\mathcal{H}}_t(x^{(i)})$$
• 根据定义，我们希望基学习器$h_t$能够拟合${\mathcal{H}}_{t-1}(x)$拟合不足的部分。关于样本$(x^{(i)},y^{(i)})$，有：
  $$h_t(x^{(i)})=y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})$$
• 至此，基于上述逻辑关系，我们要求解样本$(x^{(i)},y^{(i)})$对应的目标函数${\mathcal{L}}^{(i)}$对$t-1$时刻的预测模型${\mathcal{H}}_{t-1}(x^{(i)})$的梯度：
  $$\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}$$
  根据链式求导法则，可以将其拆成两项：
  后续梯度$\begin{array}{r}\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}\end{array}$使用符号$\mathcal{I}$替代。
  $$\mathcal{I}=\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_t(x^{(i)})}\cdot \frac{\partial {\mathcal{H}}_t(x^{(i)})}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}$$
  观察第一项，将${\mathcal{L}}^{(i)}$代入，有：
  也将$y_{pred}^{(i)}={\mathcal{H}}_t(x^{(i)})$代入公式。
  $$\begin{array}{rl}\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_t(x^{(i)})}& =\frac{1}{N}\cdot 2\times (y^{(i)}-y_{pred}^{(i)})\cdot [0-1]\\ & =-\frac{2}{N}\left[y^{(i)}-{\mathcal{H}}_t(x^{(i)})\right]\end{array}$$
  观察第二项，它的结果为：
  这里$\eta \cdot h_t(x^{(i)})$与${\mathcal{H}}_{t-1}(x^{(i)})$之间无关，视作常数，导数结果为$0$.
  $$\begin{array}{rl}\frac{\partial {\mathcal{H}}_t(x^{(i)})}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}& =\frac{\partial }{\partial {\mathcal{H}}_{t-1}(x^{(i)})}\left[{\mathcal{H}}_{t-1}(x^{(i)})+\eta \cdot h_t(x^{(i)})\right]\\ & =1+0\\ & =1\end{array}$$
  至此，梯度结果$\mathcal{I}$表示如下：
  将$h_t(x^{(i)})=y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})$代入到公式中。
  $$\begin{array}{rl}\mathcal{I}& =-\frac{2}{N}\left[y^{(i)}-{\mathcal{H}}_t(x^{(i)})\right]\times 1\\ & =-\frac{2}{N}\left[y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})-\eta \cdot h_t(x^{(i)})\right]\\ & =-\frac{2}{N}(1-\eta )\cdot h_t(x^{(i)})\end{array}$$
• 此时梯度中，$\begin{array}{r}\frac{2}{N}(1-\eta )\end{array}$仅是一个描述梯度大小的系数，和方向无关。因而可以继续化简为如下形式：
  $$\mathcal{I}=\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}\propto -h_t(x^{(i)})$$
  此时再回顾预测模型的迭代公式，可以将其转化为：
  $$\begin{array}{rl}& {\mathcal{H}}_t(x^{(i)})={\mathcal{H}}_{t-1}(x^{(i)})+\eta \cdot h_t(x^{(i)})\\ & \Rightarrow {\mathcal{H}}_t(x^{(i)})={\mathcal{H}}_{t-1}(x^{(i)})-\eta \cdot \frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}\end{array}$$
  可以看出，这就是一个梯度下降的标准公式。这说明基学习器$h_t$，它的方向与梯度优化的方向相反。
  这里是针对视频中$\begin{array}{r}\text{The residuals equal to }-\frac{\partial \mathcal{L}}{\partial \mathcal{H}}\text{ if using MSE as the loss.}\end{array}$的一个推导解释。

需要注意的是，一些其他的$\text{Boosting}$函数，也可以套用到$\text{Gradient Boosting}$这个框架下面。这里仅以回归任务(均方误差)示例描述。

下一节将针对基学习器方向与梯度方向相反的性质介绍梯度提升树($\text{Gradient Boosting Decision Tree,GBDT}$)

相关参考：
5.3 Boosting【斯坦福21秋季：实用机器学习中文版】
机器学习(周志华著)