When Can Machines Learn? ——part4
按例放上学习进度:D
一、Learning is impossible？
先从一个例子思考问题，给你6张图片的资料，你可以预测第7张属于1还是-1嘛？
答案显然是有很多种的，比如，它是属于+1的，因为+1的都是对称；
你也可以说它的属于-1的，因为-1的图形左上角第一个格子都是黑的；
emmmm……
这……
对的，根本无法知道哪个才是想要的f.
再来看一个数学一点的例子:
现在给你5个资料，要你预测其他3个资料:P
在给的资料D里面，g完全可以接近f，但是，在资料外呢?
有很多种可能，根本不知道哪个才是想要的，也就是说，无法判断g是不是靠近f的。然而，机器学习是想知道现有资料外的事，已经有结果的事为啥还要预测，我们想要知道的是未知的事。
这……
emmmm……
无法做到D以外的g接近f,这种特性称为No Free Lunch(NFL)定理。
这个定理告诉我们，关于某某学习算法可以在任何领域总是perfect是最准确的学习器，那是不存在的！
解决方案是，利用统计学的一些假设，加上一些假设，问题似乎变得可以解决了呢:D
二、Probability to the rescue
先从一个球球问题来看:
现在有一个罐子里面放了一些球球，有橙色的和绿色的，球球超级多，你能预测出橙色球球的比例嘛？
统计学给了一个解决方案，我先抓一把球球样本，样本orange比例为v,green就是1-v。
现在假设罐子里的全部球球orange比例为u,那么green就是1-u。
现在思考样本可以代表罐子里的全部球球嘛？
当然不可以!
v不等于u,比如，今天你欧气爆满，抓的全是green,那你可以说全部的球球都是green的嘛？显然是不可以的:D
但是，在数学角度，概率角度来说，v是接近u的！
下面用数学的方法来证明:
数学上有个Hoeffding's Inequality（霍夫丁不等式可以证明这个问题）:
设样本中的orange比例为v
罐子里的orange比例为u
样本大小为N
根据Hoeffding Inequality可以发现，只要N足够大（ps:exp()的意思是e的几次方，看式子就知道N越大，总体越小），v是与u接近的。
即只要样本的数量足够大，样本的比例是接近于罐子的比例的。
它们之间的差值在ϵ之内。
我们把'v=u'这种结论称为Probably Approximately Correct (PLA)。
这里需要说明一些特性：
- Hoeffding适用于所有的N和ϵ
- 从上面的不等式可以看出，与u无关，即我们不需要知道u
- 只要有足够大的N或者足够宽松的差值ϵ，我们很可能可以得到v接近于u
总之，如果N足够大，我们是可以通过已知的v去推断出u的。
三、Connection to learning
前面证明了球球的例子里v是可以推断出u的，那么如果把球球的例子转化到我们机器学习算法呢?
映射关系:
- orange比例（或者说概吧:D）=>固定的某条h=f
- 每个球球 => x,罐子=>X
- orange => h is wrong
- green => h is right
- N 个样本 => 训练样本D（就是喂给机器的资料D）
结论:如果N足够大，且xn独立同分布，我们就可以从v推断出u!
所以呢，现在我们的算法流程增加了一些部分:
- 从H中取一个固定h
- D（训练样本）是从X来的，同时也用x去测验h会不会接近f
- 用Eout(h)来代表我们不知道的那个东西，即f(或者说前面提到的罐子的所所有球球中orange的概率u)
- 用Ein(h)来代表N个样本（即D）中的出错率(或者说前面提到的橙色球球的概率v）
与v,u相同，对任何固定的h,将Eout(h)，Ein(h)代入Hoeffding's Inequality中也是成立的。
和之前的球球问题一样，也具有如下特性：
- Hoeffding适用于所有的N和ϵ
- 因为不取决于Eout(h)，所以我们不需要知道Eout(h),f和P都可以未知
- Ein(h)= Eout(h)是PAC的
还有一个问题需要考虑，上面的证明都是针对一个固定的h的，现在我们已经可以确定对任何一个固定的h,当样本数据足够大，Ein(h)是接近Eout(h)的,那么,这样就可以证明机器会学习了（g接近f）嘛？
当A选择了这个固定的h作为g时，上面的句子是成立的;
但是如果A是强制性选择这个固定的h的，即A不考虑别的h就选这个fixed h时,上面的句子是错误的。因为，说不定别的h更加优秀（Ein(h)接近于0）。所以，一般会通过A选择最好的h，使Ein(h)足够小，从而保证Eout(h)很小。固定的h，使用新数据进行测试，验证其错误率是多少。
流程如图:
四、Connection to real learning
现在有很多个h,其中有一个正好全部正确，那么，可以认为罐子里的都是green嘛？
不行！
从扔硬币的例子也可以看出，当选择多了以后，会恶化BAD sample,也就是说，Ein和Eout的差值很大。最简单的扔硬币的例子，虽然可能有的人扔了10次都是正面，但是我们不能说正面的概率就是1，概率还是0.5。这个例子中10次就足以造成BAD sample.
- BAD sample: Ein 和Eout的差值很大
- BAD Data for One h:Eout(h)和Ein(h)差值很大，比如，Eout很大，离f很远，但是，Ein很小（样本出错很少，可是最后结果还是很差，这时候该怪样本）
关于这部分再添加一些解释好了:D
- 比如150个人每个人扔5次硬币，至少一个人5次都是正面朝上的概率是大于99%的，但是，单从一个人来看，这个概率是1/32. => BAD D
- 比如我今天来扔个硬币，扔了5次，全是正面朝上，这样看起来好像正面朝上的概率是1，但是其实还是1/2,Ein和Eout差值太大了 =>BAD sample
- 所以区别是，比较的预期不一样，BAD sample是说和yn不一样，BAD D是直接和f(x)不一样了，前者是样本里的，后者就是整体的了。
根据许多次抽样的到的不同的D，Hoeffding’s Inequality保证了大多数的D都是比较好的（即对于某个h，保证Ein≈Eout），但是也有可能出现BAD D(比如前面提到的150个人扔硬币的例子，有一个人5次全是正面朝上在个人来看概率是很小的，1/32，机器对于这个固定的h,选择了它，但是它在整体来看是>99%的，是一个BAD D),这就是为什么说小概率事件在选择多的情况下概率会变大，恶化结果。
- 不同的D，对于不同的h，有可能成为BAD D
- 只要Dn在某个h上是BAD ，那么Dn就是BAD
- 只有当Dn在所有的h上都是好的，才说明Dn不是BAD，可以自由选择A进行建模
M是h的个数，N是样本D的数量，ϵ是参数。
用Hoeffding和union bound可以推出:对于任意D,它是某些h的BAD D的概率为P,推导可得P与N成正比，与M成反比,即，M越小，N越大时，我们越可以放心地在H中选择错误率最小的h作为想要的g.
如果h的个数M是有限的，N足够大，那么通过A任意选择一个g，都有Ein≈Eout成立
如果找到一个g，使Ein≈0，PAC就能保证Eout≈0。
这样，就证明了机器学习是可行的。
至此，我们现在证明了一个问题，即开篇讲到的，如果是预测资料外的事，结果那么多种，我怎么知道哪个才是想要的，现在我们有了一些假设条件，那就是我们假设有Ein和Eout,是对出错率的一种评估，现在只要我们选择Ein最小的，就可以推出Eout(就是那个未知的东西的出错率）也是最小的，那么，此时的g就可以认为是最优秀的，最接近于f的。
但是，如上面的学习流程图右下角所示，如果M是无数个，例如之前介绍的PLA直线有无数条，是否这些推论就不成立了呢？(之后会处理:D)
五、Summary
总结:
- 从一个图片和二进制例子告诉我们NFL定理，告诉我们ML无法做到g完全等于f
- 对于一个固定的h,用Hoeffding不等式引出Ein,Eout,证明了对于一个固定的h,当N足够大时，Ein≈Eout是PAC的
- 对于multi-h情况下，用Hoeffding和union bound证明了只要M(h的个数)是有限的，且N足够大，Ein≈Eout是PAC的
- 最后，就证明了ML是可行的。
以上:D
注明:以上图片都来自Cousera台大林轩田老师的《机器学习基石》哦 QwQ
