我们在评价机器学习模型的性能时,往往以 $E_{in}$ 作为泛化误差的代表。本文将探讨这样做的合理性,换句话说是在探讨机器学习算法为什么可行。如无特别提及,本文一律以PLA算法为例。

目标:证明$E_{in}$和$E_{out}$差距足够小

我们要讨论将 $E_{in}$ 作为 $E_{out}$的替代,一个很自然的目标就是给出这它们之间的差距足够小。也就是$\mathbb{P}[|E_{in}(g)-E_{out}(g)|]$足够小。本篇文章中的推导步骤略多,但实质上都是去找到$\mathbb{P}[|E_{in}(g)-E_{out}(g)|]$的上界。

理论基础:Hoeffding 不等式

Hoeffding 不等式给出的结论如下:
$$
\mathbb{P}[|E_{in}(g)-E_{out}(g)|>\epsilon]\leq 2Me^{-2\epsilon^2N} \tag{1}
$$
其中,$E_{in}$$E_{out}$ 分别为样本内误差和样本外误差。$M$是假设集(hypothesis set)$\cal{H}$的大小。

我们定义$\delta = 2Me^{-2\epsilon^2N}$
即:$$\epsilon=\sqrt{\frac{1}{2N}ln(\frac{2M}{\delta})} \tag{2}$$
又因为$|E_{in}(g)-E_{out}(g)|>\epsilon$即:
$$
E_{out}(g) \geq E_{in}(g) - \epsilon\
E_{out}(g) \leq E_{in}(g) + \epsilon
$$
根据上式,可以看出$E_{in}$越小,则$E_{out}$越小。因为,如果有一个比$E_{in}(g)$更大的$E_{in}(f)$那么根据上式的第二部分,一定有$E_{out}(g)$越大。所以,我们需要选择小的$E_{in}$。

从上面的推导,我们可以得到
$$
E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{1}{2N}ln(\frac{2M}{\delta})} \tag{3}
$$
我们把(3)称作error bound。可以看到error bound是关于M($\cal{H}$的个数)的函数。如果$\cal{H}$是一个有限集合,那么$M$就会是一个有界量。由此,error bound就将会是一个有界函数。但实际上,我们知道$\cal{H}$是一个无限集合:考虑PLA算法,分界面的参数是无限的,分界面也是无限的。所以,如果这样分析,我们是得不到$E_{in} \approx E_{out}$的。

回到式(1),我们发现我们计算的实际上是
$$
|E_{in}(h_1)-E_{out}(h_1)|>\epsilon \quad or \
|E_{in}(h_2)-E_{out}(h_2)|>\epsilon \quad or \
… \
|E_{in}(h_3)-E_{out}(h_3)|>\epsilon \quad \quad
$$
这样的结果一定会是被过分估计了的。我们将相同的部分,考虑了若干次。
$$
\mathbb{P}[\cal{B_1} \ or \ \cal{B_2} \ or \ … \ or \ \cal{B_m} \ ] \leq \mathbb{P}[\cal{B_1}] + \mathbb{P}[\cal{B_2}] + \ … \ + \mathbb{P}[\cal{B_m}]
$$
所以,接下来尝试能否通过其他的方式,避免这种过分估计。我们需要引入另一个概念:有效假设个数(effective number of hypotheses)

主推导

有效假设个数

所谓有效假设个数,即去掉实际效果一样的假设,剩余的所有假设的个数。下面的推导,将尝试使用增长函数$m_H(N)$来替换$M$。我们将以PLA算法为例,介绍什么是增长函数(growth function)。

首先引入dichtomy这个概念。我们知道,PLA算法通过一个线性分界面将点集分为正类和负类(${+1,-1}$)。也就是说,当且仅当一个假设模型对若干个点的分类结果不同时,我们才认为它们是不同的假设。而这种分类,我们就把它称作dichtomy。

增长函数m_H(N)

