关于《对泛化的一个观察》的笔记
摘要
本文是对 Ilya Sutskever 在2023年西蒙斯研究所研讨会演讲的详细笔记。演讲从压缩理论的视角解释无监督学习为何有效，核心论点是预测与压缩之间存在一一对应关系。通过引入柯尔莫戈洛夫复杂度、条件复杂度和联合压缩等概念，论证了好的无监督学习算法本质上是好的压缩器，并最终将联合压缩与最大似然估计联系起来。
核心概念及解读
压缩与预测的等价性：所有压缩器和所有预测器之间存在一一对应关系，能更好预测下一个字符就能更好压缩数据，这为理解无监督学习提供了理论基础
柯尔莫戈洛夫复杂度：一个对象的柯尔莫戈洛夫复杂度是能输出该对象的最短程序的长度，它代表了理论上的终极压缩器，虽然不可计算但为分析提供了理论上界
条件柯尔莫戈洛夫复杂度：K(Y|X) 衡量在已知数据集 X 的情况下描述 Y 所需的最短程序长度，它形式化了无监督数据对下游任务的价值
分布匹配：在没有对应关系的两个数据源之间寻找映射函数，使一个数据源的变换分布近似另一个数据源的分布，是理解无监督学习的重要桥梁
联合压缩与最大似然估计：将两个数据集拼接后联合压缩等价于最大似然估计，这将压缩理论的分析框架与机器学习的标准训练范式统一起来
深入探讨 Ilya Sutskever 在 2023 年西蒙斯研究所大型语言模型与 Transformer 研讨会上的演讲“对泛化的一个观察”。
Ilya Sutskever，OpenAI 的联合创始人之一，最近在 2023 年西蒙斯研究所（Simons Institute）的大型语言模型与 Transformer 研讨会上发表了演讲。该演讲已被录制，并可在 YouTube 上观看。演讲的主题是“对泛化的一个观察”（An Observation on Generalization），Ilya 探讨了我们如何利用压缩理论的视角来理解无监督学习。我觉得这次演讲非常有见地，但有时可能难以跟上思路，更难把握整体脉络，至少对于像我这样（大脑皮层功能没那么强大）的人来说是这样。不幸的是，这是研讨会中少数几个没有附带详细论文的演讲之一。我觉得这是一个很好的机会，可以写下我从演讲中做的笔记。鉴于 Ilya 阐述其理论的方式非常精彩，很难真正用不同的方式来解释和呈现。因此，我首先转录了演讲内容，然后添加了我自己的笔记，以提供更好的背景信息或更详细的说明以求清晰。
对泛化的一个观察
这次演讲的核心是试图真正理解为什么无监督学习能够奏效，并对其进行数学上的推理。为了达到这个目的，Ilya 首先提出了学习本身（从数据中学习）的概念以及为什么机器学习会起作用。这里的期望是数据具有规律性，而机器学习模型被期望学习我们数据中的这种规律性。谈到监督学习，他提出了这个等式：
低训练误差 + 训练数据量 > “自由度” = 低测试误差
现在，对于无监督学习，我们的梦想是，给定所有这些未标记的数据（图像、文本块等），我们期望机器学习模型能够发现数据中“真实”的、隐藏的结构。无监督学习的一个关键点是，我们通常优化一个代理目标（例如下一个词预测或重构），而我们关心的是一个不同的目标（例如学习数据中的隐藏模式以进行序列分类）。这为什么会奏效呢？
通过分布匹配进行无监督学习
为了理解这一点，我们首先来看分布匹配。考虑两个数据源 X 和 Y，它们之间没有任何对应关系。这可能就像是不同语言的数据集（比如英语和法语），样本之间没有对应。分布匹配的思想是找到一个映射 F，使得：
distribution(F(X)) ∼ Y
在我们上面的例子中，就是：distribution(F(English)) ∼ French
之前已经提出了许多方法（一个相关的例子：无监督机器翻译），表明即使对于高维度的 X 和 Y，这种方法也是可行的。
有了这个背景，我们现在如何理解无监督学习呢？
压缩理论
引用 Ilya 的话：
所有压缩器和所有预测器之间存在一一对应的关系
乍一看，这个说法完全不明显！我认为仅凭这一句话就可以写一整篇文章，但为了给出一个直观（不幸的是，定性）的答案：
考虑压缩 PNG 文件的情况。图像中的像素模式越可预测，跨像素包含的真正独特信息量就越少，压缩效果就越好。另一个我觉得有帮助的例子来自 Xiaoyu He 关于预测和压缩的演讲，发布在 LessWrong 上：
假设你试图为一个字符串找到一种编码，其中每个字符只能是“a”、“b”、“c”或“d”。考虑字符串“abaaabaacbabaaabcd”。让我们采用下面这个简单的编码方案：
| 字符 | 编码 |
|---|---|
| a | 00 |
| b | 01 |
| c | 10 |
| d | 11 |
上述字符串需要的比特数：36 比特。假设我们数据中的所有字符串都具有以下特征：“a”出现最频繁，而“c”和“d”很少出现（这与我们这个轶事例子的情况大致相符）。因此，你可以使用下面修改后的编码方案：
| 字符 | 编码 |
|---|---|
| a | 0 |
| b | 10 |
| c | 110 |
| d | 111 |
该字符串需要的比特数：29 比特。通过能够更好地预测每个字符串的下一个字符，我们能够更好地压缩该字符串。
现在，带着这个想法，让我们回到最初关于无监督学习的讨论。在无监督学习中，至少在表示学习领域，我们通常试图为我们的数据学习有用的表示，最终目标是使用这些学到的表示来完成下游的预测任务（例如，在其上训练一个线性分类器）。因此，一个好的无监督学习算法学会了对你的数据进行良好的压缩。我们现在将使用压缩（而非预测）的语言。
一个简单的思想实验
考虑两个数据集 X 和 Y。假设我们还有一个好的压缩算法 C(data) —— 给定一个数据集 d，压缩器 C 将输出一个压缩对象 C(d)。现在，假设我们将 X 和 Y 连接起来并联合压缩它们。一个好的压缩器现在将利用数据集 X 中的模式来压缩 Y：
|C(concat(X,Y))| < |C(X)| + |C(Y)| + O(1)
（你可以将 |⋅| 理解为压缩对象大小的概念）
左侧（LHS）和右侧（RHS）之间的差距取决于两个数据集中共享的信息/结构，或者说算法互信息。
好的，但这如何与无监督学习联系起来呢？Y 可以是你关心的监督任务的数据集（序列分类），而 X 是你的无监督任务的数据。Ilya 还谈到这如何推广了分布匹配，即如果存在一个函数 F 使得 Distribution(F(X)) ≈ Distribution(Y)，那么一个“好的”压缩器应该能够找到并利用这一点。为什么？你可以简单地考虑一个二维情况，其中 X 中的所有数据点大约位于直线 y=x 上，而 Y 中的所有数据点大约位于直线 y=2x 上。能够找到转换函数 F 将使你能够进一步压缩你的组合数据集。
形式化
考虑一个试图压缩 Y 的机器学习算法 A。假设该算法可以访问数据集 X。现在，我们将目标形式化为最小化使用此算法的遗憾（regret）。遗憾是相对于一个黄金标准的——在这种情况下，定性地说，就是能够从我们的未标记数据集 X 中获得尽可能多的价值。
低遗憾 = 我们从无标签数据中“获得了所有价值”，并且没有人能做得更好！
柯尔莫戈洛夫复杂度作为终极压缩器
一个对象（这可以是任何数据）的柯尔莫戈洛夫复杂度（Kolmogorov complexity）是产生该对象作为其输出的（或者说，某个）最短程序的长度。本质上，这是产生输出所需的所有信息。如果创建一个 20MB 图像的程序只需要 10 行代码，那么该程序就是你图像的一个有效压缩。更进一步，对于一个（可计算的）压缩器 C，以下结论成立：
K(X) ≤ |C(X)| + K(C) + O(1)
虽然我不会对此深入探讨太多，但你可以用前面字符串压缩的例子更好地理解这一点。假设我们没有压缩器，即我们只是将字符串存储为比特。因此，如果我们有一个字符串 s，其比特长度为 |s|，那么 K(s) ≤ |s| + O(1) （这是柯尔莫戈洛夫复杂度定义的一个简单推论）。现在，如果我们加入一个压缩器，柯尔莫戈洛夫复杂度将小于压缩对象的大小，加上对压缩器的最短描述的长度。这个证明可以用三个词（相当精彩地）概括：模拟论证（The simulation argument）。如果你有一个很棒的压缩器，那么你应该能够用一个计算机程序来模拟它，并且根据柯尔莫戈洛夫复杂度的定义，你的新计算机程序加上压缩对象的大小，不可能比不进行任何压缩来模拟 X 的最优、最短程序更短。
就在这里，让我们暂停一下，让 Ilya 阐述一个与神经网络的精彩类比。对于一般的 X，柯尔莫戈洛夫复杂度是不可计算的（关于这一点，我让维基百科来做所有的解释工作）。神经网络是计算机，是的，是能够模拟不同程序的计算机。SGD（随机梯度下降）是我们用来在无限大的程序/电路空间中有效搜索的便捷搜索算法。
条件柯尔莫戈洛夫复杂度作为解决方案
我们来看看条件柯尔莫戈洛夫复杂度如何被视为我们在无监督学习中寻找的解决方案。如果 C 是一个可计算的压缩器，那么：
∀X , K(Y|X) < |C(Y|X)| + K(C) + O(1)
首先，条件柯尔莫戈洛夫复杂度意味着什么？这里的条件柯尔莫戈洛夫复杂度 K(Y|X) 是指，在可以探测 X（或者说，使用 X 作为辅助输入）的情况下，能够输出 Y 的最短程序。它量化了在已知 X 的情况下，Y 的复杂程度。考虑这个例子：如果 X 是互联网上所有网页的集合，而 Y 只是 www.google.com 上的信息，那么你可以非常容易地描述一个短程序来在给定 X 的情况下获得 Y，因此 K(Y|X) 很低。类似地，如果 X 只是一个随机字符串的数据集，而 Y 是 www.google.com 中的信息，那么我们从了解 X 中获益不多，K(Y|X) 就只是 K(Y)。
只需压缩一切
关于上面提到的条件复杂度的一些技术细节：与其讨论“以数据集为条件”（conditioning on a dataset），即压缩器在能够“访问”X 的同时压缩 Y，我们也可以从连接数据集 concat(X,Y) 的角度来看待这个问题。这是因为在机器学习中，我们可以拟合大型数据集，但目前还没有好的方法来“以整个数据集为条件”。关于两个数据集的联合复杂度有一个关系：
K(X,Y) = K(X) + K(Y|X) + O(log(K(X|Y)))
这来自于柯尔莫戈洛夫复杂度的链式法则。用文字来说，这意味着输出 X 和 Y 的最短程序可以从输出 X 的最短程序，加上给定 X 输出 Y 的最短程序，再加上某个对数因子得到。或者，正如 Ilya 所说：
首先，“生成”X，然后“使用”X 来生成 Y，这与联合生成两个数据集不会有太大区别。
因此，你现在可以简单地讨论传统的柯尔莫戈洛夫压缩器，它联合压缩两个数据集 X 和 Y。让我们回到我们的主要讨论：在无监督学习中，我们希望从未标记数据 X 中提取尽可能多的价值，以达到在与某个标记数据 Y 具有相同分布的测试数据集上进行某种预测的目标。我们阐述了如何将无监督学习算法视为压缩器，并且使用上面的方程，你可以看到连接数据集的柯尔莫戈洛夫复杂度确实是你能做到的最好的压缩器，它从 X 中提取了尽可能多的价值。
联合压缩就是最大似然估计
Ilya 现在提出了联合压缩和最大似然之间的等价性。假设我们有一个数据集 X = x₁, x₂, …, x<0xE2><0x82><0x99>。那么，使用由参数 θ 控制的无监督机器学习算法来“压缩”该数据集的成本是负对数似然——即你的 ML 算法/压缩器未能为其所见数据样本正确分配最高可能概率的程度： 成本 = −∑ᵢᴺ logP(xᵢ|θ)
添加另一个数据集——或者执行联合压缩，仅仅是在上面的求和中添加更多样本。
这里的一个关键启示：神经网络/Transformer 是通过最大似然对所有输入数据样本执行联合压缩的计算机，我们使用 SGD 在无限大的可能执行压缩的程序空间中进行搜索，并选择一个足够好的压缩器。
GPT
OpenAI 训练的 GPT-N 模型可以通过思考文本的条件分布来理解。在训练期间，像 GPT 这样的因果语言模型被训练来根据来自某个随机文档的文本块来执行下一个词的预测。通过在巨大的、互联网规模的此类文档语料库上进行训练，这些神经网络学习了不同文本条件分布的内部模型。
这在所有数据领域都通用吗？
这在处理图像或视频的计算机视觉领域也能奏效吗？Ilya 引用了 OpenAI 的研究来论证这是可行的。
iGPT
iGPT 是一个在图像上训练的无监督的基于 Transformer 的模型。数据预处理很简单：他们只是通过首先将原始图像调整到低分辨率，然后将其重塑为一维序列来预处理原始图像。该模型被训练来对这些像素序列执行下一个像素的预测。Ilya 接着更详细地介绍了 iGPT 在不同规模下的性能，我在这里就不赘述了。有趣或者说值得注意的是，iGPT 的性能非常接近在 ImageNet 上训练的最佳无监督模型。
不同模型间的线性探针准确率比较，摘自 iGPT 论文。最大的 iGPT 模型 iGPT-XL 的性能接近当时 ImageNet 上最好的无监督学习方法 SimCLR。注意，SimCLR 使用了全分辨率图像，而 iGPT 使用了缩小的 64x64 图像。另请注意参数量的差异——iGPT 的参数量多了 20 倍。
关于如何衡量线性探针准确率的评论：iGPT 和 SimCLR 提供了图像的一种表示——一种好的压缩——然后在这个表示之上训练一个线性分类器来执行分类。这个线性分类器的准确率就是线性探针准确率。
局限性/未解答的问题
以下是上述关于无监督学习的压缩理论未能解决的一些局限性或未解答的问题。我不想过多扩展这一部分，所以我会几乎逐字地列出 Ilya 演讲中的观点：
- 压缩理论并没有直接解释为什么表示是好的并且是线性可分的。
- 线性表示非常普遍，以至于它们形成的原因必定非常根本，但这并未被捕捉到。
- 自回归（AR）模型似乎比 BERT 类模型具有更好的表示。Ilya 在此的推测是：对于 AR 模型，你需要根据之前所有的词/像素来预测下一个词/像素，并且你需要查看整个上下文。而对于 BERT 类模型则不是这样，你掩盖掉一定比例的像素/词，然后稍微看看过去和未来。下一个词预测中最难的预测任务比掩码语言建模中最难的预测任务要难得多。
总结
- Ilya 深入探讨了无监督学习的数学和概念基础，形式化了机器学习算法如何通过捕捉数据固有的规律性从未标记数据中学习。
- 压缩理论可以用来解释无监督学习。所有压缩器和预测器之间存在一一对应的关系，一个好的无监督学习算法需要对你的数据执行良好的压缩，以便在下游的监督学习任务上获得良好的预测。
- 柯尔莫戈洛夫复杂度可以被视为压缩的黄金标准。在无监督学习中，我们期望从未标记数据 X 中提取尽可能多的价值，以达到在与某个标记数据 Y 具有相同分布的测试数据集上进行某种预测的目标。无监督学习算法通过最大似然被训练成良好的联合压缩器，而连接数据集的柯尔莫戈洛夫复杂度是你能做到的最好的压缩器，它能从 X 中提取尽可能多的价值。
- 神经网络是可以模拟不同程序的计算机，而 SGD 是我们用来在无限大的程序/电路空间中有效搜索，以尽可能接近最优程序（柯尔莫戈洛夫复杂度）的便捷搜索算法。
- OpenAI 的通用预训练 Transformer (GPT) 模型及其在计算机视觉（iGPT）等其他领域的变体，是通过下一个 token/像素预测这一代理任务进行无监督学习的一些现实世界示例。下一个 token/像素预测已被证明是学习数据中真实的、隐藏结构的良好代理，即执行良好的压缩。
- 该理论的一些局限性在于，它没有解释我们从好的无监督学习算法中获得的线性表示，我们也不理解为什么自回归建模在学习良好表示方面优于掩码语言建模。