1956 年达特茅斯会议的部分与会者。左二罗切斯特、左三索罗门诺夫、左四明斯基、右二麦卡锡、右一香农介绍：目前最火的大型模型公司是OpenAI。 OpenAI首席科学家Ilya Sutskever在采访中不断暗示，接下来的token预测是GPT系列大型模型成功的关键。然而直到2023年8月他在伯克利理论计算机科学研究所发表演讲时，才明确透露GPT的数学基础是所罗门诺夫归纳法。那么，什么是所罗门诺夫归纳法？对于大模型研究有什么意义？今年是所罗门诺夫感应诞生60周年。人工智能学者尼克写了一篇万字文章，解释了为什么索罗门诺夫归纳法是大语言模型的理论基础，以及如何解释GPT的核心机制，下一个令牌预测。尼克|第三条科学的发展有时是理论在前，实践在后；有时工程或实验先产生结果，理论解释才慢慢出现；但有时理论和实践是纠缠在一起的。自然语言处理（NLP）的历史更加曲折，更像是最后一个案例。大语言模型作为NLP的最新发展，不仅是理论与实践，还与业务混杂在一起，这使得厘清历史变得更加困难。随着大语言模型在工程上的不断进步，有理论意识的工程师正在努力寻找其数学基础，为大语言模型的成功提供解释。然而，许多背离第一性原理的观察和拟合并不是理论基础，反而徒然给工程师增加更多的困惑。事实上，特立独行的数学家雷·所罗门诺夫（Ray Solomonoff，1926-2009）在20 世纪60 年代初的天才贡献为大型模型奠定了数学基础。他最初的理论开始被重新发现，至今仍指导着工程实践，并可能为未来指明道路。所罗门诺夫堪称大语言模型的先知。 1956年，麦卡锡（John McCarthy，1927-2011）和明斯基（Marvin Lee Minsky，1927-2016）带头，在贝尔实验室和IBM的克劳德·埃尔伍德·香农（Claude Elwood Shannon，1916-2001）的帮助下。在纳撒尼尔·罗切斯特（Nathaniel Rochester，1919-2001）的支持下，一场关于人工智能的夏季研讨会在麦卡锡当时任教的达特茅斯学院举行。这次会议标志着人工智能作为一门独立学科的建立。这次会议聚集了一群来自不同学科的年轻而雄心勃勃的学者。对这次会议最重视的人是所罗门诺夫。与其他来来往往的与会者不同，所罗门诺夫整个夏天都留在达特茅斯。 1951年，他在芝加哥大学跟随费米主修物理学。获得硕士学位后，他离开象牙塔，移居美国东北部（波士顿和纽约），开始了他半工作半学习、幸福但并不富裕的生活。在芝加哥求学期间，对他影响最大的是哲学家鲁道夫·卡尔纳普（Rudolf Carnap，1891-1970）。卡尔纳普当时的主要兴趣是概率论和归纳推理。他的想法和成果反映在他1950年出版的书《概率的逻辑基础》()中（参见Carnap-1950）。索罗门诺夫深入研究了这本书，并得出推理成为他一生的研究方向。所罗门诺夫（Solomonov，1926年7月25日- 2009年12月7日） 有趣的是，神经网络的创始人之一沃尔特·皮茨（Walter Pitts，1923年- 1969年）也受到了卡尔纳普的影响。另一位人工智能先驱赫伯特·西蒙（Herbert Simon，1916-2001）在回忆录中表示，他在芝加哥参加了卡尔纳普的数理逻辑课程，从而开始对机器定理证明的思想和更广泛的智能问题产生兴趣。

