machine learning可行性数学原理论证篇（一）

一、hypothesis set 有限个数时，machine learning 靠谱吗
样本空间的target函数我们是不知道的！凭什么说学习到的规则就可以表示样本空间的规则？
但是在概率论中，我们有一条原理是说，利用已知的概率可以大概推断出未知的概率。所以我们就思考啊，能否利用hypothesis在抽样样本的表现来推断出这个hypothesis 在样本空间上的表现，进而选出最好的hypothesis。顺着思路，我们具体来看看数学上的证明。

主要利用的概率论公式，利用已知推断未知：
联系机器学习过程，针对一个给定的hypothesis ，我们可以认为u是在整个样本空间上hypothesis 函数的表现（误分率），v是在抽样空间上hypothesis 表现（误分率），根据hoeffding公式，我们可以认为u和v大概率差不多是相等的。具体来说，大概率表示说随机在样本空间上进行抽样（保证样本空间足够大），绝大多数情况下，得到的这些抽样样本的表现都是可以表明整个样本空间上的表现，只有极少极少的情况下，抽样样本的表现和样本空间的表现相差甚远（正是由于这点 会影响在多个hypothesis set里选择g时 产生新的问题）。而差不多表明，u和v不可能完全相等，存在着可包容的误差。
解释一下上图，从服从P的样本空间里抽取n个样本，这n个样本在不同hypothesis 上的表现可以用来衡量相应的hypothesis 在同样服从P的样本空间上表现。利用这个原理，我们就可以解释清machine learning 验证的正确性了，利用训练样本挑出g，验证样本看其泛化能力，泛化能力不错的话，最后就可以放心使用测试样本进行预测（保证验证样本、训练样本、测试样本服从同一个概率分布）。
machine 学习过程就是找到E_in（h）最小的hypothesis，但是对于挑选出的训练集来说，一旦使用多个hypothesis ，E_in（h）可能在某个hypothesis 上的值很小，但是也许这个训练集表现无法表示整个样本空间的样本表现（所谓不好就是极小极小可能性出现了，训练集上表现无法表示其余服从统一概率分布的样本空间内的样本），所以相较于给定h时，需要对多个h进行比较时，对于抽样样本的选择更为严苛才可以保证其泛化效果！
公式推导中，保证不能取到对于所有hypothesis 上的bad data（有可能多个hypothesis 的D_k是重合的，因此这里使用M来表示的上限其实过高，为之后我们希望证明对于hypothesis 无穷多个时机器学习也是靠谱的留下了希望，我们可以使用其他表示来表明这个上限）

根据上图，可以说当hypothesis set个数有限时，有很多样本下，无论怎么抽取训练集，可以g在保证训练集的表现可以泛化为g在服从相同概率分布的整个样本空间上的表现。有了这个保证，机器只需要找到在训练集上E_in（h）最小的hypothesis即可！这个就是g啦！g就是机器学习到的规则！