机器学习笔记之集成学习——Gradient Boosting

• 引言
• • 回顾：Boosting\text{Boosting}Boosting算法思想与AdaBoost\text{AdaBoost}AdaBoost
  • Gradient Boosting\text{Gradient Boosting}Gradient Boosting算法介绍
  • • 场景构建
    • 算法过程
    • 迭代过程与梯度下降法之间的关联关系

引言

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

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

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

基于加性模型的AdaBoost\text{AdaBoost}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}.

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

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

通过上面的算法流程，可以发现：关于权重分布Dt\mathcal D_tDt​，它并不是我们想要关注的对象。我们真正关注的对象只有αt\alpha_tαt​和hth_tht​。它的更新顺序表示为：
Dinit⇒h1,α1⇒D1⇒⋯⇒DT−1⇒hT,αT⇒DT\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}Dinit​⇒h1​,α1​⇒D1​⇒⋯⇒DT−1​⇒hT​,αT​⇒DT​

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

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

• 一般情况下，无论是重新赋权，还是重采样，两种方法没有优劣区别。但重新赋权方法中需要判别ϵt=Px∼Dt[ht(x)≠f(x)]\epsilon_t = \mathcal P_{x \sim \mathcal D_t} \left[h_t(x) \neq f(x)\right]ϵt​=Px∼Dt​​[ht​(x)=f(x)]的结果是否满足条件，如果不满足条件，会提前停止迭代。

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

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

场景构建

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

算法过程

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

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

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

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

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

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

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

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

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

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

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