转载请注明出处：http://www.cnblogs.com/ymingjingr/p/4271742.html

目录

机器学习基石笔记1——在何时可以使用机器学习(1)

机器学习基石笔记2——在何时可以使用机器学习(2)

机器学习基石笔记3——在何时可以使用机器学习(3)(修改版)

机器学习基石笔记4——在何时可以使用机器学习（4）

机器学习基石笔记5——为什么机器可以学习（1）

机器学习基石笔记6——为什么机器可以学习（2）

机器学习基石笔记7——为什么机器可以学习（3）

机器学习基石笔记8——为什么机器可以学习（4）

机器学习基石笔记9——机器可以怎样学习（1）

机器学习基石笔记10——机器可以怎样学习（2）

机器学习基石笔记11——机器可以怎样学习（3）

机器学习基石笔记12——机器可以怎样学习（4）

机器学习基石笔记13——机器可以怎样学得更好（1）

机器学习基石笔记14——机器可以怎样学得更好（2）

机器学习基石笔记15——机器可以怎样学得更好（3）

机器学习基石笔记16——机器可以怎样学得更好（4）

四、Feasibility of Learning

机器学习的可能性。

4.1 Learning is Impossible

学习可能是做不到的。

在训练样本集（in-sample）中，可以求得一个最佳的假设g，该假设最大可能的接近目标函数f，但是在训练样本集之外的其他样本（out-of-sample）中，假设g和目标函数f可能差别很远。

4.2 Probability to the Rescue

可能的补救方式。

通过上一小节，我们得到一个结论,机器学习无法求得近似目标函数f的假设函数g。

回忆在以前学过的知识中，有无遇到过类似的问题：通过少量的已知样本推论整个样本集的情况。

是否想到一个曾经学过的知识，其实就是概率统计中的知识。

通过一个例子来复习下该知识。有一个罐子，这个罐子里盛放着橙色和绿色两种颜色的小球，我们如何在不查遍所有小球的情况下，得知罐子中橙子小球所占的比例呢？抽取样本，如图4-1所示。

图4-1 抽取样本

假设罐子中橙色小球的概率为，不难得出绿色小球的概率为，其中 为未知值；

而通过抽样查出的橙色小球比例为，绿色小球的比例为 ， 是从抽样数据中计算出的，因此为已知值。

如何通过已知样本，求得未知的样本？

可以想象到，在很大的几率上接近的结果。因为在罐子里的小球均匀搅拌过后，抽出小球中的橙色小球比例很有可能接近整个罐子中橙色小球的比例，不难想象在抽出的小球数量等于罐中小球数量时，两者完全一致。

