机器为什么能学习(上)

作者: ringotc | 来源:发表于2018-09-02 11:19 被阅读0次

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

问题概述

机器学习在当前发展得很快，我们不由得发问：为什么这种算法是可行的。
我们说机器学习算法是可行的，是指它的损失函数值很小。比如在回归问题里，我们的目标是让 $g \approx f$
我们用更为数学化的语言表述这件事情：
首先定义一下本文需要用到的数学符号
$\begin{array} \\ \hline x & 输入数据 \\ y&输出结果 \\ f&目标函数 \\ g&预测函数\\ data&训练样本 \\ hypothesis & 假设 \\ alogrithm & 算法\\ E_{in}(h)&在抽样样本中h(x)!=y的概率\\ E_{out}(h)&在抽样样本外h(x)!=y的概率 \end{array}$
我们让 $g \approx f$ 本质上就是要使得 $E(h)$ 足够小且 $E_{in} \approx E_{out}$ 。
我们这篇文章需要证明的两个保证机器学习可行的结论，就是：

$E_{in} \approx E_{out}$
$E_{in} 足够小$

但是，我们知道在计算机科学里有一个著名的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

经过分析，我们得到平面上线的种类是有限的。并且可以发现，有效的种类数目总是 $\leq 2^N$ 。
我们用 $effective(N)$ 来代替 $M$ ，重新写一下Hoeffding's inequality。
$P[|E_{in}(g) - E_{out}(g)| > \epsilon] \leq2 * effective(N)*exp(-2\epsilon^2N)$
我们在刚刚已经知道了 $effective(N)<2^N$ ，现在如果有 $effective(N)\ll 2^N$ 就能保证不等式的右边足够小（接近于0）。这个时候机器学习就是可行的。