机器学习第十二章集成学习（1）提升学习（Boosting） AdaBoost

资料来源参考：

清华大学出版社周志华《机器学习》第八章

清华大学出版社李航《统计学习方法》第八章

前言

前面几天一直都在写支持向量机的代码，但最后感觉还是写不出符合要求的代码，因此就仅留了一个备份在我的github做参考。

个体与集成

集成学习（ensemble learning）通过构建并结合多个学习学习器来完成学习任务，有时也被称为多分类器系统（multi-classifier system）、基于委员会的学习（committee-based learning）等。

我们首先用一幅图来表示集成学习的一般结构：

图中我们可以看出，集成学习先产生一组“个体学习器”（individual learner），再用某种策略将它们结合起来。通常来说，很多现有的学习算法都足矣从训练数据中产生一个个体学习器，C4.5决策树，BP神经网络等等。

一般来说，我们会将这种由个体学习器集成的算法分为两类，一类是同质（homogeneous）的，即集成中仅包含同种类型的额个体学习器，像“决策树集成”中就仅包含决策树，“神经网络集成”中就全是神经网络。同质集成中的个体学习器又称为基学习器（base learner），相应的学习算法也被称为基学习算法（base learning algorithm）。

第二类就是异质（heterogenous）的，相对同质，异质集成中的个体学习其就是由不同的学习算法生成的，这是，个体学习器就被称为组件学习器（component learner）

性能评估

现在我们来简单评估一下集成学习方法的性能：

考虑一个简单的例子，在二分类任务中，假定三个分类器在三个测试样本上的表现入下图所示，其中√代表正确，×代表分类错误，集成学习的结果则是由投票法（voting）决出，即“少数服从多数”：

可以看出，在a图中每个分类器只有66.6%的精度的时候，集成学习达到了100%的精度；在b图中，三个分类器相同导致集成性能没有提高；c图中由于每个分类器的精度只有33.3%导致集成学习的效果变得更糟。

由此我们可以看出来，集成学习中对个体学习器的要求应该是“好而不同”，即既满足准确性，又满足多样性（diversity），也即是说，学习器既不能太坏，而且学习器与学习器之间也要有差异。

例子比较具体但不具有普适性，因此，我们再来做一个更具体的分析：

考虑二分类问题 $$y∈\{-1,+1\}$ $和真实函数f，假定基分类器的错误率为ε，即对每个基分类器 $$h_i$ $有

假设集成通过简单投票法结合T个基分类器，若有超过半数的基分类器正确，则集成分类正确：

假设基分类器的错误率相互独立（注意到这是一个相当强的假设），则由Hoeffding不等式可知，集成的错误率为：

其中那个 $$\left(\begin{matrix}T\\k\end{matrix}\right)$ $表示 $$C^k_T$ $，意思是从T个中取k个的组合数。

Hoeffding不等式

关于Hoeffding不等式（霍弗丁不等式），它是由Wassily Hoeffding在1963年提出并证明，它的意义是提供一个上限，限定了随机变量偏离其期望值的概率。

我们可以借用西瓜书在p192中的习题8.1来大概了解一下这个不等式是如何用Hoeffding不等式得到的：

习题8.1

假设抛硬币正面朝上的概率为：

对 $$\delta > 0 ,k=(p-\delta)n$ $，有Hoeffding不等式：

试推导出式子：

解：

我们知道 $$P(h_i(x)≠f(x))=\epsilon$ $， $$H(n)$ $表示硬币在n次抛掷中朝上的概率，因此 $$P(H(n)≤k)$ $就是这个事件的分布函数。由 $$H(x)$ $的表达式我们有：