这其中不了解的是，到底有多大的可能性两者接近？此处使用数学的方式给予答案，如公式4-1所示。

    (公式4-1）

该公式称之为霍夫丁不等式（Hoeffding‘s Inequality），其中P为概率符号， 表示与的接近程度， 为此程度的下界，N表示样本数量，其中不等式左边表示 与 之间相差大于某值时的概率。从该不等式不难得出，随着样本量的增大， 与 相差较大的概率就不断变小。两者相差越多，即越大，该概率越低，就意味着 与 相等的结论大概近似正确（probably approximately correct PAC）。

同时可以得出当N足够大时，能够从已知的 推导出未知的 。

4.3 Connection to Learning

联系到机器学习上。

上一节得出的结论可以扩展到其他应用场景，其中包括机器学习。

为方便理解，做一个对比表，如表4-1所示。

表4-1 机器学习与统计中的对比

更通俗一点的解释上表表达的内容：训练输入样本集类比随机抽取的小球样本；此样本集中，先确定一个假设函数h，满足条件的输入向量x占整个样本的比例类比于橙色小球在随机抽取小球样本的比例，写成公式的形式可以入公式4-2所示；因此使用上一节中的PAC（（可能近似正确的理论），在整个输入空间中这个固定的假设函数h同目标函数f不相等的输入量占整个输入空间数量的概率 （ 的取值如公式4-3所示）与上述随机样本中两个函数不相等的样本数占抽样数的比例 相同，这一结论也是大概近似正确的。

（公式4-2）

（公式4-3）

其中N为随机独立抽样的样本数，X为整个输入空间， 满足条件为1否则为0，E为取期望值。

对1.4节的机器学习流程图进行扩展，得到如图4-2所示。

图4-2 引入统计学知识的机器学习流程图

其中虚线表示未知概率P对随机抽样以及概率 的影响，实线表示已经随机抽出的训练样本及某一确定的假设对比例 的影响。

得出的结论如下：对任意已确定的假设函数h，都可以通过已知的求出未知的 。

以后我们将使用和 这种专业的符号，分别表示在某一确定的假设函数h中，随机抽样得到的样本错误率和整个输入空间的错误率，同样可以使用霍夫丁不等式对以上得到的结论做出相应的数学表达，如公式4-4所示。

    （公式4-4）

但是，我们想得到的不是给定一个已确定的假设函数h，通过样本的错误比例来推断出在整个输入空间上的错误概率，而是在整个输入空间上同目标函数f最接近的假设函数h。

那如何实现最接近呢？说白了错误率最低。只需在上述结论上再加一个条件，即错误比例 很小即可。总结下，在结论基础之上，加上 很小，可以推出 也很小，即在整个输入空间中h≈f。

上面说了那么多，可能很多人已经糊涂了，因为这并不是一个学习问题，而是一个固定假设函数h，判断该假设函数是否满足上述性质，这准确的讲是一种确认（Verification），确实如此，这种形式不能称为学习，如图4-3所示。

图4-3 确认流程图

4.4 Connection to Real Learning

联系到真正的学习上。

首先我们要再次确认下我们上一小节确定的概念，要寻找的是一个使得 很小的假设函数h，这样就可以使得h和目标函数f在整个输入空间中也很接近。

继续以丢硬币为例，形象的观察这种学习方法有无问题，如图4-4所示。

图4-4 丢硬币的例子

假设有150个人同时丢五次硬币，统计其中有一个人丢出五次全部正面向上的概率是多少，不难得出一个人丢出五次正面向上的概率为 ，则150人中有一人丢出全正面向上的概率为 。

这其中抛出正面类比于绿色小球的概率也就是。当然从选择的角度肯定要选择犯错最小的，即正面尽可能多的情况，此例中不难发现存在全部都为正面的概率是非常大的，此处应注意，选择全为正面的或者说 为0 并不正确（因为想得到的结果是 ，而不是99%）这一结论与真实的情况或者说 差的太远（我们不仅仅要满足 很小条件，同时还要使得 与 不能有太大差距）。因此这种不好的样本的存在得到了很糟糕的结果。

上面介绍了坏的样例（bad sample），把本来很高的，通过一个使得的坏抽样样本进行了错误的估计。

到底是什么造成了这种错误，要深入了解。我们还需要介绍坏的数据（bad data）的概念。（这里写一下自己的理解，坏的样本bad sample∈坏的数据bad data）

坏的数据就是使得 与 相差很大时，抽样到的N个输入样本（我的理解不是这N个输入样本都不好，可能只是有几个不好的样本，导致该次抽样的数据产生不好的结果，但此次抽样的数据集被统一叫做坏的数据），根据霍夫丁不等式这种情况很少出现，但是并不代表没有，特别是当进行假设函数的选择时，它的影响会被放大，以下进行一个具体的说明，如表4-2所示。

表4-2 单个假设函数时的霍夫丁不等式

计算所有不好的D出现的概率如公式4-5所示。

    （公式4-5）

单一假设函数中不好的D出现的概率其实不算高，但是当在做选择时，面对的是从整个假设空间选出的无数种可能的假设，因此不好D的计算就有所改变，当然我们先讨论假设函数是有限多种的情况，如表4-3所示。

表4-3 M个假设情况下的霍夫丁不等式

这其中包含了M个假设，而不好的D不是由单一假设就确定的，而是只要有一个假设在此抽样D上表现不好则该抽样被标记为坏的，因此霍夫丁不等式如公式4-6所示。

(联合上界)

    (公式4-6)

因此如果|H|=M的这种有限情况下，抽样样本N足够大时，可以确保假设空间中每个假设都满足。

如果通过算法找出的g满足 ，则通过PAC的规则可以保证。

机器学习基石笔记4——在何时可以使用机器学习(4)

原文：http://www.cnblogs.com/ymingjingr/p/4276386.html