集成学习
集成学习(ensemble learning)是通过构建并结合多个学习器来完成学习任务。个体学习器可以是同质的(同一类学习器)，也可以是异质的(不同类学习器)。
集成学习通过将多个学习器(一般是弱学习器)结合，可以得到比单一学习器优越很多的泛化性能。一般来说，把好的东西和坏的东西掺到一起，得到的应该是比好的差一些，比坏的好一些。但集成学习为什么能得到比最好的单一学习器更好的性能呢？
考虑一个简单的例子，在二分类问题中，三个分类器在三个测试样本上的表现如下图所示，$\surd$表示分类正确，$\times$ 表示分类错误，集成学习的结果通过投票法产生。
这个例子表明，要获得好的集成，个体学习器应“好而不同”，即学习器不能太坏，并且要有“多样性”，即学习器之间具有差异。然而事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性很高之后，要增加多样性就需要牺牲准确性。
根据个体学习器的生成方式，目前的集成学习方法大致可分为两类，即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法。前者的代表是Boosting，后者的代表是Bagging和随机森林(Random Forest)。
Boosting
Boosting是一类可将弱学习器提升为强学习器的算法。这类算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值$T$，最终将这$T$个基学习器进行加权结合。
AdaBoost
假设给定一个二分类的训练数据集$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$其中，每个样本点由实例与标记组成。实例$x_i\in\mathcal{X}\subseteq\mathbb{R}^n$，标记$y_i\in\mathcal{Y}=\{-1,+1\}$。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器，并将它们线性组合得到一个强分类器。
- 初始化训练数据的权值分布$$\mathcal{D}_1=(w_{11},w_{12},\cdots,w_{1N}),\quad w_{1i}=\cfrac{1}{N},\quad i=1,2,\cdots,N$$
- 对$m=1,2,\cdots,M$
(a) 使用具有权值分布$\mathcal{D}_m$的训练数据学习，得到基本分类器$$G_m(x):\mathcal{X}\to\{-1,+1\}$$
(b) 计算$G_m(x)$在训练数据集上的分类误差率$$e_m=P(G_m(x_i)\neq y_i)=\sum\limits_{i=1}^N w_{mi}I(G_m(x_i)\neq y_i)$$
(c) 如果$e_m>0.5$，则跳出循环，否则继续
(d) 计算这个弱分类器$G_m(x)$所占权重$$\alpha_m=\cfrac{1}{2}\ln\cfrac{1-e_m}{e_m}$$
(e) 更新训练数据集的权值分布$$\mathcal{D}_{m+1}=(w_{m+1,1},w_{m+1,2},\cdots,w_{m+1,N})$$ $$w_{m+1,i}=\cfrac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,\cdots,N$$这里的$Z_m$是规范化因子，$Z_m=\sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))$，使得$\mathcal{D}_{m+1}$成为一个概率分布 - 构建基本分类器的线性组合$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$得到最终分类器$$G(x)=\text{sign}(f(x))=\text{sign}\left(\sum_{m=1}^M\alpha_mG_m(x)\right)$$
$\text{sign}(x) =
\begin{cases}
-1, & \text{if $x<0$} \\
0, & \text{if $x=0$} \\
1, & \text{if $x\gt0$}
\end{cases}
$
由上面的式子可知，当$e_m\leq\frac{1}{2}$时，$\alpha_m\geq 0$，并且$\alpha_m$随着$e_m$的减小而增大，所以分类误差越小的基本分类器在最终分类器中的作用越大。
另外，在权值更新中，误分类的样本的权值被放大，被正确分类样本的权值得以减小。不改变所给的训练数据，而不断改变训练数据的权值分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点
注意，系数$\alpha_m$表示基本分类器的重要性，所以所有$\alpha_m$之和不为0。
Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足条件（如算法中的$e_m>0.5$，检查当前基分类器是否比随机猜测好），一旦条件不满足，则当前基学习器被抛弃，且学习过程停止。在这种情形下，初始设置的学习轮数$M$也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。可以采取“重采样法”，在抛弃当前基学习器后，可根据当前分布重新对训练样本进行采样，基于新的采样结果重新训练出满足要求的基学习器。
从偏差-方差分解地角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。
Bagging
要获得泛化性能强的集成，集成中的个体学习器应尽可能相互独立（具有差异）。一个可能的做法是对训练样本进行采样，产生若干个不同的子集，再从每个数据子集中训练出一个基学习器。由于训练样本不同，获得的基学习器可望具有比较大的差异。但我们又需要基学习器不能太差，所以使用的样本不能太小。为解决这个问题，我们可以考虑采用bootstrap采样。
Bagging是并行式集成学习方法的代表。我们用bootstrap采样出$T$个含$m$个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类时票数相同，则可以随机选择一个或进一步考察学习器投票的置信度。
Bagging其实是Bootstrap AGGregatING的缩写
训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度同阶，说明Bagging是一个很高效的集成算法。此外，与标准AdaBoost只适用于二分类任务不同，Bagging能不加修改地用于多分类、回归等任务。
从偏差-方差分解地角度看，Bagging主要关注降低方差。因此，它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。
随机森林(Random Forest)
随机森林(简称RF)是Bagging的一个扩展变体。RF在以决策树为基学习器构建Bagging集成的基础上，在决策树的训练过程中引入了随机属性选择。
传统决策树在选择划分属性时是在当前结点的属性集合(假定有$d$个属性)中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含$k$个属性的子集，然后再从这个子集中选一个最优属性用于划分。这里的 $k$ 控制了随机性的引入程度：若 $k=d$，则基决策树构建与传统决策树相同；若 $k=1$，则是随机选择一个属性划分；一般情况下，选择 $k=\log_2 d$。
随机森林简单、容易实现、计算开销小，但在很多问题上作用强大。它对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终学习器的泛化性能进一步提升。
随着学习器数目的增加，随机森林会收敛到比Bagging更低的泛化误差。而且，RF的训练开销要比Bagging小，因为它只需要对属性子集进行考察，而不是整个属性集。
参考资料：
- 《机器学习》周志华著
- 《统计学习方法》李航著