这样，人工智能的两大流派，逻辑学和神经网络，都是卡尔纳普教授的（见Nick-2021）。所罗门诺夫在1952 年左右认识了明斯基和麦卡锡，当时两人都是普林斯顿大学数学系的博士生。虽然阿朗佐·丘奇在那里负责逻辑学，但明斯基和麦卡锡的博士论文并不是关于逻辑的。不过，他们无疑是受到了逻辑的强烈影响，刚开始的时候专注于逻辑，尤其是递归函数的研究。当时，逻辑学是美国大学数学系的一门新兴学科。递归函数作为数理逻辑的一个分支学科，逐渐演变成现在的可计算性理论，并进一步衍生出计算复杂性。明斯基还于1967 年撰写了一本早期且有影响力的计算理论教科书《计算：有限与无限机器》（参见Minsky-1967）。他还带领几名学生在麻省理工学院专门研究计算理论，其中曼努埃尔·曼努埃尔·布鲁姆(Manuel Manuel Blum) 后来因计算机科学而获得了图灵奖。他对计算复杂性和密码学的贡献。明斯基“人工智能孵化计算理论”的说法不无道理。 1953年夏天，已经博士毕业的麦卡锡和即将博士毕业的明斯基都在贝尔实验室工作。他们都围绕着因信息论而闻名的香农。香农当时的兴趣是图灵机以及图灵机是否可以作为智能活动的理论基础。当时比较出名的人是老维纳，他刚刚出版了一本有影响力的新书。书名《控制论》借用自希腊语“舵手”。维纳试图用这个新词统一世界。在世界上，他在书中不时暗示或表达香农的信息论也受到了他的启发。很明显，年轻的香农和年轻的麦卡锡都没有购买维纳的账户，他们也不喜欢“控制论”这个词。麦卡锡建议香农编一本选集，邀请当时相关的一线研究人员来投稿。该选集直到1956 年才以《自动机研究》（自动机研究）的名称出版。这个平凡的称号最终被香农解决了。他不喜欢用创造新术语的手段来吸引注意力，但麦卡锡认为这个不显眼的标题并不能体现他们的初衷，这导致他后来坚持使用另一个新术语“人工智能”。为这个全新的领域命名。在这本选集中，麦卡锡本人还贡献了一篇只有5 页的短文，标题为“图灵机定义的函数的反转”（参见McCarthy-1956）。在文章中，麦卡锡讨论了如何在假设图灵机的输出已知的情况下猜测图灵机的输入的问题。更严格地说：给定一个递归函数（即图灵机）fm 及其输出r (fm(n)=r)，如何找到一个“有效”反函数g(m, r) 使得fm(g(m , r))=r，其中m 是图灵机的序列号。本题是试图通过观察黑匣子（图灵机）的输出来猜测黑匣子的内部结构。最幼稚的方法是枚举所有可以产生输出的图灵机，但显然这种方法并不一定会关闭机器。事实上，在当今大型模型的背景下，g(m,r)是一个大型语言模型。麦卡锡意识到这个问题相当于通过按某种顺序检查所有可能的英语论文来寻找猜想的证明。麦卡锡认为，所有的数学问题都可以用图灵机来表达为反演，这正是所罗门诺夫想要解决的归纳推理问题。在达特茅斯会议期间，麦卡锡和所罗门诺夫有更多机会进行长时间的讨论。

