04 Feasibility of Learning
一.Learning is Impossible?
机器学习的目标：演算法A根据给定数据集D从假设空间H中选择一个与f最为接近的g，还要保证g与f在给定数据集之外的数据上表现也相似。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
在资料以外的部分，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有无好坏？
举例：掷硬币，每次掷5次，进行150次实验，总共有10个h，有1个h在看得见的资料上全对，要不要选它？
我们发现在150次试验中，至少出现1次5个正面的概率是超过99%的，所以很容易就会认为Ein(h)=0，认为Eout(h)近似=0，但是实际上Eout(h)=1/2。很明显Ein(h)和Eout(h)不接近。认为5个正面是不好的样本（坏数据）。
坏数据：对于一个h，使得h在该数据内外表现差异很大的数据认为是坏数据。
为了让演算法自由选择H中的h，要求数据集D对所有的h来说都是好的数据。
