所罗门的遗产

将时钟拨回1956年8月的达特茅斯，当时正值夏天的末尾，来自于各方的学术巨擘们刚刚结束了自6月中旬开始的一场对于人工智能的会议。他们当中的大部分都已经离开。但是，有三个人留了下来（实际上，这三个人一整个夏天都呆在那里进行讨论）。这三个人分别是马文·明斯基、约翰·麦卡锡还有为会议做了最后一场报告的雷·所罗门诺夫。

三人花费了一整个夏天的时间来争论AI未来的道路，但是最后他们并没能达成一致。前两人去往MIT成立了著名的人工智能实验室，领导了未来数十年AI发展的潮流。

但是对于参与讨论的第三人雷·所罗门诺夫（以下简称所罗门），大部分人却闻所未闻。这其实是由于所罗门一生的研究领域，看起来实在是太过抽象、太过偏门且似乎不像同会议其他人的成果那么有用。尽管所罗门诺夫本人是人类历史上首位使用概率论进行机器学习研究的学者，但是他的主要成就是一门名叫算法概率（Algorithmic probability）——后被发展为算法信息理论（Algorithmic Information Theory）——的古怪学科和关于形式化归纳推理的数学理论（General Theory of Inductive Inference）。并且所罗门本人相当清贫，一生未曾荣华富贵。

但实际上，这位不为人知的雷·所罗门诺夫所提出的理论，被许多伟大的AI研究者（如Ilya Sutskever、Wojciech Zaremba、Marcus Hutter等）视为帮助其指明了研究方向的伟大理论。晚年的明斯基甚至直接表示所罗门的理论是自哥德尔不完备性定理之后最大的数学突破，所有人都应该致力于研究它。

换句话说，一些世界上最顶尖AI研究者真心认为，所罗门的理论可能是实现AGI关键理论。

AGI的实现理论

那么，为什么说所罗门的理论是AGI的实现理论？实际上，所罗门身前所研究的理论的正式名称是“Solomonoff`s Induction Inference(SI，所罗门诺夫归纳推理法)”。这是一种形式化的归纳推理理论。从更一般的归纳推理理论的角度来看来看，人脑的思维活动、各种基于统计的传统ML算法、人工神经网络（ANN），本质上都是在给定的数据下进行归纳推理。而我们可以证明，许多的归纳推理方法实际上是SI的一个特例（虽然SI本质上是不可计算的）。并且我们有理由相信，人脑和ANN实际上也属于这些特例。比较SI和人脑，我们可以许多相同之处：

  1. 在面对不同的问题时，人脑和SI实际上都对简单的回答更偏好（这被称为奥卡姆剃刀原则）。
  2. 人脑在进行推理时和SI一样都会保留对一件事情的多种解释（多重选择原理）。
  3. 人脑、ANN、SI实际上都在进行程序搜索。

下面详细描述SI的具体内容和其与AGI理论的关系。

柯尔莫哥洛夫复杂度与通用先验

如果要使用归纳推理，那么我们必须使用贝叶斯律。但是根据贝叶斯公式：

\[P(x|y)=\frac{P(xy)}{P(y)}=\frac{P(x)P(y|x)}{P(y)}\]

我们必须知道$P(x)$，也即我们的先验概率。一般的，我们需要对这个概率进行假设，然后才能进行推理。

在1956年的达特茅斯会议上，麦卡锡和所罗门将所有归纳推理问题总结为一个字符串外推问题，即给定一系列符号，预测下一个会是哪一个（也即自回归生成范式）。所罗门从这个问题出发，给出了基于奥卡姆剃刀原理的一种先验概率。

\[M(x)=2^{-K(\mu())}\]

其中，$\mu()$是指一个可以产生y的程序，$K()$指柯尔莫哥洛夫复杂度。

考虑所有可能产生y的程序则有 \(M(x)=\sum_{\mu \in U}2^{-K(\mu)}\mu(x)\)

其中U是所有可能的可计算假设，或者说所有可以产生y的程序$\mu$的集合。

这里使用$M()$，而不使用$P()$，是因为$M()$并不是一个严格的概率分布（$M()$实际上是一个概率半测度）。

我们可以证明，这个先验概率随着给定的字符串长度n的增加（也即推理前信息的增加），其与真实分布之间的差距，以比$\frac{1}{n}$更快的速度趋近于0。这个先验被称为通用先验概率。

$K()$的名字有很多：柯尔莫哥洛夫复杂度，描述复杂度，柴廷常数……。但是最主流的称呼为柯尔莫哥洛夫复杂度（虽然这个概念最早实际上由所罗门诺夫提出，但是柯尔莫哥洛夫使其流行）。我们在此处简称其为柯氏复杂度。通俗的来讲，我们可以这样理解这个概念：我们宇宙中所有的字符串，都是由某些程序产生的，那么这些程序的长度，衡量了这些字符串的复杂度和信息量。

例如，我们都见过芒德布洛特集在复平面上形成的美丽图案。

alt text

但是我们只需要使用$z:=z^2+c$这个简单的公式进行迭代即可得到这个集合。也就是说，这个公式代表了这个美丽集合的全部。所有芒德布洛特集中的元素都可以用基于这个公式写就的程序产生。我们说，这个程序的所组成的二进制代码串的长度（我们这里使用二进制串进行讨论，但是实际上不同语言下的同一字符串之间的柯氏复杂度可以视作不变，因此这并不影响讨论），就是整个芒德布洛特集组成的串的柯氏复杂度。

接下来我们将看到，通过柯氏复杂度定义的通用先验分布是相当合理且优秀的。对于一个长度为n的二元字符串x，其产生的概率为$2^{-n}$，而其使用最短描述程序产生这个串的概率至少为$2^{-K(x)}$。如果x是有规律的，是可压缩的，那么$K(x) \ll n$，这时的x是由于某种简单的原因（如最短程序）计算出来的概率，这比随机产生的可能性大$2^{n-K(x)}$倍数。

但是遗憾的是，$K()$是不可计算的，我们永远也不能直接利用通用先验分布进行计算。

所罗门诺夫归纳法与莱文通用搜索

尽管通用先验分布是不可计算的，我们依旧可以利用它在数学上做一些事情。

利用通用先验分布和贝叶斯律，我们可以得到所罗门诺夫归纳法（SI）。围绕着SI，我们可以发展出一整套对信息的全新理论，这被称为算法信息论。

SI发明的初衷是利用已知的n位字符串，来推测第n+1位字符串。那么，设字符串为x，下一个需要预测的字符为a，产生x的程序为$\mu()$，利用贝叶斯公式我们有：

\[M(xa|x)=\frac{M(xa)}{M(x)}\]

这个公式和通用先验一起，被统称为所罗门诺夫归纳法。尽管事先不知道真正的先验分布（即$P(x)$和$P(xa)$），但是我们可以证明，随着x长度的增加，$M(x)$和$M(xa)$以比$\frac{1}{n}$更快的速度趋近于真实分布。这告诉了我们一个惊人的事实，那就是在给定数据x的情况下，搜索其对应的最短的程序，等价于是在搜索数据x对应的真实分布！

由于柯氏复杂度的不可计算性，整个SI都是不可计算的。但是用所罗门本人的话来说，这是一个“小小的代价”。实际上也确实如此，柯尔莫哥洛夫的学生莱文（Levin）根据SI设计了一个搜索算法，可以作为一种对SI的近似实现。这被称为莱文通用搜索（Levin`s Universal Algorithm）。

