集成学习

简介

  集成学习 ($ensemble \ learning$) 是通过构建并结合多个学习器来完成学习任务。其一般结构为：

1. 先产生一组“个体学习器” ($individual \ learner$)。个体学习器通常由一种或者多种现有的学习算法从训练数据中产生。
   1. 如果个体学习器都是从某一种学习算法从训练数据中产生，则称这样的集成学习是同质的 ($homogenerous$)。此时的个体学习器也称作基学习器 ($base \ learner$)，相应的学习算法称作基学习算法。
   2. 如果个体学习器是从某几种学习算法从训练数据中产生，则称这样的集成学习是异质的 ($homogenerous$)。
2. 再使用某种策略将它们结合起来。集成学习通过将多个学习器进行组合，通常可以获得比单一学习器显著优越的泛化性能。

  集成学习研究的核心，生成“好而不同”的个体学习器，即个体学习器要有一定的“准确性”（学习器不能太坏），并且要有“多样性”（学习器之间要有差异）。

  通常基于实际考虑，往往使用预测能力较强的个体学习器（即强学习器，与之对应的为弱学习器）。强学习器的一个显著的好处就是可以使用较少数量的个体学习器来集成就可以获得很好的效果。

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

1. 序列化方法，个体学习器间存在强依赖关系，必须串行生成的序列化方法，其代表是 $Boosting$。
2. 并行化方法，个体学习器间不存在依赖关系，可同时生成的并行化方法，其代表有 $Bagging$。

误差分析

  考虑一个二类分类问题。设单个样本为 $\mathbf {x}$，真实类别为 $y \in \mathcal Y={-1,+1}$。假定基类分类器的错误率为 $\epsilon$，即对每个基分类器 $h_i$ 有：$p(h _ i(\mathbf {x}) \ne y)=\epsilon$。

1. 假设集成学习通过简单投票法结合 $M$ 个基分类器 $h _ 1,h _ 2,\cdots,h _ M $。即：若有超过半数的基分类器正确，则集成分类就正确。根据描述，给出集成学习器为：$H(\mathbf {x})=\text{sign}\left(\sum _ {i=1}^{M}h _ i(\mathbf {x})\right)$。
2. 集成学习器预测错误的条件为：$k$个基分类器预测正确，其中 $k \le \left\lfloor M/2\right\rfloor$（即：少于一半的基分类器预测正确），$M-k$ 个基分类器预测错误。假设基分类器的错误率相互独立，则集成学习器预测错误的概率为： \(p(H(\mathbf {x}) \ne y)=\sum_{k=0}^{\left\lfloor M/2\right\rfloor}C_M^{k}(1-\epsilon)^{k}\epsilon^{M-k}\)
3. 根据 $Hoeffding$ 不等式有： \(p(H(\mathbf {x}) \ne y)=\sum_{k=0}^{\left\lfloor M/2\right\rfloor}C_M^{k}(1-\epsilon)^{k}\epsilon^{M-k}\le \exp\left(-\frac 12 M(1-2\epsilon)^{2}\right)\) 可以看出：随着 $M \rightarrow \infty$， 集成学习器预测错误的概率 $p(H(\mathbf {x}) \ne y) \rightarrow 0$。

  上述推论有非常关键的一个地方：假设基分类器的错误率相互独立。

1. 实际上个体学习器是为了解决同一个问题训练出来的，而且可能是同一类算法从同一个训练集中产生。这样个体学习器的错误率显然不能相互独立。
2. 实际上个体学习器的准确性和多样性本身就存在冲突。
   1. 通常个体学习器的准确性很高之后，要增加多样性就需要牺牲准确性。
   2. 实际上如何产生并结合”好而不同“的个体学习器就是集成学习研究的核心。

Bagging

原理

  $Bagging$ 是并行化集成学习方法最著名的代表，该模型的关键之处是使用了“自助采样法”。给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有机会被选中。这样经过$m$次有放回的随机采样操作，得到一个含有 $m$ 个样本的采样集。

  初始训练集中有的样本在采样集中多次出现，有的则从未出现。一个样本始终不在采样集中出现的概率是 $(1-\frac 1N)^{N}$。根据 $\lim _ {N\rightarrow \infty} (1-\frac 1N)^{N} =\frac 1e \simeq=0.368$，因此初始训练集中约有 63.2% 的样本出现在采样集中。

  自助采样法给 $Bagging$ 算法带来了额外的优点：由于每个基学习器只用初始训练集中约 63.2% 的样本来训练，剩下的约 36.8% 的样本可用作验证集来对泛化性能进行包外估计。

