模型集成-三个“臭皮匠”顶一个“诸葛亮”

未经博主允许,请勿随意转载。部分图片来源均已标明出处。

注:由于在编写本文时参考了不同的资料,图片中的符号表示可能会和文中的符号表示有差异,但不影响理解。文章后部分从Adaboost到GBDT的推理涉及较多的数学知识,若理解有困难可参考文末给出的链接(也可理解整体流程即可,不必拘泥于细节)。

模型集成理论基础

集成学习通过将多个学习器进行组合,常可获得比单一学习器显著优越的泛化性能。

在一般的经验中,如果把好坏不等的东西掺杂在一起,通常结果会比最坏的要好一些,比最好的要差一些。集成学习把多个学习器结合起来,如何能获得比最好的单一学习器更好的性能呢?

要获得好的集成,个体学习器应“好而不同”,即单个学习器要具有足够好的性能,且各个学习器之间具有较大的差异性。

那么,对于任意一个样本,假设各个基学习器相互独立的情况下,且学习器的错误率为$\epsilon$,考虑二分类问题$y \in \{-1, 1\}$,假设集成通过简单投票法结合$T$个基分类器,若有超过半数的基分类器正确,则集成分类正确:

由$Hoeffding$不等式的,集成的错误率为:

由上式可以看出,随着基学习器个数的增加,集成的错误率将逐渐减小,直至为0。

在计算过程中,我们假设各个基学习器之间是相互独立的,但实际上要想获得较高的准确度就需要牺牲基学习器之间的独立性。如何生成并结合“好而不同”的个体学习器便是集成学习方法研究的重心。可以将集成学习方法分为以下两大类:

  • 基学习器之间存在较强的依赖关系,基学习器是串行生成的,例如Boosting算法。
  • 基学习器之间不存在较强的依赖关系,基学习器是并行生成的,例如Bagging算法。

Blending-结合策略

假设我们已经得到了包含$T$个基学习器${h_1,h_2,h_3,…,h_T}$的集合,其中$h_i$在示例$x$上的输出为$h_i(x)$。现在需要对这些基学习器的输出进行结合得到最终的输出,Blending所研究的就是如何将这些基学习器的输出进行结合的方法。

简单平均法(Uniform Blending)

直接将所有基学习器的输出进行求和平均:

在使用简单平均法时,一般要求每个候选的基学习器之间存在一些差别,这样通过平均可以得到比单一基学习器更好的模型。

通过平均可以得到比单一的基学习器更稳定、更好的结果,在台大-林轩田的机器学习技法课程中给出了简单的证明,过程如下(其中$g_t$为单一的基学习器,$G$为求和平均后得到的集成的学习器,$f(x)$为样本的真实输出):

img

在上图的推导结果中,$\mathrm {avg}(g_t(x)-f(x))^2=\mathrm {avg}((g_t-G)^2)+(G-f)^2$,等号左边为单一的基学习器的误差,右边第二项为平均后的集成学习器的误差,等式右边第一项大于等于0,因而$\mathrm {avg}(g_t(x)-f(x))^2\ge (G-f)^2$。即集成后的学习器的表现要等于或优于任何一个单一的基学习器。

加权平均法(Linear Blending)

在简单平均法中,给每个基学习器赋予了相同的权重1。更进一步,给不同的基学习器赋予不同的权重便可以得到加权平均法。

加权平均法可以被视为集成学习研究的基本出发点,对给定的基学习器,不同的集成学习方法可视为通过不同的方式来确定加权平均法中的基学习器权重,例如可以将简单平均法视作所有权重为1的加权平均法。

加权平均法的权重一般从训练数据中学习而得,例如在台大-林轩田的机器学习技法中指出,可以在解决回归问题时,可以采用最小化均方误差的方法来求得合适的权重。如下图左侧所示,为当基学习器处理的是回归问题时的学习权重的方法:

img

左侧的学习权重的方法和右侧使用了$\phi(x)$转换的线性回归的学习方法很类似,区别在于左侧对权重有约束$\alpha_i\ge0$,而右侧对$w_i$无约束。但在《机器学习技法》这门课中指出,对于$\alpha_i$的约束是可以去除的。

可以将Linear Blending看作two-level的学习过程,首先得到基学习器,再在此基础上学习得到权重。

在Linear Blending中,对基学习器采用的是线性加权的方式,实际上,最终得到的集成模型可以是基学习器的任何形式的组合,可以是线性的,也可以是非线性的。甚至于可以直接使用一个独立的模型来学习基学习器之间的组合方式,这也就是后面将要讲的Stacking方法。

现实任务中的数据通常不充分或存在噪声,这将使得学出的权重不完全可靠。一般而言,在个体学习器的性能相差较大时宜使用加权平均法,个体学习器的性能相近时使用简单平均法

投票法(voting)

将上述Blending方法推广到分类问题中就可以得到类似于投票法的方法。对于每一个样本,学习器将从类别集合中预测出一个标记。将$h_i$在样本$x$上的预测输出表示为一个$N$维向量$(h_i^1(x), h_i^2(x),…,h_i^N(x))$,其中$h_i^j(x)$表示$h_i$在类别$c_j$上的输出。

  • 绝对投票法

    所谓绝对投票法,即若某标记票数过半,则预测为该标记,否则拒绝预测。

  • 相对多数投票法

    即预测为得票最多的标记,若同时有多个标记获得最高票,则从中随机选取一个。

  • 加权投票法

    基学习器的权重要求与加权平均法相同。

在现实任务中,不同类型的个体学习器可能产生不同类型的预测值:

  • 类标记:个体学习器将样本预测为类别$c_j$则取值为1,否则取值为0,这种预测成为“硬投票”。
  • 类概率:个体学习器将样本预测为属于各个类别的概率值,这种预测成为“软投票”。

这里要注意的是,不同类型的预测值之间不能混合使用。一般情况下,分类器的类别概率预测并不是非常准确,但有趣的是,将类别概率转换为类别标记后进行投票往往会获得比使用类标记进行投票更好的性能。

Stacking-学习法

当训练数据很多时,一种更为强大的结合策略是“学习法”,即使用另一个学习器来对多个模型进行结合。Stacking方法就是一种学习法。将个体学习器称为初级学习器,用于结合的学习器称为次级学习器或元学习器(meta-learner)。

Stacking先从初始数据集训练出初级学习器,然后使用初级学习器生成一个新的数据集,使用这个新的数据集来训练次级学习器。在这个新的数据集中,初级学习器的输出被当作样例的输入特征,初始样本所对应的标记仍被当作样例标记。

首先给出一张比较形象的示意图:

stacking

该图来源

在训练阶段,次级训练集是使用初级学习器产生的,那么这里就涉及到如何产生次级训练集的问题。如果直接使用整个初级训练集在初级学习器上产生次级训练集,由于初级训练集中存在被初级学习器学习过的样本,将会增大过拟合的风险。因而在stacking中,我们常使用交叉验证或者留一法来训练初级学习器,接着使用初级学习器未见过的样本来产生次级训练集。

以交叉验证为例,假设有$T$个初级学习算法,对于其中的每一个初级学习算法,使用$K$折交叉验证,我们可以得到$K$个不同的模型,正如上图所示。对于model1进行了5折交叉验证,便可以得到5个模型;接着,使用这5个模型在各自折的验证集上进行预测,得到5折验证集的预测结果,将这5折验证集的初级学习器的预测结果拼在一起,便可以得到一个学习算法对应的次级训练集。

上述步骤仅是$T$个初级学习算法中的一个,对于剩余的初级学习算法重复执行上述步骤,那么对于初级训练集中的每一个样本$x_i$,都可以得到$T$个预测结果,将这$T$个预测结果进行结合,并赋予$x_i$对应的类标$y_i$,就可以得到次级训练集中的一个样本。对初级训练集中的每一个样本执行同样的流程,便可以得到完整的次级训练集。

