机器学习笔记之集成学习——梯度提升树[GBDT]

• 引言
• • 回顾：
  • • Boosting\text{Boosting}Boosting架构
    • Gradient Boosting VS AdaBoost\text{Gradient Boosting VS AdaBoost}Gradient Boosting VS AdaBoost
  • CART\text{CART}CART回归树
  • 梯度提升树(Gradient Boosting Decision Tree,GBDT\text{Gradient Boosting Decision Tree,GBDT}Gradient Boosting Decision Tree,GBDT)
  • • Gradient Boosting\text{Gradient Boosting}Gradient Boosting算法过程
    • 梯度提升树算法过程

引言

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

回顾：

Boosting\text{Boosting}Boosting架构

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

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

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

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

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

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

Gradient Boosting VS AdaBoost\text{Gradient Boosting VS AdaBoost}Gradient Boosting VS AdaBoost

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

• (加性模型)AdaBoost\text{AdaBoost}AdaBoost ：预测模型HT(x)\mathcal H_{\mathcal T}(x)HT​(x)具体描述为各基学习器h1,h2,⋯,hTh_1,h_2,\cdots,h_{\mathcal T}h1​,h2​,⋯,hT​之间的线性组合：
  其中Sign\text{Sign}Sign表示基于二分类任务的指示函数;αt(t=1,2,⋯,T)\alpha_t(t=1,2,\cdots,\mathcal T)αt​(t=1,2,⋯,T)表示各基学习器对应的权重参数。
  HT(x)=Sign(∑t=1Tαt⋅ht)\mathcal H_{\mathcal T}(x) = \text{Sign}\left(\sum_{t=1}^{\mathcal T} \alpha_t \cdot h_t\right)HT​(x)=Sign(t=1∑T​αt​⋅ht​)