$Bagging$ 的基本流程：

1. 采出 $T$ 个采样集，每个采样集含有 $m$ 个训练样本；
2. 基于每个采样集训练出一个基学习器，总共生成 $T$ 个基学习器；
3. 将这 $T$ 个基学习器结合；

在使用 $Bagging$ 学习器进行预测时：

1. 分类任务采取简单投票法，取每个基学习器的预测类别的众数。
2. 回归任务使用简单平均法，取每个基学习器的预测值的平均。

从偏差-方差分解的角度来看：

1. $Bagging$ 主要关注降低方差，它能平滑强学习器的方差。因此它在非剪枝决策树、神经网络等容易受到样本扰动的学习器上效果更为明显。
2. $Boosting$ 主要关注降低偏差，它能将一些弱学习器提升为强学习器。因此它在 $SVM$、$kNN$ 等不容易受到样本扰动的学习器上效果更为明显。

随机森林

原理

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

1. 传统决策树在选择划分属性时，是在当前结点的属性集合（假定有$N$个属性）中选择一个最优属性。
2. 随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 $n$ 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。
   1. 如果 $n=N$，则基决策树的构建与传统决策树相同。
   2. 如果 $n=1$，则随机选择一个属性用于划分。
   3. 通常建议 $n=\log _ 2 N$。

伪码

1. 假设原始训练数据集中有 $M$ 个样本，有放回的随机选择 $M$ 个样本；
2. 决策树中的每个节点分裂时从当前节点的属性集合中（假设有 $N$ 个属性）随机选取 $n$ 个属性，$n$ 一般满足 $n\ll N$，一般取 $n=\log _ 2 N$。从这 $n$ 个属性中采用某种策略（分类：信息增益比、基尼指数；回归：平方误差最小化）选择最优划分属性进行划分。
3. 使用 $1$ 中随机选择的 $M$ 个样本构建决策树，决策树形成过程中对每个节点执行 $2$ 分裂（如果下一次该结点选出来的那个属性是刚刚其父结点分裂时用过的属性，则该结点已经达到了叶子结点，无需继续分裂）。决策树生成过程中不需要剪枝。
4. 执行 1-3 生成大量的决策树，这样就构成了随机森林。

优点

1. 随机森林中基学习器的多样性来自样本扰动和属性扰动，这使得不剪枝也不会出现过拟合现象，还可以提高泛化性能；
2. 简单、容易实现、计算开销小；
3. 容易实现并行化;

缺点

1. 数据量小的时候性能不是很好

常见参数

1. 树的最大深度
2. 树的个数
3. 节点上最小的样本数
4. 特征数量

Boosting

$Boosting$ 是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：

1. 从初始训练集训练出一个基学习器；
2. 根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
3. 基于调整后的样本分布来训练下一个基学习器；
4. 重复 1~3，直至基学习器数目达到事先指定的值 $T$；
5. 最终将这$T$个基学习器进行加权结合

AdaBoost 算法(Adaptive Boosting)

$Boosting$ 族算法最著名的代表是 $AdaBoost$ 算法。

$AdaBoost$ 算法两个核心步骤：

1. 每一轮中如何改变训练数据的权值？

   $AdaBoost$ 算法提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。

2. 最后如何将一系列弱分类器组合成一个强分类器？

   $AdaBoost$ 采用加权多数表决的方法：

   1. 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
   2. 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小作用。

$AdaBoost$ 算法有两个特点：

1. 不改变所给的训练数据，只改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用。
   1. 因此 $AdaBoost$ 要求基本学习器能够对特定的数据分布进行学习，这一般是在学习的时候为每个训练样本赋予一个权重。
   2. 对于无法接受带权样本的基本学习算法，则可以通过“重采样法”来处理：即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样的样本集对基本学习器进行训练。
   3. 一般而言这两者没有显著的优劣差别。
2. 利用基本分类器的线性组合 $f(x)=\sum _ {m=1}^{M}\alpha _ mh _ m(x)$ 构成最终分类器： \(H\left( x \right) =sign\left( f\left( x \right) \right) =sign\left( \sum _ { m=1 }^{ M }{ { \alpha }_ { m }{ h }_ { m }\left( x \right) } \right)\) 其中：$f(x)$ 号决定实例 $x$ 的分类。$f(x)$ 的绝对值表示分类的确信度。

   $AdaBoost$ 算法具有自适应性，即它能够自动适应弱分类器各自的训练误差率，这也是它的名字（适应的提升）的由来。

