PAC概率近似正确学习模型

《Understanding Machine Learning-From Theory to Algorithms》
第二章，最后一段关于predictor 失败的分析

一个upper bound的推导和理解

有了精度参数 $\epsilon$ , 我们就可以定义失败的假设 $L_{(D,f)}(h_S)>\epsilon$ . 我们有m个训练样本 $(x_1,...,x_m)$ ，是通过采样产生的，组成了样本集合 $S$ 。不同人/时间，采样的结果是不一样的，就有不同的样本集合，比如有 $S_1, S_2, ...,S_N$ . 这些样本集合有多大概率产生失败的predictor呢？记训练实例集为 $S|x=(x_1,...,x_m)$ . 我们关心的是下面概率的上界。

$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})$ #m-组实例采样中导致失败预测器的概率。

怎么算这个上界 upper bound?

引入bad hypothesis set的集合
$\mathcal{H}_B =\{h\in \mathcal{H}:L_{(D,f)}(h)>\epsilon\}$ .
从bad hypothesis出发，定义数据误导集
$M=\{S|x:\exists h \in \mathcal{H}_B,L_S(h)=0 \}$
也就是误导集是依赖bad hypothesis的，不同的 $h_B$ 会有不同的误导集，整个误导集是所有bad hypothesis的并集。
回到关注的问题中的集合 $\{S|x:L_{(D,f)}(h_S)>\epsilon\}$ , 这个集合等价于：
$\{S|x:L_{(D,f)}(h)>\epsilon,L_S(h)=0\}$ ,继续等价于：
$\{S|x:h \in \mathcal{H}_B,L_S(h)=0\}$ ，子集关系就出来了：
$\{S|x:L_{(D,f)}(h_S)>\epsilon\}\subseteq M$ , 这个集合只是误导集的子集而已。
概率不等关系也就出来了：
$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})\leq D^m(M)$
从第2点中可以看出 $M$ 还是个并集。 $M = \mathop{\cup}_{h\in\mathcal{H}_B}\{S|x:L_S(h)=0\}$ 。利用联合界的方式缩放：
$D^m(M)\leq\mathop{\Sigma}_{h\in\mathcal{H}_B} D^m(\{S|x:L_S(h)=0\})$ .
固定某个"bad"假设，展开：
$D^m(\{S|x:L_S(h)=0\})=D^m(\{S|x:\forall i, h(x_i)=f(x_i)\})=\mathop{\Pi}_{i=1}^m D(\{x_i: h(x_i)=f(x_i)\})$
对于每个sample, $D(\{x_i: h(x_i)=f(x_i)\})=1-L_{(D,f)}(h)\leq 1-\epsilon\leq e^{-\epsilon}$ ，注意第6步中使用的bad hypothesis, 所以不等式成立。
所以整个的上界upper bound
$D^m(\{S|x:L_{(D,f)}(h_S)>\epsilon\})\leq |\mathcal{H}|e^{-\epsilon m}$
说明：

假设空间很小 $|\mathcal{H}|=1$ , 训练样本量 $m$ 只需要很少；但是由于实际问题的复杂性， $|\mathcal{H}|$ 必须要很大(比如深度学习)。为了控制这个upper bound, 就必然要求大的 $m$ ，大数据量。
精度参数 $\epsilon$ 是一个要求指标，精度需求越高， $\epsilon$ 越小，实现相同的upper bound，就需要更大的 $m$ ，数据量和精度有关系。通过数据增强提高分类精度，这个公式也可以看出端倪。
算法理论分析的牛逼之处在于：给定少量的假设条件，就能够分析出关键配置对性能影响关系。