引言

上一节介绍了$\text{Boosting}$集成思想的经典样例——$\text{Gradient Boosting}$，本节将介绍基于$\text{Gradient Boosting}$的经典模型——梯度提升树($\text{Gradient Boosting Decision Tree,GBDT}$)。

回顾：

$\text{Boosting}$架构

$\text{Boosting}$，它自身不是一个算法，也不是一个模型，相比之下，它更像是一个架构($\text{Structure}$)：若干个弱模型($\text{Weak Model}$)通过该架构整合成一个强模型($\text{Strong Model}$)。

弱模型与强模型之间是如何进行划分的？
题外话。在集成学习思想中，$\text{Bagging,Stacking}$使用的基学习器$(\text{Base Learner})$属于强模型(高方差、低偏差)，针对不同的学习任务，将各个强模型的预测结果‘结合’，从而降低强模型的‘高方差’弊端;相反，$\text{Boosting}$使用的基学习器属于弱模型(低方差、高偏差)，从而通过有序迭代，将若干模型整合成强模型。

• 关于分类$(\text{Classification})$任务，通过投票$(\text{Voting})$的方式选择最优预测类别(少数服从多数)。
• 关于回归$(\text{Regression})$任务，采用取均值$(\text{Meaning})$的方式消掉各学习器预测结果的方差信息。

从模型的预测性能——偏差与方差的角度观察：

• 强模型属于预测低偏差$(\text{Low-Bias})$、高方差$(\text{High-Varance})$的模型；
  也就是说，强模型对于真实模型的位置预测的更加准确，但覆盖的范围更加广阔。
• 弱模型属于预测高偏差$(\text{High-Bias})$、低方差$(\text{Low-Varance})$的模型；
  相反，弱模型对于真实模型的‘规模’预测的更加准确，但对于分布位置的精确度可能不尽人意。

从样本拟合$(\text{Fitting})$的角度观察：弱模型属于对样本特征拟合不够/拟合不完整；相反，强模型能够对样本特征的拟合效果过于完整，甚至覆盖真实模型的分布区域。

$\text{Gradient Boosting VS AdaBoost}$

不同于$\text{Bagging}$学习思想，$\text{Boosting}$使用数据集内的全部数据去有顺序地训练若干基学习器，使训练的相邻的基学习器之间相互依赖，当前迭代步骤下的预测模型${\mathcal{H}}_t(x)$是前面所有基学习器$h_1,h_2,\cdots ,h_{t-1}$的结果。

• (加性模型)$\text{AdaBoost}$ ：预测模型${\mathcal{H}}_{\mathcal{T}}(x)$具体描述为各基学习器$h_1,h_2,\cdots ,h_{\mathcal{T}}$之间的线性组合：
  其中$\text{Sign}$表示基于二分类任务的指示函数;${\alpha }_t(t=1,2,\cdots ,\mathcal{T})$表示各基学习器对应的权重参数。
  $${\mathcal{H}}_{\mathcal{T}}(x)=\text{Sign}\left(\sum _{t=1}^{\mathcal{T}}{\alpha }_t\cdot h_t\right)$$
• $\text{Gradient Boosting}$：其描述的是当前时刻预测模型${\mathcal{H}}_t(x)$与上一时刻预测模型${\mathcal{H}}_{t-1}(x)$之间的迭代关系：
  $${\mathcal{H}}_t(x)={\mathcal{H}}_{t-1}(x)+\eta \cdot h_t$$
  将上式展开，关于迭代结束后的预测模型${\mathcal{H}}_{\mathcal{T}}(x)$表示为如下形式：
  $${\mathcal{H}}_{\mathcal{T}}(x)=\underset{{\mathcal{H}}_2(x)}{\underbrace{\underset{{\mathcal{H}}_1(x)}{\underbrace{{\mathcal{H}}_{init}+\eta \cdot h_1}}+\eta \cdot h_2}}+\cdots +\eta \cdot h_{\mathcal{T}}$$

