【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.可分情形
可分情形意味着目标概念$c$属于假设空间$\mathcal{H}$，即$c\in \mathcal{H}$。给定包含$m$个样例的训练集$D$，如何找出满足误差参数的假设呢？
容易想到一种简单的学习策略：既然$D$中样例标记都是由目标概念$c$赋予的，并且$c$存在于假设空间$\mathcal{H}$中，那么，任何在训练集$D$上出现标记错误的假设肯定不是目标概念$c$。于是，我们只需保留与$D$一致的假设，剔除与$D$不一致的假设即可。若训练集$D$足够大，则可不断借助$D$中的样例剔除不一致的假设，直到$\mathcal{H}$中仅剩下一个假设为止，这个假设就是目标概念$c$，通常情形下，由于训练集规模有限，假设空间$\mathcal{H}$中可能存在不止一个与$D$一致的“等效”假设，对这些等效假设，无法根据$D$来对它们的优劣做进一步区分。
到底需多少样例才能学得目标概念$c$的有效近似呢？对PAC学习来说，只要训练集$D$的规模能使学习算法$\mathcal{L}$以概率$1-\delta$找到目标假设的$\epsilon$近似即可。
我们先估计泛化误差大于$\epsilon$但在训练集上仍表现完美的假设出现的概率。假定$h$的泛化误差大于$\epsilon$，对分布$\mathcal{D}$上随机采样而得的任何样例$(\mathbf{x},y)$，有：
\[\begin{align}P(h(\mathbf{x})=y) &= 1-P(h(\mathbf{x})\neq y) \\&= 1-E(h) \\&< 1-\epsilon \end{align} \tag{1}\]由于$D$包含$m$个从$\mathcal{D}$独立同分布采样而得的样例，因此，$h$与$D$表现一致的概率为：
\[\begin{align} P((h(\mathbf{x}_1)=y_1) \land \cdots \land (h(\mathbf{x}_m)=y_m)) &= (1-P(h(\mathbf{x})\neq y))^m \\&< (1-\epsilon)^m \end{align} \tag{2}\]我们事先并不知道学习算法$\mathcal{L}$会输出$\mathcal{H}$中的哪个假设，但仅需保证泛化误差大于$\epsilon$，且在训练集上表现完美的所有假设出现概率之和不大于$\delta$即可：
\[\begin{align} P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0) &< \lvert \mathcal{H} \rvert (1-\epsilon)^m \\&< \lvert \mathcal{H} \rvert e^{-m\epsilon} \end{align} \tag{3}\]令式(3)不大于$\delta$，即：
\[\lvert \mathcal{H} \rvert e^{-m\epsilon} \leqslant \delta \tag{4}\]可得：
\[m \geqslant \frac{1}{\epsilon} (\ln \lvert \mathcal{H} \rvert + \ln \frac{1}{\delta} ) \tag{5}\]由此可知，有限假设空间$\mathcal{H}$都是PAC可学习的，所需的样例数目如式(5)所示，输出假设$h$的泛化误差随样例数目的增多而收敛到0，收敛速率为$O(\frac{1}{m})$。
1.1.式(3)的推导
首先解释为什么“我们事先并不知道学习算法$\mathcal{L}$会输出$\mathcal{H}$中的哪个假设”，因为一些学习算法对用一个观察集$D$的输出结果是非确定的，比如感知机就是个典型的例子，训练样本的顺序也会影响感知机学习到的假设$h$参数的值。泛化误差大于$\epsilon$且经验误差为0的假设（即在训练集上表现完美的假设）出现的概率可以表示为$P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0)$，根据式(2)，每一个这样的假设$h$都满足$P(E(h) > \epsilon \land \hat{E}(h) = 0) < (1-\epsilon)^m$，假设一共有$\lvert \mathcal{H} \rvert$这么多个这样的假设$h$，因为每个假设$h$满足$E(h)>\epsilon$且$\hat{E}(h)=0$是互斥的，因此总的概率$P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0)$就是这些互斥事件之和，即：
\[\begin{align} P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0) &= \sum_{i}^{\lvert \mathcal{H} \rvert} P(E(h_i) > \epsilon \land \hat{E}(h_i) = 0) \\&< \lvert \mathcal{H} \rvert (1-\epsilon)^m \end{align}\]式(3)的第二个小于号实际上是要证明$\lvert \mathcal{H} \rvert (1-\epsilon)^m < \lvert \mathcal{H} \rvert e^{-m\epsilon}$，即证明$(1-\epsilon)^m < e^{-m\epsilon}$，其中$\epsilon \in (0,1]$，$m$是正整数，推导如下。
当$\epsilon=1$时，显然成立。当$\epsilon \in (0,1)$时，因为左式和右式的值域均大于0，所以可以左右两边同时取对数，又因为对数函数是单调递增函数，所以即证明$m\ln (1-\epsilon) < -m\epsilon$，即证明$\ln (1-\epsilon) < -\epsilon$。令$f(\epsilon) = \ln (1-\epsilon) + \epsilon$，其中$\epsilon \in (0,1)$，$f’(\epsilon) = 1 - \frac{1}{1-\epsilon} =0$，$\epsilon=0$取极大值0，因此$\ln (1-\epsilon)<-\epsilon$，也即$\lvert \mathcal{H} \rvert (1-\epsilon)^m < \lvert \mathcal{H} \rvert e^{-m\epsilon}$成立。
1.2.式(4)的推导
回到我们要回答的问题：到底需要多少样例才能学得目标概念$c$的有效近似。只要训练集$D$的规模能使学习算法$\mathcal{L}$以概率$1-\delta$找到目标假设的$\epsilon$近似即可。根据式(3)，学习算法$\mathcal{L}$生成的假设大于目标假设的$\epsilon$近似的概率为$P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0) < \lvert \mathcal{H} \rvert e^{-m\epsilon}$，因此学习算法$\mathcal{L}$生成的假设落在目标假设的$\epsilon$近似的概率为$1-P(h \in \mathcal{H} : E(h) > \epsilon \land \hat{E}(h) = 0) \geqslant 1- \lvert \mathcal{H} \rvert e^{-m\epsilon}$，这个概率我们希望至少是$1-\delta$，因此$1-\delta \leqslant 1- \lvert \mathcal{H} \rvert e^{-m\epsilon}$，即$\lvert \mathcal{H} \rvert e^{-m\epsilon} \leqslant \delta$。
1.3.式(5)的推导
\[\lvert \mathcal{H} \rvert e^{-m\epsilon} \leqslant \delta\] \[e^{-m\epsilon} \leqslant \frac{\delta}{\lvert \mathcal{H} \rvert}\] \[-m\epsilon \leqslant \ln \delta - \ln \lvert \mathcal{H} \rvert\] \[m \geqslant \frac{1}{\epsilon} \left( \ln \lvert \mathcal{H} \rvert + \ln \frac{1}{\delta} \right)\]这个结论也是我们在机器学习中的一个共识，即可供模型训练的观测集样本数量越多，机器学习模型的泛化性能越好。
2.不可分情形
对较为困难的学习问题，目标概念$c$往往不存在于假设空间$\mathcal{H}$中。假定对于任何$h\in \mathcal{H},\hat{E}(h)\neq 0$，也就是说，$\mathcal{H}$中的任意一个假设都会在训练集上出现或多或少的错误。由Hoeffding不等式易知：
引理12.1 若训练集$D$包含$m$个从分布$\mathcal{D}$上独立同分布采样而得的样例，$0<\epsilon <1$，则对任意$h \in \mathcal{H}$，有：
\[P(\hat{E}(h)-E(h) \geqslant \epsilon) \leqslant \exp (-2m\epsilon^2) \tag{6}\] \[P(E(h)-\hat{E}(h) \geqslant \epsilon) \leqslant \exp(-2m\epsilon^2) \tag{7}\] \[P(\lvert E(h)-\hat{E}(h) \rvert \geqslant \epsilon) \leqslant 2 \exp (-2m\epsilon^2) \tag{8}\]推论12.1 若训练集$D$包含$m$个从分布$\mathcal{D}$上独立同分布采样而得的样例，$0< \epsilon < 1$，则对任意$h \in \mathcal{H}$，式(9)以至少$1-\delta$的概率成立：
\[\hat{E}(h) - \sqrt{\frac{\ln (2/\delta)}{2m}} \leqslant E(h) \leqslant \hat{E}(h) + \sqrt{\frac{\ln (2/\delta)}{2m}} \tag{9}\]推论12.1表明，样例数目$m$较大时，$h$的经验误差是其泛化误差很好的近似。对于有限假设空间$\mathcal{H}$，我们有：
定理12.1 若$\mathcal{H}$为有限假设空间，$0 < \delta <1$，则对任意$h \in \mathcal{H}$，有：
\[P\left( \lvert E(h)-\hat{E}(h) \rvert \leqslant \sqrt{\frac{\ln \lvert \mathcal{H} \rvert + \ln (2/\delta)}{2m}} \right) \geqslant 1-\delta \tag{10}\]显然，当$c \notin \mathcal{H}$时，学习算法$\mathcal{L}$无法学得目标概念$c$的$\epsilon$近似。但是，当假设空间$\mathcal{H}$给定时，其中必存在一个泛化误差最小的假设，找出此假设的$\epsilon$近似也不失为一个较好的目标。$\mathcal{H}$中泛化误差最小的假设是$\text{argmin}_{h\in\mathcal{H}}E(h)$，于是，以此为目标可将PAC学习推广到$c \notin \mathcal{H}$的情况，这称为“不可知学习”（agnostic learning）。相应的，我们有：
定义12.5 不可知PAC可学习（agnostic PAC learnable）：令$m$表示从分布$\mathcal{D}$中独立同分布采样得到的样例数目，$0<\epsilon,\delta < 1$，对所有分布$\mathcal{D}$，若存在学习算法$\mathcal{L}$和多项式函数$\text{poly}(\cdot,\cdot,\cdot,\cdot)$，使得对于任何$m\geqslant \text{poly} (1/\epsilon,1/\delta,\text{size}(\mathbf{x}),\text{size}(c))$，$\mathcal{L}$能从假设空间$\mathcal{H}$中输出满足式(11)的假设$h$：
\[P(E(h)-\min_{h'\in \mathcal{H}} E(h') \leqslant \epsilon) \geqslant 1-\delta \tag{11}\]则称假设空间$\mathcal{H}$是不可知PAC可学习的。
与PAC可学习类似，若学习算法$\mathcal{L}$的运行时间也是多项式函数$\text{poly} (1/\epsilon,1/\delta,\text{size}(\mathbf{x}),\text{size}(c))$，则称假设空间$\mathcal{H}$是高效不可知PAC可学习的，学习算法$\mathcal{L}$则称为假设空间$\mathcal{H}$的不可知PAC学习算法，满足上述要求的最小$m$称为学习算法$\mathcal{L}$的样本复杂度。
2.1.对于式(6)-式(8)的理解
Hoeffding不等式中用到了$m$个独立随机变量，我们这里将这$m$个独立随机变量视为$m$个预测误差（归一化到$[0,1]$）：$\ell (h(x_i),y_i)$。这$m$个预测误差的均值便是经验误差$\hat{E}(h)$，而这$m$个预测误差的期望的均值便是泛化误差$E(h)$。其中，式(6)是经验误差大于泛化误差的情况，式(7)是泛化误差大于经验误差的情况。
2.2.式(9)的推导
令$\delta = 2e^{-2m\epsilon^2}$，则$\epsilon = \sqrt{\frac{\ln (2/\delta)}{2m}}$，由式(8)：
\[\begin{align} P(\lvert E(h)-\hat{E}(h) \rvert \geqslant \epsilon ) &\leqslant 2 \exp (-2m\epsilon^2) \\ P(\lvert E(h)-\hat{E}(h) \rvert \geqslant \epsilon ) &\leqslant \delta \\ P(\lvert E(h)-\hat{E}(h) \rvert \leqslant \epsilon ) &\geqslant 1-\delta \\ P(-\epsilon \leqslant E(h)-\hat{E}(h) \leqslant \epsilon) &\geqslant 1-\delta \\ P(\hat{E}(h)-\epsilon \leqslant E(h) \leqslant \hat{E}(h)+\epsilon) &\geqslant 1-\delta \end{align}\]代入$\epsilon = \sqrt{\frac{\ln (2/\delta)}{2m}}$得证。
2.3.式(10)的推导
令$h_1,h_2,…,h_{\lvert \mathcal{H} \rvert}$表示假设空间$\mathcal{H}$中的假设，有：
\[\begin{align} P(\exists h \in \mathcal{H} : \lvert E(h) - \hat{E}(h) \rvert > \epsilon) &= P \left( (\lvert E_{h_1} - \hat{E}_{h_1} \rvert > \epsilon) \lor \cdots \lor (\lvert E_{h_{\lvert \mathcal{H} \rvert}} - \hat{E}_{h_{\lvert \mathcal{H}\rvert}} \rvert > \epsilon) \right) \\&\leqslant \sum_{h \in \mathcal{H}} P(\lvert E(h)-\hat{E}(h) \rvert > \epsilon) \end{align}\]这一步很好理解，即存在一个假设$h$使得$\lvert E(h)-\hat{E}(h) \rvert > \epsilon$的概率可以表示为对假设空间内所有的假设$h_i,i\in 1,…,\lvert \mathcal{H} \rvert$，使得$\lvert E_{h_i}-\hat{E}_{h_i}\rvert > \epsilon$这个事件成立的“或”事件。因为$P(A \lor B) = P(A)+P(B) - P(A \land B)$，而$P(A \land B) \geqslant 0$，所以最后一行的不等式成立。
由式(8)可得：
\[\sum_{h\in \mathcal{H}} P(\lvert E(h)-\hat{E}(h) \rvert > \epsilon) \leqslant 2 \lvert \mathcal{H} \rvert \exp (-2m\epsilon^2)\]因此，
\[\begin{align} P(\exists h \in \mathcal{H} : \lvert E(h) - \hat{E}(h) \rvert > \epsilon) &\leqslant \sum_{h\in \mathcal{H}} P(\lvert E(h)-\hat{E}(h) \rvert > \epsilon) \\&\leqslant 2 \lvert \mathcal{H} \rvert \exp (-2m\epsilon^2) \end{align}\]其对立事件：
\[\begin{align} P(\forall h \in \mathcal{H} : \lvert E(h)-\hat{E}(h) \rvert \leqslant \epsilon) &= 1- P(\exists h \in \mathcal{H} : \lvert E(h) - \hat{E}(h) \rvert > \epsilon) \\&\geqslant 1- 2 \lvert \mathcal{H} \rvert \exp (-2m\epsilon^2) \end{align}\]令$\delta = 2\lvert \mathcal{H} \rvert e^{-2m\epsilon^2}$，则$\epsilon = \sqrt{\frac{\ln \lvert \mathcal{H}\rvert + \ln (2/\delta)}{2m}}$，代入上式中即可得到：
\[P\left( \forall h \in \mathcal{H} : \lvert E(h)-\hat{E}(h) \rvert \leqslant \sqrt{\frac{\ln \lvert \mathcal{H}\rvert + \ln (2/\delta)}{2m}} \right) \geqslant 1-\delta\]其中$\forall h \in \mathcal{H}$这个前置条件可以省略。
