集成学习

个体与集成

集成学习通过构建并结合多个学习器来完成学习任务，以下图为例，集成学习时先产生一组个体学习器，然后通过某种策略将其结合起来。如果其中的个体学习器是同种类型的，则是同质集成，否则叫异质的，

集成学习的结果是通过投票法产生的，为了使得集成学习的效果比单一学习器更好，应该要保证个体学习器具备一定的准确性，同时要有多样性，则学习器之间具有差异。

假设存在二分类问题和真实函数f，如果基分类器的错误率为\(\epsilon\)，则对于每个分类器hi有： \[ P(h_i(x) \ne f(x)) = \epsilon \] 如果基分类器的错误率相互独立，那么集成学习的错误率有： \[ P(h_i(x) \ne f(x)) = \sum_{k=0}^{[T/2]} C_T^k (1-\epsilon)^k \epsilon^{T-k} \\ \leq exp(-1/2T(1-2\epsilon)^2) \] 可以看到随着个体学习器数目的增加，集成的错误率降指数下降。

但往往基学习器的误差不是相互独立的，而且一般准确性很高的话，要增加多样性就必须牺牲准确性，

目前集成学习中，个体学习强依赖的代表是Boosting，而非强依赖的代表是Bagging和Random Forest。

Boosting

Boosting是将弱学习器提升为强学习器的算法：先从初始训练集中训练出一个基学习器，然后根据该学习器的表现对训练样本的分布进行调整，根据调整后的样本分布来训练下一个基学习器。

Boost的代表是AdaBoost。

AdaBoost有多种推导方式，我们这里采用基学习器的线性组合： \[ H(x) = \sum_{t=1}^T\alpha_th_t(x) \] AdaBoost的算法如下：

给定一个训练数据集D={(x1,y1), (x2,y2)…(xN,yN)}，yi属于标记集合{-1,+1}。

\(D_1(x) = 1/m\)，每一个训练样本最开始时都被赋予相同的权值：1/N；
进行多轮迭代，假设迭代T次。for t = 1, 2, .. ,T

\(h_t = \xi(D, D_t);\)基于分布\(D_t\)从数据集中训练出分类器\(h_t\)；
\(\epsilon_{t} = P_{x-D_t}(h_t(x)\ne f(x));\)计算分类器的错误率；
如果错误率比随机猜测还要差，那么意味着当前的基学习器不满足基本条件，放弃该学习器；
\(\alpha_t = 1/2 ln(\frac{1-\epsilon_t}{\epsilon_t})\)；确定该分类器的权重；
\(D_{t+1}(x) = \frac{D_t(x) exp(-\alpha_tf(x)h_t(x))}{Z_t}\)；更新样本的权重，其中Z是一个规范化因子，以确保\(D_{t+1}\)是一个分布；每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确；

输出\(H(x)=sign(\sum_{t=1}^T \alpha_th_t(x))\)；

若H(x)能令指数损失函数最小化，可以求偏导： \[ \frac {\alpha l_{exp}(H|D)} {\alpha H(x)} = -e^{-H(x)} P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) \] 令上式为0，可求解： \[ H(x) = 1/2 ln \frac{P(f(x)=1|x)}{P(f(x)=-1|x)} \] 依赖这个式子，我们可以求得分类器权重的更新公式。

对于无法重新赋权的训练样本，可以通过重新采样的方法来处理。如上所述，如果初始设置的学习轮数还没到T，可能导致只包含少量基学习器而性能不佳的情况。重采样可以在抛弃不满足基本条件的基学习器之后，根据当前分布重新对样本进行采样，再基于采样结果训练出基学习器，使得学习过程可以在T轮完成。

Boosting主要关注降低偏差，可以基于泛化能力较弱的学习器构建出强的集成。

Bagging与随机森林

为了得到泛化能力强的集成，集成中的个体学习器应该尽可能独立，一种可能的做法是进行随机取样，根据不同的样本训练得到相对独立的基学习器。但这种做法又可能因为数据量不够而导致学习器的准确性不够高。

Bagging

bagging是一种并行式的集成学习方法。给定m个样本的数据集，我们每次随机从中抽出一个样本放入采样集中，抽出的样本需要重新放回去。经过m次抽取，我们得到一个m个样本的数据集。其中采样集中有可能存在重复的数据。

采样了T个含有m个训练样本的数据集，然后基于每个数据集训练出一个基学习器，然后将这些基学习器进行组合，对于分类任务使用简单投票法，而对于回归任务则是使用简单平均法。

优点：

Bagging可以应用于多分类、回归等任务；
由于每个基学习器只用了六成的数据，因此可以用剩下的数据坐泛化能力的"包外预计"；

随机森林

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

传统决策树在当前节点从d个属性中选择一个最优属性，而在RF中，则是先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从中选择一个最优属性。

一般情况下，推荐\(k=log_2d\)。

随机森林的泛化误差比Bagging更小。

结合策略

学习器结合的优点：

减小因为单学习器可能带来的误选而导致泛化能力不佳的风险；
多次运行进行结合，避免陷入局部最小点；
某些学习任务的真实假设可能并不在单学习器当前学习算法所考虑的假设空间中；

平均法

加权平均法： \[ H(x) = \sum_{i=1}^Tw_ih_i(w) \] 其中，\(w_i \ge 0, \sum_{i=1}^Tw_i=1\)；简单平均法，则是令\(w_i=1/T\)的特例。

