机器学习-集成学习-boosting之AdaBoost算法详解

1. 概述

1.1 集成学习

目前存在各种各样的机器学习算法,例如SVM、决策树、感知机等等。但是实际应用中,或者说在打比赛时,成绩较好的队伍几乎都用了集成学习(ensemble learning)的方法。集成学习的思想,简单来讲,就是“三个臭皮匠顶个诸葛亮”。集成学习通过结合多个学习器(例如同种算法但是参数不同,或者不同算法),一般会获得比任意单个学习器都要好的性能,尤其是在这些学习器都是"弱学习器"的时候提升效果会很明显。

弱学习器指的是性能不太好的学习器,比如一个准确率略微超过50%的二分类器。

下面看看西瓜书对此做的一个简单理论分析。
考虑一个二分类问题机器学习-集成学习-boosting之AdaBoost算法详解、真实函数机器学习-集成学习-boosting之AdaBoost算法详解以及奇数机器学习-集成学习-boosting之AdaBoost算法详解个犯错概率相互独立且均为机器学习-集成学习-boosting之AdaBoost算法详解的个体学习器(或者称基学习器)机器学习-集成学习-boosting之AdaBoost算法详解我们用简单的投票进行集成学习,即分类结果取半数以上的基学习器的结果:机器学习-集成学习-boosting之AdaBoost算法详解

由Hoeffding不等式知,集成学习后的犯错(即过半数基学习器犯错)概率满足机器学习-集成学习-boosting之AdaBoost算法详解

机器学习-集成学习-boosting之AdaBoost算法详解的证明是周志华《机器学习》的习题8.1,题解可参考此处

机器学习-集成学习-boosting之AdaBoost算法详解指出,当犯错概率独立的基学习器个数机器学习-集成学习-boosting之AdaBoost算法详解很大时,集成后的犯错概率接近0,这也很符合直观想法: 大多数人同时犯错的概率是比较低的。

就如上面加粗字体强调的,以上推论全部建立在基学习器犯错相互独立的情况下,但实际中这些学习器不可能相互独立,而如何让基学习器变得“相对独立一些”,也即增加这些基学习器的多样性,正是集成学习需要考虑的主要问题。

按照每个基学习器之间是否存在依赖关系可以将集成学习分为两类:

  1. 基学习器之间存在强依赖关系,一系列基学习器需要串行生成,代表算法是Boosting;
  2. 基学习器之间不存在强依赖关系,一系列基学习器可并行生成,代表算法是Bagging和随机森林

Boosting系列算法里最著名算法主要有AdaBoost和提升树(Boosting tree)系列算法,本文只介绍最具代表性的AdaBoost。提升树、Bagging以及随机森林不在本文介绍范围内,有时间了再另外介绍。

https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.BaggingClassifier.html?highlight=bagging#sklearn.ensemble.BaggingClassifier

https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.BaggingRegressor.html?highlight=bagging#sklearn.ensemble.BaggingRegressor

随机森林是Bagging的一个实现,使用了决策树,Bagging也可使用其他分类器。

1.2 Boosting

Boosting指的是一类集成方法,其主要思想就是将弱的基学习器提升(boost)为强学习器。具体步骤如下:

  1. 先用每个样本权重相等的训练集训练一个初始的基学习器;
  2. 根据上轮得到的学习器对训练集的预测表现情况调整训练集中的样本权重(例如提高被错分类的样本的权重使之在下轮训练中得到更多的关注), 然后据此训练一个新的基学习器;
  3. 重复2直到得到机器学习-集成学习-boosting之AdaBoost算法详解个基学习器,最终的集成结果是机器学习-集成学习-boosting之AdaBoost算法详解个基学习器的组合。

由此看出,Boosting算法是一个串行的过程。

Boosting算法簇中最著名的就是AdaBoost,下文将会详细介绍。

2. AdaBoost原理

2.1 基本思想

对于1.2节所述的Boosting算法步骤,需要回答两个问题:

  1. 如何调整每一轮的训练集中的样本权重?
  2. 如何将得到的机器学习-集成学习-boosting之AdaBoost算法详解个组合成最终的学习器?