这是一个极为复杂的算法，但是其大体思想是说：我们可以在n个并行的图灵机上进行程序搜索，并逐步依据搜索到的程序的长度进行改进，最终在有限时间内，我们可以得到一个接近SI的结果。

尽管这个算法时间开销极大，难以在现实中实现。但是这依旧给了我们一个很好的启发，这让我们意识到SI并非是数学家的无用玩具，SI是可以以某种方式近似实现的。

Compression=Intelligence

SI理论最伟大的地方在于，我们可以从SI得出”compression=intelligence“这个极为有力的结论。

SI告诉我们，寻找最短的程序，几乎等价于寻找真实分布。

从这个角度来看，我们可以发现SI理论与数据压缩深度学习有着极为深厚的联系。

首先，ANN实际上可以看作一台执行多步程序的多路并行的计算机（由Ilya提出，这个想法与莱文通用搜索不谋而合）。例如，一个50层的网络运行的过程就是同时也运行n个可以执行50步的程序，然后将这些程序的输出加权。优化网络的过程就是搜索程序的过程。

随后，我们可以看到，当我们使用神经网路（如GPT）进行完形填空式的自监督学习的时候，我们实际上是在解决所罗门所预定义的问题，即对于一个字符串，预测其下一个是什么。结合上面所说的ANN是对SI的近似的结论。我们可以认为现代的各种LLM都是在尝试实现一个SI。

而预测下一个token这种自监督学习的方法，确实使得GPT4这些模型产生了一部分智能。

而数据压缩理论告诉我们：任何一个预测器，都有唯一的一个压缩器与其对应。因此，我们可以使用各种LLM作为一种对数据的无损压缩。这恰恰告诉我们，使用训练LLM的过程就是压缩数据的过程。

因此，使用“compression=intelligence”这个公式来总结和说明LLM的智能从何而来这个问题，再合适不过了。

对泛化的解释

利用SI来解释神经网络最美妙的地方就在于，这种视角解释了神经网络为何会有如此强的泛化性能。

实际上已经有很多了解算法信息理论的人，看到了神经网络与SI之间的关系。他们尝试使用算法信息论的方法去解释过参数化的神经网络为什么可以进行有效的泛化。

现在有已经有许许多多的工作提出，神经网络之所以能在过参数的情况下泛化，其实就是因为其总是能在训练的过程中拟合到柯氏复杂度较低的函数，而这类函数正是最接近真实分布的一类函数，也是泛化性能最好的一类函数。可以说，神经网络的泛化难题完全可以通过算法信息论得到解释。

结语

令人遗憾的是，雷·所罗门诺夫，这位伟大的思想家、AI领域的先驱，已经于2009年永远的离开了我们。人类利用概率论来实现AI的伟大探索，正是由他开始。而我也十分的确信，他深邃而超前的思维将永远伴随着我们，走到AGI追寻之路的末尾，帮助我们捧起AGI的圣杯。R.I.P. Ray。

Referring:
所罗门诺夫的个人网站
所罗门诺夫的归纳推理理论
算法概率
柯尔莫哥洛夫复杂度
译作——老师柯尔莫哥洛夫的生平和工作（9）：1960年代之算法信息论，算法概率论，柯尔莫哥洛夫复杂度（Kolmogorov complexity）
莱文通用搜索
通用搜索