【机器学习基础】第二十七课:集成学习之个体与集成

集成学习简介,霍夫丁不等式

Posted by x-jeff on October 12, 2021

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.个体与集成

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

集成学习的一般结构:

如果个体学习器都是同一算法,例如都为C4.5决策树算法,则这样的集成是“同质”的(homogeneous)。同质集成中的个体学习器亦称“基学习器”(base learner),相应的学习算法称为“基学习算法”(base learning algorithm)。集成也可包含不同类型的个体学习器,这样的集成是“异质”的(heterogenous),此时,个体学习器常称为“组件学习器”(component learner)或直接称为个体学习器。

集成学习通过将多个学习器进行结合,常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”(weak learner)尤为明显,因此集成学习的很多理论研究都是针对弱学习器进行的,而基学习器有时也被直接称为弱学习器。但需注意的是,虽然从理论上来说使用弱学习器集成足以获得好的性能,但在实践中出于种种考虑,例如希望使用较少的个体学习器,或是重用关于常见学习器的一些经验等,人们往往会使用比较强的学习器。

弱学习器常指泛化性能略优于随机猜测的学习器;例如在二分类问题上精度略高于50%的分类器。

在一般经验中,如果把好坏不等的东西掺到一起,那么通常结果会是比最坏的要好一些,比最好的要坏一些。集成学习把多个学习器结合起来,如何能获得比最好的单一学习器更好的性能呢?

考虑一个简单的例子:在二分类任务中,假定三个分类器在三个测试样本上的表现如下图所示,其中对号表示分类正确,叉号表示分类错误,集成学习的结果通过投票法产生,即“少数服从多数”。

这个简单的例子显示出:要获得好的集成,个体学习器应“好而不同”,即个体学习器要有一定的“准确性”,即学习器不能太坏,并且要有“多样性”,即学习器间具有差异。

个体学习器至少不差于弱学习器。

我们来做个简单的分析。考虑二分类问题$y \in \{ -1,+1 \}$和真实函数$f$,假定基分类器的错误率为$\epsilon$,即对每个基分类器$h_i$有:

\[P(h_i(\mathbf x) \neq f (\mathbf x))=\epsilon \tag{1}\]

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

\[H(\mathbf x)=sign (\sum^T_{i=1} h_i (\mathbf x)) \tag{2}\]

为简化讨论,假设$T$为奇数。

假设基分类器的错误率相互独立,则由Hoeffding不等式(见本文第2部分)可知,集成的错误率为:

\[\begin{align} P(H(\mathbf x) \neq f(\mathbf x)) & = \sum^{\lfloor T/2 \rfloor}_{k=0} \begin{pmatrix} T \\ k \end{pmatrix} (1-\epsilon)^k \epsilon^{T-k} \\& \leqslant exp (-\frac{1}{2}T(1-2\epsilon)^2 ) \end{align} \tag{3}\]

k为分类正确的基分类器的个数。

式(3)的证明见本文第3部分。

式(3)显示出,随着集成中个体分类器数目T的增大,集成的错误率将指数级下降,最终趋向于零。

然而我们必须注意到,上面的分析有一个关键假设:基学习器的误差相互独立。在现实任务中,个体学习器是为解决同一个问题训练出来的,它们显然不可能相互独立!事实上,个体学习器的“准确性”和“多样性”本身就存在冲突。一般的,准确性很高之后,要增加多样性就需牺牲准确性。事实上,如何产生并结合“好而不同”的个体学习器,恰是集成学习研究的核心。

根据个体学习器的生成方式,目前的集成学习方法大致可分为两大类,即个体学习器间存在强依赖关系、必须串行生成的序列化方法,以及个体学习器间不存在强依赖关系、可同时生成的并行化方法;前者的代表是Boosting,后者的代表是Bagging和“随机森林”(Random Forest)。

2.霍夫丁不等式

霍夫丁不等式(Hoeffding’s inequality)适用于有界的随机变量。设有两两独立的一系列随机变量$X_1,…,X_n$。假设对所有的$1 \leqslant i \leqslant n$,$X_i$都是几乎有界的变量,即满足:

\[\mathbb{P} (X_i \in [a_i,b_i])=1 \tag{4}\]

那么这n个随机变量的经验期望:

\[\bar{X} = \frac{X_1+...+X_n}{n} \tag{5}\]

满足以下的不等式:

\[\mathbb{P} (\bar{X} - \mathbb{E}[\bar{X}] \geqslant t) \leqslant exp(-\frac{2t^2n^2}{\sum^n_{i=1} (b_i-a_i)^2}) \tag{6}\] \[\mathbb{P} (\mid \bar{X} - \mathbb{E}[\bar{X}] \mid\geqslant t) \leqslant 2exp(-\frac{2t^2n^2}{\sum^n_{i=1} (b_i-a_i)^2}) \tag{7}\]

2.1.伯努利随机变量的特例

伯努利分布

以投掷硬币为例,假设其正面朝上的概率为p,反面朝上的概率为1-p,投掷n次,可得以下不等式:

\[P(H(n) \leqslant k)=\sum^k_{i=0} \begin{pmatrix} n \\ i \end{pmatrix} p^i (1-p)^{n-i} \tag{8}\]

其中,$H(n)$为投掷n次,正面朝上的次数。

对某一$\delta>0$,有$k=(p-\delta)n$,则霍夫丁不等式可表示为:

\[P(H(n) \leqslant (p-\delta)n) \leqslant exp(-2\delta^2 n) \tag{9}\]

类似地,如果有$k=(p+\delta)n$且$\delta>0$,则可得到:

\[P(H(n) \geqslant (p+\delta)n) \leqslant exp(-2\delta^2 n) \tag{10}\]

综合式(9)和式(10)可得:

\[P((p-\delta)n \leqslant H(n) \leqslant (p+\delta)n) \geqslant 1- 2exp(-2\delta^2 n) \tag{11}\]

3.式(3)的证明

根据式(9),令$n=T,p=1-\epsilon,k=\frac{T}{2}$,可得$\delta=\frac{1}{2}-\epsilon$,那么:

\[\begin{align} P(H(\mathbf x) \neq f(\mathbf x)) & = P(H(T) \leqslant \lfloor T/2\rfloor ) \\&= P(H(T) \leqslant \frac{T}{2} ) \\& \leqslant exp (-\frac{1}{2}T(1-2\epsilon)^2 ) \end{align} \tag{12}\]

4.参考资料

  1. Hoeffding’s inequality