【西瓜书】第八章 集成学习

本文是周志华老师《机器学习》第八章集成学习的学习笔记。　　

集成学习(ensemble learning)通过构建多个学习器来完成学习任务。一般来说，先产生一组个体学习器，再用某种策略将其结合。
当个体学习器均为同种类型的学习器时（如全都是决策树），我们称该集成为同质集成，此时称个体学习器为基学习器；否则称该集成为异质集成。

对于集成学习效果的理论保证，有一个简单的分析：
对于二分类问题，其真实函数为$f$ ，假定基分类器的错误为$\epsilon$ ，对于每个基分类器有：

$$P(h_i(x)\ne f(x))=\epsilon$$

假设我们的集成策略为简单投票法（超过半数基分类器分类正确，集成结果就正确）：

$$H(x)=sign(\sum_{i=1}^Th_i(x))$$

则根据Hoeffding不等式，集成的错误率为：

$$P(H(x)\ne f(x))=\sum_{k=0}^{\lfloor{T/2}\rfloor}C_T^k(1-\epsilon)^k\epsilon^{T-k}\le e^{-\frac{1}{2}T(1-2\epsilon)^2}$$

该式显示出，随着集成中个体分类器数目$T$ 的增大，集成的错误率将指数级下降。
Hoeffding不等式 :

对于相互独立的有界随机变量 $x_1,...,x_n$ ，若有$P(x_i \in [a_i, b_i])=1$ ，则

$$\bar{x}=\frac{x_1+...+x_n}{n}$$

满足不等式:

$$p(\bar{X}-E(\bar{X}))\lt exp(-2t^2n^2/\sum_{i=1}^n(b_i - a_i)^2)$$

需要注意的是，这里的有个假设为基学习器之间相互独立，但是现实中这一点往往不可能保证，所以集成学习研究的核心就是产生和集合“好而不同”的个体学习器。

分类

按照个体学习器的生成方式，当前的集成学习方法可以分为两大类：

• 个体学习器之间存在强依赖，串行生成的序列化方法（Boosting）
• 个体学习器之间不存在强依赖，并行化生成方法（Bagging/Random Forest）

Boosting

Boosting算法是一组能够将弱学习器提升为强学习其的算法，这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整。如此重复进行，直到基学习器数目达到事先指定的T，最终将这T个基学习器加权。
其中最著名的算法是AdaBoost。 其算法步骤如下图：

其思想在于加大当前基学习器学习错误的样本在下一轮学习中的权重（图中的第7步），也因此能适应弱分类器各自的训练误差（也就是为什么叫做ada(adaptive自适应)-boost）。该算法最为巧妙的一点在于将样本权重调整和基学习器的权重结合起来了。算法的推导在p174-176。
这里我们在迭代基学习器时采用的是重赋权法，对于无法接受带权样本的基学习器，我们可以使用重采样(resampling)来处理。

从偏差-方差分解的角度来看，Boosting主要关注降低偏差。

Bagging 与随机森林

Baggin算法

该算法基于bootstrap sampling，我们采样出T个含有m个训练样本的采样集，对每个采样集训练出一个基学习器,再将这些基学习器结合。
由于bootstrap sampling只用到初始数据集中63.2%的样本，所以，我们还有36%的数据可以用来做包外估计(out-of-bag estimate)。
从偏差-方差分解的角度来看，Bagging主要关注降低方差，因此它在易受样本扰动的学习器上效果更明显。
其实这里的Bagging主要就是做了一个数据扰动的工作。

随机森林

随机森林是在以决策树为基学习器的Bagging基础上，加入了特征扰动，或者说属性扰动，传统决策树每次在挑选划分属性时都是在当前结点的所有可能的n个属性中挑最优属性，而随机森林则是在其中随机选取k个属性，再从该子集中选择最优。如果k=n，则退化为传统决策树的Bagging，如果k=1，则为随机选择一个属性划分。一般推荐$k=log_2d$。

结合策略

学习器可能会从三个方面带来好处：

• 统计：减小单学习器泛化性能不佳的风险
• 计算：减小陷入局部最小的风险
• 表示：通过结合增加假设空间，更好应对真实假设在当前学习算法考虑的假设空间之外的情况
  
  对于结合策略而言，主要是有三类方法：