所罗门诺夫认为，麦卡锡的问题可以转化为：“给定一个序列的初始片段，找到这个序列的延续”。通过已知的初始片段，利用建模来预测后续序列。麦卡锡一开始并没有意识到这个想法的重要性，并问道：这不只是推断吗？在场所有人都被麦卡锡的反问惊呆了。麦卡锡第二天做出了反应。他说，所罗门诺夫的问题通俗地说就是：“假设我们在一栋老房子里找到一台计算机正在打印你提到的序列，而且它已经接近序列的结尾了。很快就会打印出一个字符，你能打赌吗？”它会打印出正确的字符吗？”麦卡锡和所罗门诺夫称之为“序列延续”、“下一个词”或“下一个符号”，用今天的话说就是“下一个标记”。 2006 年达特茅斯会议50 周年纪念活动。左边是麦卡锡（第二位），左边是明斯基（第三位），右边是所罗门诺夫（第一位）。其实，这种说法的由来更早。法国数学家Flix douard Justin mile Borel（1871-1956）在他1913年的文章《Mcanique Statistique et Irrversibilit》（统计力学和不可逆性）中考虑了这样一个问题：让猴子在打字机上操作如果你在电脑上随机打字，它可以吗？输入《哈姆雷特》？博雷尔指出，猴子随机敲出数字《哈姆雷特》的概率是5.0210。这种可能性极小，但也不是绝对不可能。这就是所谓的“无限猴子定理”。阿根廷诗人兼作家豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges，1899-1986）在1944年出版的短篇小说集《小径分岔的花园》中收录了他的一部哲学小说（实际上更像散文）《巴比伦图书馆》，其中他想象了一个完美的图书馆，可以容纳所有可能的字母枚举产生的书籍；事实上，他在1939年写了一篇更严肃的哲学文章《全面图书馆》，它回顾了从亚里士多德开始的不同阶段的思想家对这一理想的各种推测。以今天的眼光来看，大模型的训练不就是在努力穷尽人类现有的所有知识吗？如果说博尔赫斯的出发点是理性主义的，那么随机猴子肯定是经验主义的，但它们都可以统一成某种形式。图灵机枚举过程使用麦卡锡的逆图灵1948年的文章“智能机器”的价值正在被越来越多的人注意到，他的文章中提到了几种机器学习方法。在通用图灵机中，程序就等于数据，因此所有程序都像数据一样可以被一一枚举。这种枚举方法可以让你自己学习所有可能的程序。这就是图灵所说的“主动性”（参见Nick-2024）。图灵明确表示，所有的“学习”都可以归结为这种方法。计算理论告诉我们，这个枚举过程不会停止，或者说是不可计算的。与麦卡锡的讨论促使所罗门诺夫进一步完善他的想法。在达特茅斯会议结束之前，他写了一篇关于归纳推理的备忘录，“归纳推理机”。这份打字稿的日期是1956 年8 月14 日。所罗门诺夫将打字稿分发给与会者。 1956年底，他还把改进版寄给了卡内基理工学院工业管理系的赫伯特·西蒙。 Solomonov 的工作首次在1960 年加州理工学院大脑系统和计算机会议上公开发表。同年，这篇文章以Zator 报告和美国空军AFOSR 报告的形式广为流传。

明斯基在1961 年一篇具有广泛影响力的文章《迈向人工智能的步伐》中提到了这项工作（参见Minsky-1961）。索罗门诺夫后来进一步修改了1960年的作品，题为《归纳推理的形式理论》，并于1964年正式发表在计算理论重要期刊《信息与控制》()上。由于文章太长，分成两部分，分两期发表。前半部分讲理论，后半部分讲几个实际例子（见Solomonoff-1964）。所罗门诺夫归纳法可以定义如下：给定序列(x1, x2, …, xn)，预测xn+1。归纳推理试图找到一个最小的图灵机，可以对(x1, x2, …, xn) 进行建模，以准确预测后续序列。序列的描述长度就是图灵机的大小，这实际上就是麦卡锡一开始隐约意识到的“有效”。例如，如果一个序列是n个数字1:(1,1,1,)，那么我们可以编写以下程序来输出序列：这个序列的描述长度是O(log(n))。例如，如果我们给出序列(3,5,7)，将会有无数种方法来预测后续的结果，其中之一是9，因为程序可能会打印奇数，如下： 但也许猜测是错误的，还有另一种可能属性是11，因为程序可能会打印素数。显然，打印素数的程序比打印奇数的程序复杂得多，这意味着素数的描述长度大于奇数的描述长度。监督学习也可以被视为自监督学习的一个特例。监督学习（包括分类问题）是在给定序列对（元组）的情况下预测cn+1：(x1,c1)、(x2,c2)、(xn,cn) 和xn+1。学习过程就是寻找拟合函数c=f(x)。这类问题可以很容易地转化为自监督学习，如下所示：给定序列(x1,c1,x2,c2,…,xn,cn,xn+1)，预测cn+1。这个被麦卡锡描述为“押注下一个符号”的问题，实际上就是以GPT为代表的大型语言模型的核心机制：下一个符号预测。能够对已知数据进行概括的图灵机是一个大型模型。对于同一个数据集，我们当然期望覆盖该数据集的大模型的参数尽可能少。换句话说，我们期望找到最经济的、可以概括的图灵机，即最小的图灵机。从这个意义上说，学习可以被认为是压缩。这里还可以研究参数数量和代币数量之间的关系。所罗门诺夫归纳法可能不会停止，因此只能使用近似算法来放松对图灵机“极小性”和预测精度的限制。所罗门诺夫利用贝叶斯定理推导了序列的先验概率分布。作为通用逼近器，神经网络可以成为实现所罗门诺夫归纳法的良好候选机制。这实际上是当今大型模型的方法。所罗门诺夫想要解决的另一个问题是给出一些句子，看看他是否可以学习语法来生成这些句子。此时，诺姆·乔姆斯基的文章《语言描述的三种模型》刚刚发表。所罗门诺夫受到启发，将乔姆斯基的语法概括为概率语法。他的“归纳推理引擎”的一个应用场景是通过输入文本来学习语法，他后来称之为“语法的发现”。乔姆斯基的先天语法实际上是所罗门诺夫的先验概率分布，但乔姆斯基采取的是理性主义立场，而所罗门诺夫无疑是经验主义者。事实上，如果接受丘奇-图灵论点，理性主义和经验主义之间的区别只是口头上的，而不是本质上的。

