Lecture 4：Feasibility of Learning

Lecture 4：Feasibility of Learning

探讨机器学习的可行性：假设集有限，资料数据量足够大
参考：https://beader.me/mlnotebook/section2/is-learning-feasible.html

4.1 Learning is Impossible

虽然我们可以保证我们的在上的判断和真实的一致，但我们无法保证在之外也同样如此。那么这里便值得怀疑一下机器学习的可行性，机器学习到底可不可行？

4.2 Possibility to the Rescue

在统计推断中，我们可以利用样本的统计量(statistic)来推断总体的参数(parameter)，譬如使用样本均值来估计总体期望。

在概率论中，可以用Hoeffding’s Inequality来描述上面那件事情的概率：

注：是我们的容忍度，当与的差别小于容忍度时，我们称与“差不多”(PAC, probably approximately correct)，当与差别大于容忍度时，我们称与"差很多"。“差很多”这件事发生的概率越小越好，最大不会超过右边。

4.3 Connection to Learning

利用之前抓小球的逻辑，我们可以利用sample中orange的比例来推断总体中orange出现的概率，则同样的，我们可以利用sample中的比例来推断总体中的概率。这里表示一个error，则我们可以称 在sample中出现error的比例为 (in-sample-error)，在总体中出现error的概率为 (out-of-sample-error)。

当右边这个“上界”足够小时，我们可以说在sample中的表现(错误率)与在总体中的表现是差不多的。

我们的算法要能够自由的假设集从中挑选方程，我们把挑选出的最好的称为 final hypothesis。所以需要添加一个验证流程(Verification Flow)，这个流程使用历史数据来判断某个hypothesis够不够好。

4.4 Connection to Real Learning（Bad Data）

来自于总体的一个样本 (sample)，既然是sample，就一定会存在抽样误差。
譬如你想知道一枚硬币抛出正面的概率是多少，于是扔了5次，有一定的可能你连续扔了5个正面出来，这时候说抛出正面的概率是1，这当然是行不通的，因此你扔的这5次硬币，就是一个bad sample。凡是由于抽样误差所造成样本分布与总体分布相差很大的样本，我们都可以称之为bad sample。

Learning同样会遇到bad sample的麻烦。比如实际上是个很好的方程，本来能够成为final hypothesis的，但是由于抽样误差，碰到了bad sample，造成很大error，最终没有选择它。
又比如是个不好的方程，碰到了bad sample，碰巧又很小，导致错误得选择了它作为final hypothesis。

**当假设集是有限的时候，数据量越大，发生bad sample的可能性越低。**同理如果太大，我们也越容易遇到bad sample。