算法

1. 输入：
   1. 训练数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y\ _ N)},\;\mathbf{x} _ i \in \mathcal X \subset \mathbb R^{n},\tilde y _ i \in \mathcal Y={-1,+1}$
   2. 弱学习算法
2. 输出：集成分类器 $H(x)$
3. 算法步骤：
   1. 初始化训练数据的权值分布 $W _ 1=(w _ {1,1},w _ {1,2},\cdots,w _ {1,N}),w _ {1,i}=\frac 1N$。
   2. 对$m=1,2,\cdots,M$
      1. 使用具有权值分布$W _ m$的训练数据集学习，根据输入的弱学习算法得到基本分类器：$h _ m(x):\mathcal X \rightarrow {-1,+1}$。

      2. 计算$ h _ m(x)$在训练数据集上的分类误差率： \({ e }_ { m }=\sum _ { i=1 }^{ N }{ { w }_ { m,i }I\left( { h }_ { m }\left( { x }_ { i } \right) \neq { \tilde { y } }_ { i } \right) }\) 它就是所有误分类点的权重之和。其中权重越大的误差分类点，其在误差率中占比越大。

      3. 若 $e _ m \ge \frac 12$，算法终止，构建失败！

      4. 计算 $h _ m(x)$ 的系数：$\alpha _ m=\frac 12 \log \frac{1-e _ m}{e _ m}$。该系数表示 $h _ m(x)$ 在集成分类器中的重要性。它是 $e _ m$ 的单调减函数，说明误差越小的基本分类器，其重要性越高。根据系数大于零要求 $e _ m \lt \frac 12$。

      5. 更新训练数据集的权值分布：$W _ {m+1}=(w _ {m+1,1},w _ {m+1,2},\cdots,w _ {m+1,N})$。其中： \(w_{m+1,i}=\frac{w_{m,i}}{Z_m}\exp(-\alpha_m\tilde y_i h_m(x_i))\) 其中，$Z _ m=\sum _ {i=1}^{N}w _ {m,i}\exp(-\alpha _ m\tilde y _ ih _ m(x _ i))$ 为规范化因子，它使得 $W _ {m+1}$ 成为一个概率分布 。
   3. 构建基本分类器的线性组合：$f(x)=\sum _ {m=1}^{M}\alpha _ mh _ m(x)$，于是得到集成分类器： \(H(x)=\text{sign}\left(\sum_{m=1}^{M}\alpha_mh_m(x)\right)\)   为防止过拟合，$AdaBoost$ 通常会加入正则化项。该正则化项称作步长或者学习率，定义为 $\nu$。考虑正则化项之后，模型的更新方式为：

算法解释

  $AdaBoost$ 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这是通过更新训练数据集的权值分布 $W _ 1=(w _ {1,1},w _ {1,2},\cdots,w _ {1,N}),w _ {1,i}=\frac 1N$ 来实现的。其中：

对于正确分类样本，${ h } _ { m }\left( { x } _ { i } \right) \neq { \tilde { y } } _ { i }$ 下一轮权重为：

对于错误分类样本，${ h } _ { m }\left( { x } _ { i } \right) \neq { \tilde { y } } _ { i }$ 下一轮权重为：

两者比较，误分类样本的权重是正确分类样本的权重的 $\exp(2\alpha _ m)=\frac{e _ m}{1-e _ m}$ 倍。于是误分类样本在下一轮学习中权重更大。

   集成分类器 $H(x)=\text{sign}\left(\sum _ {m=1}^{M}\alpha\ _ mh _ m(x)\right)$ 结合 $M$ 个基本分类器的方式为加权表决。

系数 $\alpha _ m$ 表示了基本分类器$h _ m(x)$ 的重要性。其中：

由于 $\alpha _ m$ 是分类误差率 $e _ m$ 的单调递减函数，因此：

1. $AdaBoost$ 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大的作用。
2. $AdaBoost$ 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

误差分析

定理一：$AdaBoost$ 算法集成分类器的训练误差上界为：

这一定理说明：可以在每一轮选取适当的 $h _ m$ 使得 $Z _ m$ 最小，从而使得训练误差下降最快。

定理二：二类分类 $AdaBoost$ 的训练误差界：

