所罗门诺夫：大年夜措辞模型的先知_所罗门_洛夫

2024-09-30 14:19:27 智能助手

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

所罗门诺夫：大年夜措辞模型的先知_所罗门_洛夫智能助手

导读：

目前最火热的大模型公司莫过于OpenAI。
OpenAI首席科学家Ilya Sutskever在接管采访时不断暗示，next token prediction是GPT系列大模型成功的关键，但直到2023年8月，他在伯克利理论打算机科学研究所演讲时才明确透露，GPT的数学依据是所罗门诺夫归纳法（Solomonoff Induction）。

那么，所罗门诺夫归纳法是什么？其对大模型研究有何主要意义？今年正值所罗门诺夫归纳法出身60周年，人工智能学者尼克，撰写万字长文，阐明所罗门诺夫归纳法为何是大措辞模型的理论根本，如何阐明GPT的核心机制next token prediction。

尼克 | 撰文

科学发展有时理论先行，实践随后；有时则是工程或实验先出成果，理论阐明逐步到来；但也有时是理论和实践纠缠在一起。

自然措辞处理(NLP)的历史较为弯曲，更像末了一种情形。
大措辞模型，作为NLP的最新进展，除了理论和实践外，还夹杂着商业，这使得澄清历史更加困难。
随着大措辞模型在工程上的不断进展，有理论意识的工程师们企图探求其数学根本，以求为大模型的成功供应阐明。
但很多分开第一性事理的不雅观察和拟合实在算不上理论根本，反而徒劳为工程师们增加了更多的困惑。

事实上，特立独行的数学家所罗门诺夫(Ray Solomonoff，1926年-2009年)在1960年代初期的天才贡献已经为大模型奠定了数学根本。
他的原创理论开始被重新创造，至今对工程实践仍具辅导浸染，并可能为未来指明方向。
所罗门诺夫可算得大措辞模型的先知。

1956年麦卡锡(John McCarthy，1927年-2011年)和明斯基(Marvin Lee Minsky，1927年—2016年)牵头，在贝尔实验室的喷鼻香农(Claude Elwood Shannon，1916年—2001年)和IBM的罗切斯特(Nathaniel Rochester, 1919年—2001年)支持下在麦卡锡当时任教的达特茅斯学院召开了人工智能夏季研讨会。
这次会议标志人工智能作为一门独立学科的建立。
会议聚拢了一群来自多个不同学科、年轻且野心勃勃的学者。

最负责对待这个会议的便是所罗门诺夫。
和其他来来往往的参会者不同，所罗门诺夫在达特茅斯待了整整一个暑假。
他1951年在芝加哥大学跟随费米主修物理，只得了硕士就离开象牙塔，转往美国东北部（波士顿和纽约一带）开始了他半工半学、快乐但并不富贵的生平。
在芝加哥求学期间，对他影响最大的是哲学家卡尔纳普（Rudolf Carnap，1891年-1970年）。
卡尔纳普那时的紧张兴趣是概率论和归纳推理，思想和成果都表示在他1950年出版的《概率的逻辑根本》（）一书中（见Carnap-1950），所罗门诺夫深研此书，归纳推理遂成为他毕生的研究方向。

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

故意思的是，神经网络的奠基者之一皮茨（Walter Pitts，1923年-1969年）也沾恩于卡尔纳普。
而另一位人工智能的开拓者司马贺（Herbert Simon，1916年-2001年）在他的回顾录里讲到自己在芝加哥时听过卡尔纳普的数理逻辑课，从而开始萌生对机器定理证明以及更广泛的智能问题的兴趣。
这么说来，人工智能的两大流派——逻辑和神经网络——都受教于卡尔纳普（见尼克-2021）。

所罗门诺夫1952年旁边结识了明斯基和麦卡锡，那时两人还都是普林斯顿大学数学系的博士生。
虽然丘奇（Alonzo Church）在那里坐镇逻辑学，但明斯基和麦卡锡的博士论文却都不是关于逻辑的，不过他们毫无疑问都受到了逻辑的强烈熏陶，刚出道时都聚焦逻辑，尤其是递归函数的研究。
当时逻辑在美国大学的数学系是新兴学科。
递归函数作为数理逻辑的子学科，逐渐演化成现在的可打算性理论，并进一步衍生出打算繁芜性。
明斯基1967年还写过一本早期颇有影响的打算理论教科书Computation：Finite and Infinite Machines（见Minsky-1967），在麻省理工还带过几个专做打算理论的学生，个中曼纽尔· 布鲁姆（Manuel Blum）后来由于打算繁芜性和密码学的贡献得了图灵奖。
明斯基所谓“AI孵化出打算理论”的说法不无道理。

