集成学习—AdaBoost

1、Boosting方法的基本思想：

在集成学习的“弱分类器集成”领域，除了降低方差来降低整体泛化误差的装袋法Bagging，还有专注于降低整体偏差来降低泛化误差的提升法Boosting。相比起操作简单、大道至简的Bagging算法，Boosting算法在操作和原理上的难度都更大，但由于专注于偏差降低，Boosting算法们在模型效果方面的突出表现制霸整个弱分类器集成的领域。当代知名的Boosting算法当中，Xgboost，LightGBM与Catboost都是机器学习领域最强大的强学习器，Boosting毫无疑问是当代机器学习领域最具统治力的算法领域。

在随机森林算法中，一次性建立多个平行且独立的弱评估器，然后以bagging的方法来综合各弱评估器的预测值，最终输出模型最终的预测值。而boosting集成算法，逐一建立多个弱评估器，并且下一个弱评估器的建立方式依赖于上一个弱评估器的评估结果，最终综合各个弱评估器的结果进行输出，因此boosting算法中的弱评估器不仅不是相互独立的，而是强相关的，同时boosting算法不是依赖弱评估器之间独立性来提高模型的泛化能力，而是通过降低模型的偏差来提高模型的泛化能力。这是Boosting与Bagging的一大差别。

与Bagging算法中统一的回归求平均、分类少数服从多数的输出不同，Boosting算法在结果输出方面表现得十分多样。早期的Boosting算法的输出一般是最后一个弱评估器的输出，当代Boosting算法的输出都会考虑整个集成模型中全部的弱评估器。一般来说，每个Boosting算法会其以独特的规则自定义集成输出的具体形式，但对大部分算法而言，集成算法的输出结果往往是关于弱评估器的某种结果的加权平均，其中权重的求解是boosting领域中非常关键的步骤。

1.1、Boosting算法的基本元素与基本流程：

基于上面所明确的“降低偏差”、“逐一建树”、以及“以独特规则输出结果”的三大特色，我们可以确立任意boosting算法的三大基本元素以及boosting算法自适应建模的基本流程：

损失函数𝐿(𝑥,𝑦)：用以衡量模型预测结果与真实结果的差异

弱评估器𝑓(𝑥)：（一般为）决策树，不同的boosting算法使用不同的建树过程

综合集成结果𝐻(𝑥)：即集成算法具体如何输出集成结果

这三大元素将会贯穿所有我们即将学习的boosting算法，我们会发现几乎所有boosting算法的原理都围绕这三大元素构建。在此三大要素基础上，所有boosting算法都遵循以下流程进行建模：

1.2、sklearn中的boosting算法：

在sklearn当中，我们可以接触到数个Boosting集成算法，包括Boosting入门算法AdaBoost，性能最稳定、奠定了整个Boosting效果基础的梯度提升树GBDT（Gradient Boosting Decision Tree），以及近几年才逐渐被验证有效的直方提升树（Hist Gradient Boosting Tree）。

在过去5年之间，除了sklearn，研究者们还创造了大量基于GBDT进行改造的提升类算法，这些算法大多需要从第三方库进行调用，例如极限提升树XGBoost（Extreme Gradient Boosting Tree），轻量梯度提升树LightGBM（Light Gradiant Boosting Machine），以及离散提升树CatBoost（Categorial Boosting Tree）。

2、AdaBoost：

AdaBoost（Adaptive Boosting，自适应提升法）是当代boosting领域的开山鼻祖，它虽然不是首个实践boosting思想算法，却是首个成功将boosting思想发扬光大的算法。它的主要贡献在于实现了两个变化：

1、首次实现根据之前弱评估器的结果自适应地影响后续建模过程

2、在Boosting算法中，首次实现考虑全部弱评估器结果的输出方式

作为开山算法，AdaBoost的构筑过程非常简单：首先，在全样本上建立一棵决策树，根据该决策树预测的结果和损失函数值，增加被预测错误的样本在数据集中的样本权重，并让加权后的数据集被用于训练下一棵决策树。这个过程相当于有意地加重“难以被分类正确的样本”的权重，同时降低“容易被分类正确的样本”的权重，而将后续要建立的弱评估器的注意力引导到难以被分类正确的样本上。

