Basic Machine Learning Theories

本文将简要介绍机器学习理论的基础内容，主要是依赖于先前介绍的集中不等式给出一些优化函数空间有限时相对简单的界，并引入 VC 维。此外本文也将简要介绍 bias-various tradeoff ，尽管此中似乎并无什么深入的理论，连是否应该归于本篇也是有待商榷的。

PAC Assumptions and ERM

• 机器学习理论这一方向与我们先前所介绍的内容有所不同，这里我们更关注如何对一般的（监督）学习框架建模，并用严格的数学工具刻画，从而得到可以描述模型行为、指导模型设计的理论。本节中我们主要关注两个问题：

  1. 在 ERM 损失函数泛化误差的尺度上如何衡量训练得到的模型与理论最优模型的差距。
  2. 固定训练集大小时如何度量模型的误差，模型的误差被哪些因子影响。

  其中第二个问题由稍后介绍的 Bias-Variance Tradeoff 解答，现在我们考虑第一个问题。对于给定的数据集 ，以及假设 ，定义 在 上的训练误差为：¹ 这也是某种 ERM 。当然我们最终关注的并不是 ，而是 在全体（特别是不可见的）数据上的表现。假设真实的数据以及标注 服从一定的联合分布 ，那么定义泛化误差（Generalization Error）为： 实际上我们无法直接计算泛化误差，因此我们期待训练误差可以在一定程度上反映前者。为此，假设 中的每个数据对 通过从 中独立采样得到，这样便可通过 估计 。这一套设定便被称作 PAC（Probably Approximately Correct）Assumptions 。可以看出，在 PAC 假设下，训练误差是对泛化误差做 次独立采样的无偏估计。以下的讨论都将以 PAC 假设作为基础。

• 假设 落在一定的函数空间 中，则 ERM 的一般形式服从： 将其最优解记作 ，再将泛化误差的最优解记作 。我们希望说明 距离 不会太远，更确切的说， 可以被 控制。在 有限时，这一点是容易说明的，我们就从此处开始。²

The Case of Finite

• 对于 ，记 。考虑数据集中的 个数据点，记随机变量 。由于 从 中独立采样得到， 是一系列独立同分布的伯努利随机变量，而 的训练误差恰为 的均值。记 ，注意到 的泛化误差恰为 的期望，因此由先前介绍的 Hoeffding Bound ，可以得到： 这就是说固定 ，当 很大时训练误差与泛化误差以很大的概率差距很小。再由 Union Bound ： 这说明 中全体函数的的训练误差与泛化误差在 较大时都差得不多。从以上的界出发我们可以得到很多有趣的结果。固定 ，若要： 只需： 那么以至少 的概率有： 这便保证了在 较大时 ERM 的解离理论最优解在泛化误差上差得不远。式 被称作 ERM 的取样复杂度（Sample Complexity）。综上所述，我们便得到定理：

  • 【定理 1. PAC 下的泛化误差】对于 ，固定 与 ，则以至少 的概率有：

  • Remark. 上式在一定程度上反映了 Bias-Variance Tradeoff 。考虑选择函数空间 ，对应更复杂的模型。此时 必然缩小了，然而因为 的扩大， 项会变大，从而不一定使得 ERM 解的泛化误差更好。

  • 【定理 2. 取样复杂度】对于 ，固定 ，则当： 时，有 。

The Case of Infinite

• 在 无限时，情况会复杂很多，因为我们不再能使用 Union Bound 来做控制了。对此，CS229 的 Lecture Notes 里给了一个很有趣的捷径。假设我们的模型是参数化的，具备 个实参数。实践中的模型必须要部署到计算机上，假设我们使用 double 类型来存储这 个参数。熟知 double 具备 64 位，这就是说实际上可以认为函数空间最大只有 。那么按照【定理 2.】，该模型的 sample complexity 约为： 这就说要使得 ERM 解距离理论最优解不远，数据集大小应至少达到参数量的线性级别。

• 当然以上讨论在真实的函数空间 中是不成立的。但令人惊讶的是即使在严格的理论建模当中，使得 ERM 解逼近最优解所需的数据量也确实大概是参数量的线性级别。之所以说“大概”，是因为一方面在稍后介绍的理论建模当中，函数空间的复杂度并不直接使用“参数量”来度量；另一方面即使是同一函数空间也有不同的参数化方式。具体的，我们将使用 VC 维这一著名的理论来严格的度量函数空间 的复杂度。