得到次级训练集后,便可以训练得出次级学习器。在执行预测时,首先将样本经过所有的初级学习器,得到初级输出特征图后,将初级输出特征图作为次级学习器的输入,便可以得到最终的输出。

Bagging-Bootstraping Aggregation

在blending中,假设条件是我们手头已经有了不同的基学习器,其研究的是如何对这些已有的基学习器进行融合。那么,我们该如何得到这些不同的基学习器。

有如下几种方法:

  • 选择不同的模型;
  • 设置不同的参数,如迭代次数、学习率等;
  • 使用本身就具有随机性的算法,如感知机学习算法;
  • 选择不同的数据样本。

那么,我们该如何从现有的数据集中构建出不同的数据集合?这里就要用到bootstrap方法。

Bootstrap-自助法划分数据集

Bagging方法基于自助采样法生成数据集,那么什么是自助采样法?

自助采样法的内容如下:给定包含$m$个样本的数据集$D$,我们对它进行采样产生数据集$D’$。每次随机从$D$中挑选一个样本,将其拷贝放入$D’$中,然后再将该样本放回原始数据集$D$中,使得该样本在下次采样时仍可能被采到;将这一过程重复$m$次,便可以得到包含$m$个样本的数据集$D’$,这就是自助采样的结果。

在采样过程中,总会有一部分数据集无法被采到,那么大概会有多少样本未被采到?

对于数据集中的任意一个样本,在一次采样中,其未被采到的概率是:

那么,重复$m$次采样都未被采到的概率是:

当$m$趋于无穷大时,上式趋于$0.368$。

通过自助采样,初始数据集中会有$36.8\%$的样本未出现在采样数据集中。我们可以将未出现的样本作为测试集,这种测试方法称为“包外估计”(out-of-bag estimate)。

通过反复使用bootstrap,我们可以得到多个不同的数据集合。通过使用这些数据集合训练得到不同的基学习器,再对这些基学习器进行集成的方法就是Bagging。

Bagging集成法

首先使用自助采样法获得$T$个数据集,然后基于每个采样集训练出一个基学习器,再将这些基学习器进行结合。在对基学习器进行结合时,Bagging通常对分类任务使用简单投票法,对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形,则最简单的做法是随机选择一个,也可进一步考察学习器投票的置信度来确定最终胜者。

从偏差-方差的角度看,Bagging主要关注降低方差,因此它在不剪枝决策树、神经网络等易受样本干扰的学习器上效用更为明显。对于这些易受样本干扰的学习器,使用不同的数据集合,我们很容易得到不同的基学习器,而这正是我们所需要的。

随机森林

随机森林(Random Forest,简称RF)是Bagging的一个扩展变体。随机森林在以决策树为基学习器构建Bagging的基础上,进一步在决策树的训练过程中引入随机属性选择。

具体来说,传统决策树在选择划分属性时是在当前节点的属性集合中随机选择一个属性;而在随机森林中,对于基决策树的每一个结点,先从该结点的属性集合中随机选择一个包含$k$个属性的子集,然后再从这个子集中选择一个最优属性用于划分。这里的$k$控制了随机性的引入程度:$k=d$时,基决策树的构建与传统决策树相同,$k=1$时,则是随机选择一个属性用于划分;一般情况下,推荐$k=log_2d$。

与bagging中基学习器的多样性仅通过样本扰动得到不同,随机森林的样本多样性来自于两个方面:

  • 样本扰动
  • 属性扰动

这样一来,最终集成的泛化性能可以通过个体学习器之间差异度的增加而进一步提升

随机森林的起始性能往往较差,特别是在包含一个基学习器时(引入属性扰动导致)。而当个体学习器的数目增加时(需要非常多的基学习器),随机森林往往会收敛到更低的泛化误差。

Boosting-提升

何为boosting提升算法,这是一种可将弱学习器提升为强学习器的方法,工作机制为:

先从初始训练集训练出一个基学习器,再根据基学习器的表现对训练样本的分布进行调整,使得先前基学习器做错的训练样本在后续受到更多关注,然后基于调整后的样本分布来训练下一个基学习器;如此重复进行,直至基学习器数目达到事先指定的值T,最终将这T个基学习器进行加权求和。

这里,我们主要介绍AdaBoost方法。

AdaBoost方法

从bootstrap说起

从上面的介绍中看到,提升方法的重点之一就是在每一次迭代中,对训练样本的分布进行调整。比较常用的方法是给不同的样本赋予不同的权重,那么,我们该如何得到权重的调整方式呢?实际上,可以从Bagging的bootstrap方法中逐步推导出权重的调整方式。

首先,让我们转换一种理解bootstrap的方式。通过上面的学习,可以知道bootstrap的核心就是对数据集进行不放回采样来得到不同的数据集。现在,假设经过不放回采样,从包含有四个样本的数据集$\mathcal D$中得到新的数据集$\mathcal {\hat D}$:

image-20200326223758816

在采样得到的$\mathcal {\hat D}$上的训练误差可以表示为:

image-20200326223923548

从另一个角度看,上述计算误差的方式可以等价为在原始数据集$\mathcal D$上的加权误差,其中对于不同的样本,其权重为该样本被采样的次数:

image-20200326225429255

那么,对于同一个原始数据集$\mathcal D$,在使用同一个基础学习算法的情况下,通过设计不同的样本权重$\mathcal u$便可以得到不同的基学习器。在上面的集成方法中,我们说过,如果各个基学习器之间的差异越大,则最终进行集成的效果就越好。此时,问题就转换为,如何选取样本权重$\mathcal u$来使得不同的基学习器之间的差异尽可能的大。

以两个不同的权重学习得到的两个不同的基学习器为例:

image-20200326230114552

一种度量$g_t$和$g_{t+1}$的差异性的方法是,如果在$u_t$条件下学习到的$g_t$在$u_{t+1}$条件下的误差特别大,那么我们就可以认为$g_t$和$g_{t+1}$之间的差异非常大。如何使得$g_t$在$u_{t+1}$条件下的误差特别大呢?

想法是,如果通过构建$u_{t+1}$使得$g_t$的表现就像随机猜测一样,即分类错误的样本占总的样本的一半,那么就可以认为$g_t$在$u_{t+1}$条件下的误差特别大,或者说性能特别差。表示为数学形式,如下图所示:

image-20200326230620195

要使得上式的结果为$\frac{1}{2}$,最简单的方法就是通过调整$u_{t+1}$使得错误样本的数据和正确样本的数目相同即可。如下表所示:

image-20200326230931515

一种方法是,给犯错的$u_{t}$和未犯错的$u_{t}$分别乘以某个数使得两者的大小相同,如上表中的第二行;另一种方法是,按照错误比例,给犯错的$u_{t}$和未犯错的$u_t$进行缩放,如上表中的第一行。更普遍的表示方式如下所示:

image-20200326231327147

即,给犯错的$u_{t}$乘以$(1-\epsilon)$,即:

给犯错的$u_t$乘以$\epsilon$,即:

通过上述的权重调整方式,就可以使得$g_t$和$g_{t+1}$的差距尽可能的大。当然,这只是一个很简单的调整比例计算方式,在下文中介绍AdaBoost时,会介绍另一种调整比例计算方式。但两者的所依据的本质都是一样的,即通过调整权重使得基学习器之间的差异尽可能的大。

AdaBoost

在上文中已经说明了增大两个基学习器的差异的方式,即给分类正确的样本权重和分类错误的样本权重进行放缩。这里,我们仍旧采取和上文相同的方式,不过要对放缩系数进行重新定义:

image-20200327154533340

如上图所示,上述的放缩方法等价于之前的optimal re-weighting操作。当误差$\epsilon_t\le \frac{1}{2}$,也就是当当前的基学习器的性能优于随机猜测时,会放大分类错误的样本的权重,而缩小分类正确的样本的权重。