$h_i(x)= \left\{ \begin{matrix} 1&C_n^{x}p^{x}(1-p)^{n-{x}}>=0.5\\ -1&C_n^{x}p^{x}(1-p)^{n-{x}} < 0.5 \end{matrix} \right. \\ H(x)=sign(\sum^T_{i=1}h_i(x))$

记得我们假设每个基分类器的错误率为 $$\epsilon$ $并且相互独立，因此，超过50%的分类器分错一个事件的概率为:

$p(H(x)≠f(x))=\sum^{T/2}_{k=0}C^k_T(1-\epsilon)\epsilon^{T-k}=P(G(T)≤\frac{1}{2}T)$

T是分类器总数。由此我们可以得到 $$\frac{1}{2}T=(p-\delta)n=(\epsilon-\delta)T$ $ 再由Hoeffding不等式得到：

$\epsilon-\frac{1}{2}=\delta\\ -2\delta^2T=-2(\epsilon-\frac{1}{2})^2T=-\frac{1}{2}T(2\epsilon-1)^2$

从而得到:

$p(H(x)≠f(x))=P(G(T)≤\frac{1}{2}T) \\=\sum^{T/2}_{k=0}C^k_T(1-\epsilon)\epsilon^{T-k}=\sum^{T/2}_{k=0}\left(\begin{matrix}T\\k\end{matrix}\right)(1-\epsilon)\epsilon^{T-k} \\≤ e^{-\frac{1}{2}T(1-2\epsilon)^2}=exp(-\frac{1}{2}T(1-2\epsilon)^2)$

式子得证。

意义

这个式子的意义在于表示，随着集成中个体分类器数目T的增大，集成的错误率将指数级下降从而最终趋于0（这里还有一个前置条件就是个体分类器的错误率不能大于50%）。

但我们曾假设各个分类器之间的错误率是相互独立的，而实际上再同一个任务中个体学习器视为解决同一个问题训练出来的，这也就意味着它们之间显然不可能相互独立。换句话说，个体学习器的“准确性”和“多样性”本身也是存在冲突的。一般的，准确性很高之后，若要增加多样性就需要准确性做出一定的牺牲。因此，如何产生“好而不同”的个体学习器，便是集成学习研究的核心。

根据个体学习器的生成方式，目前集成学习方法大致可分为两大类，即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，这类方法的代表为提升（Boosting）方法；以及个体学习器间不存在强依赖关系，可同时生成的并行化方法，这类方法的代表为Bagging和随机森林（Random Forest）。

我们这一章就主要讨论一下关于Boosting的内容

AdaBoost

提升（boosting）方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重来学习多个分类器，并将这些分类器进行线性组合，提高分类性能。

引子

提升方法可以用一句著名的谚语来形容：“三个臭皮匠顶过一个诸葛亮”，事实上，虽然很搞笑，但这句话确实是提升方法的核心所在。

Kearns 和 Vailiant 在概率近似正确（probably approximately correct，PAC）学习的框架中，首先提出了强可学习（strongly learnable）和弱可学习（weakly learnable）的概念：

一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率高，那么这个概念就称是强可学习的；反之，如果存在一个多项式的学习算法能够学习它，但学习的正确率仅仅比随机猜测略好，那么这个概念就称为是弱可学习的。

但有趣的是，Schapire后来证明强可学习与弱可学习是等价的，换句话说，在PAC学习框架下，一个概念是强可学习的充分必要条件就是这个概念是弱可学习的，也即是说，在发现一个概念拥有“弱可学习算法”的时候，这个方法或许可以被提升（boost）为“强可学习算法”，这样的方法我们就称作是提升方法。

那么我们的问题就变成了如何提升方法，因为一般而言，发现弱学习方法要比发现强学习方法更简单，所以我们往往需要通过提升方法来得到强学习方法。关于提升方法的研究有很多，一个最具代表性的被提出的算法便是AdaBoost算法（AdaBoost algorithm）。

基本思路

假设我们有一个分类问题，给定一个训练样本集，从这个分类问题中求出一个粗糙的分类规则（弱分类器）往往要比求一个精确的分类规则（强分类器）容易得多。提升方法便是从弱学习算法出发，反复学习得到一系列弱分类器（又称为基本分类器），然后通过组合这些弱分类器来构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（或说训练数据的权值分布），来针对不同的训练分布调用若学习算法学习一系列弱分类器。

这样一来，对于提升方法而言，就有了两个问题需要去解决：

在每一轮如何改变训练数据的权值或概率分布？
如何将弱分类器组合成一个强分类器？

AdaBoost针对第一个问题的做法是提高那些被前一轮弱分类器错误分类样本的权值，并降低那些被正确分类的样本的权值。这样一来，经过一轮的权值加大后，后一轮的弱分类器就会更关注那些没有被正确分类的样本。持续下去，分类问题便会被一系列弱分类器“分而治之”。

而对于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决法，具体的所，就是加大误差率小的弱分类器的权值，使其在表决中起更大的作用，另一方面，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

AdaBoost算法

大概了解了思路之后，我们就可以来看一下AdaBoost的算法了：

假设给定一个二类分类的训练数据集：

其中，每个样本点由实例与标记组成。实例 $$x_i∈X\subseteq R^n$ $，标记 $$y_i∈Y=\{-1,+1\}$ $，X是实例空间，Y是标记集合

算法（AdaBoost）

输入：训练数据集；弱学习算法

输出：最终分类器

步骤：

1.初始化训练数据的权值分布：

2.对 $$m=1,2,...,M$ $

a. 使用权值分布 $$D_m$ $的训练数据集学习，得到基本分类器：

b. 计算 $$G_m(x)$ $在训练数据集上的分类误差率：

I是指示函数。

c. 计算 $$G_m(x)$ $的系数

这里的对数是自然对数（ $$ln$ $）

d. 更新训练数据集的权值分布

其中 $$Z_m$ $是规范化因子：

它使 $$D_{m+1}$ $成为一个概率分布。

3.构建基本分类器的线性组合：

从而得到最终分类器：

对于该算法我们作如下说明：

步骤1. 假设训练集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第一步能够在原始数据上学习基本分类器 $$G_1(x)$ $。

步骤2. 中AdaBoost反复学习基本分类器，在每一轮 $$m=1,2,...,M$ $中顺次地执行下列操作：

操作a.使用当前分布 $$D_m$ $加权的训练数据集，学习基本分类器 $$G_m(x)$ $
操作b.计算基本分类器 $$G_m(x)$ $在加权训练数据集上的分类误差率：这里 $$w_{mi}$ $表示第m轮中第i个实例的权值， $$\sum^N_{i=1}w_{mi}=1$ $。这表示 $$G_m(x)$ $在加权的训练数据集上的分类误差率是被分类器 $$G_m(x)$ $误分类样本的权值之和，由此可以看出数据权值分布 $$D_m$ $与基本分类器 $$G_m(x)$ $的分类误差率的关系。（一个样本被分错的次数越多，它的权值就会变得越大，而下一个分类器如果再分错这个样本，那么它的分类误差率也会相较分错一般的样本更大）
操作c.计算基本分类器 $$G_m(x)$ $的系数 $$\alpha_m$ $。其中 $$\alpha_m$ $表示 $$G_m(x)$ $在最终分类器中的重要性。由计算 $$\alpha_m$ $的表达式 $$\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$ $可知当 $$e_m≤\frac{1}{2}$ $时 $$\alpha_m≥0$ $，并且 $$\alpha_m$ $随着 $$e_m$ $的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
操作d.更新训练数据的权值为下一轮做准备，我们可以将（8.4）中的式子写成：由此得到被基本分类器 $$G_m(x)$ $误分类的权值得以扩大（正如我们在上面所说），而正确分类样本的权值就会缩小。两相比较，误分类样本的权值就会被放大 $$e^{2\alpha_m}=\frac{e_m}{1-e_m}$ $倍。从这里我们也可以看出AdaBoost的一个特点就是，不改变所给的训练数据，而是通过不断改变训练数据的圈子分部，使得训练数据在基本分类器的学习中起不同的作用。

步骤3. 线性组合 $$f(x)$ $实现M个基本分类器的加权表决。系数 $$\alpha_m$ $表示了基本分类器 $$G_m(x)$ $的重要性，要注意的是，在这里所有的 $$\alpha_m$ $之和并不为1. $$f(x)$ $的符号决定实例x的类， $$f(x)$ $的绝对值则表示分类的确信度（就像在支持向量机中所说的一样）。利用基本分类器的线性组合构建最终分类器便是AdaBoost的另一特点。

我们可以用一个更简洁的图片来表示整个算法结构：

AdaBoost例子

下面我们来看一个AdaBoost的例子：

给定下图所示的数据，假设弱分类器由 $$x < v$ $或 $$x > v$ $产生，其阈值v使该分类器在训练数据集上分类误差率最低。试用AdaBoost算法学习一个强分类器：

解

首先初始化数据权值分布：

对 $$m=1$ $（第一轮）

（a）在权值分布为 $$D_1$ $的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为

（b） $$G_1(x)$ $在训练数据集上的误差率为

$e_1=P(G_1(x_i)≠y_i)=0.3$

（c）计算 $$G_1(x)$ $的系数：

$\alpha_1=\frac{1}{2}ln\frac{1-e_1}{e_1}=0.4236$

（d）更新数据的权值分布：

并得到分类器 $$sign[f(x)]$ $在训练数据集上有3个误分类点。

对m=2（第二轮）

（a）在圈子分部为 $$D_2$ $的训练数据集上，阈值v是8.5时分类误差率最低，基本分类器为：

（b） $$G_2(x)$ $在训练数据集上的误差率:

$e_2=0.2143$

（C）计算得到 $$G_2(x)$ $的系数 $$\alpha_2=0.6496$ $

（d）更新训练数据权值分布：

并得到分类器 $$sign[f_2(x)]$ $在训练数据集上有3个误分类点。

对m=3（第三轮）

（a）基本分类器：

（b）误差率 $$e_3=0.1820$ $

（c）系数 $$\alpha_3=0.7514$ $

（d）更新训练数据的权值分布：

最终得到分类函数：

并且分类器 $$sign[f_3(x)]$ $在训练数据集上误分类点个数为0

于是我们得到最终分类器：

AdaBoost推导

在了解了AdaBoost的算法结构之后我们来讨论一下它的推导方式。

AdaBoost有多种推导方式，比较容易理解的是基于加性模型（additive model）（即基学习器的线性组合）

（我们可以使 $$h_t(x)=b(x;\gamma_t)$ $表示基函数， $$\gamma_t$ $为基函数的参数， $$\alpha_t$ $表示基函数的系数。）

来最小化指数损失函数（exponential loss function）：

更广泛的，我们称AdaBoost是由前向分步（forward stagewise）加法算法的特例，即模型是由基本分类其组成的加法模型，通常来说，前向分布算法就是在给定训练数据与损失函数 $$L(y,f(x))$ $的条件下求经验风险极小化问题：

（此处的β即加性模型表达式中的α，m即t，M即T）

向前分布学习的基本思想就是：从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，从而简化优化的复杂度。

将对应损失函数用指数损失函数代替之后就可以得到我们的AdaBoost算法，这个我们之后再来详细讨论，前面仅仅是为了了解一下AdaBoost的由来。

回到AdaBoost的推导，我们对指数损失函数中的 $$H(x)$ $求偏导，有：

令该式为0，我们可以解得：

从而有：

这个式子意味着 $$sign(H(x))$ $达到了贝叶斯最优错误率。换句话说，若指数函数最小化，分类错误率也将最小化；这也说明指数损失函数是分类任务原本0/1损失函数的一致的（consistent）替代损失函数（或许，我们可以将这个类比为支持向量集中合页损失函数作为的代理损失函数（surrogate loss function）？）。由于这个替代函数有更好的数学性质（像是连续可微），我们可以用它替代0/1损失函数作为优化目标。

在AdaBoost算法中，第一个基分类器 $$h_1$ $是通过直接将基学习算法用于初始分布数据而得；此后迭代地生成 $$h_t$ $和 $$\alpha_t$ $，当基分类器 $$h_t$ $基于分布 $$D_t$ $产生后，该基分类器的权重 $$\alpha_t$ $应使得 $$\alpha_th_t$ $最小化指数损失函数：

其中 $$\epsilon_t=P_{x\sim D_t}(h_t(x)≠f(x))$ $。考虑指数损失函数的导数：

令导数为0可解得：

这恰是AdaBoost算法中的分类器权重更新公式。

我们知道AdaBoost算法在步骤2.操作d.中获得 $$H_{t-1}$ $之后将对样本权值分布进行调整，使下一轮的基学习器 $$h_t$ $能纠正 $$H_{t-1}$ $的一些错误。我们假设有理想的 $$h_t$ $能纠正 $$H_{t-1}$ $的全部错误，即最小化

因为 $$f^2(x)=h^2_t(x)=1$ $，因此上式可使用 $$e^{-f(x)h_t(x)}$ $的泰勒展开式近似为：

（证明并不难，我们知道泰勒展开式为

$f(x)=\frac{f(x_0)}{0!}+\frac{f'(x_0)}{1!}(x-x_0)+...+\frac{f^n(x_0)}{n!}(x-x_0)^n+R_n(x)$

由此有

$e^x≈1+x+\frac{x^2}{2!}$

所以

$e^{-h(x)f(x)}=1-f(x)h_t(x)+\frac{f^2(x)h^2_t(x)}{2}$

）

于是，我们得到理想的基学习器为：

式中因为 $$E_{x\sim D}[e^{-f(x)H_{t-1}(x)}]$ $是一个常数（ $$e^{-1}(1-\delta)+e\delta ,\delta$ $表示集成分类器 $$H_{t-1}(x)$ $在原始数据集上的错误率），所以在计算中直接省略掉了。

令 $$D_t$ $表示一个分布：

这个式子表示第t轮数据集中的权值分布由t-1轮的集成分类器的损失除以期望乘上初始权值分布得到，换句话说，就是让t-1轮集成分类器在原始数据集中分出的误差越大的样本再误分的期望越小，对应权值越大。

根据期望的定义，这个式子等价于令

也即是将第t个基分类器在原始数据上的误分类期望转变成了在第t个数据集上的误分类期望。

由 $$f(x),h(x)∈\{-1,+1\}$ $，有：

所以有理想的基学习器：

由此可见，理想的 $$h_t$ $将在分布 $$D_t$ $下最小化分类误差，同时也即意味着基分类器将基于权值分布 $$D_t$ $来训练，且针对 $$D_t$ $的分类误差应小于0.5 。考虑到 $$D_t$ $和 $$D_{t+1}$ $的关系，有：

（这个公式的推导并不困难，用上面给出的 $$D_t(x)$ $关于 $$D(x)$ $的分布函数）

恰好就是AdaBoost算法在步骤3.中更新样本权值分布的公式。

至此我们就基于加性模型迭代式优化指数损失函数的角度推出了AdaBoost算法。

重采样与重赋权

重赋权法（re-weighting）表示在训练过程中的每一轮都根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基本学习算法则可通过重采样法（re-sampling）来实现，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。一般而言两个方法没有显著区别，但更为常见的是将二者结合：

因为Boosting算法在训练的每一轮都检查当前生成的基学习器是否满足基本条件（如基分类器的准确率是否比随机猜测高），一旦条件不满足，就需要抛弃当前基学习器，这个时候学习过程往往会停止。在这种情况下，初始设置的迭代次数T也许还远未达到，可能会导致最终集成中只包含很少的基学习器使得性能不佳。因此，若加入重采样法就可以让学习器获得重启动机会以避免训练过早停止——换句话说，就是在抛弃不满足条件的基学习器后，学习器可以根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的T轮完成。（重采样的方法本身也是一个需要另外专门详细讨论的内容，我们这里仅简单了解即可。）

从偏差-方差分解的角度来看，Boosting主要关注降低偏差（就是表示精确度的误差，可理解为经验风险），因此Boosting能够基于泛化性能很弱的学习器构建出很强的集成。

我们可以看一个以决策树桩为基学习器，再西瓜数据集3.0α（就是曾在决策树一章中用过的数据集，不需要特地去找，因为这对于我们要表达的内容其实并不重要）上运行AdaBoost算法的图例，不同规模（size）（指集成中包含的个体学习器数目）的集成及其基学习器所对应的分类边界如图：

介于截的图颜色是黑白的，我们将粗线理解为集成分类器的分类边界，细线理解为基学习器的分类边界即可。

关于AdaBoost的推导与误差分析，《统计学习方法》还有从另一个角度分析的方式（或许更偏向于代数角度？反正不是西瓜书这让人无比苦恼的概率分析角度），但由于结果一样仅是方法不同，我这里就不再赘述了。

ZyBlog

机器学习第十二章集成学习（1）提升学习（Boosting） AdaBoost

前言

个体与集成