1953年夏天，已经博士毕业的麦卡锡和即将博士毕业的明斯基都在贝尔实验室事情，他们都环绕着由于信息论而声名雀起的喷鼻香农。
喷鼻香农当时的兴趣则是图灵机以及是否可用图灵机作为智能活动的理论根本。
那时名气更大的是更长一辈的维纳，他刚出版了一本颇有影响的新书，书名Cybernetics（掌握论）借用自希腊语（舵手），维纳企图以这个新词一统天下，他在书中时时暗示或昭示喷鼻香农的信息论也是受到他的启示。
很明显，年轻的喷鼻香农和更年轻的麦卡锡都不买维纳的账，也不喜好“掌握论”这个词。
麦卡锡向喷鼻香农建议编一本文集，请当时干系的一线研究职员都贡献文章，这本文集直到1956年才以《自动机研究》（Automata Studies）为名出版，这个通俗俗通的书名末了是喷鼻香农定的，他不喜好用创造新名词的手段来吸引眼球，但麦卡锡认为这个不显山不露水的书名并没有反响出他们的初衷，这导致他后来坚持用另一个新词“人工智能”来命名这个全新的领域。
在这本文集中，麦卡锡本人也贡献了一篇只有5页的短文，题为“图灵机定义的逆函数”(The Inversion of Functions Defined by Turing Machines，见McCarthy-1956)。

麦卡锡在文中谈论了这样一个问题：假设知道一个图灵机的输出，如何猜到其输入。
更严谨地：给定一个递归函数（即一个图灵机）fm及其输出r（fm(n)=r），如何找到一个“有效”的逆函数g(m, r) 使得 fm(g(m, r)) = r，这里m是图灵机的序号。
这个问题便是通过不雅观察一个黑盒子（图灵机）的输出，力争猜出黑盒子的内部布局。
最土的办法便是列举所有能够产生输出的图灵机，但很明显这个办法不一定停机。
事实上，在本日大模型的语境里，g(m, r)便是一个大措辞模型。
麦卡锡意识到这个问题对应于在所有可能的文章中以某种顺序探求证明（It corresponds to looking for a proof of a conjecture by checking in some order all possible English essays）。
麦卡锡认为所有的数学问题都可以表达为用图灵机求逆，这正是所罗门诺夫想办理的归纳推理问题。

达特茅斯会议期间，麦卡锡和所罗门诺夫有了更多的机会进行永劫光谈论。
所罗门诺夫认为麦卡锡的问题可以转化成：“给定一个序列的初始段，求这个序列的后续”。
通过已知的初始段，建模，以模型来预测后续序列。
麦卡锡一开始并没故意识到这个思路的主要性，反问了一句：这不便是外插吗？当时在场的人都被麦卡锡的反问卡住了。
第二天麦卡锡反应过来，他说所罗门诺夫的问题普通地说，便是：“假设我们创造一座老屋子里有一个打算机正在打印你说的序列，并且已经靠近序列的末端，立时就要打印下一个字符，你敢打赌它会打印精确的字符吗？” 麦卡锡和所罗门诺夫所谓“sequence continuation”，“next word”或者“next symbol”，用本日的话说便是 “next token”。

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