基于上述的样本权重调整策略,定义如下的训练方法:

image-20200327154934487

在上述算法中,有两处需要考虑的问题:

  • 如何初始化样本权重$u^{(1)}$;
  • 如何对最终得到的多个基学习器进行组合?

针对第一个问题,为了使初始的基学习器在原始的训练集上表现最好,令$u^{(1)}=\frac{1}{N}$。

针对第二个问题,首先需要明确的是,我们不能直接使用求和平均的方式,其原因在于权重调整策略的使用使得基学习器$g_2$在$g_1$上的表现非常差劲。既然无法使用简单的求和平均的方式,那我们就可以尝试使用线性加权求和的方式。

AdaBoost方法就给出了在学习基学习器的同时,计算在最终组合时基学习器所对应的权重的方法。下面,给出AdaBoost的整体算法流程:

image-20200327155542296

AdaBoost中计算$\alpha_t$所遵循的原理如下:

如果一个基学习器$g_t$在其对应的数据集上的误差$\epsilon_t$越大,我们就认为该基学习器的性能越差,其最终的权重$\alpha_t$就应该越小。为了达到这一目的,在AdaBoost中令$\alpha_t=\ln(\diamond t)$:

  • 当误差$\epsilon=\frac{1}{2}$时,$\alpha_t=0$,对应的基学习器的权重为0;
  • 当误差$\epsilon=0$时,$\alpha_t=\infin$,对应的基学习器的影响远超于其他基学习器。

在此基础上,给出AdaBoost的完整算法流程:

image-20200327160602880

对于AdaBoost来说,只要其基学习器的性能稍微优于随机选择,即误差$\alpha_t\le \frac{1}{2}$,那么最终得到的集成后的学习器的性能就会优于任何一个基学习器。

GBDT(梯度提升决策树)

在上面的内容中,简要介绍了随机森林,可以将随机森林简单地看作Bagging和决策树的结合。那么,既然已经了解了AdaBoost提升方法,是否也存在类似的将AdaBoost和决策树进行结合的算法?这就是接下来要讲的梯度提升决策树(GBDT, gredient boosted decision tree)算法。

AdaBoost DTree

通过AdaBoost的学习,我们了解到AdaBoost通过调整样本的权重$u^{(t)}$来学习到一系列的具有较大差异的基学习器,最后使用线性加权操作对这些基学习器进行组合。这样一来,就对基学习器提出了要求,即基学习器可以接收样本的权重进行学习,例如感知机、SVM等可以通过修改学习过程中与样本权重有关的部分来达到利用样本权重的目的。

但对于决策树,例如CART算法来说,其学习过程并未引入$u^{(t)}$。那么,该如何在决策树中引入样本权重$u^{(t)}$来得到不同的基学习器$g_t$同时不改变原始的决策树算法?

为此,可以将决策树当作一个黑盒子,不对其结构和算法本身进行修改,而是对数据进行处理。为此可以对bootstrap的过程进行反向考虑,在原始的bootstrap中,首先进行的是不放回采样操作,接着根据采样的结果得到样本的权重;而现在,我们首先将样本权重$u^{(t)}$看作采样频率,依据采样频率对原始数据集$\mathcal D$进行采样,得到采样后的数据集$\mathcal D’$。$\mathcal D’$中各个样本的出现次数与其权重的比例接近。

image-20200329184244397

得到后,可以将其直接用于决策树的训练,进而无需改变决策树算法的结构。

通过使用采样操作代替$u^{(t)}$,可以将不同的数据集代入决策树中得到不同的基学习器$g_t$。除此之外,还需要确定每一个基学习器在最终组合时的权重$\alpha_t$。

在AdaBoost中,基学习器的权重的计算方式为:

我们知道,对于给定的数据集$\mathcal D$,如果对决策树的生成不加限制,最终得到一棵完全生长的决策树,那么该决策树的误差$\epsilon_t=0$,进而导致$\alpha_t=\infin$,这棵决策树完全主宰了最终的集成结果。

为了避免这种情况的发生,可以采取如下的两种改进方法:

  • 不使用所有的样本,只使用一部分样本(在依据$u^{(t)}$进行采样的基础上进一步采样);
  • 对树的高度进行限制,避免树的完全生长。

因此,AdaBoost-DTree通常可以表示为如下的公式:

如果对决策树的高度施加很强的限制,比如限制高度为1,同时如果模型解决的是二分类问题,那么Adaboost-DTree就变成了Adaboost-DStump。

从优化的视角讨论AdaBoost

在AdaBoost中,其样本权重的更新公式如下:

image-20200329215514014

为了方便,将两种情况合并为一种形式:

image-20200329215608281

依据上式,可以将$u^{(t+1)}$写成$u^{(1)}$的级联形式:

image-20200329215912287

称上式中的$\sum_{t=1}^T\alpha_tg_t(x_n)$为voting score,则有:

image-20200329221031060

所以:

image-20200329221058822

那么,voting score到底有着什么样的含义?

如下图所示,对比SVM中的margin的计算式,voting score可以看作没有经过正则化的距离,即可以看作点到分类边界距离的一种度量。voting score越大则距离越大。

image-20200329221354888

如果给voting score乘以$y_n$,则表示是否分类正确的距离,如果两者的乘积为负数,则说明分类错误;乘积为正数,则说明分类正确。我们的目的是让两者的乘积为正数,且越大越好。

而如果$y_n(voting \ \ score)$越大,则相应的$u^{(T+1)}$就会越小。在AdaBoost中,随着训练的进行,单个样本的权重$u^{(t)}$是逐渐减小的,直到$u^{(T+1)}$达到最小。那么最终,所有样本的权重之和应该也是最小的。最终,AdaBoost的学习目标就转换为,在最后一轮$(T+1)$的学习后,使得所有样本的$u^{(T+1)}$之和尽可能小

image-20200329222031872

这样,我们就将AdaBoost的权重的迭代更新过程转换为使得上式取得最小值的最优化问题。那么,如何才能取得上式的最小值?

一种方法是采用梯度下降的思路,对于梯度下降法来说,其核心是在某点处对损失函数进行泰勒展开:

image-20200329222829785

仿照上式,对损失进行展开,区别在于,这里的方向是函数$g_t$,函数的下标是连续的,而梯度为向量,下标是离散的。除此之外,两者在对于梯度下降算法的应用上没有很大的区别。展开的过程如下:

image-20200329223210931

在上式中,目标是在第$t$轮迭代时,在已有的一系列基学习器权重和基学习器的基础上,通过求解最优化问题,找到使得$\hat E_{ADA}$最小的$g_t$和$\alpha_t$。

在上述推导的结果中,要让$\hat E_{ADA}$最小化,就要让第二项:

image-20200329223715209

越小越好。问题就转换为:找到一个好的$h(x_n)$来最小化(忽略步长):

对于二分类问题,$y_n$和$h(x_n)$均限定取值为-1或+1两种。对上式进行转换:

image-20200329224027607

最终问题转换为最小化上式的推导结果中的第二项:

而最小化上式,正是AdaBoost中每一步在权重为$u^{(t)}$时,求解当前最优模型的算法所做的事。也就是说,AdaBoost的每一步的模型求解算法正好解决的就是梯度下降法中的最优函数方向的求解问题。

即:上述推导过程证明了AdaBoost中的每一步的模型求解过程得到的基学习器$g_t$等价于求得让$\hat E_{ADA}$减小的方向(只不过该方向是函数而已)。

上述过程解决了方向的求解问题,还剩余一个问题,就是步长$\eta$的求解问题。所采取的方法是:确定方向$g_t$之后,将$ \hat E_{ADA}$看作步长$\eta$的函数,即经过如下的思维转换:

image-20200329225034366

进一步对$ \hat E_{ADA}$的表达式进行化简:

image-20200329225255208

通过求导数并令其为0的方式求出$\eta$的值:

即最大的步长即为各基学习器$g_t$的权重。进而得出如下的结论:

AdaBoost中每一步确定基学习器$g_t$和权重$\alpha_t$的过程就等价于求解梯度下降法中最快的下降方向和最大的步长的过程。

至此,我们从求解优化问题的角度解释了AdaBoost的求解过程。

Gradient Boost

通过上文的分析,我们发现可以从梯度下降的角度对AdaBoost进行解释。也就是说,可以将AdaBoost的整个过程概括为求解如下的优化问题:

image-20200403191549155

在进行上述推导的过程中,我们假设要解决的是一个二分类问题。那么,是否可以将其推广到更加一般的情况。将上面的指数损失函数替换为更一般的损失函数,如回归问题中的均方误差损失。替换后如下所示:

image-20200403191830499

上述形式的问题就是接下来将要介绍的梯度提升(Gradient Boost)问题。

借助梯度下降的思想,可以将上述问题中的$h(x_n)$看作下一步前进方向,$\eta$看作前进的步长。损失函数也推广到了更为一般的形式。进而可以被用于求解更为一般的问题。

下面,就来看一下如何使用上述的形式来求解回归的Gradient Boost问题。在回归问题中,我们一般使用的损失函数是平方误差:

image-20200403192247585

同样为了求解上述问题,我们先求解最优方向,再求解最优步长。对上式进行一阶泰勒展开,再代入平方误差的表达式:

image-20200403192502122

要想取得上式的最小值,只需要使得第二项:

最小即可。在上式中,$(s_n-y_n)$是确定的,要想使得上式尽可能的小,只需要让$h(x_n)$与$(s_n-y_n)$的方向相反即可。但如果不对$h(x_n)$的大小进行限制,我们无法通过优化的方式来取得一个确定的值。

实际上,由于步长$\eta$的存在,$h(x_n)$的大小就变得不重要,只需要与$(s_n-y_n)$反向即可。因此,我们可以对$h(x_n)$的大小添加一些限制,最简单的做法就是将$h(x_n)$当作一个惩罚项添加到上述的优化问题中(类似于正则化的做法)。

image-20200403193231126

经过推导,并忽略掉不必要的常数,就将求解最优方向$h(x_n)$的最优化问题转换为:

其中,$(y_n-s_n)$表示第n个样本的真实值与当前已有模型的预测值之差,这里称其为余数(residual)。要想使得上式最小化,只需要使得$h(x_n)$的输出尽可能接近余数即可。而上述优化问题的形式又是平方误差,所以,我们可以使用回归的方法来求解,最终得到$h(x_n)$。

求出最优方向之后,就需要求解最优步长$\eta$,将$h(x_n)$视为已知,那么上述问题就转换为:

image-20200403193906541

将平方误差函数代入,并进一步简化得到:

image-20200403193955563

可以看出,最优步长$\eta$的求解就是一个简单的单变量回归问题。同样,只需要让$\eta g_t(x_n)$的值尽可能的接近余数$(y_n-s_n)$即可。只要对所有样本点求解平方误差下的线性回归即可求解。

经过上述步骤,我们成功使用Gradient Boost求解了回归问题。在求解最优方向$g_t$的时候,采用的是求解关于余数的均方误差的回归问题的方式。我们知道,CART算法中的回归树可以被看作求解使得均方误差最小化的回归问题。那么,很自然的,我们可以使用CART算法来求解关于最优方向$g_t$的回归问题。这样一来,就得到了Gradient Boosted Decision Tree(GBDT):fire:。GBDT的算法流程如下所示:

image-20200403194742332

一般将$s_N$的初始值设置为0。通过CART求解最优方向$g_t$,通过单参数的线性回归求解步长$\eta$,经过$T$轮迭代得到最终的集成模型$G(x)$。

至此,我们就得到了经典的GBDT算法:sparkles:。

参考