集成学习

  1. 集成学习ensemble learning是通过构建并结合多个学习器来完成学习任务。其一般结构为:

    • 先产生一组“个体学习器”(individual learner) 。个体学习器通常由一种或者多种现有的学习算法从训练数据中产生。

      • 如果个体学习器都是从某一种学习算法从训练数据中产生,则称这样的集成学习是同质的homogenerous

        此时的个体学习器也称作基学习器base learner,相应的学习算法称作基学习算法。

      • 如果个体学习器是从某几种学习算法从训练数据中产生,则称这样的集成学习是异质的heterogenous

    • 再使用某种策略将它们结合起来。集成学习通过将多个学习器进行组合,通常可以获得比单一学习器显著优越的泛化性能。

  2. 通常选取个体学习器的准则是:

    • 个体学习器要有一定的准确性,预测能力不能太差。
    • 个体学习器之间要有多样性,即学习器之间要有差异。
  3. 通常基于实际考虑,往往使用预测能力较强的个体学习器(即强学习器,与之对应的为弱学习器)。

    强学习器的一个显著的好处就是可以使用较少数量的个体学习器来集成就可以获得很好的效果。

  4. 根据个体学习器的生成方式,目前的集成学习方法大概可以分作两类:

    • 个体学习器之间存在强依赖关系、必须串行生成的序列化方法,每一轮迭代产生一个个体学习器。其中以Boosting为代表。
    • 个体学习器之间不存在强依赖关系、可同时生成的并行化方法。其中以Bagging和随机森林Random Forest为代表。

一、集成学习误差

  1. 考虑一个二类分类问题。设单个样本为 ,真实类别为

    假定基类分类器的错误率为 ,即对每个基分类器 有:

    • 假设集成学习通过简单投票法结合 个基分类器 。即:若有超过半数的基分类器正确,则集成分类就正确。根据描述,给出集成学习器为:

    • 集成学习器预测错误的条件为: 个基分类器预测正确,其中 (即:少于一半的基分类器预测正确), 个基分类器预测错误。

      假设基分类器的错误率相互独立,则集成学习器预测错误的概率为:

    • 根据Hoeffding不等式有:

      可以看出:随着 , 集成学习器预测错误的概率

  2. 上述推论有非常关键的一个地方:假设基分类器的错误率相互独立。

    • 实际上个体学习器是为了解决同一个问题训练出来的,而且可能是同一类算法从同一个训练集中产生。

      这样个体学习器的错误率显然不能相互独立。

    • 实际上个体学习器的准确性和多样性本身就存在冲突。

      • 通常个体学习器的准确性很高之后,要增加多样性就需要牺牲准确性。
      • 实际上如何产生并结合”好而不同“的个体学习器就是集成学习研究的核心。

二、 Boosting

  1. 提升方法(boosting) 是一种常用的统计学习方法。在分类问题中,它通过改变训练样本的权重学习多个分类器,并将这些分类器们进行线性组合来提高分类的能力。

  2. 提升方法的基本思想是:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断要好。类似于”三个臭皮匠顶一个诸葛亮“。

  3. 提升方法的理论基础是:强可学习与弱可学习是等价的。

    在概率近似正确(probably approximately correct,PAC)学习的框架下:

    • 强可学习:一个概念(或一个类别),若存在一个多项式的学习算法能够学习它并且正确率很高,那么称这个概念是强可学习的。
    • 弱可学习:一个概念(或一个类别),若存在一个多项式的学习算法能够学习它,学习的正确率仅比随机猜测略好,那么称这个概念是弱可学习的。

    可以证明:强可学习与弱可学习是等价的。

    即:若在学习中发现了 ”弱学习算法“ ,则可以通过某些办法将它提升为 ”强学习算法“。

  4. 对于分类问题而言,求一个比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)要容易得多。

  5. Boosting 就是一族可以将弱学习器提升为强学习器的算法。

    这族算法的工作原理类似:

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

2.1 AdaBoost 算法

  1. Boosting族算法最著名的代表是AdaBoost算法。

  2. AdaBoot算法两个核心步骤:

    • 每一轮中如何改变训练数据的权值?

      AdaBoost算法提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。

      于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。

    • 最后如何将一系列弱分类器组合成一个强分类器?

      AdaBoost 采用加权多数表决的方法:

      • 加大分类误差率较小的弱分类器的权值,使得它在表决中起较大作用。
      • 减小分类误差率较大的弱分类器的权值,使得它在表决中起较小的作用。
  3. AdaBoost算法有两个特点:

    • 不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基本分类器的学习中起不同作用。

      • 因此AdaBoost要求基本学习器能够对特定的数据分布进行学习,这一般是在学习的时候为每个训练样本赋予一个权重。
      • 对于无法接受带权样本的基本学习算法,则可以通过“重采样法”来处理:即在每一轮学习中,根据样本分布对训练集重新采样,再用重采样的样本集对基本学习器进行训练。
      • 一般而言这两者没有显著的优劣差别。
    • 利用基本分类器的线性组合 构成最终分类器:

      其中:

      • 的符号决定实例 的分类。
      • 的绝对值表示分类的确信度。
  4. AdaBoost 算法具有自适应性,即它能够自动适应弱分类器各自的训练误差率,这也是它的名字(适应的提升)的由来。