从结构格式上观察，$\text{AdaBoost}$与$\text{Gradient Boosting}$的迭代结果很相似，但核心区别在于它们对于训练数据的描述过程：

• $\text{AdaBoost}$在迭代过程使用的数据集$\mathcal{D}$从始至终都没有发生过修改。而仅修改每次迭代过程中对于数据集内不同样本的关注度：
  $${\mathcal{D}}_1,{\mathcal{D}}_2,\cdots ,{\mathcal{D}}_{\mathcal{T}}$$
  ${\mathcal{D}}_t(t=1,2,\cdots ,\mathcal{T})$可以理解成一个概率集合，而这种操作被称作重赋权($\text{Re-Weighting}$)操作：
  其中${\mathcal{P}}_t^{(i)}$表示第$t$次迭代关于样本$x^{(i)}$的关注度。
  D t = { P t ( 1 ) , P t ( 2 ) , ⋯   , P t ( N ) } ∑ i = 1 N P t ( i ) = 1 \mathcal D_t = \{\mathcal P_t^{(1)},\mathcal P_t^{(2)},\cdots,\mathcal P_t^{(N)}\} \quad \sum_{i=1}^N \mathcal P_t^{(i)} = 1 Dt​={Pt(1)​,Pt(2)​,⋯,Pt(N)​}i=1∑N​Pt(i)​=1
  如果数据集合$\mathcal{D}$不支持带权样本的学习算法，同样可以将${\mathcal{P}}_t^{(i)}(i=1,2,\cdots ,N)$视作采样概率，使用重采样($\text{Re-Sampling}$)操作产生新的数据集。
  采样概率即：以${\mathcal{P}}_t^{(i)}$的概率将样本$x^{(i)}$从数据集$\mathcal{D}$中采样出来，作为当前迭代步骤下数据集合的样本。
  但无论是重赋权，还是重采样，它们都没有对数据集$\mathcal{D}$的样本产生任何修改。

  并且，$\text{AdaBoost}$关于数据集合$\mathcal{D}$的关注度直接影响每次迭代下权重参数${\alpha }_t$的取值结果。相比之下，对应迭代产生的基学习器$h_t$相比之下关注差一些。

  • 如果是重赋权，那么至始至终都没有缺失过样本,仅是每次迭代关注的样本点不同;
  • 如果是重采样,那么每次迭代采样产生的新集合必然也是数据集合$\mathcal{D}$的子集，对应学习出的基学习器与之前迭代的基学习器之间存在相似性。如何对这些基学习器进行权重分配才是$\text{AdaBoost}$架构的核心要素。

• 相反，$\text{Gradient Boosting}$在算法的迭代过程中对数据集$\mathcal{D}$的标签信息进行了修改：
  $${\mathcal{D}}_t=\{(x^{(i)},y^{(i)}-{\mathcal{H}}_t(x^{(i)})){\}}_{i=1}^N$$
  其中，$y^{(i)}$是样本特征$x^{(i)}$的标签信息，也就是真实模型$f(x)$关于样本特征$x^{(i)}$的映射结果；而${\mathcal{H}}_t(x^{(i)})$表示第$t$次迭代过程产生的预测模型${\mathcal{H}}_t(x)$对于样本$x^{(i)}$的预测标签。

  那么$y^{(i)}-{\mathcal{H}}_t(x^{(i)})$表示预测标签与真实标签之间的差距。而基学习器$h_{t+1}$就是通过学习算法$\mathcal{K}$对这个差距进行建模并学习特征：
  $$h_{t+1}=\mathcal{K}({\mathcal{D}}_t)$$
  与此同时，由于每次迭代过程种数据集合的变化，使得$\text{Gradient Boosting}$关注点在于基学习器自身，而不是学习率。
  学习率作为权重参数，自身就是人为设置的常数，以防止过拟合。而基学习器的学习效果才是最终模型预测效果的核心要素。

