本篇文章是台湾大学《机器学习基石上》的课程笔记。以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
显然，根据统计学的原理，我们会从桶中抽取一个抽样样本（
compute bad data
上面的推导涉及到的符号解释如下：
hypothesis
这就给了我们启发，是不是能够找到一个能够表示真正有所不同的
one-point
可以看到，当平面上只有一个点的时候，PLA算法只有两种
point-4
经过分析，我们得到平面上线的种类是有限的。并且可以发现，有效的种类数目总是。
我们用来代替
，重新写一下Hoeffding's inequality。
我们在刚刚已经知道了，现在如果有
就能保证不等式的右边足够小（接近于0）。这个时候机器学习就是可行的。
替代 
）和负类（红色
）。令
是将平面上的点用直线分开的所有
h的集合。
dichotomy与hypotheses 的关系是：hypotheses 是平面上所有直线的集合，个数可能是无限个，而dichotomy 是平面上能将点完全用直线分开的直线种类，它的上界是
。
成长函数 )
成长函数的定义
成长函数
个点组成的不同集合中，某集合对于的
根据我们上面的推导，在二维平面上，随
的变化关系是：
m(N)
接下来，我们将告诉大家如何去计算成长函数，以及如何运用VC维去分析。
网友评论