Learning is Impossible?

机器学习的目标：演算法A根据给定数据集D从假设空间H中选择一个与f最为接近的g，还要保证g与f在给定数据集之外的数据上表现也相似。

在资料以外的部分，g和f一不一样是不知道的，因为f是不知道的，但是我们想要知道资料以外的部分g和f是否接近，因此需要加一些假设：

霍夫丁不等式：有一个装有绿色小球和黄色小球的罐子（假设球数无限），从中进行N次有放回的取球实验，在这N次实验中取出黄色小球的频率为ν，只要N足够大，就可以用ν来估计μ，即罐子中黄色小球的实际概率。

足够大的N或者足够小的范围=>v和μ有很大的可能性是相似的。

将霍夫丁不等式与学习相联系，当h选定时，保证D里样本数N足够大且样本点是独立同分布的，就能保证h在整个输入空间里的表现（异常点的概率）与数据集内的表现（D里异常点的频率）在一定的概率范围内近似相等。

 

以上只是说明了当g给定时，验证g和f在输入空间上接不接近，但并没有学习如何从假设空间中挑选与f最接近的h作为g。

如果给定的h使得Ein(h)很小，那么可以说g=f（PAC），如果给定的h使得Ein(h)不是很小，那么g≠f（PAC），所以真正的学习算法应该能从假设空间中进行选择，找使得Ein(h)小的h做为g，而不是每次都选择固定的h。比如PLA就是每次都选择不同的直线，逼近最终能够正确分类的直线。

目前为止，我们得到的只是选择好固定的h作为g后，验证g和f是否接近的过程，即选择的h是否在数据集以外的部分和f的表现相同，过程如下：

接下来讲述如何做到从假设空间H中选择h，首先假设有有限个h。

思考：要不要选择在D上表现最好的h？D有无好坏？

不行，因为在D上表现最好的的确会使Ein最小，但是Eout有可能会很大，即Ein和Eout不接近，不能由Ein近似Eout。

举例：掷硬币，每次掷5次，进行150（M）次实验。

总共有M个h，有1个h在看得见的资料上全对，要不要选它？

我们发现在150次试验中，至少出现1次5个正面的概率是超过99%的（h越多，D成为某个hj的坏数据的可能性越大，很容易就会选择该hj），所以很容易就会认为Ein(h)=0，认为Eout(h)近似=0，但是实际上Eout(h)=1/2。很明显Ein(h)和Eout(h)不接近。认为5个正面是不好的样本（坏数据）。

坏数据：对于一个h，使得h在该数据内外表现差异很大的数据认为是坏数据。

为了让演算法自由选择H中的h，要求数据集D对所有的h来说都是好的数据。

霍夫丁不等式说明对h来说资料D是坏数据的概率不超过多少。

为了让演算法自由选择H中的h，要求数据集D对所有的h来说都是好的数据，D是坏数据≤D对h1来说是坏数据orD对h2来说是坏数据or......D对hM来说是坏数据。（因为D对h1和h2都有可能是坏数据，所以本质是求并集）

 

 

对于一个输入空间X，能够产生的用于训练的数据D有很多个，若对于一个h，给定的数据刚好就是坏数据的概率是小于等于霍夫丁的右式的；若有M个h，给定的数据是其中某个h的坏数据的概率是小于等于数据为h1的坏数据的概率+数据为h2的坏数据的概率+数据为h3的坏数据的概率+......+数据为hM的坏数据的概率。本质是求并集（小于等于的原因是有可能存在交集）。这里的M实际是|H|，即H的size。

说明当M有限时，N足够大，不等式右边就足够小，所以，假设空间有限，N足够大，不管A选择哪个h，Ein和Eout在一定范围内都是近似相等的，A根据D在H中挑选使得Ein小的g，就能说Ein=Eout(PAC)，即学习是可能的。

 

思考当假设空间H是无限的时候，还能学习吗？