$\text{CART}$回归树

关于梯度提升树($\text{GBDT}$)使用的决策树是$\text{CART}$($\text{Classification And Regression Tree}$)回归树。$\text{GBDT}$处理的无论是回归任务还是分类任务，均使用$\text{CART}$回归树作为基学习器。

其核心原因在于：在$\text{GBDT}$迭代的过程中，需要计算梯度结果，只有$\text{CART}$回归树才能保证在函数空间内连续、可微。

在决策树算法——基本介绍中提到，分类树的最优划分点的判别标准是熵($\text{Entropy}$)或者$\text{GINI}$系数，它们的准确度是由纯度衡量。关于回归任务中的标签信息是连续型随机变量，因而使用平方误差($\text{Squared Error}$)作为评判回归树拟合程度的损失函数。
纯度是指叶子结点内的样本属于相同类型的程度。

关于回归树的生成算法表示如下：
再回首：关于树的生成逻辑：
遍历样本特征内的属性，每一次遍历均可以将对应的样本空间划分成两个子集;
计算两个子集的$\mathcal{C}$值，再基于$\mathcal{C}$值计算对应的平方误差结果。
遍历结束后，谁的平方误差小，就选对应属性作为划分点，以此类推。

• 场景构建

  • 给定训练数据集$\mathcal{D}=\{(x^{(i)},y^{(i)}){\}}_{i=1}^N{x}^{(i)}\in {\mathbb{R}}^p$
  • 关于回归树$f(x)$的构建：将$\mathcal{X}$的特征空间划分为$\mathcal{M}$份，每一份都对应回归树的叶子结点：
    需要注意的是,${\mathcal{R}}_1,\cdots ,{\mathcal{R}}_{\mathcal{M}}$的并集是样本$\mathcal{X}$的特征空间，但它和$\mathcal{X}$的特征维度$p$不是一个概念。
    $${\mathcal{R}}_1,{\mathcal{R}}_2,\cdots ,{\mathcal{R}}_{\mathcal{M}}$$
    并且每个特征子空间(叶子结点)${\mathcal{R}}_m(m=1,2,\cdots ,\mathcal{M})$均对应一个固定的输出结果${\mathcal{C}}_m(m=1,2,\cdots ,\mathcal{M})$。因而关于回归树的模型$f(x^{(i)})$可表示为：
    若样本被划分进同一个特征空间${\mathcal{R}}_m$,它们的预测结果是相同的。均为${\mathcal{C}}_m$.
    $$f(x^{(i)})=\sum _{m=1}^{\mathcal{M}}{\mathcal{C}}_m\cdot \mathbb{I}(x^{(i)}\in {\mathcal{R}}_m)$$
    其中$\mathbb{I}$表示指示函数($\text{Indicator Function}$)：
    $$\mathbb{I}(x^{(i)}\in {\mathcal{R}}_m)=\{\begin{array}{l}1\text{if }{x}^{(i)}\in {\mathcal{R}}_m\\ 0\text{otherwise}\end{array}$$
  • 关于训练过程的损失函数——平方误差表示为：
    需要注意的是，这个$\mathcal{L}$描述的是每个特征空间${\mathcal{R}}_m(m=1,2,\cdots ,\mathcal{M})$中的样本，其预测结果与真实标签的平方误差。
    $$\mathcal{L}=\sum _{x^{(i)}\in {\mathcal{R}}_m}{\left[y^{(i)}-f(x^{(i)})\right]}^2$$

• 算法执行过程：

  • 通过遍历样本特征$\mathcal{X}$的 属性$s$：
  • 每一次遍历得到的属性$s$，可以基于该属性，将对应的特征空间划分为两个子特征空间：
    ${\mathcal{R}}_1(j,s),{\mathcal{R}}_2(j,s)$是基于当前特征空间中，满足/不满足属性条件$s$的样本集合。
    $j$并不是什么正儿八经的参数，它仅是样本编号。
    R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } ; R 2 ( j , s ) = { x ∣ x ( j ) > s } \mathcal R_1(j,s) = \{x \mid x^{(j)} \leq s\};\mathcal R_2(j,s) = \{x \mid x^{(j)} > s\} R1​(j,s)={x∣x(j)≤s};R2​(j,s)={x∣x(j)>s}
  • 如何判别被划分的集合${\mathcal{R}}_1(j,s),{\mathcal{R}}_2(j,s)$是优秀的？也就是说，如何判别属性$s$是一个优秀的划分点——使用平方误差进行描述：
    如果能使下式达到最小，对应的划分属性$s$与集合${\mathcal{R}}_1(j,s)$与${\mathcal{R}}_2(j,s)$就是该次划分下的最优子集合。
    $$\underset{j,s}{\min }\left[\underset{{\mathcal{C}}_1}{\min }\sum _{x^{(i)}\in {\mathcal{R}}_1(j,s)}(y^{(i)}-{\mathcal{C}}_1{)}^2+\underset{{\mathcal{C}}_2}{\min }\sum _{x^{(i)}\in {\mathcal{R}}_2(j,s)}(y^{(i)}-{\mathcal{C}}_2{)}^2\right]$$
  • 各子集合对应的$\mathcal{C}$的最优值${\hat{\mathcal{C}}}_m(m=1,2,\cdots ,\mathcal{M})$可表示为：
    $${\hat{\mathcal{C}}}_m=\text{AVG}(y^{(i)}\mid x^{(i)}\in {\mathcal{R}}_m)$$
  • 重复执行上述$2,3$步骤，直到满足停止条件。此时得到了$\mathcal{M}$个满足条件的特征空间，生成决策树：
    下面则以某样本$x^{(i)}\in {\mathcal{R}}_m$为例，描述它的预测结果。
    $$\begin{array}{rl}f(x^{(i)})& =\sum _{m=1}^{\mathcal{M}}{\hat{\mathcal{C}}}_m\cdot \mathbb{I}(x^{(i)}\in {\mathcal{R}}_m)\\ & =\widehat{{\mathcal{C}}_1}\cdot \underset{=0}{\underbrace{\mathbb{I}(x^{(i)}\in {\mathcal{R}}_1)}}+\cdots +{\hat{\mathcal{C}}}_m\cdot \underset{=1}{\underbrace{\mathbb{I}(x^{(i)}\in {\mathcal{R}}_m)}}+\cdots +{\hat{\mathcal{C}}}_{\mathcal{M}}\cdot \underset{=0}{\underbrace{\mathbb{I}(x^{(i)}\in {\mathcal{R}}_{\mathcal{M}})}}\\ & ={\hat{\mathcal{C}}}_m\cdot 1\\ & ={\hat{\mathcal{C}}}_m\end{array}$$