• Gradient Boosting\text{Gradient Boosting}Gradient Boosting：其描述的是当前时刻预测模型Ht(x)\mathcal H_t(x)Ht​(x)与上一时刻预测模型Ht−1(x)\mathcal H_{t-1}(x)Ht−1​(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​
  将上式展开，关于迭代结束后的预测模型HT(x)\mathcal H_{\mathcal T}(x)HT​(x)表示为如下形式：
  HT(x)=Hinit+η⋅h1⏟H1(x)+η⋅h2⏟H2(x)+⋯+η⋅hT\mathcal H_{\mathcal T}(x) = \underbrace{\underbrace{\mathcal H_{init} + \eta \cdot h_1}_{\mathcal H_1(x)} + \eta \cdot h_2}_{\mathcal H_2(x)} + \cdots + \eta \cdot h_{\mathcal T}HT​(x)=H2​(x)H1​(x)Hinit​+η⋅h1​​​+η⋅h2​​​+⋯+η⋅hT​

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

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

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

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

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

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

CART\text{CART}CART回归树

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

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

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

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

• 场景构建

  • 给定训练数据集D={(x(i),y(i))}i=1Nx(i)∈Rp\mathcal D = \{(x^{(i)},y^{(i)})\}_{i=1}^N \quad x^{(i)} \in \mathbb R^pD={(x(i),y(i))}i=1N​x(i)∈Rp
  • 关于回归树f(x)f(x)f(x)的构建：将X\mathcal XX的特征空间划分为M\mathcal MM份，每一份都对应回归树的叶子结点：
    需要注意的是,R1,⋯,RM\mathcal R_1,\cdots,\mathcal R_{\mathcal M}R1​,⋯,RM​的并集是样本X\mathcal XX的特征空间，但它和X\mathcal XX的特征维度ppp不是一个概念。
    R1,R2,⋯,RM\mathcal R_1,\mathcal R_2,\cdots,\mathcal R_{\mathcal M}R1​,R2​,⋯,RM​
    并且每个特征子空间(叶子结点)Rm(m=1,2,⋯,M)\mathcal R_m(m=1,2,\cdots,\mathcal M)Rm​(m=1,2,⋯,M)均对应一个固定的输出结果Cm(m=1,2,⋯,M)\mathcal C_{m}(m=1,2,\cdots,\mathcal M)Cm​(m=1,2,⋯,M)。因而关于回归树的模型f(x(i))f(x^{(i)})f(x(i))可表示为：
    若样本被划分进同一个特征空间Rm\mathcal R_mRm​,它们的预测结果是相同的。均为Cm\mathcal C_mCm​.
    f(x(i))=∑m=1MCm⋅I(x(i)∈Rm)f(x^{(i)}) = \sum_{m=1}^{\mathcal M} \mathcal C_m \cdot \mathbb I(x^{(i)} \in \mathcal R_m)f(x(i))=m=1∑M​Cm​⋅I(x(i)∈Rm​)
    其中I\mathbb II表示指示函数(Indicator Function\text{Indicator Function}Indicator Function)：
    I(x(i)∈Rm)={1if x(i)∈Rm0otherwise\mathbb I(x^{(i)} \in \mathcal R_m) = \begin{cases} 1 \quad \text{if } x^{(i)} \in \mathcal R_m \\ 0 \quad \text{otherwise} \end{cases}I(x(i)∈Rm​)={1if x(i)∈Rm​0otherwise​
  • 关于训练过程的损失函数——平方误差表示为：
    需要注意的是，这个L\mathcal LL描述的是每个特征空间Rm(m=1,2,⋯,M)\mathcal R_m(m=1,2,\cdots,\mathcal M)Rm​(m=1,2,⋯,M)中的样本，其预测结果与真实标签的平方误差。
    L=∑x(i)∈Rm[y(i)−f(x(i))]2\mathcal L = \sum_{x^{(i)} \in \mathcal R_m} \left[y^{(i)} - f(x^{(i)})\right]^2L=x(i)∈Rm​∑​[y(i)−f(x(i))]2

• 算法执行过程：

  • 通过遍历样本特征X\mathcal XX的 属性sss：
  • 每一次遍历得到的属性sss，可以基于该属性，将对应的特征空间划分为两个子特征空间：
    R1(j,s),R2(j,s)\mathcal R_1(j,s),\mathcal R_2(j,s)R1​(j,s),R2​(j,s)是基于当前特征空间中，满足/不满足属性条件sss的样本集合。
    jjj并不是什么正儿八经的参数，它仅是样本编号。
    R1(j,s)={x∣x(j)≤s};R2(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}
  • 如何判别被划分的集合R1(j,s),R2(j,s)\mathcal R_1(j,s),\mathcal R_2(j,s)R1​(j,s),R2​(j,s)是优秀的？也就是说，如何判别属性sss是一个优秀的划分点——使用平方误差进行描述：
    如果能使下式达到最小，对应的划分属性sss与集合R1(j,s)\mathcal R_1(j,s)R1​(j,s)与R2(j,s)\mathcal R_2(j,s)R2​(j,s)就是该次划分下的最优子集合。
    min⁡j,s[min⁡C1∑x(i)∈R1(j,s)(y(i)−C1)2+min⁡C2∑x(i)∈R2(j,s)(y(i)−C2)2]\mathop{\min}\limits_{j,s} \left[\mathop{\min}\limits_{\mathcal C_1} \sum_{x^{(i)} \in \mathcal R_1(j,s)} (y^{(i)} - \mathcal C_1)^2 + \mathop{\min}\limits_{\mathcal C_2} \sum_{x^{(i)} \in \mathcal R_2(j,s)} (y^{(i)} - \mathcal C_2)^2\right]j,smin​​C1​min​x(i)∈R1​(j,s)∑​(y(i)−C1​)2+C2​min​x(i)∈R2​(j,s)∑​(y(i)−C2​)2​
  • 各子集合对应的C\mathcal CC的最优值C^m(m=1,2,⋯,M)\hat {\mathcal C}_m(m=1,2,\cdots,\mathcal M)C^m​(m=1,2,⋯,M)可表示为：
    C^m=AVG(y(i)∣x(i)∈Rm)\hat {\mathcal C}_m = \text{AVG}(y^{(i)} \mid x^{(i)} \in \mathcal R_m)C^m​=AVG(y(i)∣x(i)∈Rm​)
  • 重复执行上述2,32,32,3步骤，直到满足停止条件。此时得到了M\mathcal MM个满足条件的特征空间，生成决策树：
    下面则以某样本x(i)∈Rmx^{(i)} \in \mathcal R_mx(i)∈Rm​为例，描述它的预测结果。
    f(x(i))=∑m=1MC^m⋅I(x(i)∈Rm)=C1^⋅I(x(i)∈R1)⏟=0+⋯+C^m⋅I(x(i)∈Rm)⏟=1+⋯+C^M⋅I(x(i)∈RM)⏟=0=C^m⋅1=C^m\begin{aligned} f(x^{(i)}) & = \sum_{m=1}^{\mathcal M} \hat {\mathcal C}_m \cdot \mathbb I(x^{(i)} \in \mathcal R_m) \\ & = \hat {\mathcal C_1} \cdot \underbrace{\mathbb I(x^{(i)} \in \mathcal R_1)}_{=0} + \cdots + \hat {\mathcal C}_m \cdot \underbrace{\mathbb I(x^{(i)} \in \mathcal R_m)}_{=1} + \cdots + \hat {\mathcal C}_{\mathcal M} \cdot \underbrace{\mathbb I (x^{(i)} \in \mathcal R_{\mathcal M})}_{=0} \\ & = \hat {\mathcal C}_m \cdot 1 \\ & = \hat {\mathcal C}_m \end{aligned}f(x(i))​=m=1∑M​C^m​⋅I(x(i)∈Rm​)=C1​^​⋅=0I(x(i)∈R1​)​​+⋯+C^m​⋅=1I(x(i)∈Rm​)​​+⋯+C^M​⋅=0I(x(i)∈RM​)​​=C^m​⋅1=C^m​​

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

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

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

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

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

• 对预测模型进行初始化：Hinit(x)=0\mathcal H_{init}(x) = 0Hinit​(x)=0
• 执行T\mathcal TT次迭代：t=1,2,⋯,Tt = 1,2,\cdots,\mathcal Tt=1,2,⋯,T：
  • 计算残差(Residual\text{Residual}Residual)：rt(i)=y(i)−Ht−1(x(i))i=1,2,⋯,Nr_t^{(i)} = y^{(i)} - \mathcal H_{t-1}(x^{(i)}) \quad i=1,2,\cdots,Nrt(i)​=y(i)−Ht−1​(x(i))i=1,2,⋯,N；
  • 通过样本特征x(i)(i=1,2,⋯,N)x^{(i)}(i=1,2,\cdots,N)x(i)(i=1,2,⋯,N)以及对应的残差结果rt(i)r_t^{(i)}rt(i)​构成新数据集Dt={(x(i),rt(i))}i=1N\mathcal D_{t}=\{(x^{(i)},r_t^{(i)})\}_{i=1}^NDt​={(x(i),rt(i)​)}i=1N​，并基于Dt\mathcal D_{t}Dt​，使用学习算法K\mathcal KK，学习出一个新的基学习器(回归树) ht(x)h_t(x)ht​(x)：
    ht(x)=K(Dt)h_t(x) = \mathcal K(\mathcal D_{t})ht​(x)=K(Dt​)
  • 使用基学习器ht(x)h_t(x)ht​(x)更新预测模型(回归树)Ht−1(x)\mathcal H_{t-1}(x)Ht−1​(x)：
    Ht(x)=Ht−1(x)+η⋅ht(x)\mathcal H_t(x) = \mathcal H_{t-1}(x) + \eta \cdot h_t(x)Ht​(x)=Ht−1​(x)+η⋅ht​(x)
• T\mathcal TT次迭代步骤执行结束，最终得到预测模型HT(x)\mathcal H_{\mathcal T}(x)HT​(x)
  HT(x)=Hinit(x)+η⋅h1(x)+⋯+η⋅hT(x)\mathcal H_{\mathcal T}(x) = \mathcal H_{init}(x) + \eta \cdot h_1(x) + \cdots + \eta \cdot h_{\mathcal T}(x)HT​(x)=Hinit​(x)+η⋅h1​(x)+⋯+η⋅hT​(x)

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

梯度提升树算法过程

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

• 将L\mathcal LL使用平方误差展开。
• 系数12\begin{aligned}\frac{1}{2}\end{aligned}21​​本身是不存在的，这里仅是将导数过程中的系数222消去，增加一个系数只会影响梯度大小，并不改变梯度方向。
  −∂L(i)∂Ht−1(x(i))≈−∂[12(y(i)−Ht−1(x(i)))2]∂Ht−1(x(i))=−12⋅2⋅[y(i)−Ht−1(x(i))]⋅[0−1]=y(i)−Ht−1(x(i))=rt(i)\begin{aligned} - \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{aligned}−∂Ht−1​(x(i))∂L(i)​​≈−∂Ht−1​(x(i))∂[21​(y(i)−Ht−1​(x(i)))2]​=−21​⋅2⋅[y(i)−Ht−1​(x(i))]⋅[0−1]=y(i)−Ht−1​(x(i))=rt(i)​​

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

• 初始化预测模型Hinit(x)\mathcal H_{init}(x)Hinit​(x)

  • 样本之间独立同分布，因而损失函数表示为NNN个样本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)偏差的总和。
  • 初始状态下，每一个样本各自被划分为一个特征子空间;而ccc表示各样本的标签自身。L\mathcal LL表示平方误差。
    Hinit(x)=arg⁡min⁡c∑i=1NL(y(i),c)\mathcal H_{init}(x) = \mathop{\arg\min}\limits_{c}\sum_{i=1}^N \mathcal L(y^{(i)},c)Hinit​(x)=cargmin​i=1∑N​L(y(i),c)

• 执行T\mathcal TT次迭代：t=1,2,⋯,Tt=1,2,\cdots,\mathcal Tt=1,2,⋯,T：
  这里以t=1t=1t=1为例。

  • 对于每个样本(x(i),y(i))(i=1,2,⋯,N)(x^{(i)},y^{(i)})(i=1,2,\cdots,N)(x(i),y(i))(i=1,2,⋯,N)，计算当前迭代过程的残差：
    r1(i)⇐−[∂L(y(i),Hinit(x(i)))∂Hinit(x(i))]r_1^{(i)} \Leftarrow - \left[\frac{\partial \mathcal L(y^{(i)},\mathcal H_{init}(x^{(i)}))}{\partial \mathcal H_{init}(x^{(i)})}\right]r1(i)​⇐−[∂Hinit​(x(i))∂L(y(i),Hinit​(x(i)))​]
  • 将产生的新样本集合D1={(x(i),r1(i))}i=1N\mathcal D_1 = \{(x^{(i)},r_1^{(i)})\}_{i=1}^ND1​={(x(i),r1(i)​)}i=1N​作为下一棵树的训练数据，并得到一棵新的回归树(基学习器)h1(x)h_1(x)h1​(x)。并将回归树h1(x)h_{1}(x)h1​(x)划分的特征空间集合记作R1={R11,R21,⋯,RM1}\mathcal R^1 = \{\mathcal R_1^1,\mathcal R_2^1,\cdots,\mathcal R_{\mathcal M}^1\}R1={R11​,R21​,⋯,RM1​}
    这里的M\mathcal MM指回归树h1(x)h_1(x)h1​(x)划分的特征空间(叶子结点)的个数。
  • 对每一个特征子空间Rm1(m=1,2,⋯,M)\mathcal R_m^1(m=1,2,\cdots,\mathcal M)Rm1​(m=1,2,⋯,M)计算最优拟合结果：
    个人解惑：关于上一次迭代拟合的剩余部分就是我们的拟合目标。因而L\mathcal LL内部并不是Hinit(x(i))+η⋅Cm\mathcal H_{init}(x^{(i)}) + \eta \cdot \mathcal C_mHinit​(x(i))+η⋅Cm​.
    C^m1=arg⁡min⁡Cm∑x(i)∈Rm1L[y(i),Hinit(x(i))+Cm]m=1,2,⋯,M\hat {\mathcal C}_m^1 = \mathop{\arg\min}\limits_{\mathcal C_m} \sum_{x^{(i)} \in \mathcal R_{m}^1} \mathcal L \left[y^{(i)},\mathcal H_{init}(x^{(i)}) + \mathcal C_m\right] \quad m=1,2,\cdots,\mathcal MC^m1​=Cm​argmin​x(i)∈Rm1​∑​L[y(i),Hinit​(x(i))+Cm​]m=1,2,⋯,M
  • 至此，得到了M\mathcal MM个h1(x)h_{1}(x)h1​(x)对于各特征子空间的最优均值结果：C^11,C^21,⋯,C^M1\hat {\mathcal C}_1^1,\hat {\mathcal C}_2^1,\cdots,\hat {\mathcal C}_{\mathcal M}^1C^11​,C^21​,⋯,C^M1​，使用该结果去优化当前迭代步骤下的预测模型H1(x)\mathcal H_1(x)H1​(x)：
    H1(x)=Hinit(x)+η⋅h1(x)=Hinit(x)+η⋅[C^11⋅I(x∈R11)+⋯+C^M1⋅I(x∈RM1)]=Hinit(x)+η⋅∑m=1MC^m1⋅I(x∈Rm1)\begin{aligned} \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{aligned}H1​(x)​=Hinit​(x)+η⋅h1​(x)=Hinit​(x)+η⋅[C^11​⋅I(x∈R11​)+⋯+C^M1​⋅I(x∈RM1​)]=Hinit​(x)+η⋅m=1∑M​C^m1​⋅I(x∈Rm1​)​

重复执行上述步骤T\mathcal TT次，最终可得到最终预测模型HT(x)\mathcal H_{\mathcal T}(x)HT​(x)：
HT(x)=Hinit(x)+η⋅[h1(x)+h2(x)+⋯+hT(x)]=Hinit(x)+η⋅∑t=1T∑m=1MC^mt⋅I(x∈Rmt)\begin{aligned} \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{aligned}HT​(x)​=Hinit​(x)+η⋅[h1​(x)+h2​(x)+⋯+hT​(x)]=Hinit​(x)+η⋅t=1∑T​m=1∑M​C^mt​⋅I(x∈Rmt​)​
下一节将介绍集成学习方法——Stacking\text{Stacking}Stacking。

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