2.1.1 算法

  1. AdaBoost算法:

    • 输入:

      • 训练数据集
      • 弱学习算法
    • 输出:集成分类器

    • 算法步骤:

      • 初始化训练数据的权值分布

        • 使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器:

        • 计算 在训练数据集上的分类误差率:

          它就是所有误分类点的权重之和。其中权重越大的误差分类点,其在误差率中占比越大。

        • ,算法终止,构建失败!

        • 计算 的系数:

          该系数表示 在集成分类器中的重要性。它是 的单调减函数,说明误差越小的基本分类器,其重要性越高。

          根据系数大于零要求

        • 更新训练数据集的权值分布: 。其中:

          为规范化因子,它使得 成为一个概率分布 。

      • 构建基本分类器的线性组合: ,于是得到集成分类器:

  2. 为防止过拟合,AdaBoost 通常会加入正则化项。该正则化项称作步长或者学习率,定义为

    考虑正则化项之后,模型的更新方式为:

2.1.2 算法解释

  1. AdaBoost 提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。

    这是通过更新训练数据集的权值分布 来实现的。其中:

    • 对于正确分类样本, 下一轮权重为:
    • 对于错误分类样本, 下一轮权重为:

    两者比较,误分类样本的权重是正确分类样本的权重的 倍。于是误分类样本在下一轮学习中权重更大。

  2. 集成分类器 结合 个基本分类器的方式为加权表决。

    • 系数 表示了基本分类器 的重要性。其中:

    • 由于 是分类误差率 的单调递减函数,因此:

      • AdaBoost 加大分类误差率较小的弱分类器的权值,使得它在表决中起较大作用。
      • AdaBoost 减小分类误差率较大的弱分类器的权值,使得它在表决中起较小的作用。

2.1.3 误差分析

  1. 定理一:AdaBoost算法集成分类器的训练误差上界为:

    这一定理说明:可以在每一轮选取适当的 使得 最小,从而使得训练误差下降最快。

  2. 定理二:二类分类 AdaBoost 的训练误差界:

    其中

  3. 推论:若存在 ,对所有 ,则有:

    这表明在此条件下 AdaBoost 的训练误差是以指数速率下降的。

  4. 上述定理都只是关于训练误差的分析,实际应用中更关系测试集的误差。

    AdaBoost 算法也会出现过拟合,此时训练误差为 0 但是测试集的误差较大。

  5. AdaBoost 的基础分类器比较复杂时,AdaBoost 很容易陷入过拟合。

    但是当AdaBoost 的基础分类器比较简单时,AdaBoost 反而难以陷入过拟合。这也是为什么AdaBoost 的基础分类器经常选择使用树桩的原因。

2.3 AdaBoost 多分类

  1. 标准的AdaBoost算法只适用二类分类问题,可以将它推广到多分类问题。 有两种算法:

    • SAMME 算法:该算法不需要个体分类器输出类别的概率。
    • SAMME.R 算法:该算法需要个体分类器输出类别的概率。

2.3.1 SAMME 算法

  1. SAMME算法:

    • 输入:

      • 训练数据集
      • 弱学习算法
    • 输出:集成分类器

    • 算法步骤:

      • 初始化训练数据的权值分布

        • 使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器:

        • 计算 在训练数据集上的分类误差率:

        • 计算 的系数:

          因为系数 ,因此要求

        • 更新训练数据集的权值分布: 。其中:

          其中 为规范化因子,它使得 成为一个概率分布。

      • 构建基本分类器的线性组合,于是得到集成分类器:

  2. SAMME算法退化为标准的AdaBoost算法。

2.3.2 SAMME.R算法

  1. SAMME.R算法:

    • 输入:

      • 训练数据集
      • 弱学习算法
    • 输出:集成分类器

    • 算法步骤:

      • 初始化训练数据的权值分布

        • 使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器:

        • 计算 在训练数据集上的加权概率估计:

          其中:

          • 的真实标记。
          • 的权重。
          • 刻画基本分类器 预测 的输出为类别 的概率的加权值。
        • 和类别 ,定义:

          它刻画了: 预测的输出类别为 的概率加权值的对数 ,距离所有概率加权值对数的均值 的距离。

        • 更新训练数据集的权值分布: 。其中:

        • 归一化训练数据集的权值分布 ,使得权值之和为 1 。

      • 构建基本分类器的线性组合,于是得到集成分类器:

2.4 Adaboost 回归

  1. Adaboost 的回归问题有很多变种,这里介绍AdaBoost R2 算法。

  2. AdaBoost R2 回归算法:

    • 输入:

      • 训练数据集
      • 弱学习算法
    • 输出:集成回归器

    • 算法步骤:

      • 初始化训练数据的权值分布

        • 使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本回归器:

        • 计算 在训练数据集上的误差:

          它就是所有样本的回归误差的加权和。

          其中 为误差绝对值的最大值,通过它来对所有的回归误差归一化。

        • 计算 的系数:

          该系数表示 在集成回归器中的重要性。

          它是 的单调减函数,说明误差越小的基本回归器,其重要性越高。

        • 更新训练数据集的权值分布: 。其中:

          为规范化因子,它使得 成为一个概率分布 。

      • 构建基本回归器的线性组合 ,于是得到集成回归器:

2.5 AdaBoost与加法模型

2.5.1 加法模型

  1. AdaBoost 算法可以认为是:模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。

    其中指数损失函数为:

  2. 考虑加法模型 ,其中 为基函数、 为基函数的参数、 为基函数的系数。

    给定训练数据以及损失函数 的条件下,根据经验风险极小化(即:损失函数极小化)准测来学习加法模型

  3. 这是个复杂的最优化问题,通常可以采用前向分步算法求解。

    前向分步算法求解这一优化问题的思想是:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数,则可以简化优化的复杂度。

    具体地,每一步只需要优化如下的损失函数: