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), 了解圖靈.（即将出版）
來源：賽先生
編輯：藍多多
轉載内容僅代表作者觀點
不代表中科院實體所立場
如需轉載請聯系原公衆号
近期熱門文章Top10
↓ 點選标題即可檢視 ↓
1.為什麼陰幹的衣服那麼臭？原因竟然是……
2.手榴彈的保險拔了到底還能不能插回去？（400期福利）| No.400
3.青蛙身上長蘑菇，“最後生還蛙”還能活多久？
4.人為什麼會有5根手指？5很特殊嗎？
5.“詩仙”李白沒眼花，原來真的會“生紫煙”！
6.為什麼内急時尿液在空中的時候呈流柱狀而不是噴霧狀呢？| No.401
7.鬧鐘響了要不要立刻起床？
8.回家忘帶充電器，可以使用非原裝充電器充電嗎？安全嗎？
9.大地磁暴結束，它影響我們正常上班嗎？
10.為了慶祝π day，我們給π 介紹了一個對象？|happy π day
點此檢視以往全部熱門文章