悟了！大模型的数学原理！

刘海明 · 发表于 2024-6-8 13:01:48

1956年达特茅斯会议部分参会者。左2 罗切斯特，左3所罗门诺夫，左4 明斯基，右2麦卡锡，右1香农

导读：

目前最热门的大模型公司OpenAI的GPT系列成功的秘诀在于next token prediction（本质既：预测下一个词），其数学基础为所罗门诺夫归纳法。

该法是大语言模型的理论基石，用于揭示GPT的核心机制。正值此理论诞生60周年，本文概述所罗门诺夫归纳法的重要性及其与其他学者的独特贡献。文章也探讨了该理论的最新发展、在AI领域的应用及哲学内涵。对AI感兴趣的读者不容错过。

所罗门诺夫（1926年7月25日-2009年12月7日）

科学发展常涉及理论与实践的交织。自然语言处理（NLP）历史曲折，尤其是大语言模型的发展，既涉及理论又关乎实践，还受商业因素影响。尽管工程师们尝试寻找其数学基础，但真正的理论基础却鲜有发现。事实上，数学家所罗门诺夫早在1960年代就已为大模型奠定数学基础，其理论至今仍有指导意义。

1956年，麦卡锡和明斯基在贝尔实验室的香农和IBM的罗切斯特支持下，在达特茅斯学院召开了人工智能夏季研讨会，标志着人工智能作为独立学科的诞生。所罗门诺夫是最认真对待这次会议的人，他在达特茅斯待了整个暑假。他的学术生涯受哲学家卡尔纳普影响，专注于归纳推理。

神经网络奠基者皮茨和人工智能开拓者司马贺也都受惠于卡尔纳普的思想。所罗门诺夫与明斯基和麦卡锡结识后，开始关注逻辑和递归函数的研究。递归函数逐渐演变成可计算性理论，进而衍生出计算复杂性。明斯基的计算理论教科书对早期计算理论发展有重要影响，他的“AI孵化出计算理论”的观点也有一定道理。1953年，麦卡锡和明斯基在贝尔实验室工作，围绕信息论专家香农，他们对图灵机的理论和智能活动的基础进行研究。当时，老一辈的维纳推出了他的新书《控制论》，但香农和麦卡锡对此并不认同。麦卡锡向香农建议出一本文集，邀请了当时的一线研究人员撰写文章，该书于1956年出版，名为《自动机研究》。麦卡锡在其中发表了一篇短文，讨论了图灵机的逆函数问题，即如何通过观察图灵机的输出来推测其输入。麦卡锡认为所有数学问题都可以通过图灵机求逆来解决。在达特茅斯会议期间，麦卡锡和所罗门诺夫进行了长时间的讨论，所罗门诺夫将麦卡锡的问题转化为给定初始段求序列后续的问题，麦卡锡起初并不理解这个思路，但后来明白了其重要性。他们所谓的“sequence continuation”、“next word”或“next symbol”，现在被称为“next token”。

* O) n V2 c8 Y8 d

2006年达特茅斯会议50年周纪念会。左2麦卡锡，左3明斯基，右1所罗门诺夫

这个说法源于法国数学家博雷尔1913年的文章，他考虑了猴子在打字机上随机敲字能否敲出《哈姆雷特》的问题，指出概率虽小但非零，被称为“无限猴子定理”。阿根廷作家博尔赫斯在其作品中设想了一个完美图书馆，收藏所有可能的书籍。今天的大模型训练也在朝这个方向努力，力图穷举人类所有知识。博尔赫斯出发点是理性主义，而随机猴子是经验主义，但都可用麦卡锡的求逆统一为图灵机的枚举过程。图灵1948年的文章“智能机器”提到机器学习的方法，并指出所有学习都可归约为枚举过程，但这个过程不停机或不可计算。

所罗门诺夫归纳

与麦卡锡的讨论后，所罗门诺夫在达特茅斯会议结束前完成了关于归纳推理的备忘录“An Inductive Inference Machine”，日期为1956年8月14日。他向参会人员传阅了这份打字稿，并在1956年底将改进版本寄给卡内基理工学院的司马贺。

