Generalization Theorem

这里关注的是，对于sample训练集的error和整体数据或者说general的error之间的slack，也就是关注overfitting发生的可能性，我们希望这个slack越小越好，这样就可以置信度尽可能高地由errorS(h)error_{\mathbb{S}}(h)预测errorG(h)error_{\mathbb{G}}(h)，其中hh是当前的classifier。

For the following words, “True” with probability at least 1−δ1 - \delta, which is confident:

errorG(h)⩽errorS(h)+ln(1/δ)+ln(H)2∣S∣error_{\mathbb{G}}(h) \leqslant error_{\mathbb{S}}(h) + \sqrt{\frac{ln(1 / \delta) + ln(\mathbb{H})}{2|\mathbb{S}|}}

其中H\mathbb{H}指的是classifier的全集，含义是，当我sample的训练集越大，那么slack就会越小，我越可以用训练集的error估计整体分布的error。当我的classifier全集的数量越多，或者说函数参数量越多，slack越大，overfitting越容易发生。此外δ\delta越小，上面公式置信度越高，slack就越大。

Q: 如何确定Sample Size

下面给出一个场景：让H\mathbb{H}表示拥有k个叶子节点的所有决策树集合，也就是2k−12k - 1个节点。

那么∣H∣|\mathbb{H}|是多少，我们假设一个node是2个words，然后在内存空间占用128bits，那么满足这个条件的所有的决策树，一定在128(2k−1)128(2k - 1)这个内存空间内，然后每个bit都有两个可能的状态，有数据或者没有数据，所以∣H∣|\mathbb{H}|也就是所有决策树的possibles一共有2128(2k−1)2^{128(2k - 1)}。这里我们令：

l←128(2k−1)l \leftarrow 128(2k - 1)

∣H∣⩽2l|\mathbb{H}| \leqslant 2^{l}

所以就有，当我们希望slack少于1%时：

slack=ln(1/δ)+ln(H)2∣S∣≈l2∣S∣→0.01slack = \sqrt{\frac{ln(1 / \delta) + ln(\mathbb{H})}{2|\mathbb{S}|}} \approx \sqrt{\frac{l}{2|\mathbb{S}|}} \rightarrow 0.01

∣S∣=100002l|\mathbb{S}| = \frac{10000}{2}l

其中l就是所有当前限制下分类器的总可能数量，也可以理解为参数量。

Go to think about the scenario of Deep Learning

当我们训练集的数据量很小的时候，也就是∣S∣|\mathbb{S}|很小的时候，同时我们又使用了一个参数量很大的神经网络模型，也就是∣H∣|\mathbb{H}|很大的时候。可以发现slack就会变得非常大，所以overfitting就会发生。这也是为什么曾经在用于训练的标注数据较少的时候，不曾出现如今的较大参数量的神经网络模型，或者说DL并没有现如今这么有效。

Union Bound

给n个IID（独立同分布）随机变量

A1,A2,A3...AnA_1, A_2, A_3...A_n

Pr(A1∪A2..∪An)⩽∑i=1nPr(Ai)Pr(A_1 \cup A_2 .. \cup A_n) \leqslant \sum^{n}_{i=1}Pr(A_i)

Hoeffding Bound

同样给出服从伯努利分布的n个IID随机变量

X1,X2,X3...XnX_1, X_2, X_3...X_n

那么显然有：

t=∑i=1nXit = \sum^{n}_{i=1}X_i

E(tn)=pE(\frac{t}{n}) = p

也就是样本的均值的期望等于整体分布的期望。

于是给出：

Pr(tn<p−α)⩽e−2nα2Pr(\frac{t}{n} < p - \alpha) \leqslant e^{-2n \alpha^{2}}

Pr(tn>p−α)⩽e−2nα2Pr(\frac{t}{n} > p - \alpha) \leqslant e^{-2n \alpha^{2}}

这个边界给出了一个事实，也就是当我样本均值的期望离整体分布的期望越来越远的时候，这个事情（这个bad event）发生的概率会越来越小。

Go back to the scenario of Classifier

下面把Hoeffding Bound应用在分类器的场景下。

这里采样n个样本对:

O1,O2,..,OnO_1, O_2, .. , O_n

每一个样本对是(xi,yi)(x_i, y_i)

然后我们再定一个XiX_i，服从下面的分布。

Xi={1ifh(xi)==yi0elseX_i = \left\{\begin{matrix} 1& if h(x_i) == y_i \\ 0& else \\ \end{matrix}\right.

所以能算出sample的error：

errorS(h)=1n∑i=1nXierror_{\mathbb{S}}(h) = \frac{1}{n} \sum^{n}_{i = 1}X_i

然后我们希望的是errorS(h)error_{\mathbb{S}}(h)能够尽可能地接近general error，也就是在整体数据上的损失。也就是我们希望sample出来数据的error能够准确地体现整体数据的error。

所以当二者发生α\alpha的偏移的时候，这也是个bad event，当这个偏移越大，这个bad event发生的概率越小。所以就可以用到hoeffding bound。

Pr[errorS(h)>errorG(h)+α]⩽e−2nα2Pr[error_{\mathbb{S}}(h) > error_{\mathbb{G}}(h) + \alpha] \leqslant e^{-2n\alpha^{2}}

Pr[errorS(h)<errorG(h)−α]⩽e−2nα2Pr[error_{\mathbb{S}}(h) < error_{\mathbb{G}}(h) - \alpha] \leqslant e^{-2n\alpha^{2}}

我们再进一步思考，上面的形式就是一开我们提到的generalization theorem。但是这个不等式是针对全集分类器的，那么对于当前分类器，我们可以应用Union Bound，直接除以分类器的总数。

Pr[errorG(h)>errorS(h)+ln(1/δ)+ln(H)2∣S∣]⩽δ∣H∣Pr[error_{\mathbb{G}}(h) > error_{\mathbb{S}}(h) + \sqrt{\frac{ln(1 / \delta) + ln(\mathbb{H})}{2|\mathbb{S}|}}] \leqslant \frac{\delta}{|\mathbb{H}|}

因此我们可以：

Set:e−2nα2=δ∣H∣Set:e^{-2n\alpha^{2}} = \frac{\delta}{|\mathbb{H}|}

从而可以去量化模型的泛化能力。