其中 $\gamma _ m=\frac 12-e _ m $。

推论：若存在 $\gamma \gt 0$，对所有 $m$ 有 $\gamma _ m \ge \gamma$，则有：

这表明在此条件下 $AdaBoost$ 的训练误差是以指数速率下降的。

  上述定理都只是关于训练误差的分析，实际应用中更关系测试集的误差。$AdaBoost$ 算法也会出现过拟合，此时训练误差为 $0$ 但是测试集的误差较大。

  当 $AdaBoost$ 的基础分类器比较复杂时，$AdaBoost$ 很容易陷入过拟合。但是当 $AdaBoost$ 的基础分类器比较简单时，$AdaBoost$ 反而难以陷入过拟合。这也是为什么 $AdaBoost$ 的基础分类器经常选择使用树桩的原因。

优缺点

优点

1. 精度高
2. 可以使用各种方法构建子分类器，$AdaBoost$ 算法提供的是框架
3. 不易发生 $overfitting$

缺点

1. 对 $outlier$ 比较敏感
2. 数据不平衡会导致分类精度下降

AdaBoost 多分类

标准的 $AdaBoost$ 算法只适用二类分类问题，可以将它推广到多分类问题。 有两种算法：

1. $SAMME$ 算法：该算法不需要个体分类器输出类别的概率。
2. $SAMME.R$ 算法：该算法需要个体分类器输出类别的概率。

SAMME 算法

1. 输入：
   1. 训练数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y _ N)},\; x _ i \in \mathcal X \subset \mathbb R^{n},\tilde y _ i \in \mathcal Y={c _ 1,c _ 2,\cdots,c _ K}$
   2. 弱学习算法
2. 输出：集成分类器 $H(x)$
3. 算法步骤：
   1. 初始化训练数据的权值分布 $W _ 1=(w _ {1,1},w _ {1,2},\cdots,w _ {1,N}),w _ {1,i}=\frac 1N$。
   2. 对 $m=1,2,\cdots,M$
      1. 使用具有权值分布 $W _ m$ 的训练数据集学习，根据输入的弱学习算法得到基本分类器：$h _ m(x):\mathcal X \rightarrow {c _ 1,c _ 2,\cdots,c _ K}$。
      2. 计算 $h _ m(x)$ 在训练数据集上的分类误差率： \(e_m= \sum_{i=1}^{N}w_{m,i}I(h_m(x_i) \neq \tilde y_i)\)

      3. 计算 $h _ m(x)$ 的系数： \(\alpha_m=\frac 12 \log \frac{1-e_m}{e_m}+\log(K-1)\)
         因为系数 $\alpha _ m\gt 0 $，因此要求 $e _ m \lt \frac {K-1}{K}$。

      4. 更新训练数据集的权值分布：$W _ {m+1}=(w _ {m+1,1},w _ {m+1,2},\cdots,w _ {m+1,N})$。其中： \(\begin{aligned} { w }_ { m+1,i }&=\frac { { w }_ { m,i } }{ { Z }_ { m } } exp\left( -{ \alpha }_ { m }{ \tilde { y } }_ { i }{ h }_{ m }\left( { x }_{ i } \right) \right) \\ { Z }_{ m }&=\sum _{ i=1 }^{ N }{ { w }_{ m,i }exp\left( -{ \alpha }_{ m }{ \tilde { y } }_{ i }{ h }_{ m }\left( { x }_{ i } \right) \right) } \end{aligned}\) 其中 $Z _ m$ 为规范化因子，它使得 $W _ {m+1}$ 成为一个概率分布。
   3. 构建基本分类器的线性组合，于是得到集成分类器： \(H(x)=\arg\max_{c_k}\left(\sum_{m=1}^{M}\alpha_mI(h_m(x)=c_k)\right)\) 当 $K=2$ 时 $SAMME$ 算法退化为标准的 $AdaBoost$ 算法。

SAMME.R 算法

1. 输入：
   1. 训练数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y _ N)},\; x _ i \in \mathcal X \subset \mathbb R^{n},\tilde y _ i \in \mathcal Y={c _ 1,c _ 2,\cdots,c _ K}$
   2. 弱学习算法