根据所罗门诺夫的先验概率分布，程序的置信度随着其长度呈指数下降。这就是奥卡姆剃刀，这意味着较短的程序应该具有较高的置信度。这也可以得到经验数据的支持（参见Veldhuizen-2005）。在所罗门诺夫的纪念网站（raysolomonoff.com）上，显眼地展示了所罗门诺夫美丽的公式：他的学术自传《算法概率的发现》于1997年发表在《计算理论杂志》《计算机与系统科学》（计算机与系统科学杂志）上（参见所罗门诺夫-1997）。这篇文章后来经过修改，在多地以不同形式发表。最新版本在死后收集在选集Randomness Through Computation : Some Answers, More Questions 中（参见Solomonoff-2011）。叱咤风云的苏联数学家安德烈·尼古拉耶维奇·柯尔莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903-1987）除了对传统数学做出广泛而深刻的贡献外，还对计算机科学和信息论的许多方面做出了直接和间接的贡献。影响。 20世纪50年代初，香农的信息论和维纳的控制论通过俄文翻译传入苏联。科尔莫哥洛夫依靠他敏锐的直觉认识到信息论的重要性。同时，他表达了对控制论的蔑视，认为控制论没有内在的统一性。这种认识与香农、麦卡锡等参加达特茅斯会议的人对控制论的看法是一致的。当时苏联的科学发展形势十分复杂。即使以柯尔莫哥洛夫的地位，他对遗传学的兴趣也被李森科压制。不过，李森科下台后，科尔莫哥洛夫也为他说了好话。科尔莫哥洛夫对控制论的看法并没有阻止控制论成为苏联的主流学科。这可能导致苏联对计算机科学和人工智能的理解较晚，这在某种程度上是计算机科学的一个子学科；这当然也给中国相关学科的发展带来了偏差。控制论在美国并未成为独立学科，但计算机科学成为主导学科。从20世纪60年代末开始，美国顶尖学校纷纷设立计算机系。控制论的核心概念：反馈只是递归函数最简单的特例，不足以作为第一原理。在科尔莫戈洛夫为匈牙利数学家Rosa Pate撰写的俄文译本《递归函数论》所写的序言中（莫绍奎老师1958年根据俄文版将这本书翻译成中文），他将“柯”“戈尔莫戈洛夫”译为“戈尔莫戈洛夫” ”，而“图灵”被译为“杜灵”）指出一般递归函数和可执行可计算性仍需要从可构造性的角度进一步研究——他对Church-Turing论文也有深刻的见解（见Peter-1951）无论如何，柯尔莫哥洛夫的切入点是他最喜欢的领域：概率论。1965年，他创办了学术季刊《信息传输问题》（《信息传输问题》），该刊很快成为苏联计算理论中最重要的阵地。科尔莫哥洛夫本人在第一期发表了《信息定量定义的三种方法》，从算法的角度研究概率论和信息论。信息论的核心是对信息内容的研究。香农对信息的定义是熵。柯尔莫哥洛夫将信息论的基础分为三类，第一类是频率，第二类是组合学，第三类是算法。柯尔莫哥洛夫对信息论和概率论的评价发人深省：“信息论在逻辑上先于概率论。它不是基于后者。”他认为组合学比频率更扎实，但最有说服力的是算法。

一条信息中包含的信息量可以通过生成这条信息的最短程序的长度来衡量（参见Kolmogorov-1965）。这就是现在所说的“柯尔莫哥洛夫复杂度”（Kolmogorov Complexity），它可以定义如下：KC(x)=min{(p) : U(p)=x}，这是输出字符串x p 的长度。柯尔莫哥洛夫的经典文章只有7页，他写的以下文章