第四章 Learning via Uniform Convergence

在第三章里我们学到了第一个形式化的学习模型PAC，接下来要介绍均匀收敛。通过这个工具，可以说明任意的有限集上，都可以使形式化的学习器满足agnostic PAC 学习器。

均匀收敛是可学习的充分条件

在之前的学习中讨论的问题的场景相对来说都比较简单，对一个假设集 $\mathcal{H}$ ,ERM的工作过程是这样的：

从真实分布中采样获得训练集S，算法对训练集上的每个假设都做一个错误风险计算，并在假设集中选出经验风险最小的假设。这样的话，对经验风险的最小化过程可以看作是对采样样本风险的最小化，保证了假设集中的所有假设的经验风险都是其真是风险的良好近似值。

为了执行如上的过程，需要保证采样获得的训练集是 $\epsilon$ /2-representative sample，即采样出的训练集需要满足条件 $\forall h\in\mathcal{H},|L_S(h)-L_D(h)|< \frac{\epsilon}{2}$

引理：在S满足 $\epsilon$ /2-representative sample的情况下，对于任意的 $ERM_{\mathcal{H}}(S)$ 的输出（ $any\, h_S\in argmin_{h\in\mathcal{H}}L_S(h)$ ）都满足 $L_{\mathcal{D}}(h_s)\leqslant \min \limits_{h\in\mathcal{H}}L(h)+\epsilon$

以上证明过程

这个引理充分说明了为了保证ERM规则是一个agnostic PAC learner，采样出的训练集要满足\epsilon/2 - representative sample

我们用均匀收敛去形式化定义这个要求：

如果存在一个函数 $m_{\mathcal{H}}^{UC}:(0,1)^2\rightarrow\mathbb{N}$ 使得对于每个 $\epsilon,\delta\in(0,1)$ 以及对于每个可能的在Z上的分布D,如果样本集S是从D中独里同分布采样的m个（ $m\geqslant m_{\mathcal{H}}^{UC}(\epsilon,\delta)$ ），那么就说这个样本集以至少1- $\delta$ 的概率满足\epsilon - representative sample。

怎样得到这个m值？

第三章和第四章总的来说是为了说明一件事情，就是如果我们的样本量足够大到大过 $m_{\mathcal{H}}^{UC}(\epsilon,\delta)$ 的时候，那么就可以说明我们现在在样本集S下对这个问题是可以学习的。

这个下界就是第三章最后遗留下的那个公式，如何得到这个下界，这里要隆重引入一个非常重要的不等式 Hoeffding's Inequality，其实这个不等式在机器学习当中的用途十分广泛，我们可以查到很多算法都用到了它作为一个天然上界，这个之后再慢慢介绍。

Hoeffding's不等式

$let \,L_S(h) = \frac{1}{m}\sum_{i = 1}^{m}\theta_i,and\,let \,L_\mathcal{D}(h) = \mu$ ，通过Hoeffding's不等式可以推出

若此时使得 $m\geqslant\frac{log(2|\mathcal{H}|/\delta)}{2\epsilon^2}$ 那么可以满足：

小结

第二章第三章和第四章一共讲了一个故事，那就是，我们怎么样才能让机器去学习，怎么样构建一个学习器以及其中的数学原理。首先这本书列出了事物内部本身具有一定的关联性，比如说，一个芒果变成橙色，就表示它成熟了。我们可以利用这些特征具有的性质去推测这个事物可能状态和结果。

但实际上，我们并不能真正的去掌握这个规则到底是什么样的，可能对于一个人来说，我看到了芒果是什么颜色，就知道他是否成熟的，那也是因为我具有了这个先验知识，对于机器来说，只能通过观察一些样本和结果，去尽量的找一些预测函数符合这个预测的要求。

那么会产生几个问题，首先是，我们提供给机器的数据肯定是有限的，那么机器能通过有限的数据去学习出来一个真实环境下的情况么？其次是，在真实环境中我们去采样出来的样本，真的就是完全拟合原始分布的样本么，我们也知道，现实环境中总是存在着许多偶然因素，因为每一个事物发展的过程都不能看作是一个独立的过程，复杂的系统里，总是会存在一些必然出现的偶然因素，那么在存在这些因素的情况下，怎样才能保证机器的可学习性呢？如果以上两点都可以解决，那么到底需要多少数据才能够使机器学习出来一个我们想要的映射函数呢？

以上三章通过数学证明的方式把这三个问题一一解答，这是我们之后去了解机器学习算法的一个重要基石。

最后编辑于：2019.04.11 18:41:48