我们来补习一下统计学习框架的正式模型。
-
输入 一个学习者可以访问以下内容
- 作用域集合 (Domain set)：一个任意的集合 \(\mathcal X\)，学习者的目标是对其上面的元素进行标记。
- 标签集合 (Label set)：所有可能的标签 \(\mathcal Y\)。许多时候被限制为 \(\{0, 1\}\) 或 \(\{-1, 1\}\)，因为有限标签的问题可以通过多层二标签解决。
- 训练数据 (Training data)：或称训练集 (Training set)。\(S = ((x_1, y_1), \ldots, (x_m, y_m))\) 是一个取自 \(\mathcal X \times \mathcal Y\) 的有限序列，即一些带标签的元素。
-
输出 学习者需要输出一个函数 \(h: \mathcal X \to \mathcal Y\)，称其为 predictor, hypothesis 或者 classifier，作为对所有 \(\mathcal X\) 中标签的预测。用 \(A(S)\) 表示一个学习算法 \(A\) 接收了训练集 \(S\) 后得到的函数，不引起歧义的情况下也可直接记作 \(h_S\)。
-
训练数据的生成 一条训练数据的生成基于一个 \(\mathcal X\) 上的概率分布 \(\mathcal D\)。\(\mathcal D\) 是学习者无法得知的。对于标签，我们目前假设存在一个正确的标记函数 \(f\)，使得 \(y_i = f(x_i)\) 被认为是 \(x_i\) 正确的标签。\(f\) 是学习者无法得知的（因为我们的目标就是拟合 \(f\)）。
-
成功度的衡量 定义一个 classifier 的误差 (error) 为其预测 \(\mathcal X\) 上标签的基于分布 \(\mathcal D\) 的错误率。形式化地，定义损失函数 \(\pi:\mathcal X \to \{0, 1\}\)，\(\pi = [h(x) \neq f(x)]\)，令 \(A = \{\pi(x) = 1 \mid x \in \mathcal X\}\)，假设其是一个可测集合，则 \(A\) 在 \(\mathcal D\) 上的测度 \(\mathcal D(A)\) 为 classifier \(h\) 在 \((\mathcal D, f)\) 下的其误差。记作
\[L_{\mathcal D, f}(h) := \mathbb P_{x \sim \mathcal D} [h(x) \neq f(x)] := \mathcal D(\{h(x) \neq f(x) \mid x \in \mathcal X\}) \]这样的误差称作泛化误差或真实误差 (generalization error, true error or risk)。记号 \(L\) 总是代表损失 (loss)。
-
学习者不知道 \(\mathcal D, f\)，因此也不会知道 \(L_{\mathcal D, f}(h)\)，不过它可以计算出自己在训练集上的误差，称其为训练误差或经验误差 (training error, empirical error or empirical risk)。记作
\[L_S(h) := \frac 1m |\{h(x_i) \neq y_i \mid i \in [m]\}| \]其中 \(S = ((x_1, y_1), \ldots, (x_m, y_m))\)，\([m] = \{1, 2, \ldots, m\}\)。
泛化理论的研究点就在于，如果 empirical error \(L_S\) 很小，我们可以获得什么关于 true error \(L_{\mathcal D}\) 的结论。
显然，对任何误差的讨论都依赖于对 \(S\) 的选取方式，即 \(\mathcal D\) 与 \(S\) 的关系。一个常用的假设是每次都基于分布 \(\mathcal D\) 随机选取一个元素与其对应标签放入 \(S\) 中。这可能会导致 \(S\) 中有重复的元素，但这并不会造成太大的影响（如果有要求，每次多采几次样直到获得一个新的就行），并且让这个过程变得简洁。形式化地，
-
独立同分布假设 每一个训练集中的数据都是独立且基于同一个分布 \(\mathcal D\) 地采出的。记作
\[S \sim \mathcal D^m \]也就是说，\(S\) 不仅仅描述了元素和标签的对应，也描述了元素的分布。
如果我们相信训练集是全体数据的一个快照，即 \(L_S, L_{\mathcal D}\) 强相关，那么一个合理的想法是尽可能地减小训练集上的损失。这种最小化 \(L_S\) 的策略称为经验风险最小化 (ERM, Empirical Risk Minimization)。
在一般意义下，这个策略是有可能失效的。这种在训练集上表现良好，但是在真实情况下表现糟糕的现象称为过拟合 (overfitting)。直观地说，过拟合出现于函数过度适配于训练集的情形。
不过，与其放弃 ERM 策略，我们更倾向于寻找不会导致过拟合的条件。一个合理的策略是限制函数空间。即，在看到测试集之前就对函数的形态进行一定限制。这个空间称为假设类 (hypothesis class)，记作 \(\mathcal H\)。形式化地，
这种限制被称为归纳偏置 (inductive bias)。归纳是指由于学习者是在看到测试集之前就进行限制，这种限制必定基于某种先验的对问题规律的归纳；偏置指的是某种特定的偏好。直观地说，限制越多，过拟合的情况就更难出现，但会导致更多的偏置，因此需要对两者进行平衡。
泛化理论一个基本的问题便是，应该如何选择假设类，使得过拟合的情况不会出现。
我们首先来通过一个著名的定理加深我们的信念。其说明，没有先验知识，就不会有通用的学习者。
定理 （没有免费午餐定理，No Free Lunch Theorem） 在任务 \(\mathcal X \to \{0, 1\}\) 中，对任何学习算法 \(A\)，若训练集 \(S\) 的大小 \(m \leq \frac {|\mathcal X|}2\)，则存在分布 \(\mathcal D\) 使得
- 存在 \(f\) 使得 \(L_{\mathcal D}(f) = 0\)。
-
\[P_{S \sim \mathcal D^m}\left(L_{\mathcal D}(A(S)) \geq \frac 18\right) \geq \frac 17 \]
注：原定理的第一条要求是由于其已经阐述过下文提到的更一般化的 \(\mathcal X \times \{0, 1\}\) 上的分布，这个要求等价于存在正确的标记函数 \(f\)。
证明
考虑训练集占严格一半的情况，即只使用一个大小为 \(2m\) 的 \(\mathcal X\) 的子集 \(C\) 来说明。由于没有限制，有 \(T = 2^{2m}\) 种函数 \(\{f_1, \ldots, f_T\}\)，对于每一个函数定义一个分布 \(\{\mathcal D_1, \ldots, \mathcal D_T\}\)，满足
显然地，\(L_{\mathcal D_i}(f_i) = 0\)。因此这些 \(\mathcal D\) 是符合条件的。我们接下来说明
如果这是对的，简单地用 Markov's Ineq 就可以得到定理结论。
直观地讲，这是显然的。因为我们总是可以随机构造那些不在训练集上的标签。但是由于 \(S\) 是基于 \(\mathcal D_i\) 构造的所以这里并不能直接描述什么是“不在训练集上”。
考虑 \(k=(2m)^{m}\) 种不同的测试集 \(\{S_1, \ldots, S_k\}\)，对 \(S_i = (x_1, \ldots, x_m)\) 令 \(S_j^i = ((x_1, f_i(x_1)), \ldots, (x_m, f_i(x_m)))\)。
对固定的 \(j \in [k]\)，考虑 \(\{v_1, \ldots, v_p\}\) 是没有出现在 \(S_j\) 中的集合。\(p \geq m\)。
于是我们可以将 \((f_i, f_i')\) 配对，其中两者只在 \(v_r\) 处取值不同，在 \(C\) 的其他地方取值完全相同。所以
现在我们想探寻该如何精心挑选 \(\mathcal H\)，使得 ERM 策略生效。我们总是假设其在训练集上能够表现良好，而重点关心的是其泛化能力。形式化地，我们要求
定义（可实现性假设）存在 \(h^{\star} \in \mathcal H\) 使得 \(L_{\mathcal D, f}(h^{\star}) = 0\)。
也就是说，\(\mathcal H\) 中是有通用的好的 hypothesis 的，并且在采用 ERM 策略时总是有 \(P(L_S(h_S) = 0) = 1\)，在许多情况下我们可以直接认作其对所有的 \(S\) 成立。
我们意识到，并不是所有的 \(S\) 都具有代表性，因此不应该对所有的 \(S\) 提任何要求，而应该用其生效的概率。同样，也不应该对所有 \(\mathcal X\) 的元素提要求，而应该用其预测正确的测度。形式化地，
定义 一个假设类 \(\mathcal H\) 是概率近似正确 (PAC, Probably Approximately Correct) 可学习的，如果存在函数 \(m_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 和一个学习算法满足，对任意 \(\epsilon, \delta \in (0, 1)\)、\(\mathcal X\) 上的分布 \(\mathcal D\) 以及标签 \(f: \mathcal X \to \{0, 1\}\)，如果 \(\mathcal H, \mathcal D, f\) 满足可实现性假设，则学习算法接收长度为 \(m \geq m_{\mathcal H}(\epsilon, \delta)\) 的训练集可以给出一个假设 \(h\)，使得有至少 \(1 - \delta\) 的概率 \(L_{\mathcal D, f}(h) \leq \epsilon\)。
所以问题变为了对满足何种性质的 \(\mathcal H\)，才能用 \(m\) 限制
的上界。其中 \(S|_x = (x_1, \ldots, x_m)\) 表示测试集的所有实例。
一个简单的想法是，如果 \(\mathcal H\) 是有限的，那么我们可以对每个 \(h\) 考虑。如果 \(L_{\mathcal D, f}(h) = \theta\)，那么采样出的 \(S\) 有 \((1 - \theta)^m\) 的概率避开了这些出错的地方。
令
表示那些不好的 hypotheses；
表示所有可能导致学习者给出不好 hypothesis 的训练集。则
因此
而根据测度论中的一个引理
引理 (Union Bound) $$\mathcal D\left(\bigcup_{i=1}^{+\infty} A_i\right) \leq \sum_{i=1}^{+\infty}\mathcal D(A_i)$$
可知
因此得到
推论 任意有限假设类 \(\mathcal H\) 是 PAC 可学习的，且
对于一般的问题，我们并不能保证可实现性假设。因为我们并不一定能够给出精确的范畴，使得每个元素的标签唯一且被明确。形式化地，我们将 \(\mathcal X\) 上的概率分布 \(\mathcal D\) 和 \(f:\mathcal X \to \mathcal Y\) 改为 \(\mathcal X \times \mathcal Y\) 上的分布 \(\mathcal D\)，而 \(\mathcal Y\) 通常是 \(\{0, 1\}\) 这一点不变。这个联合分布分为两部分，边缘分布 \(\mathcal D_x\) 以及条件概率 \(\mathcal D((x, y) | x)\)。重新定义真实误差
经验误差的定义不变。因为其不涉及到 \(\mathcal D\)。
对任何 \(\mathcal X \times \{0, 1\}\) 上的分布 \(\mathcal D\)，最优的函数将为
称其为 Bayes 最优分类器。可知对一个一般的 \(\mathcal D\) 来说，\(L_{\mathcal D}(f) \neq 0\)，因此其是不可实现的，因此在其之上 PAC 的定义会失效。
定义 一个假设类 \(\mathcal H\) 是不可知 PAC 可学习的，如果存在函数 \(m_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 和一个学习算法满足，对任意 \(\epsilon, \delta \in (0, 1)\)、\(\mathcal X \times \{0, 1\}\) 上的分布 \(\mathcal D\)，学习算法接收长度为 \(m \geq m_{\mathcal H}(\epsilon, \delta)\) 的训练集可以给出一个假设 \(h\)，使得有至少 \(1 - \delta\) 的概率 \(L_{\mathcal D, f}(h) \leq \min_{h' \in \mathcal H} L_D(h') + \epsilon\)。
这个定义和 PAC 不同之处在于这里只要求了在 \(\mathcal H\) 中不比最优的大 \(\epsilon\)，而不是所有可能中的最优。这是因为没有了可实现性假设后学习者并不能知道最优的损失是多少，故只能和已知的 \(\mathcal H\) 中的比较。
因此，\(L_{\mathcal D}(h_S)\) 可以分为两部分，\(\epsilon_{\text{app}}\) 和 \(\epsilon_{\text{est}}\)，其中 \(\epsilon_{\text{app}}:= \min_{h \in \mathcal H}L_{\mathcal D}(h)\)，其又可以被分解为 \(L_{\mathcal D}(BO) + \min_{h \in \mathcal H} (L_{\mathcal D}(h) - L_{\mathcal D}(BO))\)，其中 \(L_{\mathcal D}(BO)\) 表示 Bayes 最优分类器的损失。而 \(\epsilon_{\text{est}} := L_D(h_S) - \epsilon_{\text{app}}\)，就是式子中的 \(\epsilon\)。