图解机器学习/第九章 集成分类

集成学习，是指把性能较低的多种弱学习器，通过适当组合而形成高性能的强学习器的方法。本章有介绍两种集成学习法，一种是对多个弱学习器独立进行学习的Bagging学习法，一种是对多个弱学习器依次进行学习的Boosting学习法。

剪枝分类

剪枝分类是属于弱学习器的一种单纯分类器。是指对于$d$次维的输入变量$x=(x^{(1)},\dots,x^{(d)})^{\intercal}$，任意选定其中的一维，通过将其值与给定的阈值相比较来进行分类的线性分类器。即以输入空间内的坐标轴与超平面进行正交的方式对模式进行分类。

剪枝分类器的自由度很低，但是具有计算成本低的优点。

Bagging学习法

统计学上的Bootstrap一般称为自助法，是指从$n$个训练样本$\lbrace (x_i,y_i) \rbrace_{i=1}^n$中随机选取$n$个，允许重复，生成与原始的训练样本集有些许差异的样本集的方法。

在Bagging学习中，首先经由自助法生成虚拟的训练样本，并对这些样本进行学习。然后，反复重复这一过程，对得到的多个分类器的输出求平均值。通过上述方法，就可以从大量略有不同的训练样本集合，得到多个稍微不同的弱分类器，然后再对这些分类器加以统合，就可以得到稳定、可靠的强分类器。

一般而言，像剪枝分类器这样非常单一的弱分类器，对其进行集成学习很少会发生过拟合现象，因此将Bagging学习的重复次数设置为较大的值是比较好的选择。在这种情况下，因为多个弱分类器的学习是个并行的过程，因此使用多台计算机并行处理，会使计算效率得到巨大的提升。

Bagging学习算法：

1. 对$j=1,\dots,b$重复进行如下计算

   1. 从$n$个训练样本$\lbrace (x_i,y_i) \rbrace_{i=1}^n$中随机选取$n$个，允许重复，生成若干个与原始的训练样本集有些许差异的新样本集。
   2. 使用上述得到的样本集求得弱学习器$\varphi_j$

2. 对所有的弱学习器$\lbrace \varphi_j \rbrace_{j=1}^b$，求平均值，得到一个强学习器$f$

   $$f(x) \leftarrow \frac{1}{b}\sum_{j=1}^b \varphi_j(x)$$

剪枝分类器不断地生长、积累，形成多层级的模型，该模型就称为决策树分类器。对决策树分类器进行Bagging学习的时候，通过随机选择输入变量中的某个维度进行学习，可以大幅提高分类器的性能，这种手法也称为随机森林学习。

Boosting学习法

Adaboost

Boosting学习，首先使用一个原始的学习算法，对训练样本

$$\lbrace (x_i,y_i)| x_i \in \mathbb{R}^d,y_i \in \lbrace +1,-1 \rbrace \rbrace_{i=1}^n$$

进行普通分类器的学习。如果原始算法的学习性能不高，就不能对所有的训练样本进行正确的分类。因此，对于不能正确分类的困难样本就加大其权重（反之，对于能正确分类的简单样本则减少其权重），再重新进行学习。然后，再循环多次进行加权学习，慢慢地就可以对所有的训练样本都进行正确的分类了。然而另一方面，在进行加权的过程中，最开始就能够正确分类的样本的权重会慢慢变小，有可能造成简单的样本反而不能正确分类的情况。

因此，Boosting学习应该边学习边更新样本的权重，并把学习过程中得到的所有分类器放在一起，对其可信度进行平均后训练得到最终的强分类器。

样本的加权方法多种多样，最为标准的就是Adaboost算法

Adaboost学习算法：

1. 把训练样本$\lbrace (x_i,y_i) \rbrace_{i=1}^n$对应的各个权重$\lbrace \omega_i \rbrace_{i=1}^n$设置为均等，即1/n，并把强分类器$f$的初始值设为零

   $$\omega_1,\dots,\omega_n \leftarrow 1/n, f\leftarrow0$$

2. 对$j=1,\dots,b$重复进行如下计算

   1. 对于现在的样本权重$\lbrace \omega_i \rbrace_{i=1}^n$，对加权的误分类率（0/1损失的权重之和）$R(\varphi)$为最小的弱分类器$\varphi_j$进行学习

      $$\varphi_j = \mathop{argmin}_{\varphi}R(\varphi),R(\varphi)=\sum_{i=1}^n \frac{\omega_i}{2}(1-\varphi(x_i)y_i)$$

   2. 通过下式 定义弱分类器$\varphi_i$的权重$\theta_j$由下

      $$\theta_j = \frac{1}{2}log\frac{1-R(\varphi_j)}{R(\varphi_j)}$$

   3. 通过下式更新强分类器$f$

      $$f \leftarrow f+ \theta_j \varphi_j$$

   4. 通过下式更新样本权重$\lbrace \omega_i \rbrace_{i=1}^n$

      $$\omega_i \leftarrow \frac{exp(-f(x_i)y_i)}{\sum_{i'=1}^n exp(-f(x_{i'})y_i)},\forall i=1,\dots,n$$

​