梯度提升树($\text{Gradient Boosting Decision Tree,GBDT}$)

梯度提升树本质上是以$\text{Gradient Boosting}$作为架构，以决策树($\text{Decision Tree}$)作为基学习器的模型结构。由于是$\text{Boosting}$架构，因而我们需要一种弱模型作为基学习器进行学习。但决策树并不是弱模型，它是一种强模型：随着树结构的不断加深，这意味着对于特征空间的划分更加细致，从而使样本逐渐拟合模型。

因而，我们需要限制决策树的深度：从而因特征空间划分不够细致使得某些样本的归属比较模糊，从而使决策树降为弱模型：为后续的迭代留下空间。
更有激进的工程师仅使用‘深度仅为1的树桩’作为GBDT的基学习器，哈哈~

$\text{Gradient Boosting}$算法过程

回顾$\text{Gradient Boosting}$算法过程表示如下：

• 对预测模型进行初始化：${\mathcal{H}}_{init}(x)=0$
• 执行$\mathcal{T}$次迭代：$t=1,2,\cdots ,\mathcal{T}$：
  • 计算残差($\text{Residual}$)：$r_t^{(i)}=y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})i=1,2,\cdots ,N$；
  • 通过样本特征$x^{(i)}(i=1,2,\cdots ,N)$以及对应的残差结果$r_t^{(i)}$构成新数据集${\mathcal{D}}_t=\{(x^{(i)},r_t^{(i)}){\}}_{i=1}^N$，并基于${\mathcal{D}}_t$，使用学习算法$\mathcal{K}$，学习出一个新的基学习器(回归树) $h_t(x)$：
    $$h_t(x)=\mathcal{K}({\mathcal{D}}_t)$$
  • 使用基学习器$h_t(x)$更新预测模型(回归树)${\mathcal{H}}_{t-1}(x)$：
    $${\mathcal{H}}_t(x)={\mathcal{H}}_{t-1}(x)+\eta \cdot h_t(x)$$
