contact@digquant.com.cn
400-1860-552
官方群:463071731
集成学习前传
本文来源于:王的机器微信公众号


引言


故事一


斯蒂文平时喜欢做做小投资,涉猎于外汇、商品和股票等几种资产类别。他投资的方式又很特别,自己不做基本面或者技术分析,而只是结合 (aggregate) 一些他的专业朋友 (小王、小张和小杨) 意见做一个决策。对于是否投资一个组合,他会问这三位的意见,但是他会根据不同的实际情况而用三种不同结合意见的方式:


  1. 如果只是主观的觉得他们在相同的程度上都很厉害,那么斯蒂文让他们投票,并将其意见均匀 (uniformly) 结合得到最终意见。比如小王反对投资,小张和小杨同意投资,因此斯蒂文最终决定要投资,这也是少数服从多数原则。


  2. 如果主观的觉得他们都很厉害,但还是有个强弱之分,那么斯蒂文让他们投票,并将其意见不均匀 (non-uniformly) 结合得到最终意见。比如小王反对投资,小张和小杨同意投资,但是斯蒂文觉得小王比他们两个加起来还是要厉害些,因此斯蒂文最终决定不投资,这也是加权少数服从加权多数原则。


  3. 如果他们有各自擅长的投资领域 (外汇、商品、股票),那么斯蒂文将他们的意见条件 (conditionally) 结合起来得到最终意见。比如小王擅长外汇类,小张擅长商品类而小杨擅长股票类,那么斯蒂文会根据这个投资组合的资产比重来听取他们的意见,如果组合里大都是

    • 外汇即期和远期,他听小王的

    • 黄金和原油商品,他听小张的

    • 苹果和谷歌股票,他听小杨的


这个故事告诉我们,如果已经得到了一些意见或假想 (hypothesis),我们可以将这些假想结合起来,有可能让预测效果变得更好。



故事二


斯蒂文职业是个幼教,一天他要教小朋友如何从一堆水果中辨识一堆苹果。现在斯蒂文有 10 张苹果图片和 10 张非苹果图片,如下图:

 


上图 20 个水果就是 20 个例子,斯蒂文告诉小朋友上面 10 个是苹果下面 10 个不是苹果。他的目的就是用这 20 个例子来教会小朋友识别苹果,也就是让小朋友学会提取苹果的特征,在看到新的水果一下子就能辨别它是否是苹果。


斯蒂文:看这幅图,你怎么来描述苹果?

小明:苹果是圆的。



小明认为“圆”是辨别苹果的一个特征,根据这个特征小明可以从香蕉里认出苹果,因为香蕉不是圆的,但是这个特征永远适用吗?不!小明用“圆”特征来认苹果可能会犯两种错误:

 

  1. 没认出不圆的苹果 (灰色叉叉)

  2. 误认了圆的非苹果 (粉色叉叉)


斯蒂文记下了小明犯了错的图并将其放大,同时也缩小了小明没犯错的图,展示如下:



这是辨识苹果第一个特征是“苹果是圆的”,接着斯蒂文问小芳。


斯蒂文:除小明说的以外,你还能怎样描述苹果?

小芳:苹果是红的。


注意,小芳看的图和小明看的图不大一样,因为斯蒂文根据小明的作答,放大小明犯错误的图而缩小没有犯错的图,因此小芳 (任何人类) 都会把注意力放在大图上。在那些大图里,的确“红”是一个很好的特征来区分苹果和其它水果

 


但是“红”这个特征是否适用那些小图 (即小明没犯错的图)?不!小芳用“红”特征来认苹果可能会犯两种错误:

 

  1. 没认出不红 (绿) 的苹果 (灰色叉叉)

  2. 误认了红的非苹果 (粉色叉叉)


斯蒂文又记下了小芳犯了错的图并将其放大,同时也缩小了小芳没犯错的图,展示如下:



现在辨识苹果特征是“苹果有些是圆的,有些是红的”,接着斯蒂文问小刚。

 

斯蒂文:除小明小芳说的以外,你还能怎样描述苹果?

小刚:苹果是绿的。


诚然,在那些大图里,的确“绿”是一个很好的特征来区分苹果和其它水果。



但是“绿”这个特征是否适用那些小图 (即小芳没犯错的图)?不不不!小刚用“绿”特征来认苹果可能会犯两种错误:


  1. 没认出不绿 (红) 的苹果 (很多灰色叉叉)

  2. 误认了绿的非苹果 (粉色叉叉)