我们引入增长函数$m_H(N)$定义如下:
$$
m_H(N) = \max_{x_1,…,x_n\in \cal{X}} |H(x_1,…,x_N)| \tag{4}
$$
也就是说,$m_H(N)$是所有dichtomy中最大的数。
根据排列组合的相关知识,我们知道$m_H(N) \leq 2^N$是一定成立的。

如果 $\cal{H}$ 可以使得点集中的所有点被二分为任意的结果,则称这个点集可以被$\cal{H}$ shatter。

例如这张图中,(a)和(c)不能被shatter,具体的不能被shatter的情况如图示。

我们知道,可以被shatter意味着一个点可以被任意分类,即分类的可能情况为$2^N$。即,如果一个点集可以被shatter,那么$m_H(N)=2^N$。

下面再给出三个计算$m_H(N)$的例子:

根据排列组合知识,a的可选择情况有N+1种,每种情况对于一种分类。所以$m_H(N)=N+1$
同样的,选定两个端点,一共有$m_H(N)=\frac{1}{2}N^2+\frac{1}{2}N+1$。

凸包可以shatter整个点集,所以$m_H(N)=2^N$。

我们知道,$m_H(N)$的结果和点集的分布有关,但我们不想要每次都去从实际情况出发计算$m_H(N)$的值。那么有没有办法避免呢?答案是有的。

m_H(N)的上界

根据(3),我们知道$\sqrt(\frac{1}{2N}ln(\frac{2M}{\delta}))$中的$M$如果可以被多项式函数$m_H(N)$所替代,那么这个式子就可以在$N \to \infty$时,趋近于0。所以,我们实际并不需要$m_H(N)$的精确值,只需要知道它是多项式函数还是指数函数即可。也就是说,找到它的上界,或许就能解决问题!

我们定义一个新的函数$B(N,k)$$B(N,k)$意味着一个对于任意N个点和k,k为break point,当前能做到的最大的二分类。
即:
$$
m_H(N) \leq B(N,k)
$$
此时,k为$\cal{H}$的break point。所谓break point,就是满足$m_H(N) < 2^N$ 的所有N中最大的那一个。

Sauer’s Lemma

$$
B(N,k) \leq \sum_{i=0}^{k-1}C_N^i
$$
我们这里直接用这个结论,如果需要具体的推导过程,可以查阅《Learning From Data》一书。
总之,我们得出了
$$
m_H(N) \leq \sum_{i=0}^{k-1}C_N^i \tag{5}
$$
并且,容易知道不等式的右边一定是一个多项式。

VC维

VC维定义

一个假设集$\cal{H}$的VC维,是满足$m_H(N)=2^N$的所有N中最大的那个一个。记作$d_{vc}$或者$d_{vc}(\cal{H})$。如果$m_H(N)=2^N$始终成立,则记$d_{vc}=\infty$

于是,容易得出 $k=d_{vc}+1$
同时有:
$$
m_H(N) \leq N^{d_{vc}}+1 \tag{6}
$$

VC界

如果我们用$m_H(N)$替换$M$则有不等式
$$
E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{1}{2N}ln(\frac{2m_H(N)}{\delta})} \tag{7}
$$
进一步的变形可以得到:
对于所有的$\delta>0$
$$
E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{8}{N}ln(\frac{4m_H(2N)}{\delta})} \tag{8}
$$
的概率大于等于$1-\delta$

具体的变形过程不予赘述,可以看到,这里给出的VC界是与目标函数,假设集,算法,以及输入分布都无关的。所以一定会是一个宽松的界。

结论

至此,我们就证明了机器学习是可行的。但文章对于更为复杂的数学推导与证明过程并不做涉及,有兴趣的读者请查阅参考文献。文章配图来自《Learning From Data》一书。

参考文献

[1]Yaser S. Abu-Mostafa, Malik Magdon-Ismail, Hsuan-Tien Lin-Learning From Data_ A short course-AMLBook.com (2012)