2. 输出：集成分类器 $H(x)$
3. 算法步骤：
   1. 初始化训练数据的权值分布 $W _ 1=(w _ {1,1},w _ {1,2},\cdots,w _ {1,N}),w _ {1,i}=\frac 1N$。
   2. 对 $m=1,2,\cdots,M$
      1. 使用具有权值分布 $W _ m$ 的训练数据集学习，根据输入的弱学习算法得到基本分类器 $h _ m(x):\mathcal X \rightarrow {c _ 1,c _ 2,\cdots,c _ K}$。
      2. 计算 $h _ m(x)$ 在训练数据集上的加权概率估计： \(p_{m,i}^{(k)}=w_{m,i}p(\tilde y_i=c_k \mid x_i), i=1,2,\cdots,N;k=1,2,\cdots,K\) 其中：$\tilde y _ i$ 是 $x _ i$ 的真实标记；$w _ {m,i}$ 是 $x _ i$ 的权重；$p _ {m,i}^{(k)}$ 刻画基本分类器 $h _ m(\cdot)$预测$x _ i$的输出为类别 $c _ k$ 的概率的加权值。
      3. 对 $h _ m$ 和类别 $c _ k$，定义： \(l_m^{(k)}(x_i)=(K-1)\left(\log p_{m,i}^{(k)}-\frac 1K\sum_{k'=1}^{K}\log p_{m,i}^{(k')}\right) ,k=1,2,\cdots,K\) 它刻画了 $h _ m(\cdot)$ 预测的输出类别为 $c _ k$ 的概率加权值的对数 $\log p _ {m,i}^{(k)}$，距离所有概率加权值对数的均值 $\frac 1K\sum _ {k’=1}^{K}\log p _ {m,i}^{(k’)}$ 的距离。
      4. 更新训练数据集的权值分布：$W _ {m+1}=(w _ {m+1,1},w _ {m+1,2},\cdots,w _ {m+1,N})$。其中： \(\begin{aligned} { w }_{ m+1,i }&={ w }_{ m,i }exp\left( -\frac { K }{ K-1 } \sum _{ k=1 }^{ K }{ { \delta }_{ i }^{ \left( k \right) }\log { { p }_{ m,i }^{ \left( k \right) } } } \right) \\ { \delta }_{ i }^{ \left( k \right) }&=\begin{cases} 1if{ \tilde { y } }_{ i }={ c }_{ k } \\ -\frac { K }{ K-1 } else \end{cases} \end{aligned}\)
      5. 归一化训练数据集的权值分布 $W _ {m+1}=(w _ {m+1,1},w _ {m+1,2},\cdots,w _ {m+1,N})$，使得权值之和为 $1$。
   3. 构建基本分类器的线性组合，于是得到集成分类器： \(H(x)=\arg\max_{c_k}\left(\sum_{m=1}^{M}l_m^{(k)}(x)\right)\)

Adaboost 回归

$AdaBoost$ 的回归问题有很多变种，这里介绍 $AdaBoost \ R2$ 算法。

1. 输入：
   1. 训练数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y _ N)},\;x _ i \in \mathcal X \subset \mathbb R^{n},\tilde y _ i \in \mathbb R$
   2. 弱学习算法
2. 输出：集成回归器 $H(x)$
3. 算法步骤：
   1. 初始化训练数据的权值分布 $W _ 1=(w _ {1,1},w _ {1,2},\cdots,w _ {1,N}),w _ {1,i}=\frac 1N$。
   2. 对 $m=1,2,\cdots,M$
      1. 使用具有权值分布 $W _ m$ 的训练数据集学习，根据输入的弱学习算法得到基本回归器：$h _ m(x):\mathcal X \rightarrow \mathbb R$。

      2. 计算 $h _ m(x)$ 在训练数据集上的误差： \(\begin{aligned} { E }_{ m }&=\max _{ { x }_{ i }\in D }{ \left| { \tilde { y } }_{ i }-{ h }_{ m }\left( { x }_{ i } \right) \right| } \\ { e }_{ m }&=\sum _{ i=1 }^{ N }{ { w }_{ m,i }{ \left( \frac { { \tilde { y } }_{ i }-{ h }_{ m }\left( { x }_{ i } \right) }{ { E }_{ k } } \right) }^{ 2 } } \end{aligned}\) 它就是所有样本的回归误差的加权和。其中，$E _ m$ 为误差绝对值的最大值，通过它来对所有的回归误差归一化。

      3. 计算 $h _ m(x)$ 的系数：$\alpha\ _ m = \frac{e\ _ m}{1-e _ m}$。该系数表示 $h _ m(x)$ 在集成回归器中的重要性。它是 $e _ m$ 的单调减函数，说明误差越小的基本回归器，其重要性越高。
      4. 更新训练数据集的权值分布：$W _ {m+1}=(w _ {m+1,1},w _ {m+1,2},\cdots,w _ {m+1,N})$。其中： \(\begin{aligned} { w }_ { m+1,i }&=\frac { { w }_ { m,i } }{ { Z }_ { m } } { \alpha }_ { m }^{ 1-{ \left( \frac { { \tilde { y } }_ { i }-{ h }_ { m }\left( { x }_ { i } \right) }{ { E }_ { m } } \right) }^{ 2 } } \\ { Z }_ { m }&=\sum _ { i=1 }^{ N }{ { w }_ { m,i } } { \alpha }_ { m }^{ 1-{ \left( \frac { { \tilde { y } }_ { i }-{ h }_ { m }\left( { x }_ { i } \right) }{ { E }_ { m } } \right) }^{ 2 } } \end{aligned}\) $Z _ m$ 为规范化因子，它使得 $W _ {m+1}$ 成为一个概率分布 。
   3. 构建基本回归器的线性组合 ，于是得到集成回归器： \(H(x)=\sum_{m=1}^M (\ln \frac {1}{\alpha_m})h_m(x)\)