在该过程中，上一棵决策树的的结果通过影响样本权重、即影响数据分布来影响下一棵决策树的建立，整个过程是自适应的。当全部弱评估器都被建立后，集成算法的输出𝐻(𝑥)等于所有弱评估器输出值的加权平均，加权所用的权重也是在建树过程中被自适应地计算出来的。

需要注意的是，虽然最初的原理较为简单，但近年来AdaBoost在已经发展出多个升级的版本（比如，在建立每棵树之前，允许随机抽样特征，这使得Boosting中的决策树行为更加接近Bagging中的决策树），而sklearn中使用了这些升级后的版本进行实现。

在sklearn中，AdaBoost既可以实现分类也可以实现回归，我们使用如下两个类来调用它们：

class sklearn.ensemble.AdaBoostClassifier(base_estimator=None, *, n_estimators=50, learning_rate=1.0, algorithm='SAMME.R', random_state=None)

class sklearn.ensemble.AdaBoostRegressor(base_estimator=None, *, n_estimators=50, learning_rate=1.0, loss='linear', random_state=None)

不难发现，AdaBoost的参数非常非常少，在调用AdaBoost时我们甚至无需理解AdaBoost的具体求解过程。同时，ADB分类器与ADB回归器的参数也高度一致。在课程当中，我们将重点Boosting算法独有的参数，以及ADB分类与ADB回归中表现不一致的参数。

2.1、AdaBoost中的基本参数和损失函数：

参数base_estimator，属性base_estimator_与estimators_

base_estimator是规定AdaBoost中使用弱评估器的参数。与对弱评估器有严格要求的Bagging算法不同，boosting算法通过降低偏差来降低整体泛化误差，因此可以使用任意弱评估器，且这些弱评估器往往被假设成非常弱小的评估器。当然了，默认的弱评估器还是决策树。在sklearn中，ADB分类器的默认弱评估器是最大深度为1的“树桩”，ADB回归器的默认评估器是最大深度为3的“树苗”，弱评估器本身基本不具备判断能力。而回归器中树深更深是因为boosting算法中回归任务往往更加复杂。在传统ADB理论当中，一般认为AdaBoost中的弱分类器为最大深度为1的树桩，但现在我们也可以自定义某种弱评估器来进行输入。

当模型建好之后，我们可以使用属性base_estimator_来查看当前弱评估器，同时也可以使用estimators_来查看当前集成模型中所有弱评估器的情况。

参数learning_rate

在Boosting集成方法中，集成算法的输出𝐻(𝑥)往往都是多个弱评估器的输出结果的加权平均结果。但𝐻(𝑥)并不是在所有树建好之后才统一加权求解的，而是在算法逐渐建树的过程当中就随着迭代不断计算出来的。例如，对于样本𝑥𝑖，集成算法当中一共有𝑇T棵树（也就是参数n_estimators的取值），现在正在建立第𝑡个弱评估器，则第𝑡个弱评估器上𝑥𝑖的结果可以表示为𝑓𝑡(𝑥𝑖)。假设整个Boosting算法对样本𝑥𝑖输出的结果为𝐻(𝑥𝑖)，则该结果一般可以被表示为t=1~t=T过程当中，所有弱评估器结果的加权求和：

其中，𝜙𝑡为第t棵树的权重。对于第𝑡次迭代来说，则有：

在这个一般过程中，每次将本轮建好的决策树加入之前的建树结果时，可以在权重𝜙前面增加参数𝜂，表示为第t棵树加入整体集成算法时的学习率，对标参数learning_rate。

该学习率参数控制Boosting集成过程中𝐻(𝑥𝑖)的增长速度，是相当关键的参数。当学习率很大时，𝐻(𝑥𝑖)增长得更快，我们所需的n_estimators更少，当学习率较小时，𝐻(𝑥𝑖)增长较慢，我们所需的n_estimators就更多，因此boosting算法往往会需要在n_estimators与learning_rate当中做出权衡（以XGBoost算法为例）。

需要注意的是，以上式子为boosting算法中计算方式的一般规则，并不是具体到AdaBoost或任意Boosting集成算法的具体公式。