斯蒂文又记下了小刚犯了错的图并将其放大,同时也缩小了小刚没犯错的图,展示如下:



现在辨识苹果特征是“苹果有些是圆的,有些是红的,有些是绿的”,接着斯蒂文问小静。


斯蒂文:除小明小芳小刚说的以外,你还能怎样描述苹果?

小静:苹果带把儿。


在那些大图里,的确“带把儿”是一个很好的特征来区分苹果和其它水果



现在辨识苹果特征是“苹果有些是圆的,有些是红的,有些是绿的,带把儿”。斯蒂文当然还可以继续问小朋友,随着这个过程,小朋友学到的如何辨识苹果的特征会越来越全。即便每个小朋友只能从一个方面辨识苹果,但是结合起来的结论不得了,有可能比一个专家来辨识苹果还要准确。这个过程就是个增强或提升 (boosting) 过程。



本贴关注的是当你有了一群弱鸡假想 h,是否可以将其用某种方式结合成战斗机假想 H?第一章从结合入手 – 细讲假想的不同结合类型,第二、三章从方式入手 – 分别解释装袋法和提升法。



第一章 - 结合假想


1.1 语文和数学


假设现在有 T 个假想函数 ht(x),其中 t = 1, 2 ,…, T,那么定义 H(x) 是它们以某种方式结合的假想函数。引言故事一的三种结合假想方式都是描述分类问题的 (决定投资还是不决定投资),而假想也可以处理回归问题,下面列举了它们的在这两类问题 (分类、回归和三种结合方式 (均匀、非均匀、条件的数学表示形式:


均匀结合


对于分类问题,给每个假想的预测分类 (1为正类,-1为负类) 一票,再综合所有的票数;对于回归问题,平均每个假想的预测值 (实数)。



非均匀结合


对于分类问题,根据每个假想不同信任程度给它们的预测分类 (1为正类,-1为负类) 不同的票数,再综合所有的票数;对于回归问题,用常系数来线性组合每个假想的预测值 (实数)。



显然均匀结合非均匀结合的特例,对分类问题,将 wt 设为 1;对回归问题,将 w设为 1/T。


条件结合


对于分类问题,根据每个假想在不同的条件下,给它们的预测分类 (1为正类,-1为负类) 不同的票数,再综合所有的票数;对于回归问题,用函数系数来线性组合每个假想的预测值 (实数)。

 


显然非均匀结合条件结合的特例,对分类和回归问题,将 ct(x) 设为 wt,因此均匀结合非均匀结合条件结合的特例。


一般来说,将良莠不齐的东西掺到一起,那么通常结果是比最坏的好一些,比最好的坏一些。把多个假想结合起来,如何能获得比最好的单一假想更好的性能呢?请看下面两小节。


1.2 准确和多样


本小节解释在分类问题中,为什么结合比不结合好?

 

考虑下面例子:假设我们有三个分类器 (三个假想) 的表现,其中蓝色表示分类正确,红色表示分类错误,结合方式是均匀结合,即少数服从多数。


 

由上图可看出

 

  • 图 1 中假想都只有 66.6% 的精度,但是没在一起犯错误,结合之后精度可达100%

  • 图 2 中假想完全一样,都是 66.6% 的精度,因此结合之后精度没有提高

  • 图 3 中假想都只有 33.3% 的精度,但是在一起犯错误,结合之后精度为 0%

 

根据上例我们有种感觉,好的结合要求每个假想“好而不同”,“好”指的是假想要有“准确性”,不能像一个丢硬币一样的只有随机 50% 准确性;“不同”指的是假想要有“多样性”,即它们之间必须要具有差异。总结来说,这些假想每个性能不能太差,而相互之间越独立越好。


1.3 独裁和民主 


本小节解释在回归问题中,为什么结合比不结合好?

 

首先定义

 

    ht(x) = 某个假想函数

    f(x) = 真实函数

    H(x) = 结合函数

 

其中 H(x) 是所有假想函数 ht(x) 的平均,数学上有


这里符号 E 的滥用是为了后面推导简便,注意 E[] 不是求期望值,而是表示算数平均。


现在我们想看看“独裁的一己之见 ht 和真实意见 f 的误差的平均”和“民主的共识 H 和真实意见 f 的误差”的大小关系,见下面推导:



上面公式转成文字就是,“独裁的一己之见 ht 和真实意见 f 的误差的平均”比“民主的共识 H 真实意见 f 的误差”的大。也说明共识 H 的表现比平均的一己之见 ht 的表现要好 (有可能 H 的表现没有最好的 ht 的表现好,但是一定比平均的 ht 的表现好)上一句的结论非常非常非常重要


此外,根据偏差和方差的定义:


  • 偏差 = H  – f,代表了共识 H 和真实 f 的差距

  • 方差 = E[(ht – H)2],代表了不同意见 ht 和共识 H 差别多大,ht 多么分散


将它们带入上式可得



由此可知,均匀结合的目的就是想办法消除方差的过程,得到更稳定的表现。


1.4 学习并结合


之前我们讲的结合假想都是假设事先已经得到一群 (弱鸡) 假想 h,然后结合成 (战斗机) 假想 H。现在我们可不可以一边学习 h,一边将这些 h 结合起来?很显然假想 h 必须要不同,而且可以不同在以下几个方面:

  • 模型不同 – h1 是来自决策树模型,h是来自对率分类模型

  • 参数不同 – ht 都是来自正规化线性回归模型,但是惩罚参数不同,从 λ = 0.01, 0.1, 1, 10, …, 10000

  • 算法不同 – 算法有随机的成分,像随机初始值

  • 数据不同 – h用的训练集,h用的验证集


在本贴中,我们只关注因数据不同而导致的不同假想 h,换句话说就是它们模型、参数和算法都相同。给定一份数据,除了随机划分训练集和验证集以外,还有两种方法可以给数据注入变动性 (variability):

 

  1. 装袋法 (bagging) 里的自助采样 (bootstrap sampling)

  2. 提升法 (boosting) 里的最优加权 (optimal weighting)

 

在变动数据的过程中,切记要保证数据集的多样性或独立性。一边变动数据一边训练一个弱鸡假想 h,最终结合它们成一个战斗机假想 H。下面两章就来浅谈装袋法和提升法里面不同的变动数据方法,以及它们结合假想的方式。


第二章 - 装袋法


装袋法是由英文 bagging 而来的,而它是 bootstrap aggregating 的缩写,这个词组的意思是自助结合法,顾名思义,就是先对数据进行 (多次) 自助采样,再在每个新样本集上训练模型并结合起来。其中模型结合已在第一章详细阐述,而本章着重解释自助采样,在这之前先了解一个重要而几乎等价的概念,重置抽样 (sample with replacement)。


2.1 基本概念


重置抽样是从总体中抽取一个样本进观察、纪录后,再放回总体中,然后再抽取下一个样本,这样连续抽取样本的方法。可见,总体样本数在抽选过程中始终未减少,总体上各样本被抽中的可能性前后相同,而且各样本有被重复抽中的可能。


2.2 自助采样


如果重置抽样看成是一个抽象概念,那么自助采样就是它的一个具体实施。其采样过程是从含有 个样本的总体进行 次重置抽样 (n 可以小于等于 N),组成一个含有 个样本的自助样本集。


用以下含有 8 个样本的数据集为例:



一个含有样本数为 4 的自助样本集的可能形式如下:



一个含有样本数为 8 的自助样本集的可能形式如下:


 

需要注意的是,上述重复抽样中,样本 2 出现了两次,而样本 3 没有出现,概率是 (1-1/8)8 = 34.4%。


现在扩展到在一个样本数量为 N 的数据集,而自助样本集的样本数量也为 N,那么没有被选到的样本大概占 (1 – 1/N)N,当 N 很大时,有下列极限公式



因此每次做这样一次自助采样,里面只有 63.2% 的数据被选中当训练数据,剩下 36.8% 没被选中的可以自动作为验证数据。


2.3 结合假想


根据 1.2 小节得到的结论,共识 H 比单一意见 (假想) h 要好。但问题来了,在 1.4 小节我们知道要训练出不同的假想需要不同的数据集,但是我们现在只有一套数据集可用,那么该如何做呢?自助采样!上一节只是举了自助采样了一套样本为 N 的数据集,我们将其过程重复 T 次不就拿到了 T 套数据集了吗?接着在这 T 套数据集上训练出一系列假想 h(t = 1, 2, …, T) 并将它们结合:


分类问题 (用投票方式)



回归问题 (用平均方式)



装袋法的算法流程如下:




第三章 - 提升法


装袋法的结合法是均匀结合,即每个假想的权重一样大,而提升法的结合法是非均匀结合,即每个假想的权重不一样大。本章着重解释如何找到一个最优权重 (optimal weight),在这之前先了解两个重要的概念,加权数据 (weighted data)、加权分类误差率 (weighted misclassification error,WME) 和随机二分类器 (random binary classifier)。


3.1 基本概念


加权数据就是给每个数据赋予一个权重值,下图给出未加权数据和加权数据的直观比较。



右表的数据是加权数据,比如第一个样例权重 0.5,意思是这个样例的重要性变成原来 0.5 倍;第二个样例权重 3,意思是这个样例的重要性变成原来 3 倍;第四个样例权重 1,意思是这个样例的重要性没有变。


加权分类误差率是在加权数据上分类的误差率,假设我们对样例 1 和 3 都预测错误,下图给出分类误差率和加权分类误差率的直观比较。



从加权分类误差率公式可看出,在一个权重很大的样例上犯错误会增大很多误差。反之会减小很多误差。


随机二分类器就是错误率为 50% 的分类器,试想当你预测正类反类时,你借助扔硬币来决定,如果正面朝上你预测正类,反面朝上你预测反类,这样一个“分类器”就是随机二分类器。很显然这是个垃圾分类器,它甚至比错误率 90% 或 99% 的分类器差很多。如果你有个预测股票涨跌但错误率 99% 的分类器请告诉我,我只用和这个分类器的预测结果反向操作就能得到错误率 1%。说这么多就是为了强调错误率为 50% 的分类器是最糟糕的。


3.2 最优加权


装袋法是通过自助采样来多样化假想,提升法我们可以通过改变权重来多样化假想。提升法是按顺序的训练出一系列假想 ht (t = 1, 2, …, T),每个假想都是当前的最优假想 (加权分类误差率最小)。我们先把注意力集中在从 t 轮到 t+1 轮时 ht 和 ht+1 的加权分类误差率:



现在试想,如果 ht 使用 u(i)t+1 进行加权的结果效果非常不好,那么使用 u(i)t+1 得到的 ht+1 就会和 ht 非常不一样,那么就得到了和 ht 差别很大的 ht+1。其方法就是:让 ht 在下一轮的权重u(i)t+1 之下,表现很差。


让 ht 的表现很差是什么意思?就是 ht 的表现是随机的 (通过找到 t+1 轮是的最优权重),像随机二分类器的那样,错误率为 50%。现在的目标是希望



其中



由上式可知我们需要在 t+1 轮将“错误的权重和”等于“正确的权重和”。假如在 t 轮“错误的权重和”是38而“正确的权重和”是62,那么一个最简单的方法就是将“每个做错的样例的权重 u(i)t”乘上“正确率 62/100”,将“每个做对的样例的权重 u(i)t”乘上“错误率 38/100”,写成表达式为



这种更新权重就是最优加权方法,通过事先计算出来错误率 εt,然后将错分数据的权重乘上 (1-εt),将正确分类数据的权重乘上 εt 得到新的权重。现在我们等价的简化以上过程,引进一个放缩因子 (scaling factor) ct,然后将错分数据的权重乘上 ct (和 1-εt 成正比),将正确分类数据的权重除以 ct (和 εt 成反比) 得到新的权重,因此我们有



对于 t+1 轮的权重更新,我们可以写出以下等价表达形式



这里的 ct 有更清晰的物理意义,通常情况下 εt < 1/2 因为是学习之后分类器的错误率应该小于 50%,这样 ct 将大于 1;那么,犯错的数据权重将乘上大于 的数,正确的数据权重将除以大于 的数,使得提升了犯错数据的权重 (scale up incorrect),而降低做对数据的权重 (scale down correct),这就像引言故事二里老师做的事情,而使得学生更加专注在犯了错的地方,来得到不一样的假想。


3.3 结合假想


按照上小节的思路,当一系列假想 h(t = 1, 2, …, T) 时,将它们以非均匀方式结合:



现在的问题是 wt 是什么?基本的想法是,好的 ht 应该 wt 大一点,坏的 ht 应该  wt 小一点。我们知道好的 ht,它的错误率 εt 低,那么 ct 比较大,那么 wt 应该是 ct 的一个单调函数。设计这个算法的人将 wt 认为是 lnct,即



这个假想的系数 wt 也有物理意义:


  • 如果 εt = 1/2,那么 ct = 1,则 wt = 0,意思是随机二分类器 (错误率为 50%) 是一个坏的 ht,给 0 票,也就是不使用该 ht

  • 如果 εt = 0,那么 ct = ∞,则 wt = ∞,意思是错误率为 0 的情况,给它无限多票数,只用 h即可


这个算法全称叫做逐步提升法 (adaptive boosting,adaBoost),其算法流程如下:



第四章 - 集成学习


4.1 基本概念


将一系列假想结合起来学习,在机器学习上的术语叫做集成学习 (ensemble learning),而这些假想也可以称为个体学习器 (individual learner):


  • 如果它们是同质的 (homogenous),比如都是决策树,那么它们常称为可称为基学习器 (base learner)


  • 如果它们是异质的 (heterogenous),比如决策树和对率分类,那么它们常称为组件学习器 (component learner)


在前两章讲的装袋法和提升法用的学习器都是同质的,而后面要将的堆积法用的学习器是异质的。


4.2 装袋法和提升法


集成学习要好,个体学习器就不能太差,而且要相互独立。第一个性能条件比较容易实现,一般那些单一的学习器决策树、对率分类、支持向量机器的性能绝对比随机分类器性能好;第二个独立条件的实现稍微要花点功夫。


从假想独立性上来看,装袋法和提升法都在数据上做手脚而希望给假想带来独立性,但是

 

  • 装袋法用自助采样的数据集是随机的,然后认为从这些随机数据集训练出来的假想是独立的


  • 提升法用最优加权产生加权数据集,从而确保从这些数据集训练出来的假想是独立的

 

从训练时间上来看

 

  • 装袋法的各个假想可以并行生成,因此可以并行训练节省大量时间开销


  • 提升法的各个假想只能按顺序生成,对于像神经网络这样的模型,训练时间会非常长


从偏差和方差上来看


  • 装袋法的均匀结合的一大特点就是可以降低方差,因此该方法下的一系列假想可以是高方差低偏差 (复杂度高),比如没有修剪的决策树


  • 提升法那个例子里面的小朋友每个都弱弱的,每个人给出的答案里正确答案都差很远但是互相差别不远 (高偏差低方差),因此该方法下的一系列假想可以是高偏差低方差 (复杂度低),比如没有决策树桩


4.3 堆积法


除了装袋法和提升法,还有一种集成学习叫做堆积法 (stacking)。它的整个过程很像交叉验证,假设我们有 5 个一级学习器和 1 个二级学习器,将整个数据按 8 比 2 的比例分成训练集和测试集,然后再将训练集按 5 折交叉验证的方式分为 5 份。下图给出堆积法的完整流程。



  1. 计算新训练数据  首先将训练数据分为 5 份,接下来用 5 个一级假想 ht (t = 1, 2, …, 5) 进行 5 个迭代。每次迭代时,将 4 份数据作为 ht 进行训练,然后在剩下一份上进行预测。将 5 次迭代出来的预测数据来做新训练数据。


  2. 计算新预测数据  用  ht (t = 1, 2, …, 5)在测试数据上做预测并保存下来,求其平均当作新预测数据。


  3. 预测新数据 – 在新训练数据上训练出二级假想 H,并在新测试数据上做预测得到最后的输出。



总结和下帖预告


集成学习可分三类,即


  1. 同质的个体学习器低偏差高方差,用并行方法结合成的 bagging

  2. 同质的个体学习器高偏差低方差,用序列方法结合成的 boosting

  3. 异质的个体学习器低偏差高方差,用分堆方法结合成的 stacking

 

集成学习概念上遵循着“三个臭皮匠,顶个诸葛亮”的道理,即三个才能平庸的人,若能同心协力集思广益,也能提出比诸葛亮还周到的计策。然而,为了超越诸葛亮,集成学习里的 bagging 和 boosting 方法根据臭皮匠的特性而采取不同策略。


  • bagging 方法觉得臭皮匠是各有所短的弱鸡。如果他们弱在同处,那么其合体可能是一只更弱鸡;反之,根据均匀结合可得到一只战斗鸡


  • boosting 方法觉得臭皮匠是知错就改的弱鸡。如果他们都知错不改,那么其合体还是一只弱鸡;反之,根据非均匀结合可得到一只战斗鸡

回复 8/11 14:02

回复 8/11 14:00

回复 8/11 13:59

回复 8/11 13:56