AdaBoost与加法模型

加法模型

  $AdaBoost$ 算法可以认为是：模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。其中指数损失函数为： \(L(\tilde y,f(x))=e^{-\tilde yf(x)}\)

考虑加法模型

其中，$b(x;\gamma _ m)$ 为基函数、$\gamma _ m$ 为基函数的参数、$\beta _ m$ 为基函数的系数。   给定训练数据以及损失函数 $L(\tilde y,y)$ 的条件下，根据经验风险极小化（即：损失函数极小化）准测来学习加法模型 $f(x)$：

这是个复杂的最优化问题，通常可以采用前向分步算法求解。
  前向分步算法求解这一优化问题的思想是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，则可以简化优化的复杂度。具体地，每一步只需要优化如下的损失函数：

前向分布算法

1. 输入：
   1. 训练数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y _ N)},\quad x _ i \in \mathcal X \subset \mathbb R^{n},\tilde y _ i \in \mathcal Y={-1,+1}$
   2. 损失函数 $L(\tilde y,y)$
   3. 基函数集 ${b(x;\gamma)}$
2. 输出：加法模型 $f(x)$
3. 算法步骤：
   1. 初始化 $f _ 0(x)=0$
   2. 对 $m=1,2,\cdots,M$
      1. 极小化损失函数 $(\beta _ m,\gamma _ m)=\arg\min _ {\beta,\gamma}\sum _ {i=1}^{N}L(\tilde y _ i,f _ {m-1}(x _ i)+\beta b(x _ i;\gamma))$，得到参数 $\beta _ m,\gamma _ m$。
      2. 更新 $f _ m(x)=f _ {m-1}(x)+\beta _ m b(x;\gamma _ m)$。
   3. 最终加法模型 \(f(x)=f_M(x)=\sum_{i=1}^{M}\beta_mb(x;\gamma_m)\)

集成策略

学习器组合可以能带来好处：

1. 由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能。此时如果使用单学习器可能因为造成误选而导致泛化性能不佳，通过学习器组合之后会减小这一风险。
2. 学习算法往往会陷入局部极小。有的局部极小点所对应的泛化性能可能很差，而通过学习器组合之后可降低陷入糟糕局部极小的风险。
3. 某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时使用单学习器肯定无效。通过学习器组合之后，由于相应的假设空间有所扩大，有可能学得更好的近似。

假定集成包含$M$个基学习器 $h _ 1,h _ 2,\cdots,h _ M$。一共有三种集成策略：

1. 平均法
2. 投票法
3. 学习法

平均法

平均法通常用于回归任务中。

1. 简单平均法： \(H(x)=\frac 1M \sum_{i=1}^{M}h_i(x)\)
2. 加权平均法： \(H(x)=\frac 1M \sum_{i=1}^{M}w_ih_i(x) \ w_i \ge 0,\sum_{i=1}^{M}w_i=1\) 其中,学习器 $h_i$ 的权重 $w_i$ 是从训练数据中学的。

  现实任务中训练样本通常不充分或者存在噪声，这就使得学得的权重不完全可靠。尤其是对于规模比较大的集成学习，要学习的权重比较多，很容易出现过拟合。因此实验和应用均显示出，加权平均法不一定优于简单平均法。
  通常如果个体学习器性能相差较大时，适合使用加权平均法；个体学习器性能相差较近时，适合使用简单平均法。

