周志华先生《机器学习》一书学习笔记
记录学习过程
本博客记录Chapter8

1 个体与集成

集成学习（ensemble learning）：通过构建多个学习器来完成学习的任务。可以分成同质集成/异质集成。

• 同质集成（homogeneous）：个体学习器都是同种类型的。该类型中个体学习器称为“基学习器”（base learning algorithm）。
  
• 异质集成（heterogeneous）：包含不同类型的个体学习器。该类型中个体学习器称为“组件学习器”（component learner）。
  

集成学习通过组合多个学习器可以获得比单个学习器明显更好的泛化性能，这对于弱学习器（弱学习器是泛化性能略好于随机猜测的学习器）来说更为明显。

一般经验中，如果把好坏不等的东西掺和到一起，那么通常结果会是比最好的差一点，比最差的好一点。集成学习能获得好于最好的单一学习器的性能的原因如下：考虑二分类问题，集成学习的结果通过投票法来产生，即少数服从多数。要获得好的集成，个体学习器应该“好而不同”：即个体学习器要有一定的准确性，同时要有多样性（persity），学习器之间应该具有差异。

++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++

为简单分析，考虑二分类问题和实函数，假设基分类器的错误率为，即对于每个基分类器：

假设基分类器通过简单的投票方法组合，如果一半以上的基分类器分类正确，则集成分类正确：

假设基分类器的错误率相互独立，则由Hoeffding不等式有，集成错误率为

上式体现出，随着个体分类器数目的增大，集成错误率将指数级下降，最终趋向于0。但我们要注意到假设中基学习器的误差相互独立，在现实任务中，个体学习器是为了解决同一个问题训练出来的，因此显然不会相互独立。所以如何产生并结合“好而不同”的学习器，是集成学习研究的核心。

根据个体学习器的生成方式，目前的集成学习方法大致可以分为两类：

• 个体学习器间存在强依赖关系、必须串行生成的序列化方法：Boosting
  
• 个体学习器间不存在强依赖关系、可同时生成的并行化方法：Bagging和“随机森林”(Random Forest)。
  

2 Boosting

Boosting算法的工作机制类似：先根据初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复，直到基学习器的数目先到达，最终将个学习器进行加权结合。

Boosting族算法中的代表算法是AdaBoost算法。可以采用“加性模型”，即基学习器的线性组合

最小化指数损失函数：

该损失函数是指，若和的预测结果一致，则其乘积为1，其负数的指数就会越小。

如果可以最小化指数损失函数，则求对指数损失函数的偏导：

令偏导为0可得：

所以有：

这意味着达到了贝叶斯最优错误率。即指数损失函数可以替代原本的0/1损失函数。

++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++

再AdaBoost算法中，第一个基分类器是直接将基学习算法用于初始数据分布得到的。此后迭代地生产和，当基分类器基于分布产生后，该分类器的权重应该使得最小化指数损失函数：

导出指数损失函数：

令上式为0，得到权重更新公式：

+++

AdaBoost算法在得到之后样本分布将进行调整，使得下一轮的基学习器能够纠正的一些错误。方法是最小化，可以简化为：

注意，使用泰勒展开我们得到：

所以理想的基础学习者

让表示一个分布，我们有

理想的将在分布下最小化分类误差。因此弱分类器将基于分布来训练。且针对的分类误差应该小于0.5。

++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++

