【概述】

在 PAC 学习理论概述中，介绍了 PAC 学习理论，由于恰 PAC 学习并不实际，因此更重要的是研究假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 不同的情景，即在给定 $n$ 个样本的训练集 $D$ 时，找出满足误差参数 $\epsilon$ 的假设

在 $|\mathcal{H}|$ 有限时，称假设空间 $\mathcal{H}$ 为有限假设空间，其可分为两种情形：

可分情形：目标概念 $c$ 属于假设空间 $\mathcal{H}$，即 $c\in \mathcal{H}$
不可分情形：目标概念 $c$ 不存在于假设空间 $\mathcal{H}$，即 $c\notin \mathcal{H}$

【可分情形】

基本思想

在可分情形下，目标概念 $c$ 属于假设空间 $\mathcal{H}$，即 $c\in \mathcal{H}$，由于 $D$ 中的样本标记都是由目标概念 $c$ 赋予的，且目标概念 $c$ 存在于假设空间 $\mathcal{h}$ 中，那么任何在训练集 $D$ 上出现的标记错误的假设，肯定不是目标概念 $c$，因此，只需要保留与 $D$ 一致的假设，剔除与 $D$ 不一致的假设即可

若训练集 $D$ 足够大，那么可不断借助 $D$ 中的样本剔除不一致的假设，直到假设空间 $\mathcal{H}$ 中仅剩一个假设为止，这个假设就是目标概念 $c$

等效假设的区分

通常情况下，由于训练集规模有限，假设空间 $\mathcal{H}$ 中可能存在不止一个与 $D$ 一致的等效假设，对于这些等效假设，无法根据 $D$ 对它们的优劣进一步的区分

对 PAC 学习来说，只要训练集 $D$ 的规模能够使学习算法 $\mathcal{L}$ 以概率 $1-\delta$ 找到目标假设的 $\epsilon$ 近似即可

假设 $h$ 的泛化误差大于 $\epsilon$，对分布 $\mathcal{D}$ 上随机采样得到的任意样本 $(\mathbf{x},y)$，其在训练集 $D$ 仍表现完美的假设出现的概率为：

$\begin{align*} P(h(\mathbf{x})=y) &= 1-P(h(\mathbf{x})\neq y) \\ &= 1-E(h) \\ &< 1-\epsilon \end{align*}$

由于 $D$ 包含 $n$ 个从 $\mathcal{D}$ 独立同分布采样而得的样本，因此 $h$ 与 $D$ 表现一致的概率为：

$\begin{align*} P\Big[\big(h(\mathbf{x}_1)=y_1\big) \wedge \cdots \wedge \big(h(\mathbf{x}_n)=y_n\big) \Big] &= \Big[1-P\big(h(\mathbf{x}\neq y)\big)\Big]^n \\ &< (1-\epsilon)^n \end{align*}$

又由于事先并不知道学习算法 $\mathcal{L}$ 会输出 $\mathcal{H}$ 中的哪个假设，因此仅需保证泛化误差大于 $\epsilon$，且在训练集上表现完美的所有假设出现概率和不大于 $\delta$ 即可

对于概率和，有：

$\begin{align*} P\Big( h\in\mathcal{H}:E(h)> \epsilon \wedge \hat{E}(h)=0 \Big) &< |\mathcal{H}|(1-\epsilon)^n \\ &< |\mathcal{H}|e^{-n\epsilon} \end{align*}$

令上式不大于 $\delta$，即：

$|\mathcal{H}| e^{-n\epsilon} \leq \delta$

可得：

$n \geq \frac{1}{\epsilon} (\ln |\mathcal{H}| + \ln \frac{1}{\delta})$

由此可知，有限假设空间 $\mathcal{H}$ 都是 PAC 可学习的，所需的样本数目如上式所示，输出假设 $h$ 的泛化误差随样本数量的增多而收敛到 $0$，收敛速率为 $O(\frac{1}{n})$

【不可分情形】

基本思想

在不可分情形下，目标概念 $c$ 不存在于假设空间 $\mathcal{H}$，即 $c\notin \mathcal{H}$，假定对任意 $h\in\mathcal{H},\hat{E}(h)\neq 0$，即假设空间 $\mathcal{H}$ 中的任意假设都会在训练集上出现或多或少的错误

若训练集 $D$ 包含 $n$ 个从分布 $\mathcal{D}$ 上独立同分布采样得到的样本，$0<\epsilon< 1$，则对任意 $h\in \mathcal{H}$，根据 Hoeffding 不等式，有：

$\begin{gather*} P(\hat{E}(h)-E(h)\geq\epsilon) \leq exp(-2n\epsilon^2) \\ P(E(h)-\hat{E}(h)\geq\epsilon) \leq exp(-2n\epsilon^2) \\ P(|E(h)-\hat{E}(h)|\geq\epsilon) \leq 2exp(-2n\epsilon^2) \\ \end{gather*}$

进一步，可知下式以至少 $1-\delta$ 的概率成立

$\hat{E}(h)-\sqrt{\frac{\ln \frac{2}{\delta}}{2n}} \leq E(h)\leq \hat{E}(h)+\sqrt{\frac{\ln \frac{2}{\delta}}{2n}}$

上式表明，在样本数量 $n$ 较大时，假设 $h$ 的经验误差 $\hat{E}(h)$ 是其泛化误差 $E(h)$ 很好的近似

那么对于有限假设空间 $\mathcal{H}$ 来说，有：

$P\Bigg(|E(h)-\hat{E}(h)|\geq \sqrt{\frac{\ln|\mathcal{H}| + \ln \frac{2}{\delta}}{2n}} \Bigg) \geq 1-\delta$

显然，学习算法无法习得目标概念 $c$ 的 $\epsilon$ 近似，但当假设空间 $\mathcal{H}$ 给定时，必定存在一个泛化误差最小的假设

$\arg \min_{h\in\mathcal{H}} E(h)$

找到该泛化误差最小的假设的 $\epsilon$ 近似也不失为一个较好的目标，那么以此为目标可将 PAC 学习推广到不可分情形，即 $c\notin \mathcal{C}$ 的情况，这被称为不可知学习（Agnostic Learning）

不可知学习

假设从分布 $\mathcal{D}$ 中独立同分布采样得到的样本数目为 $n$，$0<\epsilon,\delta<1$，对于所有分布 $\mathcal{D}$，若存在学习算法 $\mathcal{L}$ 和多项式函数 $\text{poly}(\cdot,\cdot,\cdot,\cdot)$，使得对任意 $n$ 有

$n\geq \text{poly}(\frac{1}{\epsilon},\frac{1}{\delta},\text{size}(\mathbf{x}),\text{size}(c))$

学习算法 $\mathcal{L}$ 能从假设空间 $\mathcal{H}$ 中输出满足下式的假设 $h$

$P\big(E(h) -\min_{h'\in\mathcal{H}} E(h') \leq \epsilon \big) \geq 1-\delta$

则称假设空间 $\mathcal{H}$ 是不可知 PAC 可学习的

与 PAC 可学习类似，若学习算法 $\mathcal{L}$ 的运行事件也是多项式函数

$\text{poly}(\frac{1}{\epsilon},\frac{1}{\delta},\text{size}(\mathbf{x}),\text{size}(c))$

则称假设空间 $\mathcal{H}$ 是高效不可知 PAC 可学习的，学习算法 $\mathcal{L}$ 不被称为假设空间 $\mathcal{H}$ 的不可知 PAC 学习算法，满足上述要求的最小 $n$ 被称为学习算法 $\mathcal{L}$ 的样本复杂度