机器学习基石在证明过程中的思想，可以类比于集合论的思想，比如$f$是最完美的模型(函数)，那么$h$是假设函数空间(hypothesis set)$H$中的某个假设函数，$g$则是最接近$f$的那个$h$。
机器学习真的可行吗？
我们举个例子：
输入特征x是二进制、三维的，对应有8种输入，输出为y。现在假设其中5个为训练样本，有8个hypothesis在训练集D上，对应的输出都完全正确。因此在已知数据D上，$g \approx f$。但是在D以外的另外3个数据集上，我们完全无法预测对应的输出应该是哪个。
这样看起来我们似乎只能保证在D上有很好的分类效果，机器学习的这种特性又被称为没有免费午餐定理(NFL,No Free Launch)。关于NFL定理：
NFL定理最重要意义是，在脱离实际意义情况下，空泛地谈论哪种算法好毫无意义，要谈论算法优劣必须针对具体学习问题。——百度百科
上面的例子的确很绝望，模型根本没有泛化能力。当然这只是针对这个例子，在研究其他问题时，模型是可以泛化的不错的，接下来就要证明这个。
推断未知世界
换一个场景，我们现在在摸球：
- bin为总体，其中$P(\text {orange})=\mu$，$P(\text {green})=1-\mu$。但我们不知道$\mu$具体指。
- sample从bin中提取的样本，样本个数为$N$，其中orange的比例为$\mathcal{V}$，green的比例为$1-\nu$，$\nu$是可以计算的。
那么$\mu \approx \nu$？在概率论中，需要满足Hoeffding`s Inequality：
$\mathbb{P}[|\nu-\mu|>\epsilon] \leq 2 \exp \left(-2 \epsilon^{2} N\right)$
注：$\epsilon$是容忍度，当$\mu$和$\nu$的差别小于容忍度时，我们称$\mu$和$\nu$”差不多“(PAC，Probably approximately correct)。公式中描述的是$\mu$和$\nu$的差别大于容忍度的概率，我们当然希望它越小越好。观察右边发现，$\epsilon^{2}$增大(looser gap)或是$N$增大(增加样本)都能使得概率的上限减小，从而使得$\mu \approx \nu$。
Connection to Learning
我们把learning和抓球问题结合起来。
罐子相当于世界上所有有关该问题的样本空间，里面的每个球代表着每个样本，从样本中抽取的N个球类比于我们所拥有的训练样本。橙色的球代表着用模型预测数据后$h\left(x\right) \neq f\left(x\right)$，绿色的球代表$h\left(x\right)=f\left(x\right)$。根据上一part结论，如果抽样样本N够大，那么就可以从抽样样本中的$h(x) \neq f(x)$的概率来推导抽样样本以外的所有样本
$h(x) \neq f(x)$的概率。
从数学角度上看，这里的$h(x) \neq f(x)$可以看成是一个error，则可以称$h(x)$在sample中出现error的比例记为$E_{i n}$(in-sample-error)，在总体上的error所占比例记为$E_{o u t}$(out-of-sample-error)，则有：
同样，它的Hoeffding`s Inequality可以表示为：
$P\left[\left|E_{i n}(h)-E_{o u t}(h)\right|>\epsilon\right] \leq 2 \exp \left(-2 \epsilon^{2} N\right)$
因此，$E_{i n}(h)$和$E_{o u t}(h)$也满足PAC，这时候机器学习的模型预测会比较准确。
但这里仅仅针对一个固定的$h$(fixed h)而言，$E_{i n}(h)$和$E_{o u t}(h)$很接近。但这不能说是一个好的learning，因为$E_{in}(h)$可能很大，导致$E_{o u t}(h)$也很大。因此我们的算法$A$应该能从$H$中选择出最好的$h$，记为$g$(final hypothesis)因此需要添加一个验证流程(verification flow)，也就是用非训练集D里的数据来对$h$进行验证。
Bad Sample
$A$能够自由在$H$中挑选最合适的$h$，因此每个$h$($h_{1}、h_{2}…$)都有可能成为我们想要的$g$。但是我们的$D$只是来自于总体的一个抽样样本，因此必然存在抽样误差。比如你想知道抛硬币正面的概率，但有时候你连续抛了20次正面，能说明正面的概率为1吗？显然不行，因此这10次硬币，就是一个bad sample。
或者我们看不同的瓶子：
每次的$h$都不相同，而对于$h_{M}$来说，它在抽样数据$D_{M}$上的准确率为100%（都是绿球）。能说明样本空间中绿球的比例是1吗？答案显然是不行。对于learning 而言，其实Bad Sample就是$E_{in}$和$E_{out}$差别很大的情况。
我们之前说过，Hoeffding’s inequality保证了大多数的$D$都满足$E_{i n} \approx E_{o u t}$。但凡事总有个意外：
可以看出，对不同的$D_{n}$和$h_{n}$，都有可能成为Bad Sample，其上界可以表示为连级(union bound)的形式：
其中M为hypothesis的个数，N是样本$D$的数量，$\epsilon$是容忍度。union bound表明，当M有限，N足够大时。Bad Sample出现的概率比较低。如果这时能找到一个$g$，使得$E_{i n} \approx 0$，PAC就能保证$E_{o u t} \approx 0$。证明机器学习是可行的。
参考资料
[1] 机器学习的可行性