AdaBoost(Adaptive Boosting, 自适应增强)算法采取的方法是:

  1. 提高上一轮被错误分类的样本的权值,降低被正确分类的样本的权值;
  2. 线性加权求和。误差率小的基学习器拥有较大的权值,误差率大的基学习器拥有较小的权值。

Adaboost算法结构如下图(图片来源)所示。

机器学习-集成学习-boosting之AdaBoost算法详解

下面先给出AdaBoost算法具体实现步骤,至于算法解释(为什么要这样做)将在下一大节阐述。

2.2 算法步骤

考虑如下形式的二分类(标准AdaBoost算法只适用于二分类任务)训练数据集:机器学习-集成学习-boosting之AdaBoost算法详解其中机器学习-集成学习-boosting之AdaBoost算法详解是一个含有机器学习-集成学习-boosting之AdaBoost算法详解个元素的列向量, 即机器学习-集成学习-boosting之AdaBoost算法详解;机器学习-集成学习-boosting之AdaBoost算法详解是标量,机器学习-集成学习-boosting之AdaBoost算法详解

Adaboost算法具体步骤如下:

  1. 初始化样本的权重机器学习-集成学习-boosting之AdaBoost算法详解
  2. 机器学习-集成学习-boosting之AdaBoost算法详解,重复以下操作得到机器学习-集成学习-boosting之AdaBoost算法详解个基学习器:
    (1) 按照样本权重分布机器学习-集成学习-boosting之AdaBoost算法详解训练数据得到第机器学习-集成学习-boosting之AdaBoost算法详解个基学习器机器学习-集成学习-boosting之AdaBoost算法详解:机器学习-集成学习-boosting之AdaBoost算法详解(2) 计算机器学习-集成学习-boosting之AdaBoost算法详解在加权训练数据集上的分类误差率:机器学习-集成学习-boosting之AdaBoost算法详解上式中机器学习-集成学习-boosting之AdaBoost算法详解是指示函数,考虑更加周全的AdaBoost算法在这一步还应该判断是否满足基本条件(例如生成的基学习器是否比随机猜测好), 如果不满足,则当前基学习器被抛弃,学习过程提前终止。
    (3) 计算机器学习-集成学习-boosting之AdaBoost算法详解的系数(即最终集成使用的的基学习器的权重):机器学习-集成学习-boosting之AdaBoost算法详解(4) 更新训练样本的权重机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解其中机器学习-集成学习-boosting之AdaBoost算法详解是规范化因子,目的是为了使机器学习-集成学习-boosting之AdaBoost算法详解的所有元素和为1。即机器学习-集成学习-boosting之AdaBoost算法详解
  3. 构建最终的分类器线性组合机器学习-集成学习-boosting之AdaBoost算法详解得到最终的分类器为机器学习-集成学习-boosting之AdaBoost算法详解

由式机器学习-集成学习-boosting之AdaBoost算法详解知,当基学习器机器学习-集成学习-boosting之AdaBoost算法详解的误差率机器学习-集成学习-boosting之AdaBoost算法详解时,机器学习-集成学习-boosting之AdaBoost算法详解,并且机器学习-集成学习-boosting之AdaBoost算法详解随着机器学习-集成学习-boosting之AdaBoost算法详解的减小而增大,即分类误差率越小的基学习器在最终集成时占比也越大。即AdaBoost能够适应各个弱分类器的训练误差率,这也是它的名称中"适应性(Adaptive)"的由来。

由式机器学习-集成学习-boosting之AdaBoost算法详解知, 被基学习器机器学习-集成学习-boosting之AdaBoost算法详解误分类的样本权值得以扩大,而被正确分类的样本的权值被得以缩小。

需要注意的是式机器学习-集成学习-boosting之AdaBoost算法详解中所有的机器学习-集成学习-boosting之AdaBoost算法详解的和并不为1(因为没有做一个softmax操作),机器学习-集成学习-boosting之AdaBoost算法详解的符号决定了所预测的类,其绝对值代表了分类的确信度。