参数algorithm与loss

参数algorithm与loss是boosting算法中非常常见的，分类器与回归器展示出不同参数的情况。正如之前提到的，虽然AdaBoost算法的原理简单，但是在近几年已经发展出了多种不同的算法实践手段，而参数algorithm与loss正是用来控制算法实践手段的关键参数，其中algorithm控制具体的实践算法，loss控制该实践算法中所使用的具体损失函数。

algorithm

首先，参数algorithm是针对分类器设置的参数，其中备选项有"SAMME"与"SAMME.R"两个字符串。这两个字符串分别代表了两种不同的、实现AdaBoost分类的手段：AdaBoost-SAMME与AdaBoost-SAMME.R。两者在数学流程上的区别并不大，只不过SAMME是基于算法输出的具体分类结果（例如-1，1，2）进行计算，而SAMME.R则是在SAMME基础上改进过后、基于弱分配器输出的概率值进行计算，两种方法都支持在AdaBoost上完成多分类任务，但SAMME.R往往能够得到更好的结果，因此sklearn中的默认值是SAMME.R，因此sklearn中默认可以输入的base_estimators也需要是能够输出预测概率的弱评估器。实际在预测时，AdaBoost输出的𝐻(𝑥)也针对于某一类别的概率。

需要注意的是，在分类器中，我们虽然被允许选择算法，却不被允许选择算法所使用的损失函数，这是因为SAMME与SAMME.R使用了相同的损失函数：二分类指数损失（Exponential Loss Function）与多分类指数损失（Multi-class Exponential loss function）。

二分类指数损失——

其中y为真实分类，𝐻∗(𝑥)则是从集成算法输出的概率结果𝐻(𝑥)转换来的向量。转换规则如下：

在sklearn当中，由于𝐻(𝑥)是概率值，因此需要转换为𝐻∗(𝑥)，如果在其他实现AdaBoost的算法库中，𝐻(𝑥)输出直接为预测类别，则可以不执行转换流程。

根据指数损失的特殊性质，二分类状况下的类别取值只能为-1或1，因此𝑦的取值只能为-1或1。当算法预测正确时，𝑦𝐻∗(𝑥)的符号为正，则在函数𝑒−𝑥上损失很小。当算法预测错误时，𝑦𝐻∗(𝑥)的符号为负，则在函数𝑒−𝑥上损失较大。二分类指数损失是AdaBoost最经典的损失函数，它在数学推导上的有效性以及在实践过程中很强的指导性让其沿用至今。

多分类指数损失——

其中，𝐾为总类别数，如四分类[0,1,2,3]的情况时，𝐾=4，𝒚∗与𝑯∗(𝒙)都是根据多分类具体情况、以及集成算法实际输出𝐻(𝑥)转化出的向量，其中𝑦∗1与𝐻∗1(𝑥)的上标1都表示当前类别。

在二分类算法中，算法会直接针对二分类中的其中一个类别输出概率，因为在二分类中𝑃(𝑌=1)=1−𝑃(𝑌=−1)，所以只计算出一类的概率即可判断预测的标签。但在多分类算法中，算法必须针对所有可能的取值类型都输出概率，才能够从中找出最大概率所对应的预测标签。因此在集成算法中，我们对进行多分类预测时，会得到如下的表格：

每一行对应一个样本，每一列则对应该样本的预测标签为某一类别的概率，以上表格就是5个样本在10分类情况下得出的概率表格，而每一个样本的10个概率中，最大概率所对应的类别就是预测类别。而这一转换可以由函数argmax完成。argmax会取出最大值所对应的索引，刚好也就是最大概率所对应的预测标签。

在多分类算法当中，我们常常求解类似于𝒚∗或𝑯∗(𝒙)的向量，比如在softmax函数中，当预测值或真实值不等于𝑘时，我们赋予的向量值为0，而不是−1/𝐾−1。

softmax的一般规则：

同时，当K=2时，多分类指数损失的值与二分类指数损失完全一致：

多分类指数损失：

假设K=2，

假设预测分类 = 真实分类 = 1，

