机器真的可以学习吗？
在讨论机器是否可以学习之前，我们先来看看下面这个问题
什么是学习？
在课堂上听老师讲课，是进行学习; 自己通过摸索总结得出经验，也是学习; 小朋友通过模仿大人说话，从而学会说话，也是学习。
人自从出生以后，就一直在学习，一直在通过触觉，视觉以及听觉来观察感受所在的世界，并学习到各种技能，从而更加适应在这个世界中生存。
Herbert A. Simon 曾经对学习下过一个定义“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。”
按照此定义，那么人类一直是在进行学习，其实不仅仅是人类，各种动物也是同样的方式在进行着对这个世界的学习。
那么对于机器的话，如果可以通过某种方法来提高机器的某些技能，那么机器也就是学会了学习了。
人是通过观察世界来学习到技能的，那么机器所能得到的只有数据，于是机器只能观察数据，就有了下表：
人： 观察世界 ----> 通过学习 ----> 技能
机器： 观察数据 ----> 通过学习 ----> 技能
人所学得的技能是很好理解的，那么机器学得的是什么技能呢？
实践已经得出结论，机器可以学会如何区分垃圾邮件，识别图片的内容，听懂一段语音等等，并且现在大量的实践可以证明通过一些手段，
机器是可以提高这些各种各样的机器的技能的，所以，实践已经证明，机器是可以学习的，而且学得的技能甚至超越人类的平均水平。
机器真的可以学习吗？
所以机器学习，就是从数据出发，经过一系列的过程，来提高机器在某一个方面的性能。
再具体一些，就是机器学习是要根据已有的数据集合 X，且该数据集合通过一种映射关系 f，
使得每一个 \(x \in X\) 和 \(y \in Y\) 都可以通过f映射，也就是 y = f(x)。
学习则是人为的给出一组假设集 H，使用数据集合 X，以及目标集合 Y，通过学习方法，
来找到H之中最好的一个g，使得 \( g(x) \approx f(x) \)。
但是，我们找到的这个g，是针对已知数据X中表现最好的一个，但是现实是我们需要处理的不仅仅是已知的 X，
因为如果仅仅需要处理已知的问题的话，那么将这些记录全部录入电脑就可以了，电脑最擅长的就是记忆了，
我们需要的其实是将g用来对X之外的未知数据集Z做出推论Y‘=g(Z)，我们找到的这个g真的没问题吗？
这个听起来机器学习似乎有点不那么靠谱了。
但是，现实中我们处理的数据是独立同分布的数据，即每个数据个体不会影响其它个体，且每个数据的个体的分布都是一样的，
这样才有一定的模式可供我们来学习，否则个体互相关联或分布都不一样的话，那每一个个体都是单独且互相不一样的存在，是无规律可言的。
在独立同分布的前提下，那么我们要处理的数据集X其实就是未知数据集Z的一个采样，也就是\( X \in Z \)。
我们要做的事情，也就是需要通过样本来推断整体，通过身边的已知事物来认识这个世界。听起来要好多了，因为我们人类一直都是这样做的。
数学的证明
坏事情发生的概率很低
在概率论中，有一个已经被证明了的定理，Hoeffding’s Inequality (霍夫丁不等式)。
\[ \mathbb{P}[|\nu - \mu| > \epsilon] \leq 2exp(-2\epsilon^{2}N) \]
该不等式的意思是，取\(N\)个样本，那么总体的中取得Y概率\(\mu\)， 与样本中取得Y的概率\(\nu\)的误差大于\(\epsilon\)的几率会不大于这个值：\(2exp(-2\epsilon^{2}N)\)。
通俗的讲，该不等式表示一个坏事情——样本与总体中取得同一种个体的概率的误差，大于可接受的值——发生的概率，是有上限的，
而且这个上限仅与误差值以及样本大小N相关，与其他统统不相关。因为有个exp在，那么随着N的增大，
这个坏事情发生的几率就会程指数级的减小，当N足够大的时候，这个几率就变的非常非常的小了。
回到机器学习，我们在假设集H中任意取一个假设h，并且可以在已有的样本个数为N的样本数据集D上对其进行验证，
得到样本内错误 \( E_{in}(h) = \frac{1}{N}\sum_{n=1}^N[[h(x_{n}) \neq y_{n}]] \)，
对于由独立同分布 P产生的样本集，那么对于样本外的错误 \( E_{out}(h) = \varepsilon_{x\sim P}[[h(x) \neq f(x)]] \)，
将其带入 Hoeffding‘s Inequality：
\[ \mathbb{P}[|E_{in} - E_{out}| > \epsilon] \leq 2exp(-2\epsilon^{2}N) \]
可以开始学习了吗？
这样只要找到最小的那个\(E_{in}\)我们就能进行机器学习了吗？
等等，霍夫丁给我们的保证只是随机抽一个个体，对于一个h来说，那么这个个体是坏事情的概率够小。
现在我们要做的事情是提供M个h的集合H，并希望在H中找到最好的那一个g，那么该如何选呢？
我们现在需要定义一个演算法A，我们希望可以通过这个演算法A从M个h中找到那个最好的g，这可能吗？
霍夫丁只能针对一个h作出保证，但是现在有M个h，一旦任意一个数据个体在任意一个h上表现不好，
那么这个数据个体都会对A产生不好的影响，我们希望A能正常运作，那么需要看一下最坏的情况有多坏。
\[ \mathbb{P_{D}}[ D_{bad_{all}} ] \] \[ = \mathbb{P_{D}}[ D_{badh_{1}} or D_{badh_{2}} or ... or D_{badh_{M}} ] \] \[ \leq \mathbb{P_{D}}[ D_{badh_{1}} ] + \mathbb{P_{D}}[ D_{badh_{2}} ] + ... + \mathbb{P_{D}}[ D_{badh_{M}} ] \] (union bound) \[ \leq 2exp(-2\epsilon^2N) + 2exp(-2\epsilon^2N) + ... + 2exp(-2\epsilon^2N) \] \[ = 2Mexp(-2\epsilon^2N) \]
也就是说，如果H为有限集，那么只要N够大，演算法A就一定能找到一个足够好的假设g。
只要找到最小样本内错误的一个假设，也就可以认为是最好的那个假设g，从而实现了机器学习。
好像还缺些什么
只能有M个有限假设？那么M最大能是多少？
M在比较小的时候，坏事情发生的概率确实很小，但是只是能保证说 \( E_{in} \) 与 \( E_{out} \) 差别不大，
但是无法保证这个最小的\( E_{in} \)就是一个好到能够使用的h。那么要想找到一个合适的h，就需要增大假设集，
但是随着M的增大，那么坏事情发生概率就会直线的增加。目前我们的不等式如下：
\[ \mathbb{P}[|E_{in} - E_{out}| > \epsilon] \leq 2Mexp(-2\epsilon^2N) \]
我们希望能够一定找到一个比较好的h，那么在M个假设中，坏事情发生的总的概率是多少呢？
我们定义 Bad event \( B_{m} : |E_{in}(h_{m}) - E_{out}(h_{m})| \)
那么，当事情到了最坏的地步，就是所有的坏事情坏的都不一样，也就是说，所有的 \( B_{m} \) 都不重复，那么：
\[ \mathbb{P}[B_{1} or B_{2} or ... or B_{m}] \leq \mathbb{P}[B_{1}] + \mathbb{P}[B_{2}] + ... + \mathbb{P}[B_{m}] \]
那这样当M趋于无限大的时候，那么坏事情的上限也就无限大了。
这样岂不是当M比较大的时候就无法进行学习了？
那么我们做错了什么吗？
其实，在定义假设集的时候，其实定义的是有限的几组很相似的函数，也就是说，绝大部分的假设h，其实应该是重叠的，
所以我们在使用union bound估计坏事情的时候，其实是过估计了。那么N个点如果进行分类的话最多只有N种类别，
针对每一种类别，那一组的h应该都是几乎一样的，这样我们可以假设有一个函数 \( m_{h}(N) \)，
用来表示随着N的增大，H中有效h的个数，那么，之前的不等式可以替换为：
\[ \mathbb{P}[\exists h \in H\, s.t. |E_{in}(h) - E_{out}(h)| > \epsilon] \leq 2 \cdot m_{h}(N) \cdot exp(-2\epsilon^2N) \]
由于我们目前无法验证 \( E_{out} \)，我们取一个巧，我们再用同样的方式取另一个同样有N个数据的数据集D'，
同时计算出对于D'的误差，记为\( E^\prime_{in} \)，然后来计算\( E^\prime_{in} \)与\( E_{in} \)的差距。
由于大家都是独立同分布的数据，那么我们可以认为 BAD h of \( | E_{in} - E_{out} | \frac{\rightarrow}{probably} \) BAD h of \( | E_{in} - E^\prime_{in} | \)。那么，带入之前的不等式则有：
\[ \frac{1}{2}\mathbb{P}[\exists h \in H\, s.t. |E_{in}(h) - E_{out}(h)| > \epsilon] \] \[ \leq \mathbb{P}[\exists h \in H\, s.t. |E_{in}(h) - E^\prime_{in}(h)| > \frac{\epsilon}{2}] \]
因为是随机取出的D'，所以\( E^\prime_{in} \)有很大的概率不怎么好，这个概率就是第一个 \( \frac{1}{2} \)，
那么我们想让坏事情出现的概率更严格，于是在不等式的右边也/2。
现在，我们有了两个N个数据的数据集D以及D'，那么再把我们的\( m_{h}(N) \)请回来，则现在是\( m_{h}(2N) \)，
那么，坏事情发生的概率
\[ BAD \leq 2\mathbb{P}[\exists h \in H\, s.t. |E_{in}(h) - E^\prime_{in}(h)| > \frac{\epsilon}{2}] \] \[ \leq 2m_{h}(2N)\mathbb{P}[fixed\, h\, s.t. |E_{in}(h) - E^\prime_{in}(h)| > \frac{\epsilon}{2}] \]
现在，无限多个的H变成了 \( |H(x_1,...,x_{N},x^\prime_{1},...,x^\prime_{N})| \)，union bound 为 \(m_{h}(2N)\)，
再把Hoeffding请回来，考虑现在的数据集为2N，且一半的数量N是计算\(E_{in}\)的，剩下的另一半则是计算了\(E^\prime_{in}\)，
那么则有 \( |E_{in} - E^\prime_{in} | > \frac{\epsilon}{2} \leftrightarrow |E_{in} - \frac{E_{in}+E^\prime_{in}}{2}| > \frac{\epsilon}{4}\)，我们仅仅是用了稍微小一些的数据集2N，稍微小一些的\(\epsilon\)，带回不等式中得到：
\[ BAD \leq 2m_{h}(2N)\mathbb{P}[fixed\, h\, s.t. |E_{in}(h) - E^\prime_{in}(h)| > \frac{\epsilon}{2}] \] \[ \leq 2m_{h}(2N) \cdot 2exp(-2(\frac{\epsilon}{4})^2N) \]
这个也就是著名的 Vapnik-Chervonenkis (VC) bound, 我们把上面的不等式稍微整理一下：
\[ \mathbb{P}[\exists h \in H\, s.t.|E_{in}(h) - E_{out}(h)| > \epsilon] \leq 4 \cdot m_{h}(2N) \cdot exp(-\frac{1}{8} \cdot \epsilon^2N) \]
所以，随着M的增大，其实是不需要担心的，我们之前定义的通过选最小的 \( E_{in} \) 演算法A，其实还是能找到最好的g的。
所以，机器学习是可行的。
为什么需要机器学习？
回想一下，人类社会为什么需要工具？ 狩猎没有工具的话，徒手打不过猛兽; 耕地没有工具的话，徒手开垦荒地几乎不可能。
再考虑一下，人类社会为什么需要机器？ 织布机替代了大量的纺织工人，流水线替代了大量的装配工人。
自古以来，人类一直在创造着能帮助人类更加进步的工具，而能创造出能够自主思考的机器，则是发明家一直以来的梦想。 尤其是随着人类社会的进步，社会要快速发展，人类需要更加强大的有一定自主性而不是只会执行固定指令的机器来帮助自己。 比如一下一些场景：火星漫步者号在火星该怎么行走，遇到坑的话怎么绕过去？总不能一直由NASA的工程师盯着指挥吧， 信号从火星到地球一个来回需要数十分钟。想标注十万张图片中的物品，判断图片中有什么物品对人来说很容易， 但是人却很难对计算机下个定义什么是树，什么是猫。购物网站需要对数千万的用户推荐可能购买的物品， 雇佣大量的人来分析数千万用户每一个人的喜好是完全不现实的事情。
对于这些很难由人类做出定义或者很难实现的事情，但是又需要完成这样的工作，那么就需要机器的帮助，并且这个机器是要会学习的机器。
什么时候可以应用机器学习？
机器学习是机器通过对数据进行一系列的计算过程，得到性能提升。那么符合以下个条件的话，就适合应用机器学习：
- 存在一种
模式可以被总结并学得，否则机器无从学起 - 无法通过
编程的方式来解决问题，否则直接写程序就可以了 - 存在
数据可以用来学习，否则巧妇难为无米之炊