• 平均法：一般适用于回归计算等数值型输出，主要有简单平均和加权平均，在个体学习器性能相差较大时适宜采用加权平均，否则适宜简单平均。
• 投票法：一般适用于分类任务，主要有绝对多数投票(投票过半取其值)，相对多票(取得票最多)，加权投票等等。
• 学习法： stacking，简单来说就是上一级训练器的输出被当作样例输入特征，放到次级学习算法中去。研究表明，使用多响应线性回归（Multi-response Linear Regression,MLR）作为次级学习算法时效果会较好。

多样性

对于集成学习器的误差，我们可以用一个漂亮的式子来表示：

$$E=\bar{E}-\bar{A}$$

其中$\bar{A}$ 表示个体学习器的加权分歧值，$\bar{E}$ 表示个体学习器泛化误差的加权均值， 这二者我们有：

$$\bar{A}=\sum_{i=1}^T w_iA_i\qquad A_i=\int(h_i(x)-H(x))^2p(x)dx$$ $$\bar{E}=\sum_{i=1}^T w_iE_i\qquad E_i=\int(h_i(x)-f(x))^2p(x)dx$$

从这个优美的式子中我们可以看出个体学习器准确越高，多样性越大，集成越好，该式子我们称之为“误差-分歧分解”

多样性度量

对于多样性的度量，我们有几项指标，以二分类为例，假设我们有$h_i$,$h_j$两个分类器：

	h_i=1	h_i=-1
h_j=1	a	c
h_j=-1	b	d

那么我们给出如下度量：

• 不合度量： $$dis_{ij}=\frac{b+c}{m}$$
• 相关系数 $$\rho_{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$$
• Q-统计量 $$Q_{ij}=\frac{ad-bc}{ad+bc}$$
• $\kappa$-统计量 $$\kappa=\frac{p_1-p_2}{1-p_2}$$ 其中，p1是两个分类器一致的概率，p2是分类器偶然达成一致的概率： $$p_a=\frac{a+d}{m}\quadp_2=\frac{(a+b)(a+c)+(c+d)(b+d)}{m^2}$$

多样性增强

有了度量之后再来看看增强多样性的集中常用方法：

• 数据扰动： 通过采样选出不同的数据子集传给学习器，在对数据样本扰动敏感的基学习器上有较好效果，例如决策树和NN。但是对线性学习器，SVM，朴素贝叶斯，KNN效果不大。
• 属性扰动： 从高维属性空间做一个投影到低维属性空间后，将其输入，简单的做法可以仅仅从特征中取一个子集。随机森林中就用了该扰动。
• 输出表示扰动： 对输出的表示进行操纵，比如可以将分类输出转化为回归输出来构建个体学习器。
• 参数扰动： 随机设置不同的参数来得到不同的基学习器。
  值得注意的是，在各类数据竞赛中，前几名队伍往往最后都会用到集成学习做模型融合，但是在工业界，当数据量过大时，多模型融合往往较费计算力，因此采用的不是很多。

习题与答案

8.1

令$p-\delta = 1/2$ ,则有：

$$P(H(n)\le (p-\delta)n) = P(H(n)\le \frac{1}{2}n) \le e^{-2\delta^2n} \\ \le e^{-\frac{1}{2}(1-2p)^2n}\\ = exp(-\frac{1}{2}T(1-2\epsilon)^2)$$

得证

8.2

总损失函数有

$$L=l(-H(x)f(x))P(f(x)=1|x)+l(-H(x)f(x))P(f(x)=-1|x) \\ = l(-H(x))P(f(x)=1|x) + l(H(x))P(f(x)=-1|x)$$

要使$L$ 最小，那么$P(f(x)=1|x) > P(f(x)=0|x)$时，$l(-H(x))H(x)$$

8.3

占坑

8.4

• 相同：
  都是boosting算法，都是加法模型。

• 不同：
  Adaboost的损失函数是指数函数，通过求导来进行最小化损失函数。梯度boost则利用损失函数的负梯度来近似。不过也因此，GradientBoosting能处理损失函数更复杂的情况

8.5

占坑

8.6

本质上来讲Adaboost是通过调整数据分布来做数据扰动以提升学习器在上一轮迭代中出错数据的表现，但是朴素贝叶斯对数据扰动不敏感。

8.7

决策树的Bagging需要对节点所有属性进行考察（计算信息增益什么的），随机森林只需要考察其中随机抽取的一个子集。

8.8

首先MultiBoosting会比后者慢很多，因为需要训练多个AdaBoost学习器，但是相较来说后者的准确也没有前者高。