本篇文章是台湾大学《机器学习基石上》的课程笔记。以PLA算法为例，推导证明机器学习的可行性。

问题概述

机器学习在当前发展得很快，我们不由得发问：为什么这种算法是可行的。
我们说机器学习算法是可行的，是指它的损失函数值很小。比如在回归问题里，我们的目标是让
我们用更为数学化的语言表述这件事情：
首先定义一下本文需要用到的数学符号

我们让本质上就是要使得足够小且。
我们这篇文章需要证明的两个保证机器学习可行的结论，就是：

但是，我们知道在计算机科学里有一个著名的NFL（No Free Lunch）理论，它似乎在告诉我们机器学习是不可行的...

NFL理论 与 算法优越性

NFL理论的具体表述如下：

不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。平常所说的一个学习算法比另一个算法更“优越”，效果更好，只是针对特定的问题，特定的先验信息，数据的分布，训练样本的数目，代价或奖励函数等。

是不是很不符合常理？难道Hugo Sort(猴子排序)真的和快速排序优越性一样吗？我们来看看周志华教授的《机器学习》一书中，关于NFL的简要证明：

周志华《机器学习》第八页

周志华《机器学习》第九页

最后的结果里，一个算法的期望性能居然和算法本身无关！
按照NFL的理论，是不是不仅机器学习算法不可行，就连传统的算法也不可行了呢？

通过 Hoeffding's inequality 得到机器学习可行的两个条件

上面NFL理论的表述，实际上是在告诉我们：不会存在一个算法对任意一种条件都有优越性。但我们实际上只需要期望机器学习算法能解决大部分的问题。也就是说，我们的问题变成了证明机器学习算法在有界的概率下，是可行的。
我们在证明这个结论，需要用到一个数学工具 Hoeffding's inequality。

什么是Hoeffding's inequality

我们先用一个Bin Model来介绍什么是 Hoeffding's inequality。
现在假设我们有如下的一个桶，需要去预测其中绿色球与橙色球的比例。

Bin Model

Hoeffding's inequality在机器学习中的表述

我们把 Bin Model 迁移到机器学习上。
现在我们假设一个 Bin 就是一个 。其中橙色球是 ，绿色球是。
我们想要证明：的概率足够小，以至于我们可以忽略它。
我们用来重新表述 Hoeffding's inequality：

这个表达式告诉我们： 是PAC（ probably approximately correct）的。

PAC：的差值被限定在中。

也就是说：如果足够小，就可以认为足够小。

Bad Sample in Learing

上文证明了如果足够小，就可以认为足够小。但是不是一定会有这样的情况呢？
其实不然，我们在这里是概率性的描述，也就是说不能保证对于任意的都会有这样的结果。
比如我们假设：如果有150个人抛硬币，其中至少有一个人连续5次硬币都是正面朝上的概率：

显然，我们并不能说这个人抛硬币一直都会是正面朝上。
同理，如果我们选择一个都是绿色的罐子（）也不能保证这个罐子就全都是绿色的球。当罐子数目很多的时候，就会有Bad Sample。

Bad Sample：与差距很大。

我们下面做的工作，就是去证明Bad Data出现的概率足够小。

compute bad data

通过上面的推导，我们可以发现：只要证明是有界的，我们就可以认为Bad Data 出现的概率是小的。

总结一下，要证明机器学习可行我们需要做的两个工作：

• 训练样本 和最终测试 的样本都是来自同一个数据分布，且应该足够大
• 个数 有限
  然而，似乎对于PLA算法而言，的个数并不有限...

证明 是有限的

我们先给结论，M是无穷的！但是，我们可以用一个新的符号来替代。

这个式子是我们用来计算 Bad Data出现的概率。然而，我们实际上是在不断扩大概率的上界。看似当时，不等式的右边也会变得无穷大。然而，我们却忽略了各种之间可能是相互重叠的：

hypothesis

求取

用替代

我们如何把无穷的分成有穷的类别呢？
首先，我们引入一个字母，表示的就是平面上线的个数。
我们来看看平面上只有一个点的情况：

one-point

根据排列组合知识，我们可以得到，当增长到4的时候，就一定会有两种不可行。

point-4

经过分析，我们得到平面上线的种类是有限的。并且可以发现，有效的种类数目总是。
我们用来代替，重新写一下Hoeffding's inequality。

我们在刚刚已经知道了，现在如果有就能保证不等式的右边足够小（接近于0）。这个时候机器学习就是可行的。

替代

：dichotomy 就是将空间中的点（例如二维平面）用一条直线分成正类（蓝色 ）和负类（红色 ）。令是将平面上的点用直线分开的所有 h的集合。

dichotomy与hypotheses 的关系是：hypotheses 是平面上所有直线的集合，个数可能是无限个，而dichotomy 是平面上能将点完全用直线分开的直线种类，它的上界是 。

成长函数

成长函数的定义

成长函数
：对于由个点组成的不同集合中，某集合对于的最大，那么这个的值就是，它的上界是。

根据我们上面的推导，在二维平面上，随的变化关系是：

m(N)

接下来，我们将告诉大家如何去计算成长函数，以及如何运用VC维去分析。