投票法

投票法通常用于分类任务中。

1. 绝大多数投票法：若某个标记得票数过半，则预测为该标记；否则拒绝预测。此时很有可能所有标记都未过半，则预测失败。因此这种方法比较少用。
2. 相对多数投票法：选取得票最多的标记作为预测值： \(H(x)=\arg\max_{c_j} \sum_{i=1}^{M}I(h_i(x)=c_j)\)
3. 加权投票法：类似于加权平均法，其中学习器$h _ i$的权重$w _ i$是从训练数据中学的： \(H(x)=\arg\max_{c_j} \sum_{i=1}^{M}w_iI(h_i(x)=c_j)\)

学习法

  学习法中，个体学习器的分类结果通过与另一个学习器来组合。此时称个体学习器为初级学习器，用于组合的学习器称作次级学习器或者元学习器 ($meta \ learner$)。

  学习法的典型代表就是 $stacking$ 集成算法。$stacking$ 集成算法中，首先从初始数据集训练出初级学习器；然后将初级学习器的预测结果作为一个新的数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样本输入特征；初始样本的标记仍被视作标记。

  若直接使用初级学习器的输出来产生次级训练集，则容易发生过拟合。一般是通过使用交叉验证，使用训练初级学习器时未使用的样本来产生次级学习器的训练样本。

  次级学习器的输入属性表示和次级学习算法对 $stacking$ 集成算法的泛化性能有很大影响。通常推荐：

1. 次级学习器的输入特征是以初级学习器的输出类概率为特征。
2. 次级学习算法采用多响应线性回归 ($Multi-response \ Linear \ Regression:MLR$)。

多样性分析

误差-分歧分解

  假定有 $M$ 个个体学习器 $h _ 1,h _ 2,\cdots,h _ M$，通过加权平均法组合产生集成学习器 $H$ 来完成回归学习任务。即：

  对于某个样本 $x$，定义学习器 $h _ i$ 的分歧 (ambiguity) 为：

分歧刻画了个体学习器在某个样本 $x$ 上的不一致性，在一定程度上反映了个体学习器的多样性。定义集成学习器的分歧为:

  设样本 $x$ 的真实标记为 $\tilde y$，则个体学习器 $h _ i$ 和集成学习器 $H$ 的平方误差分别为：

令个体学习器误差的加权均值为：

根据 $H(x)=\sum _ {i=1}^{M}w _ ih _ i(x)$，则有：

令 $p(x)$ 为样本的概率密度，则在全样本上有：

代入各变量，则有：

定义个体学习器 $ h _ i $ 在全体样本上的泛化误差和分歧项为：

定义集成的泛化误差为：

则有：

定义个体学习器泛化误差的加权均值为：

定义个体学习器的加权分歧值为：

则有：

这就是集成学习的误差-分歧分解。该式针对回归学习，难以直接推广到分类学习任务中去。该式难以直接作为优化目标，因为现实任务中很难直接对 $\bar E-\bar A$ 进行优化：一方面是它们是定义在整体样本空间上的；另一方面是 $\bar A$ 不是一个可以直接操作的值，它是当集成学习器构造之后才能进行估计的。

  从误差-分歧分解中看出：要想降低集成学习的泛化误差 $E$，要么提高个体学习器的加权分歧值 $\bar A$，要么降低个体学习器的泛化误差的加权均值 $\bar E$。因此，个体学习器准确性越高、多样性越大，则集成越好。

多样性度量

  多样性度量 (diversity measure) 是用于刻画集成模型中的个体分类器的多样性的程度。通常是考虑个体分类器的两两相似/不相似程度。给定数据集 $\mathbb D={(x _ 1,\tilde y _ 1),(x _ 2,\tilde y _ 2),\cdots,(x _ N,\tilde y _ N)},\tilde y _ i\in \mathcal Y={-1,+1}$。考虑分类器 $h _ i,h _ j$ 的预测结果联表为：

其中：

1. $a$ 表示： $h _ i$ 预测为 $+1$，且 $h _ j$ 预测为 $+1$ 的样本的数量。
2. $b$ 表示： $h _ i$ 预测为 $+1$，且 $h _ j$ 预测为 $-1$ 的样本的数量。
3. $c$ 表示： $h _ i$ 预测为 $-1$，且 $h _ j$ 预测为 $+1$ 的样本的数量。
4. $d$ 表示： $h _ i$ 预测为 $-1$，且 $h _ j$ 预测为 $-1$ 的样本的数量。

