集成学习ensemble learning
是通过构建并结合多个学习器来完成学习任务。其一般结构为:
先产生一组“个体学习器”(individual learner
) 。个体学习器通常由一种或者多种现有的学习算法从训练数据中产生。
如果个体学习器都是从某一种学习算法从训练数据中产生,则称这样的集成学习是同质的homogenerous
。
此时的个体学习器也称作基学习器base learner
,相应的学习算法称作基学习算法。
如果个体学习器是从某几种学习算法从训练数据中产生,则称这样的集成学习是异质的heterogenous
。
再使用某种策略将它们结合起来。集成学习通过将多个学习器进行组合,通常可以获得比单一学习器显著优越的泛化性能。
通常选取个体学习器的准则是:
通常基于实际考虑,往往使用预测能力较强的个体学习器(即强学习器,与之对应的为弱学习器)。
强学习器的一个显著的好处就是可以使用较少数量的个体学习器来集成就可以获得很好的效果。
根据个体学习器的生成方式,目前的集成学习方法大概可以分作两类:
Boosting
为代表。Bagging
和随机森林Random Forest
为代表。考虑一个二类分类问题。设单个样本为 ,真实类别为 。
假定基类分类器的错误率为 ,即对每个基分类器 有: 。
假设集成学习通过简单投票法结合 个基分类器 。即:若有超过半数的基分类器正确,则集成分类就正确。根据描述,给出集成学习器为: 。
集成学习器预测错误的条件为: 个基分类器预测正确,其中 (即:少于一半的基分类器预测正确), 个基分类器预测错误。
假设基分类器的错误率相互独立,则集成学习器预测错误的概率为: 。
根据Hoeffding
不等式有: 。
可以看出:随着 , 集成学习器预测错误的概率 。
上述推论有非常关键的一个地方:假设基分类器的错误率相互独立。
实际上个体学习器是为了解决同一个问题训练出来的,而且可能是同一类算法从同一个训练集中产生。
这样个体学习器的错误率显然不能相互独立。
实际上个体学习器的准确性和多样性本身就存在冲突。
提升方法(boosting
) 是一种常用的统计学习方法。在分类问题中,它通过改变训练样本的权重学习多个分类器,并将这些分类器们进行线性组合来提高分类的能力。
提升方法的基本思想是:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家单独的判断要好。类似于”三个臭皮匠顶一个诸葛亮“。
提升方法的理论基础是:强可学习与弱可学习是等价的。
在概率近似正确(probably approximately correct,PAC
)学习的框架下:
可以证明:强可学习与弱可学习是等价的。
即:若在学习中发现了 ”弱学习算法“ ,则可以通过某些办法将它提升为 ”强学习算法“。
对于分类问题而言,求一个比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)要容易得多。
Boosting
就是一族可以将弱学习器提升为强学习器的算法。
这族算法的工作原理类似:
M
。M
个基学习器进行加权组合。Boosting
族算法最著名的代表是AdaBoost
算法。
AdaBoot
算法两个核心步骤:
每一轮中如何改变训练数据的权值?
AdaBoost
算法提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。
于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。
最后如何将一系列弱分类器组合成一个强分类器?
AdaBoost
采用加权多数表决的方法:
AdaBoost
算法有两个特点:
不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基本分类器的学习中起不同作用。
AdaBoost
要求基本学习器能够对特定的数据分布进行学习,这一般是在学习的时候为每个训练样本赋予一个权重。利用基本分类器的线性组合 构成最终分类器:
其中:
AdaBoost
算法具有自适应性,即它能够自动适应弱分类器各自的训练误差率,这也是它的名字(适应的提升)的由来。
AdaBoost
算法:
输入:
输出:集成分类器
算法步骤:
初始化训练数据的权值分布 。
对
使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器: 。
计算 在训练数据集上的分类误差率: 。
它就是所有误分类点的权重之和。其中权重越大的误差分类点,其在误差率中占比越大。
若 ,算法终止,构建失败!
计算 的系数: 。
该系数表示 在集成分类器中的重要性。它是 的单调减函数,说明误差越小的基本分类器,其重要性越高。
根据系数大于零要求 。
更新训练数据集的权值分布: 。其中:
为规范化因子,它使得 成为一个概率分布 。
构建基本分类器的线性组合: ,于是得到集成分类器: 。
为防止过拟合,AdaBoost
通常会加入正则化项。该正则化项称作步长或者学习率,定义为 。
考虑正则化项之后,模型的更新方式为: 。
AdaBoost
提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。
这是通过更新训练数据集的权值分布 来实现的。其中:
两者比较,误分类样本的权重是正确分类样本的权重的 倍。于是误分类样本在下一轮学习中权重更大。
集成分类器 结合 个基本分类器的方式为加权表决。
系数 表示了基本分类器 的重要性。其中:
由于 是分类误差率 的单调递减函数,因此:
AdaBoost
加大分类误差率较小的弱分类器的权值,使得它在表决中起较大作用。AdaBoost
减小分类误差率较大的弱分类器的权值,使得它在表决中起较小的作用。定理一:AdaBoost
算法集成分类器的训练误差上界为:
这一定理说明:可以在每一轮选取适当的 使得 最小,从而使得训练误差下降最快。
定理二:二类分类 AdaBoost
的训练误差界:
其中 。
推论:若存在 ,对所有 有 ,则有:
这表明在此条件下 AdaBoost
的训练误差是以指数速率下降的。
上述定理都只是关于训练误差的分析,实际应用中更关系测试集的误差。
AdaBoost
算法也会出现过拟合,此时训练误差为 0 但是测试集的误差较大。
当AdaBoost
的基础分类器比较复杂时,AdaBoost
很容易陷入过拟合。
但是当AdaBoost
的基础分类器比较简单时,AdaBoost
反而难以陷入过拟合。这也是为什么AdaBoost
的基础分类器经常选择使用树桩的原因。
标准的AdaBoost
算法只适用二类分类问题,可以将它推广到多分类问题。 有两种算法:
SAMME
算法:该算法不需要个体分类器输出类别的概率。SAMME.R
算法:该算法需要个体分类器输出类别的概率。SAMME
算法:
输入:
输出:集成分类器
算法步骤:
初始化训练数据的权值分布 。
对
使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器: 。
计算 在训练数据集上的分类误差率: 。
计算 的系数: 。
因为系数 ,因此要求 。
更新训练数据集的权值分布: 。其中:
其中 为规范化因子,它使得 成为一个概率分布。
构建基本分类器的线性组合,于是得到集成分类器: 。
当 时SAMME
算法退化为标准的AdaBoost
算法。
SAMME.R
算法:
输入:
输出:集成分类器
算法步骤:
初始化训练数据的权值分布 。
对
使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本分类器: 。
计算 在训练数据集上的加权概率估计:
其中:
对 和类别 ,定义:
它刻画了: 预测的输出类别为 的概率加权值的对数 ,距离所有概率加权值对数的均值 的距离。
更新训练数据集的权值分布: 。其中:
归一化训练数据集的权值分布 ,使得权值之和为 1 。
构建基本分类器的线性组合,于是得到集成分类器: 。
Adaboost
的回归问题有很多变种,这里介绍AdaBoost R2
算法。
AdaBoost R2
回归算法:
输入:
输出:集成回归器
算法步骤:
初始化训练数据的权值分布 。
对
使用具有权值分布 的训练数据集学习,根据输入的弱学习算法得到基本回归器: 。
计算 在训练数据集上的误差:
它就是所有样本的回归误差的加权和。
其中 为误差绝对值的最大值,通过它来对所有的回归误差归一化。
计算 的系数: 。
该系数表示 在集成回归器中的重要性。
它是 的单调减函数,说明误差越小的基本回归器,其重要性越高。
更新训练数据集的权值分布: 。其中:
为规范化因子,它使得 成为一个概率分布 。
构建基本回归器的线性组合 ,于是得到集成回归器: 。
AdaBoost
算法可以认为是:模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。
其中指数损失函数为: 。
考虑加法模型 ,其中 为基函数、 为基函数的参数、 为基函数的系数。
给定训练数据以及损失函数 的条件下,根据经验风险极小化(即:损失函数极小化)准测来学习加法模型 :
这是个复杂的最优化问题,通常可以采用前向分步算法求解。
前向分步算法求解这一优化问题的思想是:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数,则可以简化优化的复杂度。
具体地,每一步只需要优化如下的损失函数: