Lec 4：Feasibility of Learning

上一章中我们介绍了各种各样的机器学习，本门课的着重点是binary classification or regression from a batch of supervised data with concrete features.

这一章（实际还要加上接下来的Lec6和7）介绍机器学习是不是可行的？！这是个有趣的问题（＾_＾）机器学习当前如此热门，答案当然是可行的，但你不一定知道它为什么可行！？个人认为，机器学习的可行性问题，或者说是理论保障，是设计机器学习算法以及techniques的根本出发点！

Tips：符号含义请参照Lec1

1，Learning is impossible？

第一节的几个小栗子告诉我们，我们从已知的data（D）中学到的完美的g很可能会不适用于未知的data（outside D），而预测未来的data又是机器学习的目的。那么机器学习是不是不可行呢？

2、Inferring something unknown & 霍夫丁不等式

我们可以想一想有没有推测未知事情的场景？！学过概率论的一定都接触过。举一个具体的例子：有一个装了很多很多橘色和绿色弹珠的罐子，我们知道橘色占的比例吗？不知道。但是我们可以推测（infer）橘色占的比例吗？可以！这类问题在统计学中很常见。如何infer？

假设橘色罐子中的实际比例是�μ。�独立随机抽取样本sample，在sample中橘色比例是v，则绿色比例是1-v。统计学中，in-sample 的v跟out-of-sample的μ大部分时候是接近的。抽取sample的大小用N表示。

这件事情在数学中的描述是：

这个不等式的含义是，当N很大时，v和μ相差ε（误差范围）的概率很小，这就是著名的“霍夫丁不等式”Hoeffding‘s Inequality。我们说“v = μ”这个式子是probably approximately correct（PAC），大概差不多是对的。

关于霍夫丁不等式：

1）对任意N和ε都成立；

2）不需要知道 μ；

3）当N larger、looser gap ε（较大的容忍度），那么 v ≈ μ的概率会higher；

因此，如果sample够大的话，我们可以通过v infer μ（概率论知识）。

这个不等式十分重要～个人认为它是机器学习最基本的理论保障～

3、Connection to learning

上一节中关于弹珠和概率等等的介绍和机器学习有什么关系呢？

针对一个h，可以把抽到橘色情况看作是wrong，即h（x）≠ f（x），对应地绿色代表right，即h（x）= f（x）。那么 μ 就是Eout（h），v就是Ein（h）。这样我们可以通过已知的Ein推测未知的 Eout 。霍夫丁不等式可以写作

与前面类似，“Ein（h）= Eout（h）”是PAC。如果Ein（h）≈ Eout（h）并且Ein较小，就能推出Eout（h）较小，从而推出h≈f，我们可以依据Ein的大小verify某个h。至此，这些理论只能用来判断某个h的好坏，真正的机器学习还需要用算法A从H中选出一个“good”h作为g.

4、Multiple h

上一小节中对一个h进行讨论得出verify h的准则，这节考虑一下在很多个h中做选择的情况，霍夫丁不等式会是什么作用？

抽样存在很多情况，难免出现Bad sample（Ein和Eout相差很大的sample）。霍夫丁不等式说明针对一个h出现bad sample的几率很小。但是当有很多个h时，bad data就很可能出现（如课件中抛硬币的例子），当bad sample的Ein又很小时，我们作出选择时就会worse情况。Bad sample也就是Bad Data。

霍夫丁不等式是针对某个h成立，它表示对于一个h来说，bad data出现的几率small。

当有很多h时，出现bad data的概率上限可以使用“联级上限”union bound获得。M=|H|，即hypothesis set的size（在下一章Lec5中我们将看到这个上限实际上很loose）。

由上式可以知道：

1）当M有限大时，如果N足够大，A选出的任意g都会有Eout（g）≈ Ein（g），如果Ein（g）≈ 0，Eout（g）≈ 0是PAC的，学习有效，learning is feasible！

2）But当M无限大时，boom！如Perceptrons（注意：这里不是PLA，是Perceptrons。PLA是算法，Perceptrons才是H）。接下来将需要Lec5～Lec7三章内容揭秘类似Perceptrons情况的可行性问题。欢迎继续学习！