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