所罗门诺夫的工作在1960年的“大脑系统与计算机”会议上首次公开，同年通过Zator公司报告和美国空军AFOSR报告广泛传播。1961年，明斯基在“Steps Toward Artificial Intelligence”文章中提及这项工作。所罗门诺夫进一步修订后，以“归纳推理的形式理论”为题，于1964年在《信息与控制》正式发表。文章太长，被拆成两部分，前半部分讲理论，后半部分讲实例。

所罗门诺夫归纳法定义为：给定序列（x1, x2, …, xn），预测xn+1。归纳推理是寻找最小图灵机，为（x1, x2, …, xn）建模，以准确预测后续序列。序列的描述长度即图灵机大小，与麦卡锡最初意识到的“有效”相符。例如，序列（1, 1, 1,…）的描述长度是O(log(n))。

监督学习可视为自监督学习的特例。监督学习给定序列对（x1,c1）,（x2,c2）,…,(xn,cn）及xn+1，预测cn+1。学习过程是找到拟合函数c=f(x)。这类问题可轻松转化为自监督学习：给定序列（x1,c1,x2,c2,…,xn,cn,xn+1），预测cn+1。

麦卡锡将此描述为“在下一个字符上下注”的问题，即大语言模型如GPT的核心机制：next token prediction。概括已知数据的图灵机是大模型。对于同一数据集，期望覆盖数据集的大模型参数越少越好，即找到最经济的图灵机。学习可视为压缩，参数量与token量关系可借此研究。所罗门诺夫归纳法可能不停机，因此使用近似算法，放宽对图灵机的“最小性”和预测准确性的限制。他利用贝叶斯定理推导出序列的先验概率分布。神经网络作为通用近似器，是实现所罗门诺夫归纳法的良好候选机制，这也是今天大模型的进路。所罗门诺夫对生成句子语法的问题感兴趣，并受到乔姆斯基的启发，将文法推广为概率文法。他的“归纳推理机”可以通过输入文本学习文法，这被称为“文法发现”。乔姆斯基的先天内生文法与所罗门诺夫的先验概率分布相似，但两者立场不同。根据丘奇-图灵论题，两者区别仅为修辞。所罗门诺夫的先验概率分布中，程序置信度随长度指数递减，符合奥卡姆剃刀原则。这是个美妙的公式：

他的生活并不富裕，大部分时间在自己的咨询公司Oxbridge从事政府研究，公司仅他一人。他的学术自传“算法概率论的发现”于1997年发表，并经过修订多次发表。最新版收录在文集“Randomness Through Computation: Some Answers, More Questions”中。

历史:柯尔莫哥洛夫与复杂性

苏联数学家柯尔莫哥洛夫，对传统数学有深刻贡献，并对计算机科学和信息论产生重要影响。1950年代，他敏锐地意识到信息论的重要性，而对控制论则持怀疑态度。柯尔莫哥洛夫在概率论领域有深入研究，创办了《信息传输问题》季刊，提出信息的量化定义，并分为频率、组合学和算法三种基础。他主张信息论在逻辑上先于概率论，且算法最为坚实。柯尔莫哥洛夫的复杂性理论定义为生成最短程序的长度，其文章简洁而深入。尽管他的某些理论需要后人来完善，但他的工作仍具有重要意义。柯尔莫哥洛夫复杂性与程序的表示无关，不同的程序表示如C、Java、Python或图灵机代码，其最短描述之间的差异仅在于一个常量，这一性质被称为柯尔莫哥洛夫论题。柯尔莫哥洛夫复杂性被认为比香农熵更可靠，因为图的柯尔莫哥洛夫复杂度是不变的，而结构熵会因图的表示不同而变化。柯尔莫哥洛夫引用了所罗门诺夫的工作，使得后者在苏联的声誉超过西方。柯尔莫哥洛夫复杂性也被称为所罗门诺夫复杂性或所罗门诺夫-柯尔莫哥洛夫-蔡廷复杂性，为避免歧义，本文采用“柯尔莫哥洛夫复杂性”这一说法。受柯尔莫哥洛夫影响，该学科也被称为算法概率论或算法信息论。在伦敦大学皇家哈洛威学院，苏联学者建立了机器学习研究中心，并设立了柯尔莫哥洛夫奖章，所罗门诺夫是第一届获奖者，最近一次获奖者是弗拉基米尔·瓦普尼克。所罗门诺夫也曾在该学院担任兼职教授。

历史：蔡廷与随机性

所罗门诺夫（左一）与蔡廷，2003

阿根廷出生的犹太裔美国理论计算机科学家蔡廷（Greg Chaitin, 1947年-），在高中时期就表现出色，发表过关于自动机时钟同步的文章。他本科未毕业即随父母返回阿根廷，在IBM分公司找到程序员工作，研究哥德尔不完全性定理。他19岁时独立重新发明了所罗门诺夫归纳法和柯尔莫哥洛夫信息量的思想，并发表在美国计算机学会会刊上。

蔡廷的研究基于贝里悖论，他使用LISP函数式编程语言以避免混淆。他证明了柯尔莫哥洛夫复杂度是不可计算的，称之为“不完全性”。1974年，蔡廷回到美国并在IBM TJ Watson研究中心工作，他向哥德尔展示了利用贝里悖论得到的不完全性定理版本，尽管哥德尔对此表示无所谓，但蔡廷仍然认为他的证明为不完全性提供了新的信息论视角。蔡廷将他在IEEE Transactions on Information Theory的文章寄给哥德尔并约定了见面时间，但因哥德尔身体不好，怕雪而取消了见面，这使蔡廷深感遗憾。他在1991年被维也纳大学邀请演讲，并被誉为“比哥德尔还哥德尔”。晚年，蔡廷对生物学产生浓厚兴趣，出版科普著作《证明达尔文》，他不满生物学缺乏理论基础，提出用算法信息论解释进化论，称为“元生物学”，其思想可从遗传算法和编程中找到线索。

历史：列文与通用搜索过程

. _6 O! C c7 O

苏联数学家列文（Leonid Levin）在1972年独立提出了NP完全性并证明了几个等价问题，文章发表在柯尔莫哥洛夫创办的刊物上。尽管因政治问题未获博士学位，但他后来在美国麻省理工学院获得博士学位，并在波士顿大学教书至退休。他的贡献被广泛认可，计算理论教科书中的库克定理已改为库克-列文定理。2012年，他获得了考虑对整个学科影响的高德纳奖。

列文的文章通常都很简短，他1986年开创的算法平均复杂性分析也只有两页。尽管列文倾向于认为P=NP，但这在学术界是少数派观点。

列文在1973年的文章中给出了两个定理，其中定理1关于NP完全性，而定理2当时被忽略。定理1没有详细证明，定理2甚至没有说明。列文提出了一个通用搜索过程，这与麦卡锡提出的问题相关，所罗门诺夫在此问题上已有20年的研究。

得知列文在苏联的遭遇后，所罗门诺夫联系了美国学校和学者帮助列文。他将与列文的学术讨论写成报告，为Levin-1973补齐了定理2的证明，并称列文的通用搜索过程为L-search。

列文的L-search在柯尔莫哥洛夫复杂性的基础上加了一个时间的限制，可定义如下:

Kt(x) = min{ℓ(p) + log(time(p)): U(p) = x}

这样列文的复杂性就是可计算的了，也就是说，如果逆函数存在，总可以通过列文的通用搜索过程找到。这和所罗门诺夫更早获得的收敛性定理契合。

列文1973年文章第二页。参考文献前是一句鸣谢，鸣谢前即是定理2的陈述。

本内特与逻辑深度

物理学家本内特（Charles Bennett, 1943-）因量子计算出名，他是量子密码分发协议BB84的第一个B。他对算法信息论也有杰出贡献，他在1988年引入了逻辑深度（logical depth）的概念（见Bennett-1988），定义如下：

LD(x) = min{T(p): ℓ(p) =p*+s ∧U(p) = x}

即近乎最短的程序输出x所需的时间。这里p*就是柯尔莫哥洛夫复杂性，ℓ(p)就是近乎最短的程序的长度。可以看出，逻辑深度进一步放宽了柯尔莫哥洛夫复杂性对程序最短长度的要求。

如果把归纳看作是压缩的话，逻辑深度考虑的是解压的时间。逻辑深度让我们考虑时间和空间的关系。直觉上，我们会认为时间比空间更“贵”，但目前在计算理论中，我们尚不知多项式时间的类P是不是等于多项式空间的类PSPACE，当然NP是PSPACE的子集但不知是不是真子集。如果P≠PSPACE，那么必然存在PSPACE中可计算的字符串，其逻辑深度大于多项式。压缩首先考虑的是空间成本，但解压有时间成本。

大模型的压缩时间是训练时间，柯尔莫哥洛夫复杂度代表参数量，逻辑深度则对应最短“推断”时间。术语中“推断”更合适，因为它是统计意义上的，与逻辑意义的“推理”不同。大模型中也有逻辑意义的“推理”，如CoT，但机器定理证明的教科书常不区分inference和reasoning。若人工智能的逻辑派和统计派都说汉语，可能不会争论。

进展和应用

7 _6 h0 q7 T9 c8 z

李明夫妇和所罗门诺夫夫妇

理论计算机科学家李明等人对所罗门诺夫-柯尔莫哥洛夫-蔡廷复杂性的研究做出了重要贡献。他们合著的《柯尔莫哥洛夫复杂性及其应用》是该领域的权威参考书，目前已出到第4版。Marcus Hutter从理论物理转向通用人工智能，提出用强化学习为基础的AGI理论框架AIXI，其数学工具为所罗门诺夫归纳法。

OpenAI的ChatGPT的成功，虽常被归因于底层神经网络架构Transformer，但GPT的next token prediction（所罗门诺夫归纳）可能是其成功的关键。目前大模型研究中，理论暂时落后于工程实践。所罗门诺夫-柯尔莫哥洛夫-蔡廷理论认为，学习可看作压缩，用精简系统概括数据或从殊相到共相的过程。Hutter设立的Hutter Prize奖励最佳无损压缩工作，其文章“Language Modeling is Compression”表明大语言模型做无损压缩效果优于基于哈夫曼编码的压缩算法。

柯尔莫哥洛夫和蔡廷的出发点是信息表达和信息传输，也是压缩。这些观点在工程师群体中引起热烈讨论，为大语言模型的发展提供了新视角。

所罗门诺夫归纳法与哲学

所罗门诺夫归纳法描述如下：

1. 输入观察数据。

2. 提出新假设（图灵机）解释数据。

3. 输入新数据，检验假设。

4. 如果数据证伪假设，返回第2步。

5. 如果数据证实假设，持续接受假设，并返回第3步。

这种方法与皮尔士的实用主义相似，强调从已知中发现未知。皮尔士认为，理性主义与经验主义并不完全对立，新的假设成立并开始解释大量数据时，系统更像理性主义者；新数据证伪旧假设时，系统更像经验主义者。

所罗门诺夫归纳法也可以解释波普尔的证伪理论。他认为，证伪比证实更容易，因为说一个东西不对总比说一个东西对容易。这类似于皮尔士的“可错性”概念。此外，统计学家乔治·博克斯认为，所有模型都是错的，但有些是有用的，可以用来预测。

库恩的科学革命理论也是所罗门诺夫归纳法的特例。奥卡姆剃刀原则认为，在解释力相近的前提下，模型越小越好。在所罗门诺夫理论中，覆盖所有数据的最小模型是最短的程序或图灵机。当新旧模型差别较大时，即发生科学革命。新模型可能比旧模型更复杂，逻辑更深。

最后，所罗门诺夫归纳法可以解释关于意识的理论。

结论

亚里士多德在《形而上学》中指出，“求知是人的本性”。他描述了人从经验到技术再到科学的“求知”过程。对于“不可计算”或“不停机”的概念，或许象征着上帝为人类留下的希望。在所罗门诺夫的理论框架内，知识的进步被视为“递增学习”。深入研究所罗门诺夫归纳法和柯尔莫哥洛夫复杂性有望为机器学习提供新的理论基础。当前，遗传算法、遗传编程、强化学习均可在所罗门诺夫归纳法的框架内找到计算理论的支撑。

亚里士多德的观点也可借用为“压缩是人的本性”。休谟认为，归纳虽不能证实，但对人性至关重要。在这一观点下，压缩可被视为人性的本质。经验源自感觉，对经验数据的建模出于经济考虑，而建模就是压缩，这一过程由图灵机完成。所罗门诺夫归纳法在这种意义上可作为第一性原理。进化过程亦可视为压缩，适者生存也可解读为“最压者生存”。压缩体现了物理世界规律在信息世界中的表现。笛卡尔的“我思故我在”可被严格表达为“我压故我在”。

来源： AI大模型前沿

链接：https://mp.weixin.qq.com/s/0rDNFZdB4vlhCoIxufbTuQ

编辑：刘诗扬

帐号		自动登录	找回密码
密码			实名注册