• $\mathcal{T}$次迭代步骤执行结束，最终得到预测模型${\mathcal{H}}_{\mathcal{T}}(x)$
  $${\mathcal{H}}_{\mathcal{T}}(x)={\mathcal{H}}_{init}(x)+\eta \cdot h_1(x)+\cdots +\eta \cdot h_{\mathcal{T}}(x)$$

而上述算法过程中的残差$r_t^{(i)}$同样也是基学习器$h_t$的学习目标。根据残差与梯度下降之间关联关系，残差结果与目标函数${\mathcal{L}}^{(i)}$与预测模型${\mathcal{H}}_{t-1}(x^{(i)})$的梯度方向相反：
在推导过程中目标函数$\mathcal{L}$使用的是‘均方误差’$(\text{MSE})$，而$\text{CART}$回归树使用的是‘平方误差’，这里仅差了一个系数$\begin{array}{r}\frac{1}{N}\end{array}$,虽然不影响$\propto$关系，但是需要知道。
$$r_t^{(i)}=h_t(x^{(i)})\propto -\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}$$

梯度提升树算法过程

梯度提升树的 核心逻辑 是：利用损失函数的负梯度在当前模型的值，作为残差的近似值。即：

• 将$\mathcal{L}$使用平方误差展开。
• 系数$\begin{array}{r}\frac{1}{2}\end{array}$本身是不存在的，这里仅是将导数过程中的系数$2$消去，增加一个系数只会影响梯度大小，并不改变梯度方向。
  $$\begin{array}{rl}-\frac{\partial {\mathcal{L}}^{(i)}}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}& \approx -\frac{\partial \left[\frac{1}{2}(y^{(i)}-{\mathcal{H}}_{t-1}{\left(x^{(i)})\right)}^2\right]}{\partial {\mathcal{H}}_{t-1}(x^{(i)})}\\ & =-\frac{1}{2}\cdot 2\cdot \left[y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})\right]\cdot [0-1]\\ & =y^{(i)}-{\mathcal{H}}_{t-1}(x^{(i)})\\ & =r_t^{(i)}\end{array}$$

至此，关于梯度提升树的算法过程表示如下：

• 初始化预测模型${\mathcal{H}}_{init}(x)$

  • 样本之间独立同分布，因而损失函数表示为$N$个样本$x^{(i)}(i=1,2,\cdots ,N)$关于对应真实标签$y^{(i)}$偏差的总和。
  • 初始状态下，每一个样本各自被划分为一个特征子空间;而$c$表示各样本的标签自身。$\mathcal{L}$表示平方误差。
    $${\mathcal{H}}_{init}(x)=\underset{c}{\mathrm{argmin}}\sum _{i=1}^N\mathcal{L}(y^{(i)},c)$$

