我们上一次介绍了 Hoeffding 不等式,结论是对任意固定的 hypothesis ,我们有

但是正如教授在课上讲的一样,仅仅在一个固定的 hypothesis 上做出这样的保证并不足以构成“学习”,最多只是“验证”。为了保证我们的学习算法从 中选中任何一个 都是可行的,我们需要得到这样形式的结论:

换句话说,我们希望得到的界对于所有 能够一致成立。所以接下来我们就来尝试得到这样的结论。具体来讲,本文中我们将会介绍一种叫做 Symmetrization 的技术。方便起见,我们记 ,并记 。于是,给定的 个训练数据也记为 。此外,我们简单地将 记为 ,而 记为 (因为它依赖于 个训练数据嘛)。

接下来我们假设除了 之外还有另一组数据 ,也是 IID 地从 中采样得到的。这组数据通常称作 ghost sample,它仅在理论分析中出现,并不是说我们在实际学习中需要额外的一份数据。

为什么要引入 ghost sample 呢?为了回答这个问题,我们先定义一些辅助的符号,首先,给定了 loss 函数 之后,我们可以定义一个 Loss Class,它是一个集合,其元素和 Hypothesis Space 里的元素一一对应 (实际上,有可能存在 但是 ,但是由于在任何数据 上都有 ,所以我们的学习算法或者说我们的 problem formulation 是无法区分这样的 的,所以如果需要严格一点的话,可以将这样的 集合起来构成等价类,这样就能保证 确实是一一对应的了。)

这里每个 是这样定义的一个函数:

看着有点像同意反复,其实就是这么回事。由于 的元素一一对应,所以在 里学习也可以等价地认为是在 里学习。接下来我们定义 上的投影为:

它是由一些 维向量所构成的集合。接下来到两件事情:第一,由于我们使用的是 binary loss,因此所有 实际上只取 两个值,所以 这个由 维 binary vector 所组成的集合的元素个数是有限的,最多不超过 个——不论原来的集合 是否有限;第二,这个有限的集合完全决定了任意 的 in-sample error (因为 Loss Class 中的函数 和 Hypothesis Space 中的函数 一一对应,所以我们在谈论 的 error 的时候,可以认为实际上是在谈论它所对应的那个 的 error,以下我们将混用这样的概念。),因为

我之前在大数定理军团中曾经介绍过一种简单的利用 Union Bound 将上一次讲的 Hoeffiding 不等式推广到一致成立的方法,但是那种方法只对有限的 适用,对于无限的 ,我们将会得到一个 这样的毫无意义的结果。然而这里似乎看到了一个好兆头: 里的元素的 error 将由一个有限的集合来完全决定,不论原来的集合 是有限还是无限。不过显然还有一个问题就是这里我们只能刻画 in-sample error,而 out-of-sample error 则不只是依赖于有限的 个数据点,而需要在所有 上求值。于是 Symmetrization 就出场了。

1

引理 1(Symmetrization). 对任意的 ,且 ,我们有 这里 是定义在 ghost sample 上的 in-sample error。

这样一来,不等式的右边就可以用两个有限的集合 来进行刻画了,从而避开了无限集的问题。而 ghost sample 的引入也正是为了这个目的。至于究竟如何来进行刻画并得到最终的一致 Hoeffding 界,我们将在下一次进行介绍,本文余下来的部分将用来证明引理 (lem: 1),不感兴趣的同学可以直接跳过。

简单起见,我们假设不等式左边的上确界可以达到,并在 处达到。注意 是依赖于 的定义的,因此依赖于 。注意到

在不等式两边先对 ghost sample 求期望,得到

我们看红色的部分,由 Chebyshev’s Inequality (注意这里 是常量,而 虽然依赖于 ,但是与 ghost sample 无关,否则这里不能直接套用 Chebyshev’s Inequality。),我们有

再次注意到 只取值 ,因此 (简单证明:记 ,则 ,而 ,注意到 ,由均值不等式立即得到 。),所以

再注意到引理中有 这个奇怪的条件,所以 ,带入 (eq: 2) 的红色部分,得到:

最后两边同时再对真正的 training sample 求期望,即得到:

这样一来,引理就得证了。