集成学习前传
引言
故事一
斯蒂文平时喜欢做做小投资，涉猎于外汇、商品和股票等几种资产类别。他投资的方式又很特别，自己不做基本面或者技术分析，而只是结合 (aggregate) 一些他的专业朋友 (小王、小张和小杨) 意见做一个决策。对于是否投资一个组合，他会问这三位的意见，但是他会根据不同的实际情况而用三种不同结合意见的方式：
如果只是主观的觉得他们在相同的程度上都很厉害，那么斯蒂文让他们投票，并将其意见均匀 (uniformly) 结合得到最终意见。比如小王反对投资，小张和小杨同意投资，因此斯蒂文最终决定要投资，这也是少数服从多数原则。
如果主观的觉得他们都很厉害，但还是有个强弱之分，那么斯蒂文让他们投票，并将其意见不均匀 (non-uniformly) 结合得到最终意见。比如小王反对投资，小张和小杨同意投资，但是斯蒂文觉得小王比他们两个加起来还是要厉害些，因此斯蒂文最终决定不投资，这也是加权少数服从加权多数原则。
如果他们有各自擅长的投资领域 (外汇、商品、股票)，那么斯蒂文将他们的意见条件 (conditionally) 结合起来得到最终意见。比如小王擅长外汇类，小张擅长商品类而小杨擅长股票类，那么斯蒂文会根据这个投资组合的资产比重来听取他们的意见，如果组合里大都是
外汇即期和远期，他听小王的
黄金和原油商品，他听小张的
苹果和谷歌股票，他听小杨的
这个故事告诉我们，如果已经得到了一些意见或假想 (hypothesis)，我们可以将这些假想结合起来，有可能让预测效果变得更好。
故事二
斯蒂文职业是个幼教，一天他要教小朋友如何从一堆水果中辨识一堆苹果。现在斯蒂文有 10 张苹果图片和 10 张非苹果图片，如下图：
上图 20 个水果就是 20 个例子，斯蒂文告诉小朋友上面 10 个是苹果下面 10 个不是苹果。他的目的就是用这 20 个例子来教会小朋友识别苹果，也就是让小朋友学会提取苹果的特征，在看到新的水果一下子就能辨别它是否是苹果。
斯蒂文：看这幅图，你怎么来描述苹果？
小明：苹果是圆的。
小明认为“圆”是辨别苹果的一个特征，根据这个特征小明可以从香蕉里认出苹果，因为香蕉不是圆的，但是这个特征永远适用吗？不！小明用“圆”特征来认苹果可能会犯两种错误：
没认出不圆的苹果 (灰色叉叉)
误认了圆的非苹果 (粉色叉叉)
斯蒂文记下了小明犯了错的图并将其放大，同时也缩小了小明没犯错的图，展示如下：
这是辨识苹果第一个特征是“苹果是圆的”，接着斯蒂文问小芳。
斯蒂文：除小明说的以外，你还能怎样描述苹果？
小芳：苹果是红的。
注意，小芳看的图和小明看的图不大一样，因为斯蒂文根据小明的作答，放大小明犯错误的图而缩小没有犯错的图，因此小芳 (任何人类) 都会把注意力放在大图上。在那些大图里，的确“红”是一个很好的特征来区分苹果和其它水果。
但是“红”这个特征是否适用那些小图 (即小明没犯错的图)？不！小芳用“红”特征来认苹果可能会犯两种错误：
没认出不红 (绿) 的苹果 (灰色叉叉)
误认了红的非苹果 (粉色叉叉)
斯蒂文又记下了小芳犯了错的图并将其放大，同时也缩小了小芳没犯错的图，展示如下：
现在辨识苹果特征是“苹果有些是圆的，有些是红的”，接着斯蒂文问小刚。
斯蒂文：除小明小芳说的以外，你还能怎样描述苹果？
小刚：苹果是绿的。
诚然，在那些大图里，的确“绿”是一个很好的特征来区分苹果和其它水果。
但是“绿”这个特征是否适用那些小图 (即小芳没犯错的图)？不不不！小刚用“绿”特征来认苹果可能会犯两种错误：
没认出不绿 (红) 的苹果 (很多灰色叉叉)
误认了绿的非苹果 (粉色叉叉)
斯蒂文又记下了小刚犯了错的图并将其放大，同时也缩小了小刚没犯错的图，展示如下：
现在辨识苹果特征是“苹果有些是圆的，有些是红的，有些是绿的”，接着斯蒂文问小静。
斯蒂文：除小明小芳小刚说的以外，你还能怎样描述苹果？
小静：苹果带把儿。
在那些大图里，的确“带把儿”是一个很好的特征来区分苹果和其它水果。
现在辨识苹果特征是“苹果有些是圆的，有些是红的，有些是绿的，带把儿”。斯蒂文当然还可以继续问小朋友，随着这个过程，小朋友学到的如何辨识苹果的特征会越来越全。即便每个小朋友只能从一个方面辨识苹果，但是结合起来的结论不得了，有可能比一个专家来辨识苹果还要准确。这个过程就是个增强或提升 (boosting) 过程。
本贴关注的是当你有了一群弱鸡假想 h，是否可以将其用某种方式结合成战斗机假想 H？第一章从结合入手 – 细讲假想的不同结合类型，第二、三章从方式入手 – 分别解释装袋法和提升法。
第一章 - 结合假想
1.1 语文和数学
假设现在有 T 个假想函数 ht(x)，其中 t = 1, 2 ,…, T，那么定义 H(x) 是它们以某种方式结合的假想函数。引言故事一的三种结合假想方式都是描述分类问题的 (决定投资还是不决定投资)，而假想也可以处理回归问题，下面列举了它们的在这两类问题 (分类、回归) 和三种结合方式 (均匀、非均匀、条件) 的数学表示形式：
均匀结合
对于分类问题，给每个假想的预测分类 (1为正类，-1为负类) 一票，再综合所有的票数；对于回归问题，平均每个假想的预测值 (实数)。
非均匀结合
对于分类问题，根据每个假想不同信任程度给它们的预测分类 (1为正类，-1为负类) 不同的票数，再综合所有的票数；对于回归问题，用常系数来线性组合每个假想的预测值 (实数)。
显然均匀结合是非均匀结合的特例，对分类问题，将 wt 设为 1；对回归问题，将 wt 设为 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 是来自决策树模型，h2 是来自对率分类模型
参数不同 – ht 都是来自正规化线性回归模型，但是惩罚参数不同，从 λ = 0.01, 0.1, 1, 10, …, 10000
算法不同 – 算法有随机的成分，像随机初始值
数据不同 – h1 用的训练集，h2 用的验证集
在本贴中，我们只关注因数据不同而导致的不同假想 h，换句话说就是它们模型、参数和算法都相同。给定一份数据，除了随机划分训练集和验证集以外，还有两种方法可以给数据注入变动性 (variability)：
装袋法 (bagging) 里的自助采样 (bootstrap sampling)
提升法 (boosting) 里的最优加权 (optimal weighting)
在变动数据的过程中，切记要保证数据集的多样性或独立性。一边变动数据一边训练一个弱鸡假想 h，最终结合它们成一个战斗机假想 H。下面两章就来浅谈装袋法和提升法里面不同的变动数据方法，以及它们结合假想的方式。
第二章 - 装袋法
装袋法是由英文 bagging 而来的，而它是 bootstrap aggregating 的缩写，这个词组的意思是自助结合法，顾名思义，就是先对数据进行 (多次) 自助采样，再在每个新样本集上训练模型并结合起来。其中模型结合已在第一章详细阐述，而本章着重解释自助采样，在这之前先了解一个重要而几乎等价的概念，重置抽样 (sample with replacement)。
2.1 基本概念
重置抽样是从总体中抽取一个样本进观察、纪录后，再放回总体中，然后再抽取下一个样本，这样连续抽取样本的方法。可见，总体样本数在抽选过程中始终未减少，总体上各样本被抽中的可能性前后相同，而且各样本有被重复抽中的可能。
2.2 自助采样
如果重置抽样看成是一个抽象概念，那么自助采样就是它的一个具体实施。其采样过程是从含有 N 个样本的总体进行 n 次重置抽样 (n 可以小于等于 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 套数据集上训练出一系列假想 ht (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；那么，犯错的数据权重将乘上大于 1 的数，正确的数据权重将除以大于 1 的数，使得提升了犯错数据的权重 (scale up incorrect)，而降低做对数据的权重 (scale down correct)，这就像引言故事二里老师做的事情，而使得学生更加专注在犯了错的地方，来得到不一样的假想。
3.3 结合假想
按照上小节的思路，当一系列假想 ht (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 的情况，给它无限多票数，只用 ht 即可
这个算法全称叫做逐步提升法 (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 份。下图给出堆积法的完整流程。
计算新训练数据 – 首先将训练数据分为 5 份，接下来用 5 个一级假想 ht (t = 1, 2, …, 5) 进行 5 个迭代。每次迭代时，将 4 份数据作为 ht 进行训练，然后在剩下一份上进行预测。将 5 次迭代出来的预测数据来做新训练数据。
计算新预测数据 – 用 ht (t = 1, 2, …, 5)在测试数据上做预测并保存下来，求其平均当作新预测数据。
预测新数据 – 在新训练数据上训练出二级假想 H，并在新测试数据上做预测得到最后的输出。
总结和下帖预告
集成学习可分三类，即
同质的个体学习器低偏差高方差，用并行方法结合成的 bagging
同质的个体学习器高偏差低方差，用序列方法结合成的 boosting
异质的个体学习器低偏差高方差，用分堆方法结合成的 stacking
集成学习概念上遵循着“三个臭皮匠，顶个诸葛亮”的道理，即三个才能平庸的人，若能同心协力集思广益，也能提出比诸葛亮还周到的计策。然而，为了超越诸葛亮，集成学习里的 bagging 和 boosting 方法根据臭皮匠的特性而采取不同策略。
bagging 方法觉得臭皮匠是各有所短的弱鸡。如果他们弱在同处，那么其合体可能是一只更弱鸡；反之，根据均匀结合可得到一只战斗鸡
boosting 方法觉得臭皮匠是知错就改的弱鸡。如果他们都知错不改，那么其合体还是一只弱鸡；反之，根据非均匀结合可得到一只战斗鸡
下一贴讲“集成树”，即将这些集成方法运用在决策树或决策树桩上，主要介绍 bagging 版本的随机森林 (random forest, RF)和 boosting 版本的梯度提升树 (gradient boosted tree, GBT)。Stay Tuned!