二分类指数损失，y=1，由于预测正确，所以𝐻∗(𝑥) = 1

在实践中，无论是SAMME还是SAMME.R，我们都无法改变使用的损失函数，因此参数中没有为我们提供相应的选择。

loss

看完参数algorithm，我们来看参数loss。与分类的情况完全相反，在AdaBoost回归当中，我们能够使用的算法是唯一的，即AdaBoost.R2，但是在R2算法下，我们却可以选择三种损失函数，分别是"linear"（线性）,"square"（平方）,"exponential"（指数）。

在算法AdaBoost.R2当中，三种损失函数如下定义：

首先：

𝐷=𝑠𝑢𝑝|𝐻(𝑥𝑖)−𝑦𝑖|,𝑖=1,2,...,𝑁

其中𝑦𝑖yi为真实标签，𝐻(𝑥𝑖)H(xi)为预测标签，sup表示“取最大值”，但它与直接写作max的函数的区别在于，max中的元素已是固定的数值，而sup中的元素可以是一个表达式、并让该表达式在i的备选值中循环。上述式子表示，取出1~N号样本中真实值与预测值差距最大的那一组差异来作为D的值。

R2算法线性损失——

R2算法平方损失——

R2算法指数损失——

不难发现，其实线性损失就是我们常说的MAE的变体，平方损失就是MSE的变体，而指数损失也与分类中的指数损失高度相似。在R2算法当中，这些损失函数特殊的地方在于分母D。由于D是所有样本中真实值与预测值差异最大的那一组差异，因此任意样本的𝐿𝑖在上述线性与平方损失定义下，取值范围都只有[0,1]（当真实值=预测值时，取值为0，当真实值-预测值=D时，取值为1）。

特别的，对于指数损失来说，自变量的部分是在[0,1]中取值，因此𝑒−𝑥的在该定义域上的值域也为[0,1]，因此1−𝑒−𝑥的值域为[0,1]。事实上，在R2算法的论文当中，就有明确对损失函数的唯一要求：即值域为[0,1]。该规则使得整个AdaBoost算法的求解流程变得顺畅，具体可以在《2 原理进阶：AdaBoost的求解流程》中看到。

现在，我们已经了解了AdaBoost的全部参数了。不难发现，在AdaBoost的参数空间中，n_estimators与learning_rate是最为重要的两个参数。当我们在进行超参数调整时，注意对这两个参数的组合进行同时调整即可。

2.2、原理进阶：AdaBoost的求解流程：

在使用AdaBoost算法时，我们并不需要对AdaBoost的具体求解流程掌握太过于深入。严格来说，只要知道参数的含义，即便我们完全不了解AdaBoost的求解流程，我们也能够自由地调用这个算法。然而，对于参数较少、原理简单的AdaBoost来说或许是okay的，对于后续即将要学习的复杂Boosting算法而言，我们却很难再避开复杂数学推导与原理。即便是为了应对面试中会出现的“你都知道哪些boosting算法？这些算法之间有什么异同？”，我们也必须对Boosting算法的原理有所掌握。

对于任意Boosting算法，我们都需要明确以下几点：

损失函数𝐿(𝑥,𝑦)的表达式是什么？损失函数如何影响模型构建？

弱评估器𝑓(𝑥)是什么，当下boosting算法使用的具体建树过程是什么？

综合集成结果𝐻(𝑥)是什么？集成算法具体如何输出集成结果？

同时，还可能存在其他需要明确的问题，例如：

是加权求和吗？如果是，加权求和中的权重如何求解？

训练过程中，拟合的数据𝑋与𝑦分别是什么？

模型训练到什么时候停下来最好？

同时，别忘记boosting算法的基本规则：

依据上一个弱评估器𝑓(𝑥)𝑡−1的结果，计算损失函数𝐿(𝑥,𝑦)，

并使用𝐿(𝑥,𝑦)自适应地影响下一个弱评估器𝑓(𝑥)𝑡的构建。

集成模型输出的结果，受到整体所有弱评估器𝑓(𝑥)0~ 𝑓(𝑥)𝑇的影响。

在此基本指导思想下，我们来梳理回归算法的基本流程（考虑到后续Boosting算法也是以回归为主流，因此在这里我们梳理回归算法的基本流程）。