• 执行$\mathcal{T}$次迭代：$t=1,2,\cdots ,\mathcal{T}$：
  这里以$t=1$为例。

  • 对于每个样本$(x^{(i)},y^{(i)})(i=1,2,\cdots ,N)$，计算当前迭代过程的残差：
    $$r_1^{(i)}\Leftarrow -\left[\frac{\partial \mathcal{L}(y^{(i)},{\mathcal{H}}_{init}(x^{(i)}))}{\partial {\mathcal{H}}_{init}(x^{(i)})}\right]$$
  • 将产生的新样本集合${\mathcal{D}}_1=\{(x^{(i)},r_1^{(i)}){\}}_{i=1}^N$作为下一棵树的训练数据，并得到一棵新的回归树(基学习器)$h_1(x)$。并将回归树$h_1(x)$划分的特征空间集合记作 R 1 = { R 1 1 , R 2 1 , ⋯   , R M 1 } \mathcal R^1 = \{\mathcal R_1^1,\mathcal R_2^1,\cdots,\mathcal R_{\mathcal M}^1\} R1={R11​,R21​,⋯,RM1​}
    这里的$\mathcal{M}$指回归树$h_1(x)$划分的特征空间(叶子结点)的个数。
  • 对每一个特征子空间${\mathcal{R}}_m^1(m=1,2,\cdots ,\mathcal{M})$计算最优拟合结果：
    个人解惑：关于上一次迭代拟合的剩余部分就是我们的拟合目标。因而$\mathcal{L}$内部并不是${\mathcal{H}}_{init}(x^{(i)})+\eta \cdot {\mathcal{C}}_m$.
    $${\hat{\mathcal{C}}}_m^1=\underset{{\mathcal{C}}_m}{\mathrm{argmin}}\sum _{x^{(i)}\in {\mathcal{R}}_m^1}\mathcal{L}\left[y^{(i)},{\mathcal{H}}_{init}(x^{(i)})+{\mathcal{C}}_m\right]m=1,2,\cdots ,\mathcal{M}$$
  • 至此，得到了$\mathcal{M}$个$h_1(x)$对于各特征子空间的最优均值结果：${\hat{\mathcal{C}}}_1^1,{\hat{\mathcal{C}}}_2^1,\cdots ,{\hat{\mathcal{C}}}_{\mathcal{M}}^1$，使用该结果去优化当前迭代步骤下的预测模型${\mathcal{H}}_1(x)$：
    $$\begin{array}{rl}{\mathcal{H}}_1(x)& ={\mathcal{H}}_{init}(x)+\eta \cdot h_1(x)\\ & ={\mathcal{H}}_{init}(x)+\eta \cdot \left[{\hat{\mathcal{C}}}_1^1\cdot \mathbb{I}(x\in {\mathcal{R}}_1^1)+\cdots +{\hat{\mathcal{C}}}_{\mathcal{M}}^1\cdot \mathbb{I}(x\in {\mathcal{R}}_{\mathcal{M}}^1)\right]\\ & ={\mathcal{H}}_{init}(x)+\eta \cdot \sum _{m=1}^{\mathcal{M}}{\hat{\mathcal{C}}}_m^1\cdot \mathbb{I}(x\in {\mathcal{R}}_m^1)\end{array}$$

重复执行上述步骤$\mathcal{T}$次，最终可得到最终预测模型${\mathcal{H}}_{\mathcal{T}}(x)$：
$$\begin{array}{rl}{\mathcal{H}}_{\mathcal{T}}(x)& ={\mathcal{H}}_{init}(x)+\eta \cdot \left[h_1(x)+h_2(x)+\cdots +h_{\mathcal{T}}(x)\right]\\ & ={\mathcal{H}}_{init}(x)+\eta \cdot \sum _{t=1}^{\mathcal{T}}\sum _{m=1}^{\mathcal{M}}{\hat{\mathcal{C}}}_m^t\cdot \mathbb{I}(x\in {\mathcal{R}}_m^t)\end{array}$$
下一节将介绍集成学习方法——$\text{Stacking}$。

相关参考：
【算法岗求职笔记】集成学习(一)通用概念·八问八答
第09讲：GBDT堪称最好的算法之一
GBDT算法原理以及实例理解（含Python代码简单实现版）