一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时则使用简单平均法。

投票法

投票法有几种，假设\(h_i^j(x)\)是分类器\(h_i\)在类别标记\(c_j\)上的输出。

绝对多数投票法

\[ H(x)=\left\{ \begin{array}{rcl} c_j & & {if \sum_{i=1}^T h_i^j(x) \ge 0.5\sum_{k=1}^T \sum_{i=1}^T h_i^k(x)}\\ reject & & {otherwise} \end{array} \right. \]

对于可靠性的学习任务中，这个机制提供了拒绝预测的选项

相对多数投票法

\[ H(x) = c_{arg max _j } \sum_{i=1}^Th_i^j(x) \]

若同时有多个类别获得了最高票，则随机选一个。

加权投票法

\[ H(x) = c_{arg max _j } \sum_{i=1}^T w_ih_i^j(x) \]

一般情况下，对于不同的学习器可能会产生不同类型的值，比如类标记和类概率。在这种情况下，类概率输出转化为类标记输出（例如将类概率最大的设置为1，其它为0），然后再投票。

学习法

当训练数据很多时，我们可以使用另一种更为强大的结合策略——通过另一个学习器进行结合。

Stacking是这类策略的代表，其先从初始数据集训练出初级学习器，然后"生成"一个新的数据集用于训练次级学习器。

为了避免过拟合，一般是采用交叉验证的方式，即用训练初级学习器未使用的样本来产生次级学习器的训练样本。以k折交叉验证为例，初始训练集D被随机划分为k个大小相似的集合\(D_1,..,D_k\)。令\(D_j\)和\(\overline D_j = D-D_j\)分别表示在第j折的测试集和训练集。

算法的具体过程如下：

给定T个初级学习算法，初级学习器\(h_t^{(j)}\)通过在\(\overline D_j\)上使用第t个学习算法而得；
对\(D_j\)中每个样本\(x_i\)，计算\(z_{it}=h_t^{(j)}(x_i)\)，则由样本产生的次级训练样例为\(z_i=(z_{i1},…,z_{iT})\)，标记部分为\(y_i\)；
交叉验证结束之后，由初级学习器产生的次级训练集\(D' = \{(z_i,y_i)\}^m_{i=1}\)，并由此训练次级学习器；

次级学习器的输入属性表示和次级学习算法对stacking集成的泛化性能由很大的影响。

多样性

误差——分歧分解

为了使得泛化能力提高，个体学习器应该"好而不同"。因此我们来做一点理论分析：

假设对于数据x，定义学习器h得分歧为： \[ A(h_i|x) = (h_i(x)-H(x))^2\\ 则集成的分歧为：\overline A(h_i|x) = \sum_{i=1}^Tw_i(h_i(x)-H(x))^2 \] 而个体学习器和集成学习器的平方误差为： \[ E(h_i|x) = (f(x)-h_i(x))^2 \\ \overline E(h|x) = \sum_{i=1}^T w_i E(h_i|x) \\ E(H|x) = (f(x)-H(x))^2 \] 则可以根据上式求得： \[ \overline A(h|x) = \overline E(h|x) -E(H|x) \] 因此可以求得\(E = \overline E - \overline A\)，即个体学习器准确性越高，多样性越好，则集成效果越好。

多样性度量

多样性度量其实就是度量集成个体分类器的多样性，比较典型的做法是考虑个体分类器的两两相似/不相似性，以两分类为例：

	Hi = +1	Hi = -1
Hj = +1	a	c
Hj = -1	b	d

其中，a表示两个分类器都预测为正类的样本数目，a+b+c+d=m。以下是一些常见的多样性度量：

不合度量

\[ dis_{ij} = \frac{b+c}{m} \]

相关系数

\[ p_{ij} = \frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} \]

该系数的值域为[-1,1]，若两分类器无关，则值为0.若为正相关，则值为正，否则为负；

Q-统计量

\[ Q_{ij} = \frac{ad-bc}{ad+bc} \]

其与上面相关系数符号相同；

k-统计量

\[ k = \frac{p1-p2}{1-p2} \]

其中，p1是两个分类器取得一致的概率；p2是两个分类器偶然达成一致的概率： \[ p1 = \frac{a+d}{m} \\ p2 = \frac{(a+b)(a+c)+(c+d)(b+d)}{m^2} \] 若分类器在数据集上完全一致，则k=1；若它们仅仅是偶然性达成一致，则k=0；k通常为非负值，仅仅在分类器达成一致的概率比偶然性的情况下还低时取负值。

多样性增强

要生成多样性大的个体学习器，比较直接的方法是在学习过程引入随机性。

数据样本扰动

基于采样法，对训练样本稍加变化。但有些稳定学习器对数据样本的扰动并不敏感。

输入属性扰动

该方法一般是从初始属性集中抽出若干个属性子集，这样做不但能增加多样性，还能减少训练时间。但对于属性较少的样本不适宜。

输出表示扰动

此类做法的基本思路是对输出表示进行操纵以增强多样性，可以对训练样本的类标记做少许改动，也可以对输出表示进行转化，还可以将原任务拆解成多个子任务。

算法参数扰动

对基学习算法的一些参数进行设置，比较常见的是神经网络的参数设置。