VC dimensions

• 要定义函数空间在监督学习上的复杂度，一个符合直观的方式是考察其分类数据点的能力。对于数据空间 中的集合 ，称函数空间 粉碎（shatter） ，当且仅当对于标注空间 中的任意标注序列 ，存在 使得 。

  • 【定义 1. Vapnik-Chervonenkis Dimension】对于给定的函数空间 ，称其 VC 维为 ，当且仅当存在最大的 ，使得 粉碎 ，记作 。

  一个直观的例子是，考察二维平面上全体仿射函数构成的集合 ，显然，对于任何不共线的三点构成的集合 ， 粉碎 ；而对于任取的四点，这一性质都不存在，因此 。

  基于 VC 维，可以给出以下的对于一般 成立的结果：

  • 【定理 3. General Generalization Difference】对于给定的函数空间 ， ，令 ，则以至少 的概率有： 因此，以至少 的概率有：

  证明：[Admitted]³

  • Remark. 由该定理，便足以说明在数据量 达到 时，ERM 解与最优解的泛化误差差距不大。

  这就是说，要使得模型充分的学习到数据分布，数据量应达到 级别。值得一提的是，对于大多数实际使用的函数空间，VC 维（在恰当的参数化时）基本和参数量渐进相等。⁴综上所述，在服从 PAC 假设的问题场景下，要使得 ERM 达到与理论最优解相近的泛化误差所需的数据量基本和模型的参数量渐进同级。

Bias-Variance Tradeoff

• Bias-Variance Tradeoff 是对于模型误差的一类广泛看法，其实际上是一种技巧，可以在 MSE 的尺度⁵上对广泛的误差做偏差与方差的分解。例如我们可以从模型的参数误差和假设误差两方面考察其 MSE 的偏差-方差分解，而前者也被称作统计推断。但在这里我们着重介绍后者，这一方面是因为机器学习中我们更关心假设误差，另一方面也是因为两者的分析几乎是相同的。

The Case of Prediction

• 假定选定的训练集 整体服从一定的分布 （例如在 PAC 假设下 由从某一联合分布中的若干次独立采样构成），对于某一（来自于验证集中的）固定数据点 ，我们希望衡量 上训练得到的假设 在此处的误差。为此，考察预测与标注的 MSE 对于 的期望： 我们以 来衡量模型在 处的“真实”预测，因为我们期待 一定程度上集中于 ，这样： 其中第二项是预测的期望 与标注 的偏差，进一步衡量了模型的偏差（Bias）。而第一项是预测 关于训练集 的分布 的方差（Variance），度量了在 变化时假设 的波动。我们将模型偏差与方差形式化的定义如下：

  • 【定义 2. Bias and Variance】对于固定的 ERM ，其在服从一定分布 的固定大小数据集 上训练得到假设 。考察 在固定数据点 上由 MSE 度量的期望误差： 其恰由两部分构成，其一是期望假设 与标注 的偏差 ；其二则是模型假设的方差 。

  这一套看法可以被用来方便的描述 Overfitting 和 Underfitting（尽管我们不会对此类现象提供严格的定义）。当选择简单的模型时，因为模型表达能力的不足，偏差项较大；而因为模型的简化性，其受数据随机性的影响不大，因此方差项较小，这种现象被称作欠拟合。而选择复杂的模型时，因为模型表达能力的增强而偏差减小；然而模型受到数据随机性的影响更大，从而方差项较大，这就被称作过拟合。这两种情况都会导致不理想的泛化误差。

• 值得一提的是，偏差-方差分解可以被用于很多问题，也有不同的解读方式，这是因为其本质上只是一种处理 MSE 形式误差的技巧，而不依赖于过多假设。

---

1. 很大程度上这种误差是对于分类任务谈的，对于回归任务可能要用 MSE 之类的。但总的来说，具体模型要具体分析。↩︎

2. 本文将针对此种形式的 ERM 讨论，其余的 ERM 形式是需要推广的。↩︎

3. 不好证。但是交大 CS3936 可能会讲吧。↩︎

4. 先承认这一点，我也没做过调研。↩︎

5. 因为采用了 MSE 误差，偏差方差分解一般是对于回归模型谈的，对分类模型做 MSE 是一件很奇怪的事。在某些文献里可能会有人对分类模型谈偏差方差分解，我不清楚此处有没有严格的理论保证，因为后者的定义似乎是一件挺麻烦的事。↩︎