我们上一次介绍了 Hoeffding 不等式,结论是对任意固定的 hypothesis hHh\in\mathcal{H},我们有

P(Eout(h)Ein(h)>ϵ)e2Nϵ2 P(E_{\text{out}}(h) - E_{\text{in}}(h) > \epsilon ) \leq e^{-2N\epsilon^2}

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

P(suphH(Eout(h)Ein(h))>ϵ)something P\left(\sup_{h\in\mathcal{H}} (E_{\text{out}}(h) - E_{\text{in}}(h)) > \epsilon \right) \leq \text{something}

换句话说,我们希望得到的界对于所有 hHh\in\mathcal{H} 能够一致成立。所以接下来我们就来尝试得到这样的结论。具体来讲,本文中我们将会介绍一种叫做 Symmetrization 的技术。方便起见,我们记 Z=X×Y\mathcal{Z}=\mathcal{X}\times\mathcal{Y},并记 z=(x,y)z=(x,y)。于是,给定的 NN 个训练数据也记为 {zi}i=1N\{z_i\}_{i=1}^N。此外,我们简单地将 EoutE_{\text{out}} 记为 EE,而 EinE_{\text{in}} 记为 ENE_N(因为它依赖于 NN 个训练数据嘛)。

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

为什么要引入 ghost sample 呢?为了回答这个问题,我们先定义一些辅助的符号,首先,给定了 loss 函数 \ell 之后,我们可以定义一个 Loss Class,它是一个集合,其元素和 Hypothesis Space H\mathcal{H} 里的元素一一对应

F={fhhH} \mathcal{F} = \{f_h| h\in\mathcal{H}\}

这里每个 fh:ZR+f_h: \mathcal{Z}\rightarrow \mathbb{R}^+ 是这样定义的一个函数:

fh(z)=(h,z) f_h(z) = \ell(h, z)

看着有点像同意反复,其实就是这么回事。由于 F\mathcal{F}H\mathcal{H} 的元素一一对应,所以在 H\mathcal{H} 里学习也可以等价地认为是在 F\mathcal{F} 里学习。接下来我们定义 F\mathcal{F}{zi}i=1N\{z_i\}_{i=1}^N 上的投影为:

F(z1,,zN)={(f(z1),,f(zN)fF} \mathcal{F}(z_1,\ldots,z_N) = \{(f(z_1), \ldots, f(z_N)|f\in\mathcal{F}\}

它是由一些 NN 维向量所构成的集合。接下来到两件事情:第一,由于我们使用的是 binary loss,因此所有 ff 实际上只取 0011 两个值,所以 F(z1,,zN)\mathcal{F}(z_1,\ldots,z_N) 这个由 NN 维 binary vector 所组成的集合的元素个数是有限的,最多不超过 2N2^N 个——不论原来的集合 F\mathcal{F} 是否有限;第二,这个有限的集合完全决定了任意 fFf\in\mathcal{F} 的 in-sample error,因为

EN(f)=1Ni=1Nf(zi) E_N(f) = \frac{1}{N}\sum_{i=1}^N f(z_i)

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

1

引理 1(Symmetrization). 对任意的 ϵ>0\epsilon>0,且 Nϵ22N\epsilon^2 \geq 2,我们有 P(supfF(E(f)EN(f))>ϵ)2P(supfF(EN(f)EN(f))>ϵ2) P\left( \sup_{f\in\mathcal{F}} (E(f)- E_N(f)) > \epsilon \right) \leq 2P\left( \sup_{f\in\mathcal{F}} (E^*_N(f)- E_N(f)) > \frac{\epsilon}{2} \right) 这里 ENE_N^* 是定义在 ghost sample {z1,,zN}\{z_1^*,\ldots,z_N^*\} 上的 in-sample error。

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

简单起见,我们假设不等式左边的上确界可以达到,并在 fNFf_N\in\mathcal{F} 处达到。注意 fNf_N 是依赖于 ENE_N 的定义的,因此依赖于 {zi}i=1N\{z_i\}_{i=1}^N。注意到

1{E(fN)EN(fN)>ϵ}1{E(fN)EN(fN)<ϵ/2}=1{(E(fN)EN(fN)>ϵ)(E(fN)EN(fN)<ϵ/2)}1{EN(fN)EN(fN)>ϵ/2}(1) \begin{aligned} &\mathbf{1}\{E(f_N)-E_N(f_N)>\epsilon\}\mathbf{1}\{E(f_N)-E_N^*(f_N)< \epsilon/2\} \\ =&\mathbf{1}\left\{ (E(f_N)-E_N(f_N)>\epsilon) \wedge (E(f_N)-E_N^*(f_N)< \epsilon/2)\right\} \\ \leq &\mathbf{1}\left\{ E^*_N(f_N) - E_N(f_N) > \epsilon/2 \right\} \end{aligned} \label{fa554f2ecf7018313ab0c9b4ef09cd1fc601667c}\tag{1}

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

1{E(fN)EN(fN)>ϵ}P(E(fN)EN(fN)<ϵ/2)P(EN(fN)EN(fN)>ϵ/2)(2) \begin{aligned} &\mathbf{1}\{E(f_N)-E_N(f_N)>\epsilon\}\color{red}{P\left(E(f_N)-E_N^*(f_N)< \epsilon/2 \right)} \\ \leq& P\left( E^*_N(f_N) - E_N(f_N) > \epsilon/2 \right) \end{aligned} \label{52598da0d2b5bd1a9ce7745471cb84aa99e02aae}\tag{2}

我们看红色的部分,由 Chebyshev’s Inequality,我们有

P(E(fN)EN(fN)ϵ/2)4var(fN)Nϵ2 P(E(f_N)-E^*_N(f_N)\geq \epsilon/2)\leq \frac{4\text{var}(f_N)}{N\epsilon^2}

再次注意到 fNf_N 只取值 0011,因此 var(fN)1/4\text{var}(f_N)\leq 1/4,所以

P(E(fN)EN(fN)ϵ/2)1Nϵ211Nϵ2P(E(fN)EN(fN)<ϵ/2) \begin{aligned} &P(E(f_N)-E^*_N(f_N)\geq \epsilon/2)\leq \frac{1}{N\epsilon^2} \\ \Rightarrow & 1 - \frac{1}{N\epsilon^2} \leq \color{red}{P\left(E(f_N)-E_N^*(f_N)< \epsilon/2 \right)} \end{aligned}

再注意到引理中有 Nϵ22N\epsilon^2\geq 2 这个奇怪的条件,所以 11Nϵ21/21-\frac{1}{N\epsilon^2} \geq 1/2,带入 (eq: 2) 的红色部分,得到:

121{E(fN)EN(fN)>ϵ}P(EN(fN)EN(fN)>ϵ/2) \frac{1}{2}\mathbf{1}\{E(f_N)-E_N(f_N)>\epsilon\} \leq P\left( E^*_N(f_N) - E_N(f_N) > \epsilon/2 \right)

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

P(supfF(E(f)EN(f)))=P(E(fN)EN(fN)>ϵ)2P(EN(fN)EN(fN)>ϵ/2)2P(supfF(EN(f)EN(f))>ϵ2) \begin{aligned} P\left( \sup_{f\in\mathcal{F}} (E(f)- E_N(f))\right) &= P\left(E(f_N)-E_N(f_N)>\epsilon\right) \\ &\leq 2 P\left( E^*_N(f_N) - E_N(f_N) > \epsilon/2 \right) \\ &\leq 2 P\left( \sup_{f\in\mathcal{F}} (E^*_N(f)- E_N(f)) > \frac{\epsilon}{2} \right) \end{aligned}

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