AdaBoost.R2

AdaBoost.R2算法是当前AdaBoost实现流程中使用最多的回归类实践方式，它囊括了对数据进行有放回抽样、按损失函数结果调整样本权重、自动计算弱分类器权重、并输出预测结果等AdaBoost算法经典的全流程。假设现有数据集N，含有样本𝑀个，任意样本编号为𝑖，同时，弱评估器为决策树𝑓，总共学习𝑇轮，则AdaBoost.R2的基本流程如下所示：

1) 初始化原始数据集的权重𝑤𝑖，其中任意𝑤𝑖=1/M

开始循环，for t in 1,2,...T:

2) 在现有数据集𝑁中，有放回抽样𝑀个样本，构成训练集𝑁𝑡。在每次抽取一个样本时，任意样本被抽中的概率为𝑃𝑡𝑖=𝑤𝑖/∑𝑤𝑖，很显然，该概率就是当前样本在训练集𝑁𝑡中的权重。当从初始权重中抽样时，概率𝑃1𝑖=1/M，当后续权重变化时，拥有更大权重的样本被抽中的概率会更大。

3) 在训练集𝑁𝑡上按照CART树规则建立一棵回归树𝑓𝑡，训练时所拟合的标签为样本的真实标签𝑦𝑡𝑖。

4) 将𝑁𝑡上所有的样本输入𝑓𝑡进行预测，得出预测结果𝑓𝑡(𝑥𝑖)，其中i = 1,2,...M。

5) 计算单一样本𝑖i上的损失函数𝐿𝑡𝑖=𝐿(𝑓𝑡(𝑥𝑖),𝑦𝑖)，计算过程如下所示：

求解𝐷=𝑠𝑢𝑝|𝑓𝑡(𝑥𝑖)−𝑦𝑖|,𝑖=1,2,...,𝑁

选择线性/平方或指数损失函数中的一种计算𝐿𝑡𝑖

根据AdaBoost的要求，所有损失的值域都在[0,1]之间。

6) 计算全样本上的加权平均损失:

注意此时𝑃𝑡𝑖就等于样本的权重。由于𝑃𝑡𝑖=𝑤𝑖/∑𝑤𝑖，所以𝑃𝑡𝑖一定位于[0,1]范围内，并且∑𝑃𝑡𝑖,𝑖=1,2,...𝑀一定为1。

当权重之和为1时，加权平均值一定会小于等于单一数值的最大值（同时大于等于单一数值的最小值），因此加权平均的值域不会超出单一平均数的值域。由于所有损失的值域都是[0,1]，因此加权平均值𝐿𝑡¯的值域也是[0,1]。同时，由于损失的最大值为1，而权重𝑃𝑡𝑖Pit的最大值一定是远远小于1的，因此加权平均值𝐿𝑡¯的最大值一般也是远远小于1的。

7) 依据加权平均损失𝐿𝑡¯计算衡量当前集成算法的置信度𝛽𝑡

𝛽𝑡=𝐿𝑡¯/(1−𝐿𝑡¯+𝜆)，其中𝜆是为了防止分母为0的常数

不难发现，当加权平平均损失很高时，𝛽𝑡很大，因此置信度小，当加权平均损失很低时，𝛽𝑡很小，因此置信度大。置信度越大，集成算法当前的预测结果越好。

已知𝐿𝑡¯的理论值域是[0,1]，因此𝛽𝑡βt的理论值域是[0,+∞]，因此𝛽𝑡βt的值越接近0越好。

同时，我们还知道𝐿𝑡¯的实际范围大约都在0.2~0.3之间，因此一般来说𝛽𝑡βt的实际范围基本都是小于1的。

8) 依据置信度评估𝛽𝑡更新样本权重:

9) 求解迭代过程中弱分类器所需的权重

其中log的底数为e或者为2皆可。当𝛽值越接近于0，说明损失越小、置信度越高，则𝑙𝑜𝑔(1/)的值越大。所以，损失更小的树对应的权重更大，损失更大的树对应的权重更小。

10) 求解出当前迭代𝑡下集成算法的输出值：