实在，这个说法有着更早的起源。
法国数学家博雷尔(Félix Édouard Justin Émile Borel，1871年—1956年）在1913年的文章“Mécanique Statistique et Irréversibilité”（统计力学与不可逆性）中考虑过这样一个问题：让一个猴子在一个打字机上随意地敲字，它能敲出一部《哈姆雷特》吗？博雷尔指出猴子随机敲出一部《哈姆雷特》的概率是5.02×10，概率极小，但不是绝对不可能，这被称为“无限猴子定理”（infinite monkey theorem）。
阿根廷墨客和作家博尔赫斯（Jorge Luis Borges ，1899年-1986年）在1944年出版的短篇小说集《小径分岔的花园》中收录了一篇他的哲理小说（实在更像是散文）“巴比伦图书馆”，文中设想一个完美的图书馆，它可以收藏由字母列举产生的所有可能的书；事实上，他在1939年写过一篇更严明的哲学文章“总图书馆”（Total Library），回顾了从亚里士多德开始不同阶段思想家对这个空想的各种思辨。

本日看来，大模型不便是走在这个方向吗？大模型的演习力争穷举人类已有的所有知识。
如果博尔赫斯的出发点是理性主义的，那么随机猴子肯定是履历主义的，但他们都可以用麦卡锡的求逆统一为某种图灵机的列举过程。

图灵1948年的文章“智能机器”的代价正在被越来越多的人把稳到。
图灵文中提到了几种机器学习的方法。
在通用图灵机中，程序即是数据，于是，所有的程序，就像数据一样，是可以逐一被列举出来的。
这个列举行法是自己把所有可能的程序都学出来。
这便是图灵所谓“主动性”（initiative）（见尼克-2024）。
图灵明确表示，所有“学习”都可以归约到这个方法。
打算理论见告我们这个列举过程一直机，或者说不可打算。

和麦卡锡的谈论，匆匆使所罗门诺夫进一步完善自己的想法，达特茅斯会议结束前，他写好了一篇关于归纳推理的备忘录“An Inductive Inference Machine”，这篇打字稿的日期是1956年8月14日。
所罗门诺夫把该打字稿给参会职员传阅。
1956年底他还将一个改进的版本寄给卡内基理工学院工业管理系的司马贺（Herbert Simon）。

所罗门诺夫的事情首次公开拓表是在1960年加州理工学院召开的“大脑系统与打算机”（Cerebral Systems and Computers）会议上。
同年这篇文章作为Zator公司报告和美国空军AFOSR报告得到更广泛的流传。
1961年明斯基在一篇影响广泛的文章“Steps Toward Artificial Intelligence”中提到了这项事情（见Minsky-1961）。
所罗门诺夫后来对1960年的事情做了进一步修订，以“归纳推理的形式理论”（A Formal Theory of Inductive Inference）为题，于1964年正式揭橥在打算理论的主要刊物《信息与掌握》（）。
由于文章太长，被拆成两部分，在两期分别刊出，前半部分讲理论，后半部分讲了几个实例（见Solomonoff-1964）。

所罗门诺夫归纳法可以如下定义：给定序列（x1, x2, …, xn）, 预测xn+1。
归纳推理便是力争找到一个最小的图灵机，可以为（x1, x2, …, xn）建模，从而准确地预测后续序列。
序列的描述长度便是图灵机的大小，这实在便是麦卡锡最初模糊地意识到的“有效”。
例如，如果一个序列是n个1: （1, 1, 1,…）,那么我们可以写出如下程序输出该序列:

这个序列的描述长度便是O(log(n))。

例如，如果我们给出序列（3, 5, 7），会有无穷多种预测后续的结果，个中一种是 9，由于程序有可能打印奇数，如下：

但大概猜的不对，还有一种可能性是 11，由于程序有可能是打印素数的。
很明显，打印素数的程序就要比打印奇数的程序繁芜很多，也便是说素数的描述长度要大于奇数的描述长度。
等等。

监督学习也可以看作是自监督学习的分外情形。
监督学习（包括分类问题），便是给定序列对(tuple)：(x1,c1),(x2,c2),…,(xn,cn),以及xn+1，预测cn+1。
学习的过程便是找到拟合函数c=f(x)。
这类问题都可以轻松地转化为自监督学习如下：给定序列（x1,c1,x2,c2,…,xn,cn,xn+1）, 预测cn+1。

这个被麦卡锡刻画为“不才一个字符高下注”（bet on next symbol）的问题，实在便是GPT为代表的大措辞模型的核心机制：next token prediction。
能够对已知数据做出概括的图灵机便是大模型。
对付同样的数据集，我们当然期望覆盖数据集的大模型的参数越少越好，换句话说，我们期望找到可以做出概括的最经济的图灵机，即最小的图灵机。
在这个意义上，学习可以被当作压缩。
参数量和token量之间的关系也可借此研究。
所罗门诺夫归纳法可能一直机，于是只能用近似算法，放宽对图灵机的“最小性”和预测准确性的限定。
所罗门诺夫利用贝叶斯定理推导出序列的先验概率分布。
神经网络作为一个通用近似器（universal approximator），可以是实现所罗门诺夫归纳法的一个很好的候选机制。
这实在便是本日大模型的进路。

所罗门诺夫想到的另一个要办理的问题，是给定一些句子，看能否学会天生这些句子的语法。
此时乔姆斯基（Noam Chomsky）的“措辞描述的三种模型”的文章刚刚揭橥，所罗门诺夫受到启示，把乔姆斯基文法推广成概率文法。
他的“归纳推理机”的一种运用处景便是通过输入文本，学会文法，这被他后来称为“文法创造”（discovery of grammar）。

乔姆斯基的先天内生文法（innate grammar）实在便是所罗门诺夫的先验概率分布，只不过乔姆斯基采纳了理性主义的态度，而所罗门诺夫无疑是履历主义的。
事实上，如果认可丘奇-图灵论题，理性主义和履历主义的差异只是修辞的，而不是实质的。
在所罗门诺夫的先验概率分布下，程序的置信度随着其长度指数递减。
这便是奥卡姆剃刀，即越短的程序该当有越高的置信度。
这一点也可以从履历数据中得到佐证（见Veldhuizen-2005）。
在所罗门诺夫的纪念网站（raysolomonoff.com）上，能干地放着所罗门诺夫的俏丽公式：

他的学术自传“算法概率论的创造”（The Discovery of Algorithmic Probability）1997年揭橥在打算理论杂志《打算机与系统科学》（Journal of Computer and System Sciences）上（见Solomonoff-1997），这篇文章后来历经修订，在多处以不同形式揭橥。
最新的一版在他去世后被收录在文集Randomness Through Computation: Some Answers, More Questions之中（见Solomonoff-2011）。

万能的苏联数学家柯尔莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903年-1987年），除了对传统数学做出广泛和深刻的贡献外，对打算机科学和信息论的诸多方面，也有直接和间接的影响。

1950年代初期，喷鼻香农的信息论和维纳的掌握论，通过俄文翻译传入苏联。
柯尔莫哥洛夫凭着他敏锐的直觉，意识到信息论的主要性。
同时他对掌握论则表示出不屑，他认为掌握论并没有内在的统一性。
这个认识和喷鼻香农、麦卡锡等参与达特茅斯会议的人对掌握论的意见同等。
苏联当时的科学发展状况非常繁芜。
纵然地位如柯尔莫哥洛夫，他对遗传学的兴趣也遭到李森科的打压，倒是李森科下台后，柯尔莫哥洛夫还替他说过好话。

柯尔莫哥洛夫对掌握论的意见并没有阻挡掌握论成为苏联的主流学科。
这大概导致苏联在打算机科学以及多少作为打算机科学子学科的人工智能的后知后觉；这肯定也带偏了中国干系学科的发展。
掌握论在美国没有成为独立的学科，倒是打算机科学成为主导的学科，1960年代末开始，美国顶流学校纷纭设立打算机系。

掌握论的核心观点：反馈，不过是递归函数的一种最大略的分外情形，不敷以作为第一性事理。
柯尔莫哥洛夫在为匈牙利数学家罗莎·培特所著《递归函数论》俄译本所写的媒介中（莫绍揆师长西席1958年将此书依照俄文版译为中文，个中将“柯尔莫哥洛夫”译为“郭尔莫哥洛夫”，将“图灵”译为“杜令”）指出，一样平常递归函数和能行可打算性仍需从可布局性的角度进一步稽核——他对丘奇-图灵论题也有着深刻洞见（见Peter-1951）。

无论如何，柯尔莫哥洛夫的切入点是他喜好的领域：概率论。
1965年，他创办了学术季刊《信息传输问题》（Problems of Information Transmission），这份刊物很快成为苏联在打算理论最主要的阵地。
柯尔莫哥洛夫本人在创刊号上揭橥了 “信息的量化定义的三种办法”（Three Approaches to the Quantitative Definition of Information），从算法的角度研究了概率论和信息论。
信息论的核心是研究信息的含量。
喷鼻香农的信息量定义是熵。
柯尔莫哥洛夫把信息论的根本分成三种，第一是频率，第二是组合学，第三是算法。
柯尔莫哥洛夫对信息论和概率论的评价令人寻思：“信息论在逻辑上要先于概率论。
而不是往后者为根本。
”他认为组合学比频率更加坚实，但最令人信服的是算法。
一段信息所包含的信息量，可以用最短的天生这段信息的程序的长度来衡量（见Kolmogorov-1965）。
这便是现在所谓“柯尔莫哥洛夫繁芜性”（Kolmogorov Complexity），可定义如下：

KC(x) = min{ℓ(p) : U(p) = x}

即输出字符串x的最短程序p的长度。
柯尔莫哥洛夫这篇经典文章只有7页，而后面他写的几篇干系文章乃至更短。
这与所罗门诺夫细致但冗长的文章形成光鲜比拟。
苏联数学家的简洁是他们的一大特色，听说那是由于苏联期间纸张紧缺，但另一种说法是苏联数学家（尤其是大家）便是不太讲究细节，以至于结果的完全证明，须要他们的学生们补齐，有时乃至须要一代人。
柯尔莫哥洛夫的KAM（Kolmogorov–Arnold–Moser）理论便是后来由他的学生阿诺德（Vladimir Arnold）和德裔美国数学家Jürgen Moser等人完善的，而他关于希尔伯特第十三问题的研究，也是由阿诺德画上句号，这个主要的事情值得另写一篇长文。

可以证明柯尔莫哥洛夫繁芜性与程序的表示无关。
不同的程序表示，例如：C，Java，Python，或图灵机代码，导致的最短描述之间只差一个常量。
这个不变性定理有时也被称为“柯尔莫哥洛夫论题”（Kolmogorov Thesis）。
越来越多的证据表明柯尔莫哥洛夫繁芜性(如果能算出来的话)要比喷鼻香农熵更加靠谱，例如一个图的构造熵会由于图的表示不同而变革，而这个图的柯尔莫哥洛夫繁芜度该当是不变的。

柯尔莫哥洛夫后来把稳到所罗门诺夫的事情，他在1968年分别用俄文和英文揭橥的文章中引用了所罗门诺夫的事情，使得后者在苏联的名声比在西方更加响亮。
“柯尔莫哥洛夫繁芜性”也被称为“所罗门诺夫繁芜性”，或者“所罗门诺夫-柯尔莫哥洛夫-蔡廷繁芜性”，偶尔也被称为“描述繁芜性”，但打算繁芜性理论里有好几个东西都被称为“描述繁芜性”，为避免歧义，本文利用最常用的“柯尔莫哥洛夫繁芜性”的说法。
由于柯尔莫哥洛夫的影响，这门学科也被称为“算法概率论”，或“算法信息论”。

几位苏联学者，个中包括柯尔莫哥洛夫的学生，在伦敦大学皇家哈洛威学院（Royal Holloway）建立了机器学习研究中央。
在他们倡导下设立了柯尔莫哥洛夫奖章（Kolmogorov Medal，把稳：有别于俄国科学院颁发的柯尔莫哥洛夫奖，Kolmogorov Prize）。
所罗门诺夫是第一届柯尔莫哥洛夫奖章获奖人，最近一次（2018年）的获奖人因此发明支持向量机（Support Vector Machine）著称的苏联犹太裔统计学家弗拉基米尔·瓦普尼克（Vladimir Vapnik）。
所罗门诺夫也在伦敦大学皇家哈洛威学院兼职教授。

阿根廷出生的犹太裔美国理论打算机科学家蔡廷（Greg Chaitin, 1947年-），有着分歧凡响的发展经历。
他高中就读著名的纽约布朗克斯科学高中（Bronx High School of Science），这个学校贡献过9位诺贝尔奖，2位图灵奖。
他的第一篇文章在他18岁时揭橥于IEEE Transactions on Electronic Computers，是关于自动机时钟同步的，这是他高中时的作品，署名单位是哥伦比亚大学工程与运用学院，由于他高中时参加了哥大的名誉生项目。
他高中毕业后，入学纽约城市学院（CCNY）。
他在第一学期同时在看三本书：冯诺依曼和摩根士敦合著的《博弈论》，喷鼻香农和韦弗的《通讯的数学理论》，以及马丁·戴维斯编辑的《不可剖断》文集（个中收录了图灵1936年开天辟地的文章）。
他本科没有毕业就跟随父母回到阿根廷。

蔡廷在很小的时候就访问过IBM，于是研究逻辑和编程成为他的爱好。
他的编程能力使得他在布宜诺斯艾利斯的IBM分公司轻易地找到一份程序员的事情。
在此期间他研究哥德尔不完备性定理。
他第一篇关于最小程序长度的文章揭橥在《美国打算机学会会刊》（JACM），那时他才19岁，独立地把所罗门诺夫归纳法和柯尔莫哥洛夫信息量的思想又以新的办法重新发明了一遍。
审稿人已经知道柯尔莫哥洛夫的事情并奉告蔡廷，他不懂俄文，但还是在论文揭橥时以脚注形式承认了柯氏的事情。

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

蔡廷的出发点是贝里悖论（Berry Paradox）。
贝里悖论用英文说便是"The smallest positive integer not definable in under sixty letters"，用中文说是“不可能用少于十九个汉字命名的最小正整数”。
这是一种命名悖论。
由于贝里悖论和所用的措辞载体有关，蔡廷于是决定用函数式编程措辞LISP以避免稠浊。
所谓命名一个整数便是给出一个可以输出这个整数的程序。
蔡廷的命名便是柯尔莫哥洛夫的描述。
绝大多数整数最短的命名办法便是直接打印它们自身，而没有更短的程序表示它们，这些整数被蔡廷称为“无趣的”（uninteresting）、不可理解的（incomprehensible）、不可归约的（irreducible）以及随机的。
蔡廷事实上由此证明了柯尔莫哥洛夫繁芜度是不可打算的。
他当时称之为“不完备性”。

1974年蔡廷回到美国，在纽约州的IBM TJ Watson 研究中央事情，先是做访问学者，后来成为永久研究员。
故意思的是他刚回到美国后，就准备乘火车前往普林斯顿拜访他的上帝哥德尔。
于是1974年4月的某一天，他鼓足勇气给哥德尔打了个电话，见告哥德尔他利用贝里悖论也得出了不完备性定理的一个版本。

哥德尔说：“用什么悖论无所谓”（“It doesn’t make any difference which paradox you use!” ）。

蔡廷回答：“是的，但是我的证明指出了不完备性的信息论视角，我很想当面见告你。
”

哥德尔说：“好吧，先把论文寄给我，然后再给我打电话看能不能约上我的韶光。
”

蔡廷晚年兴趣转向生物学，出版过有趣的科普著作Proving Darwin（《证明达尔文》，见Chaitin-2012）。
一个人成名早的特点是他喜好用熟习的锤子去敲他遇见的所有钉子，所谓一招鲜吃遍天。
他不满生物学缺少理论根本，用算法信息论阐明进化论，并把这个方法称为“元生物学”（metabiology）。
一点也不惊奇，他的元生物学的核心思想可以从遗传算法和遗传编程中找到线索。

苏联数学家列文（Leonid Levin, 1948年-）1972年独立提出了NP完备性并证明了几个等价问题（见Levin-1973）。
这篇现在看来极为主要的文章只有两页纸，揭橥在柯尔莫哥洛夫创办的著名刊物Problems of Information Transmissions 1973年第3期上。
列文是柯尔莫哥洛夫的学生，但由于政治问题，他没有被付与博士学位。
1978年他移民美国，麻省理工学院很快给他补了一个博士，此后他的结果渐为人知。
他后来在波士顿大学教书直到退休。
2000年后的打算理论教科书都把原来的库克定理改为库克-列文（Cook-Levin）定理。
2012年他被付与高德纳奖（Knuth Prize）——与面向特定贡献的图灵奖和哥德尔奖不同，高德纳奖更加考虑对全体学科的影响，有点终生造诣奖的意思。
这算是对他缺失落图灵奖的补偿吧。

和他的老师一样，列文的文章也都很短，他1986年首创算法均匀繁芜性剖析的文章也只有两页（见Levin-1986）。
故意思的是，列文方向于认为P=NP，他肯定是少数派。

在Levin-1973中，列文给出了两个定理，定理1关于NP完备性，而定理2当时被忽略了。
定理1没有详细证明，而定理2乃至连解释都没有。
文章在列出定理2之后就结束了。
定理2实在和定理1的关系不大，或者至少关系并不明显。
列文给出了一个通用搜索过程（universal search），这个过程能够求解一个函数的逆，这正是麦卡锡1950年代提出的问题，而所罗门诺夫已经在这个问题上耗了20年。

当所罗门诺夫得知列文在苏联的遭遇后，联系了美国的几所学校和多逻辑学者，恳请他们帮助列文。
所罗门诺夫把他和列文的学术谈论写成报告（见Solomonoff-1984），为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中可打算的字符串，其逻辑深度大于多项式。
压缩首先考虑的是空间本钱，但解压有韶光本钱。

用大措辞模型的话来说，压缩韶光是演习韶光；柯尔莫哥洛夫繁芜度是大模型的参数量；逻辑深度对应于大模型的最短“推理”（inference）韶光。
顺便说，大模型术语中“推理”（inference）更得当的译法该当是“推断”，推断是统计意义上的，有别于逻辑意义的“推理”（reasoning）。
汉语里“推理”常常指后者。
况且，大模型中也有逻辑意义的“推理”，例如CoT（Chain of Thought），而机器定理证明的教科书里时常也不严格区分inference和reasoning。
人工智能的逻辑派和统计派，如果都是讲汉语的，估计就打不起来了。

理论打算机科学家李明等的一系列事情，为所罗门诺夫-柯尔莫哥洛夫-蔡廷繁芜性的研究做出主要贡献。
李明和维特涅（Paul Vitanyi）合著的《柯尔莫哥洛夫繁芜性及其运用》（Li-Vitanyi-2019）是这个领域的威信（definitive）参考书和教科书，也被誉为该领域的《圣经》，目前已经出到第4版。
早期版本有中译本《描述繁芜性》（科学出版社，1998），但“描述繁芜性”这个译法随意马虎和打算繁芜性里各种被称为 Descriptive Complexity的东西稠浊，本文中我们还是利用全名所罗门诺夫-柯尔莫哥洛夫-蔡廷繁芜性或柯尔莫哥洛夫繁芜性。

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

Marcus Hutter 1996年从慕尼黑大学博士毕业，他的博士论文是理论物理。
但他博士毕业后转向通用人工智能。
2000年他提出用强化学习作为根本的AGI的理论框架，AIXI，他的紧张数学工具便是所罗门诺夫归纳法(见Hutter-2005)。

OpenAI的 ChatGPT的成功，使得大家一贯在关注它的基本事情事理。
很多人把它的成功归于底层神经网络架构Transformer。
但事实上，Transformer的发明者Google在措辞大模型上反而掉队于OpenAI。
一种可能的阐明是Google利用的框架是BERT，这是当时所有大模型团队采取的框架；而OpenAI采取了GPT。
其紧张差异是：GPT是next token prediction，也即所罗门诺夫归纳；而BERT可以用类似的措辞描述为：给定序列（x1, x2, …, xn），从中抽走xi 让你猜xi是什么。
虽然没有数学证明，但我们直觉上可以预测单向的GPT该当比双向的BERT效率更高。
这作为一个开放问题留给读者。
所罗门诺夫归纳为我们供应了BERT不可能比GPT更强的证据。

目前的大模型研究中，理论暂时掉队于工程实践。
过去的打算机科学和工程的研究履历中，一样平常benchmark都是领先于工程的，但对大模型的评价，明显掉队于大模型的开拓。
ChatGPT成功后，OpenAI首席科学家伊利亚·苏茨凯弗（Ilya Sutskever）在接管采访时不断暗示next token prediction是GPT系列大模型成功的关键，但直到2023年8月他在伯克利理论打算机科学研究所（Simons Institute，另一个由数学家出身的金融家赛蒙斯捐助的根本科学机构）演讲时，才明确透露GPT的数学依据便是所罗门诺夫归纳法（见Sutskever-2023）。
他声称他自己在2016年独立想出来——这也轻微晚了点，我们自然没法强制他进行零知识证明。

按照所罗门诺夫-柯尔莫哥洛夫-蔡廷理论，所有的学习都可被看作是压缩。
形象地考虑，用精简的系统概括大量数据的过程，或者从殊相到共相的过程，自然是压缩，由于共相的表示要比诸多殊相的表示经济得多。
Hutter在2006年设立过Hutter Prize以褒奖最好的无损压缩（即压缩比最高的）事情。
Hutter现已加入DeepMind，他作为互助者的文章“Language Modeling is Compression”(见Deletang-2023)曾在工程师群体中引起过热烈谈论。
实验表明，用大措辞模型做无损压缩，效果要远远好于基于哈夫曼编码（Huffman coding）的各种压缩算法的变种（Li-2024）。
大措辞模型对token的概率预测肯定好于一样平常的压缩算法。
柯尔莫哥洛夫和蔡廷最早的出发点是信息表达和信息传输，实在也是压缩。
殊途同归。

所罗门诺夫归纳法的科普版或者哲学版（philosophical formulation）可描述如下：

1. 不雅观察结果以数据办法输入.

2. 形成新假设以阐明目前所有的数据. 假设便是图灵机。

3. 新的数据输入，检测数据是否证明假设。

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

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

我们可以用所罗门诺夫归纳法来阐明卡尔·波普尔（Karl Popper，1902-1994）的证伪理论。
历史地看，波普尔的思想也与美国哲学家卡尔纳普有关，只不过波普尔的意图是通过攻击卡尔纳普的概率论，以建立一个用新词“可证伪性”来命名的哲学路线。
事实上，“可错性”（fallibility）早就被皮尔士更深刻地谈论过。
所罗门诺夫归纳法既然可以阐明皮尔士的实用主义，当然可以轻松地概括波普尔的所有理论，并且也可以阐明波普尔难以认可的东西，例如进化论。
所谓证伪，任何有智力的人都能想的到：说一个东西不对总要比说一个东西对随意马虎得多。
统计学家乔治·博克斯（George Box）有言：“所有模型都是错的，但有些模型是有用的”（all models are wrong，but some are useful），所谓“有用”便是可以用来预测。
我们由此可看出哲学家与科学家或数学家处理问题的不同态度，前者更关心造新词儿，而后者更关心知识的进步。

库恩的科学革命理论也可以作为所罗门诺夫归纳法的特例。
奥卡姆的剃刀，在被提出之后的很永劫光里并没有严格定义，只是直觉上认为在阐明力附近的条件下，模型越小越好。
在所罗门诺夫-柯尔莫哥洛夫-蔡廷理论里，覆盖所有数据的最小的模型，便是最短的程序或者最小的图灵机。
在一定偏差内，可以有多个差不多大小的图灵机，即，可以有多个阐明，即伊比鸠鲁的无差别原则（principle of indifference）。
当然，在实际中，我们只能探求在一定偏差范围内较小的图灵机。
当我们找到的模型/程序/图灵机和以前的模型/程序/图灵机差别较大时，我们就称之为科学革命。
一样平常来讲，科学革命之后的新模型/图灵机大概率要比革命前的更长（即柯尔莫哥洛夫繁芜度更大），并且大概率其逻辑深度也要更深。
一个新的模型/程序/图灵机便是新的范式。

亚里士多德《玄学》开篇就说“求知是人的本性”（All men by nature desire to know）。
亚里士多德论述了人从履历到技能再到科学的过程便是“to know”的过程。
所谓“不可打算”或“一直机”大概是上帝留给人类的希望。
在所罗门诺夫的框架里，知识的进步便是“递促进修”（incremental learning）。
进一步研究所罗门诺夫归纳法和柯尔莫哥洛夫繁芜性会为机器学习供应新的理论根本。
现在看，遗传算法、遗传编程、强化学习都可以在所罗门诺夫归纳法的框架内得到打算理论的阐明。

我们可以讨巧地借用亚里士多德：“压缩是人的本性”（All men by nature desire to compress）。
休谟认为归纳虽然是不能用来证明(verification)，但却是人性之本（essential to human nature）。
我们可以有一个替代的说法：压缩是人性之本。
履历得自于觉得，履历数据被建模是经济的考虑，建模便是压缩，压缩是由图灵机完成的。
正是在这个意义上，所罗门诺夫归纳法可被当作第一性事理。
进化过程乃至也可以被看作是压缩，所谓“适者生存”（survival of the fittest），也可被狭义地转述成“最压者生存”（survival of who compress the most）。
压缩即物理天下规律在信息天下的表示。
笛卡尔的格言“我思故我在”可以被更严格地表达为“我压故我在”。
（I compress, therefore, I am.）

回顾了所罗门诺夫-柯尔莫哥洛夫-蔡廷理论的发展过程，再来看大措辞模型，我们会以为大概不是理论掉队于实践，而是太超前了。

参考文献：（高下滑动可浏览）

1.Bennett, Charles H. (1988), "Logical Depth and Physical Complexity", in Herken, Rolf (ed.), The Universal Turing Machine: a Half-Century Survey, Oxford U. Press, pp. 227–25

2.Calude C.S. (2007), (ed.) Randomness and Complexity, from Leibniz to Chaitin

3.Carnap, R. (1950), Logical Foundations of Probability.

4.Chaitin. G. J. (1965), “An improvement on a theorem by E. F. Moore”, IEEE Transactions on Electronic Computers, EC-14, 466–467.

5.Chaitin, G. J. (1966), “On the Length of Programs for Computing Finite Binary Sequences”, Journal of the Assoc. of Comp. Mach., 13, pp. 547–569.

6.Chaitin, G. J. (1969), “On the Length of Programs for Computing Finite Binary Sequences: Statistical Considerations,” Journal of the Assoc. of Comp. Mach., 16, pp. 145–159.

7.Chaitin, G. J. (2012), Proving Darwin: Making Biology Mathematical （证明达尔文，公民邮电出版社，2015）

8.Chaitin, G. J. (2023), Building the World from Information & Computation, Expanded 2nd ed.

9.Chomsky, A.N. “Three Models for the Description of Language,” IRE Transactions on Information Theory, Vol. IT–2, No. 3, Sept. 1956

10.Deletang, G. et al (2023), “Language Modeling is Compression”, arXiv

11.Gleick, J. (2011), The Information: A History, a Theory, a Flood.

12.Hutter, M. (2005), Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, Springer-Verlag, Berlin.

13.James, William (1907), Pragmatism: A New Name for Some Old Ways of Thinking

14.Kolmogorov, A.N. (1965), “Three Approaches to the Quantitative Definition of Information”, Problems of Information Transmission, 1 (1): 1–7.

15.Kolmogorov, A.N. (1968), “Logical Basis for Information Theory and Probability Theory”, IEEE Trans. on Information Theory, IT–14(5): 662– 664.

16.Kolmogorov, A.N. (1969), “On the Logical Foundations of Information Theory and Probability Theory”, Problems of Information Transmission, 5:1-4.

17.Kolmogorov, A.N. (1988), How I became a mathematician, (姚芳等编译，我是怎么成为数学家的，大连理工大学出版社，2023)

18.Levin, L. (1973), “Universal search problems”, Problems of Information Transmission, 9 (3): 115–116

19.Levin, L. (1986), “Average case complete problems”, SIAM Journal on Computing, 15 (1), pp. 285–286

20.Li, M. and Vitanyi, P. (2019), An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, N.Y., 1st ed. 1993, 3rd ed. 2008, 4th ed. 2019.

21.Li, M., et al (2023), “A Theory of Human-like Few-shot Learning”, work in progress.

22.Li, M. (2024), “Approximating Human-Like Few-shot Learning with GPT-based Compression”, preprint

23.McCarthy, J. (1956), The Inversion of Functions Defined by Turing Machines, in McCarthy and Shannon ed. Automata Studies.

24.Minsky, M.L. (1961), “Steps Toward Artificial Intelligence,” Proceedings of the IRE, 49:8–30, 1961. reprinted in Feigenbaum, E.A. and Feldman, J. ed. Computers and Thought, 1963

25.Peirce, C.S. (1877), “The Fixation of Belief”, in Philosophical Writings of Peirce,1955

26.Peter, Rozsa (1951), Rekursive Funktionen, Budapest, 递归函数论, 莫绍揆译, 科学出版社, 1958.

27.Shannon, C.E. (1948), “The Mathematical Theory of Communication,” Bell System Technical Journal, 27:379–423, 623–656.

28.Solomonoff, R.J. (1956), “An Inductive Inference Machine,” Report circulated at the Dartmouth Summer Workshop on Artificial Intelligence, August 1956

29.Solomonoff, R.J. (1957), “An Inductive Inference Machine,” IRE Convention Record, Section on Information Theory.

30.Solomonoff, R.J. (1960), “A Preliminary Report on a General Theory of Inductive Inference,” (Revision of Report V–131), Contract AF 49(639)– 376, Report ZTB–138, Zator Co., Cambridge, Mass., Nov, 1960.

31.Solomonoff, R.J. (1964), “A Formal Theory of Inductive Inference,” Information and Control, Part I: Vol 7, No. 1, pp. 1–22, March.

32.Solomonoff, R.J. (1964), “A Formal Theory of Inductive Inference,” Information and Control, Part II: Vol 7, No. 2, pp. 224–254, June.

33.Solomonoff, R.J. (1978), “Complexity–based induction systems: Comparisons and convergence theorems”, IEEE Trans. on Information Theory, IT–24(4):422–432.

34.Solomonoff, R.J. (1984), “Optimum Sequential Search”, Oxbridge Research Report, revised 1985

35.Solomonoff, R.J. (1997), “The Discovery of Algorithmic Probability”, J. Computer and System Sciences, 55, 73-88.

36.Solomonoff, R.J. (2010), “Algorithmic Probability, Heuristic Programming and AGI”, Proceedings of the 3d Conference on Artificial General Intelligence

37.Solomonoff, R.J. (2011), “Algorithmic Probability -- Its Discovery -- Its Properties and Application to Strong AI”, in Hector Zenil (ed.), Randomness Through Computation: Some Answers, More Questions, Chapter 11, pp. 149-157

38.Sutskever, Ilya (2023), “An Observation on Generalization”, Talk at Simons Institute Aug 14, 2023

39.Veldhuizen, Todd L. (2005), “Software Libraries and Their Reuse: Entropy, Kolmogorov Complexity, and Zipf’s Law”，arxiv

40.Vitanyi, P. (1988), “A Short Biography of A.N. Kolmogorov”, CWI Quarterly, (homepages.cwi.nl/~paulv/KOLMOGOROV.BIOGRAPHY.html)

41.Vitanyi, P. (2009), “Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory” (homepages.cwi.nl/~paulv/obituary.html)

42.Wuppuluri, S. and Doria, F.A., (ed) (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific Publishing Company

43.尼克 (2021), 人工智能简史, 第2版.

44.尼克 (2024), 理解图灵.（即将出版）

来源：赛师长西席

编辑：蓝多多

转载内容仅代表作者不雅观点

不代表中科院物理所态度

如需转载请联系原公众年夜众号