根据定义有：$a+b+c+d=N$

不合度量

不合度量 ($disagreement \ measure$)：

其范围为 $[0,1]$，值越大则多样性越大 。

相关系数

相关系数($correlation \ coefficient$)：

其范围是 $[-1,+1]$。

1. 如果 $h _ i$ 与 $h _ j$ 无关，则值为 $0$。
2. 如果 $h _ i$ 与 $h _ j$ 正相关，则值为正。
3. 如果 $h _ i$ 与 $h _ j$ 负相关，则值为 负。

Q 统计量

$Q$ 统计量($Q-statistic$)：

$Q _ {ij}$ 与相关系数 $\rho _ {ij}$ 符号相同，且 $|Q _ {ij}| \le |\rho _ {ij}|$

kappa 统计量

$\kappa$ 统计量 ($\kappa-statistic$)：

其中：$p _ 1$ 是两个分类器取得一致的概率：$p _ 1=\frac {a+d}{N}$，根据：

所以 $p _ 1$ 刻画了两个分类器取得一致的概率；$p _ 2$ 是两个分类器偶然达成一致的概率：$p _ 2=\frac{(a+b)(a+c)+(c+d)(b+d)}{N^{2}}$，根据：

如果假设 $h _ 1$ 与 $h _ 2 $ 相互独立，则：

所以 $p _ 2$ 刻画了假设两个分类器的预测结果相互独立，则两个分类器取得一致的概率。

  $\kappa$ 的取值，若两个分类器在数据集 $\mathbb D$ 上完全一致，则 $\kappa=1$，因为此时 $b=c=0$，则 $p _ 1=1$；如果两个分类器仅仅是偶然达成一致，则 $\kappa=0$，因为此时 $p(h _ i=h _ j)=\hat p(h _ i=h _ j)$，则 $p _ 1=p _ 2$ ；通常 $\kappa$ 取非负值，仅在 $h _ i$ 与 $h _ j$ 达成一致的概率甚至低于偶然性的情况下才取负值。

多样性增强

  集成学习中，需要有效地生成多样性较大的个体学习器。一般的思路是在学习过程中引入随机性。常见的做法是：对数据样本、输入属性、输出表示、算法参数进行扰动。

1. 数据样本扰动：给定初始数据集，可以从中产生出不同的数据子集。再利用不同的数据子集训练出不同的个体学习器。
   1. 数据样本扰动通常是基于采样法，此类做法简单高效、使用最广。
   2. 对于常见的基学习器，如决策树、神经网络等，训练样本稍加变化就会导致学习器有显著的变动，数据样本扰动法对这样的“不稳定基学习器”很有效。
   3. 对于一些基学习器对数据样本的扰动不敏感，如线性学习器、支持向量机、朴素贝叶斯、 $k$ 近邻学习器等，这样的基学习器称作稳定基学习器。对于此类的基学习器进行集成往往需要使用输入属性扰动等其他机制。
2. 输入属性扰动：训练样本通常由一组属性描述，不同的“子空间”提供了观察数据的不同视角。显然从不同子空间训练出来的个体学习器必然有所不同。
   1. 对于包含了大量冗余属性的数据，在子空间中训练个体学习器不仅能够产生多样性大的个体，还会因为属性数量的减少而大幅节省时间开销。同时由于冗余属性多，减少一些属性之后训练的个体学习器也不至于太差。
   2. 对于只包含少量属性的数据，或者冗余属性较少，则不宜采用输入属性扰动法。
3. 输出表示扰动：此类做法的思路是对输出表示进行操纵以增强多样性。如：可以对训练样本的类标记稍作变动，如翻转法 ($Flipping Output$) 随机改变一些训练样本的标记。
4. 算法参数扰动：基学习算法一般都有超参数需要设置。可以通过随机设置不同的超参数，从而产生差别较大的个体学习器。使用单一学习器时通常需要使用交叉验证等方法来确定最佳的超参数值。这种做法实际上是用了不同的超参数训练出来了多个学习器，只不过最终挑选出来效果最好的那个学习器来使用。集成学习则是相当于把所有这些学习器都利用起来。

不同的多样性增强机制可以同时使用。如随机森林同时是用了数据样本扰动和输入属性扰动。