综上，我们推导了权重更新公式、分布更新公式、损失函数，得到AdaBoost的完整过程：

Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法”(re-weighting)实施，即在训练过程的每一轮中, 根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基学习算法，则可通过“重采样法”(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。

一般而言，这两种做法没有显著的优劣差别。需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件(例如检查当前基分类器是否是比随机猜测好)，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止.在此种情形下，初始设置的学习轮数T也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用“重采样法”，则可获得“重启动”机会以避免训练过程过早停止，即在拋弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的T轮完成。

从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

3 Bagging与随机森林

为了获得一个泛化良好的集成，集成中的各个学习器应该尽可能地相互独立。可以使用重叠的样本子集来训练不同的基础学习器。

3.1 Bagging

Bagging是并行式集成学习方法最著名的代表。直接基于自主采样法（bootstrap sampling，每次随机从样本集中抽取一个样本，再把样本放回初始数据集）。初始训练集中约有63.2%的样本出现在采样集。

按照该方法，我们可以采样出个含有个训练样本的采样集，基于每个采样集训练出一个基学习器。Bagging往往采用简单投票法（分类）/简单平均法（回归）对多个基学习器的结果进行决策。从偏差-方差分解的角度看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

3.2 随机森林

随即森林（Random Forest）是Bagging的基础上的一个扩展变体。其在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体而言，传统决策书在选择属性进行划分时，会根据当前节点的属性集选择最优属性；在随机森林中，对于基础决策树的每个节点，首先选择节点的属性。从集合中随机选择一个包含属性的子集，然后从这个子集中选择一个最优属性进行划分。这里的参数控制引入的随机性程度。一般推荐。

随机森林简单、容易实现、计算开销小，令人惊奇的是，它在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”。可以看出，随机森林对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动(通过对初始训练集采样)而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

4 组合策略

假设集成包含学习者，其中在示例上输出。

4.1 平均法

简单平均法：

加权平均法：

4.2 投票法

绝对多数投票法：如果一个代币获得超过一半的选票，则预测为该代币。提供了拒绝预测，是学习具有高可靠性要求的任务的良好机制。

相对多数投票法：以最多票标记

加权投票方式：

4.3 学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器（meta-learner）。

Stacking先从初始数据集训练出初级学习器，然后“生成”一个新数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。

有研究表明，采用初基学习器的输出类概率作为茨基学习器的输入属性，用多响应线性回归（Multi-response Linear Regression, MLR）作为次级学习算法的效果较好。

5 多样性

5.1 误差-分歧分解

假设我们使用个体学习器将加权平均法生成的集成组合完成回归学习任务，例如，定义学习器的“散度”为：

那么综合散度为：

$$
\bar A(h|x)=\sum_{i=1}^Tw_iA(h_i|x)\
=\sum_{i=1}Tw_i(h_i(x)-H(x))2

$$

Divergence表示个体学习者在样本上的不一致性，即在一定程度上反映了个体学习者的多样性。单个学习器和集成的平方误差为：

让表示个体学习者错误的加权平均值，我们有
$$

\bar A(h|x)=\sum_{i=1}^Tw_iE(h_i|x)-E(H|x)\
=\bar E(h|x)-E(H|x)

$$

令表示样本的概率密度，那么在全样本上我们有

类似地，单个学习器在全样本上的泛化误差和散度项为：

集成的泛化误差为

令表示个体学习者的加权散度值，我们有

这个公式意味着个体学习器的准确率越高，多样性越大，集成越好。但是，我们很难通过“误差-散度分解”直接优化目标，因为不是直接可操作的多样性度量，只能在构建集成后进行估计。而上述推导只适用于回归，不适用于分类。

5.2 多样性度量

多样性度量（persity measure）：估算个体学习器的多样化程度。常用做法是考虑个体分类器的两两相似/不相似性。

给定数据集，对于二分类任务，分类器和的预测结果列联表为：

其中，表示两个分类器预测结果均为+1的样本数目，且，常用的多样性度量：

• 分歧指标：
  
  
• 相关系数：
  
  
• Q-统计量：
  
  
• -统计：是分类器达成一致的概率，是分类器偶然达​​成一致的概率。
  
  

5.3 多样性增强

• 数据样本扰动：例如Bagging中采用自主采样，AdaBoost中采用序列采样
  
• 输入属性扰动：随机森林，每次随机抽取属性…
  
• 输出表示扰动：翻转法（随机标注本世纪的一些训练样本）；输出调制方法（将分类输出转换为回归输出）等
  
• 算法参数扰动：神经网络中隐藏神经元的数量…