【树模型与集成学习】(task5)自适应提升法AdaBoost（更新ing）

2022-04-24 423

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 自适应提升算法Adaboost，Adaptive Boosting。自适应是指Adaboost会根据本轮样本的误差结果来分配下一轮模型训练时样本在模型中的相对权重，即对错误的或偏差大的样本适度“重视”，对正确的或偏差小的样本适度“放松”，这里的“重视”和“放松”具体体现在了Adaboost的损失函数设计以及样本权重的更新策略。

一、Adaboost概述

自适应提升算法Adaboost，Adaptive Boosting。

自适应是指Adaboost会根据本轮样本的误差结果来分配下一轮模型训练时样本在模型中的相对权重，即对错误的或偏差大的样本适度“重视”，对正确的或偏差小的样本适度“放松”，这里的“重视”和“放松”具体体现在了Adaboost的损失函数设计以及样本权重的更新策略。

1.1 一个栗子

【对Adaboost的通俗理解】

就像是做错题本，把每次把错题做一次，然后组成一本新的“错题本2”，依次类推，然后得到错题本n，直到所有的题目都能重做做对位置。

【对梯度提升的通俗理解】

而对于梯度提升，类似AdaBoost算法，它是拟合上一个模型预测错误的实例，即拟合上一个模型的残差（Residual Errors）。举个栗子说，做错题，但是这次不再收集错题了，是m每次查看做错的题目是从哪一步开始做错，然后从这一步开始，重新编制一道新的题目。新题的解题步骤就从做错的那一步开始，以此类推组成了一种新形式的错题本，直到将所有的题目都做对。

也就是说梯度提升是首先预测一个模型，进行预测，然后计算残差，让这些残差成为新的训练样本。用一个新模型去拟合这些残差，以此类推。最后将这一过程的所有模型累加得到最终模型。

1.2 AdaBoost二分类

（此处1.2参考李航老师的《统计学习方法》）

input：训练数据集

其中标记

output：最终分类器G ( x ) G(x)G(x)。

AdaBoost就是从训练数据中学习一系列弱分类器或者基本分类器，并将这些弱分类器线性组合成一个强分类器。具体过程：

（1）初始化训练数据的权值分布：

（2）对m=1,2,3,…,M

（2.1）使用具有权值分布D m D_mD

的训练数据集学习，得到基本分类器

（2.2）计算G m ( x ) G_{m}(x)G

(x)在训练数据集上的分类误差率

（2.3）计算G m ( x ) G_{m}(x)G

(x)的系数

这里的对数是自然对数。

（2.4）更新训练数据集的权值分布

这里的Z m Z_{m}Z

是规范化因子：

（3）构建基本分类器的线性组合

得到最终分类器：

二、分类损失

上面的计算也可以通过python计算：

>>> import math
>>> math.exp(0.15)
1.161834242728283

因此，选择指数损失能够满足贝叶斯最优决策条件。

三、SAMME算法

3.1 SAMME算法的motivation

根据Adaboost算法更新权重的原理我们知道想要在下一轮训练中使误分类的样本的权重增加，每一轮训练的错误率都必须小于0.5，包括初始化分类器时也是如此。初始化一般都是随机初始化，对于二分类任务，每个样本都有0.5的概率被预测正确，要达到0.5以上的正确率还是比较容易的，但是对于多分类问题就不一样了，在多分类问题中如果有 K个不同的类别，那么随机猜测只有 1/K 的概率预测正确，因此若直接将Adaboost算法应用于多类分类问题往往不能得到令人满意的结果。针对这个问题，Zhu Ji等人在2009年提出了SAMME及SAMME.R算法，这也是sklearn中用Adaboost做多类分类问题时采用的算法。

有几个基础知识：

（1）加法模型

这里的大G是每一轮训练的分类器的误差，α \alphaα是该分类器的权重。

（2）弱学习与强学习

弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）

强学习：识别准确率很高并能在多项式时间内完成的学习算法

一个概念是强可学习的充分必要条件是这个概念是弱可学习

（3）权重更新公式

3.2 Adaboost的SAMME实现

AdaBoost有一种解释，即可以认为它是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法。【练习】对公式进行化简，写出K = 2 K=2K=2时的SAMME算法流程，并与李航《统计学习方法》一书中所述的Adaboost二分类算法对比是否一致。

【答】一致。

3.3 SAMME算法迭代循环的优化

还能通过一些多分类的性质来改写算法的局部实现，使得一些变量前的系数得到简化。记

来代替b ∗ ( m ) ( x ) \mathbf{b}^{*(m)}(\mathbf{x})b

∗(m)

(x)。请根据本文的实现，对sklearn包的源码进行修改并构造一个例子来比较它们的输出是否会不同。（提示：修改AdaboostClassifier类中的decision_function函数和staged_decision_function函数）

对w \mathbf{w}w进行归一化操作后，不会对下一轮算法1中G ∗ G^*G

∗

和e r r ( m ) err^{(m)}err

(m)

的结果产生任何影响。同时，如果把算法1第12行的β ∗ ( m ) \beta^{*(m)}β

∗(m)

替换为α ∗ ( m ) \alpha^{*(m)}α

∗(m)

，由于它们的输出结果只相差常数倍

来更新，而不影响归一化结果。此时，算法1的迭代循环可进行如下重写：

四、SAMME.R算法

