本节的主要内容来自Hsuan-Tien Lin的机器学习基石课程[1]。
Learning is PAC-possible, if enough statistical data and finite $\left\lvert\mathcal H\right\rvert$.
基本定义
- 未知的目标函数 $f:\mathcal X \rightarrow\mathcal Y$；
- $\mathcal X$的分布$P$；
- 训练集 $\mathcal D:\left(\mathbf x_1,y_1\right),\ldots,\left(\mathbf x_N,y_N\right)$；
- 学习算法 $\mathcal A$；
- 假设集 $\mathcal H$。
机器学习的任务就是找到$f$的近似$g$，使得$g\approx f$。利用学习算法$\mathcal A$，通过数据集$\mathcal D$，从$\mathcal H$中找到合适的$h$，当$g=h$有$g\approx f$。
Hoeffding不等式
能用从罐中抽样出橙色弹珠的比率$\nu$，作为罐中橙色弹珠出现概率$\mu$的估计么？Hoeffding不等式给出了答案， \begin{equation} P\left[\lvert\nu-\mu\rvert>\epsilon\right]\leq 2\exp\left(-2\epsilon^2N\right)， \end{equation} 当$N$很大时，$\nu$和$\mu$可能很接近（PAC，Probably Approximately Correct）。一个大的$N$和松散的$\epsilon$约束，使得$\nu\approx\mu$。
####问题
设$\mu=0.4$，若从罐中抽$10$个弹珠得到$\nu\leq 0.1$。利用Hoeffding不等式估计发生这样情况的概率界。
答案：$0.33$（该概率的精确值是$0.05$）
这个问题等价于：已知一次伯努利实验成功的概率为$0.4$，求$10$重伯努利实验中，最多出现一次成功的概率。 \begin{equation*} \begin{aligned} P(最多一次成功) = &P(10次都不成功) + P(仅有1次成功）\\ = & 0.6^{10}+ \binom{10}{1} \times 0.4^1 \times 0.6^9\\ = &0.0464 \approx 0.05 \end{aligned} \end{equation*}
概率与机器学习
如上图所示，将罐中的弹珠当作$\mathcal X$。对某个特定的假设$h$，若$h(\mathbf x)\neq f(\mathbf x)$则将弹珠涂为橙色，若$h(\mathbf x)= f(\mathbf x)$则将弹珠涂为绿色。将机器学习的可行性用概率问题进行判断。
对特定的$h$，抽样出来$N$个数据的in-sample误差定义为 \begin{equation} E_{in}\left(h\right) = {1\over N}\sum_{n=1}^N\left[\left[h\left(x_n\right)\neq y_n\right]\right]， \end{equation} $\mathcal X$中数据的out-sample误差定义为 \begin{equation} E_{out}\left(h\right) = \varepsilon_{\mathbf x\sim P}\left[\left[h\left(\mathbf x\right)\neq f\left(\mathbf x\right)\right]\right]， \end{equation} 于是得到类似的Hoeffding不等式 \begin{equation} P\left[\left\lvert E_{in}\left(h\right)-E_{out}\left(h\right)\right\rvert>\epsilon\right]\leq 2\exp\left(-2\epsilon^2N\right)。 \end{equation}
由上式可知，对所有$N$和$\epsilon$而言，在不需要知道$E_{out}\left(h\right)$、$f$和$P$的前提下，$E_{in}\left(h\right)=E_{out}\left(h\right)$近似可能正确。也就是说，如果$E_{in}\left(h\right)\approx E_{out}\left(h\right)$并且$E_{in}\left(h\right)$很小，可以得出$E_{out}\left(h\right)$也很小，进而可以得出对于同样分布$P$的数据$h\approx f$。
如果令$g=h$，上述情况是否表明学习是可行的了呢？事实上，上述情况只是验证了某个特定的$h$，机器学习是要从$\mathcal H$中找出满足条件的$h$作为$g$，还没有$h$选择的过程。
从概率到机器学习
不好的数据集（BAD Data）是指，存在$h$使得该数据集上$E_{out}\left(h\right)$和$E_{in}\left(h\right)$差异很大。
上图中$\mathcal D_i$表示有$N$个数据点的数据集，BAD标注的是不好的数据集。每个$h_j$对应行上出现BAD的概率通过Hoeffding定理限定，对某个$h_j$，$E_{out}\left(h\right)$和$E_{in}\left(h\right)$差异很大的概率是受约束的。Hoeffding定理保证的是每行不会有太多的BAD。
如果某个数据集$\mathcal D_i$上，对至少一个$h_j$是不好的数据集，也就是上图中的列至少存在一个BAD，那么在该数据集上，不能通过算法$\mathcal A$自由的从假设$\mathcal H$中选择$h$，因为总存在$E_{out}\left(h\right)$和$E_{in}\left(h\right)$差异很大的情况。机器学习期望的是算法$\mathcal A$能在好的数据集（例如$\mathcal D_{1126}$）上自由的选择$h$。
根据上图可推算，选到不好数据集的概率 \begin{equation} P_{\mathcal D}\left[\mbox{BAD } \mathcal D\right] \leq 2M\exp\left(-2\epsilon^2N\right)， \end{equation} 由此可见，选到不好数据集的概率是受限的，也就是可能找到好数据集，使得可以利用它自由在假设$\mathcal H$中选择。
如果$\left\lvert\mathcal H\right\rvert=M$有限，并且$N$足够大，使得可以通过$\mathcal A$选择到$g$，选择$E_{in}\left(h_m\right)$最小的那个$h_m$作为$g$，使得$E_{out}\left(g\right)\approx E_{in}\left(g\right)$。如果$\mathcal A$找到一个$g$使得$E_{in}\left(g\right)\approx 0$，PAC保证了$E_{out}\left(g\right)\approx 0$，也就是说学习是可行的。
因此，学习的可行性通过以下两条保证：
- 可以通过$E_{in}\left(h\right)$估计$E_{out}\left(h\right)$；
- 存在数据集$\mathcal D$，使得可以在$\mathcal H$中自由的选择$h$。
满足这两条的前提条件是假设集$\mathcal H$中候选$h$的数目$M$有限且$\mathcal D$中数据点数量$N$足够大。
如果$M=\infty$，咋办？
参考资料
- [1]H.-T. Lin, “Lecture 4: Feasibility of Learning.” Coursera, 2014. [Online]