3. AdaBoost算法解释

有没有想过为什么AdaBoost算法长上面这个样子,例如为什么机器学习-集成学习-boosting之AdaBoost算法详解要用式机器学习-集成学习-boosting之AdaBoost算法详解那样计算?本节将探讨这个问题。

3.1 前向分步算法

在解释AdaBoost算法之前,先来看看前向分步算法。

就以AdaBoost算法的最终模型表达式为例:机器学习-集成学习-boosting之AdaBoost算法详解可以看到这是一个“加性模型(additive model)”。我们希望这个模型在训练集上的经验误差最小,即

机器学习-集成学习-boosting之AdaBoost算法详解通常这是一个复杂的优化问题。前向分步算法求解这一优化问题的思想就是: 因为最终模型是一个加性模型,如果能从前往后,每一步只学习一个基学习器机器学习-集成学习-boosting之AdaBoost算法详解及其权重机器学习-集成学习-boosting之AdaBoost算法详解, 不断迭代得到最终的模型,那么就可以简化问题复杂度。具体的,当我们经过机器学习-集成学习-boosting之AdaBoost算法详解轮迭代得到了最优模型机器学习-集成学习-boosting之AdaBoost算法详解时,因为

机器学习-集成学习-boosting之AdaBoost算法详解所以此轮优化目标就为机器学习-集成学习-boosting之AdaBoost算法详解求解上式即可得到第机器学习-集成学习-boosting之AdaBoost算法详解个基分类器机器学习-集成学习-boosting之AdaBoost算法详解及其权重机器学习-集成学习-boosting之AdaBoost算法详解
这样,前向分步算法就通过不断迭代求得了从机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解的所有基分类器及其权重,问题得到了解决。

3.2 AdaBoost算法证明

上一小结介绍的前向分步算法逐一学习基学习器,这一过程也即AdaBoost算法逐一学习基学习器的过程。但是为什么2.2节中的公式为什么长那样还是没有解释。本节就证明前向分步算法的损失函数是指数损失函数(exponential loss function)时,AdaBoost学习的具体步骤就如2.2节所示。

指数损失函数即机器学习-集成学习-boosting之AdaBoost算法详解周志华《机器学习》p174有证明,指数损失函数是分类任务原本0/1损失函数的一致(consistent)替代损失函数,由于指数损失函数有更好的数学性质,例如处处可微,所以我们用它替代0/1损失作为优化目标。

将指数损失函数代入式机器学习-集成学习-boosting之AdaBoost算法详解,优化目标就为机器学习-集成学习-boosting之AdaBoost算法详解因为机器学习-集成学习-boosting之AdaBoost算法详解与优化变量机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解无关,如果令机器学习-集成学习-boosting之AdaBoost算法详解

这个机器学习-集成学习-boosting之AdaBoost算法详解其实就是2.2节中归一化之前的权重机器学习-集成学习-boosting之AdaBoost算法详解

那么式机器学习-集成学习-boosting之AdaBoost算法详解等价于机器学习-集成学习-boosting之AdaBoost算法详解