许多分类器都能够输出预测样本所属某一类别的概率，但是SAMME算法只能利用分类的标签信息，而不能利用这样的概率信息。SAMME.R算法通过损失近似的思想，将加权分类模型的概率输出信息与boosting方法相结合。SAMME.R中的字母“R”代表“Real”，意味着模型每轮迭代的输出为实数。【练习】验证h k ′ ∗ h^*_{k'}h

′

∗

的求解结果。

【练习】算法3的第14行给出了w i w_iw

的更新策略，请说明其合理性。

将上述算法过程总结伪代码如下：

五、SAMME和SAMME.R代码实现

import numpy as np
from sklearn.metrics import accuracy_score
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
class AdaboostClassifier:
    def __init__(self, base_estimator, n_estimators, algorithm):
        self.base_estimator = base_estimator
        self.n_estimators = n_estimators
        self.algorithm = algorithm
        self.boostors = []
        if self.algorithm == "SAMME":
            self.boostor_weights = []
        self.classes = None
    def fit(self, X, y, **kwargs):
        w = np.repeat(1/X.shape[0], X.shape[0])
        self.classes = np.unique(y.reshape(-1)).shape[0]
        output = 0
        for n in range(self.n_estimators):
            cur_boostor = self.base_estimator(**kwargs)
            cur_boostor.fit(X, y, w)
            if self.algorithm == "SAMME":
                y_pred = cur_boostor.predict(X)
                err = (w*(y != y_pred)).sum()
                alpha = np.log((1-err)/err) + np.log(self.classes-1)
                temp_output = np.full(
                    (X.shape[0], self.classes), -1/(self.classes-1))
                temp_output[np.arange(X.shape[0]), y_pred] = 1
                # 把当前轮的基模型和模型权重加入列表，准备预测的时候用
                self.boostors.append(cur_boostor)
                self.boostor_weights.append(alpha)
                w *= np.exp(alpha * (y != y_pred))
                w /= w.sum()
                output += temp_output * alpha
            elif self.algorithm == "SAMME.R":
                y_pred = cur_boostor.predict_proba(X)
                log_proba = np.log(y_pred + 1e-6)
                temp_output = (
                    self.classes-1)*(log_proba-log_proba.mean(1).reshape(-1,1))
                temp_y = np.full(
                    (X.shape[0], self.classes), -1/(self.classes-1))
                temp_y[np.arange(X.shape[0]), y] = 1
                self.boostors.append(cur_boostor)
                w *= np.exp(
                    (1-self.classes)/self.classes * (temp_y*log_proba).sum(1))
                w /= w.sum()
                output += temp_output
            #acc = accuracy_score(y, np.argmax(output, axis=1))
            #print(acc)
    def predict(self, X):
        result = 0
        if self.algorithm == "SAMME":
            for n in range(self.n_estimators):
                cur_pred = self.boostors[n].predict(X)
                temp_output = np.full(
                    (X.shape[0], self.classes), -1/(self.classes-1))
                temp_output[np.arange(X.shape[0]), cur_pred] = 1
                result += self.boostor_weights[n] * temp_output
        elif self.algorithm == "SAMME.R":
            for n in range(self.n_estimators):
                y_pred = self.boostors[n].predict_proba(X)
                log_proba = np.log(y_pred + 1e-6)
                temp_output = (
                    self.classes-1)*(log_proba-log_proba.mean(1).reshape(-1,1))
                result += temp_output
        return np.argmax(result, axis=1)
if __name__ == "__main__":
    X, y = make_classification(
        n_samples=10000, n_features=10,
        n_informative=5, random_state=0, n_classes=2
    )
    X_train, X_test, y_train, y_test = train_test_split(
        X, y, test_size=0.3, random_state=0
    )
    from sklearn.ensemble import AdaBoostClassifier as ABC
    clf = ABC(
        DecisionTreeClassifier(max_depth=1),
        n_estimators=20, algorithm="SAMME"
    )
    clf.fit(X_train, y_train)
    result = clf.predict(X_test)
    print("sklearn中SAMME的验证集得分为: ", accuracy_score(y_test, result))
    clf = AdaboostClassifier(
        DecisionTreeClassifier,
        20, "SAMME"
    )
    clf.fit(X_train, y_train, max_depth=1)
    result = clf.predict(X_test)
    print("使用SAMME.R集成的验证集得分为: ", accuracy_score(y_test, result))
    clf = ABC(
        DecisionTreeClassifier(max_depth=1),
        n_estimators=20, algorithm="SAMME.R"
    )
    clf.fit(X_train, y_train)
    result = clf.predict(X_test)
    print("sklearn中SAMME.R的验证集得分为: ", accuracy_score(y_test, result))
    clf = AdaboostClassifier(
        DecisionTreeClassifier,
        20, "SAMME.R"
    )
    clf.fit(X_train, y_train, max_depth=1)
    result = clf.predict(X_test)
    print("使用SAMME.R集成的验证集得分为: ", accuracy_score(y_test, result))
    clf = DecisionTreeClassifier(max_depth=1)
    clf.fit(X_train, y_train)
    result = clf.predict(X_test)
    print("使用决策树桩的验证集得分为: ", accuracy_score(y_test, result))

sklearn中SAMME的验证集得分为:  0.8316666666666667
使用SAMME.R集成的验证集得分为:  0.8316666666666667
sklearn中SAMME.R的验证集得分为:  0.8503333333333334
使用SAMME.R集成的验证集得分为:  0.8503333333333334
使用决策树桩的验证集得分为:  0.7746666666666666