我们分两步来求解式机器学习-集成学习-boosting之AdaBoost算法详解所示的优化问题的最优解机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解:

  1. 对任意的机器学习-集成学习-boosting之AdaBoost算法详解, 求机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解上式将指数函数换成指示函数是因为前面说的指数损失函数和0/1损失函数是一致等价的。
    式子机器学习-集成学习-boosting之AdaBoost算法详解所示的优化问题其实就是AdaBoost算法的基学习器的学习过程,即2.2节的步骤2(1),得到的机器学习-集成学习-boosting之AdaBoost算法详解是使第机器学习-集成学习-boosting之AdaBoost算法详解轮加权训练数据分类误差最小的基分类器。
  2. 求解机器学习-集成学习-boosting之AdaBoost算法详解
    将式子机器学习-集成学习-boosting之AdaBoost算法详解中的目标函数展开机器学习-集成学习-boosting之AdaBoost算法详解注:为了简洁,上式子中的机器学习-集成学习-boosting之AdaBoost算法详解被略去了机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解被略去了下标机器学习-集成学习-boosting之AdaBoost算法详解,下同
    将上式对机器学习-集成学习-boosting之AdaBoost算法详解求导并令导数为0,即机器学习-集成学习-boosting之AdaBoost算法详解解得机器学习-集成学习-boosting之AdaBoost算法详解其中,机器学习-集成学习-boosting之AdaBoost算法详解是分类误差率:机器学习-集成学习-boosting之AdaBoost算法详解如果式子机器学习-集成学习-boosting之AdaBoost算法详解中的机器学习-集成学习-boosting之AdaBoost算法详解归一化成和为1的话那么式机器学习-集成学习-boosting之AdaBoost算法详解也就和2.2节式机器学习-集成学习-boosting之AdaBoost算法详解一模一样了,进一步地也有上面的机器学习-集成学习-boosting之AdaBoost算法详解也就是2.2节的机器学习-集成学习-boosting之AdaBoost算法详解
    最后来看看每一轮样本权值的更新,由机器学习-集成学习-boosting之AdaBoost算法详解机器学习-集成学习-boosting之AdaBoost算法详解可得机器学习-集成学习-boosting之AdaBoost算法详解如果将上式进行归一化成和为1的话就和与2.2节中机器学习-集成学习-boosting之AdaBoost算法详解完全相同了。

由此可见,2.2节所述的AdaBoost算法步骤是可以经过严密推导得来的。总结一下,本节推导有如下关键点:

  • AdaBoost算法是一个加性模型,将其简化成前向分步算法求解;
  • 将0/1损失函数用数学性质更好的指数损失函数替代。

4. python实现

4.1 基学习器

首先需要定义一个基学习器,它应该是一个弱分类器。
弱分类器使用库sklearn中的决策树分类器DecisionTreeClassifier, 可设置该决策树的最大深度为1。

# Fit a simple decision tree(weak classifier) first
clf_tree = DecisionTreeClassifier(max_depth = 1, random_state = 1)

4.2 AdaBoost实现

然后就是完整AdaBoost算法的实现了,如下所示。

def my_adaboost_clf(Y_train, X_train, Y_test, X_test, M=20, weak_clf=DecisionTreeClassifier(max_depth = 1)):
    n_train, n_test = len(X_train), len(X_test)
    # Initialize weights
    w = np.ones(n_train) / n_train
    pred_train, pred_test = [np.zeros(n_train), np.zeros(n_test)]

    for i in range(M):
        # Fit a classifier with the specific weights
        weak_clf.fit(X_train, Y_train, sample_weight = w)
        pred_train_i = weak_clf.predict(X_train)
        pred_test_i = weak_clf.predict(X_test)

        # Indicator function
        miss = [int(x) for x in (pred_train_i != Y_train)]
        print("weak_clf_%02d train acc: %.4f"
         % (i + 1, 1 - sum(miss) / n_train))

        # Error
        err_m = np.dot(w, miss)
        # Alpha
        alpha_m = 0.5 * np.log((1 - err_m) / float(err_m))
        # New weights
        miss2 = [x if x==1 else -1 for x in miss] # -1 * y_i * G(x_i): 1 / -1
        w = np.multiply(w, np.exp([float(x) * alpha_m for x in miss2]))
        w = w / sum(w)

        # Add to prediction
        pred_train_i = [1 if x == 1 else -1 for x in pred_train_i]
        pred_test_i = [1 if x == 1 else -1 for x in pred_test_i]
        pred_train = pred_train + np.multiply(alpha_m, pred_train_i)
        pred_test = pred_test + np.multiply(alpha_m, pred_test_i)

    pred_train = (pred_train > 0) * 1
    pred_test = (pred_test > 0) * 1

    print("My AdaBoost clf train accuracy: %.4f" % (sum(pred_train == Y_train) / n_train))
    print("My AdaBoost clf test accuracy: %.4f" % (sum(pred_test == Y_test) / n_test

 

 

上一篇:机器学习中分类任务的常用评估指标和python代码实现


下一篇:java并发 - 学习AQS