什麼是 Kolmogorov 複雜度？為什麼它是理解 AI 的鑰匙

---

一本 500 頁的數學教科書，為什麼進了清單？

大約在 2020 年，OpenAI 共同創辦人蘇茨克維（Ilya Sutskever）給了 id Software 共同創辦人、傳奇程式設計師約翰·卡麥克（John Carmack）一份閱讀清單。總共 27 項，涵蓋論文、部落格文章、課程和書籍章節。他對卡麥克說：「如果你真的把這些都學會，你就掌握了今天 AI 領域 90% 的重要知識。」這份清單後來在網路上廣為流傳，被稱為「Ilya 的 30u30 清單」。

27 項當中，多數是十頁左右的經典論文，例如〈Attention Is All You Need〉或 ResNet。但有一個例外格外醒目：Shen、Uspensky 和 Vereshchagin 合著的《Kolmogorov Complexity and Algorithmic Randomness》，一本超過 500 頁的純數學教科書。這本書不教你寫程式碼，不教你訓練模型，甚至不提神經網路。它從頭到尾只談一件事：什麼叫做「用最短的程式描述一段資料」。

蘇茨克維把這本書放進清單，等於告訴你他怎麼理解 AI。他不是從工程角度出發，不是從「哪個架構跑得快」開始，而是從一個更根本的問題開始：智慧到底是什麼？他的答案，或者說他花了整個職業生涯在驗證的假說，可以濃縮成一句話：壓縮就是理解。而 Kolmogorov 複雜度，正是這個信念的數學表述。

清單裡還有另一項與此直接相關的讀物：Peter Grunwald 寫的〈A Tutorial Introduction to the Minimum Description Length Principle〉。如果 Kolmogorov 複雜度是純粹的數學理論，那 MDL（最小描述長度）原則就是把這個理論拉進統計學和機器學習的那座橋。這兩項加在一起，構成了整份清單的理論地基。

用最短的程式說完一切

Kolmogorov 複雜度的想法，可以用一個很直覺的問題來理解：給你一段資料，你能寫出多短的程式來完整重現它？

假設有一段文字，是一億個 0 排成一列。你不需要真的存這一億個 0，只要寫一行程式：「印出一億個 0」。這行程式非常短，代表這段資料的 Kolmogorov 複雜度很低。換句話說，它其實沒什麼「資訊量」，因為背後的規律太簡單了。

再想像另一段文字，是圓周率小數點後一億位全部印出來。你也不需要存這一億個數字，因為有已知的演算法可以計算圓周率到任意位數。所以這段資料的 Kolmogorov 複雜度也不會太高。雖然它看起來雜亂無章，但背後有一個簡潔的生成規則。

現在想像第三種情況：一段真正隨機產生的數字序列，每個數字都是擲骰子決定的，彼此之間沒有任何規律。這段資料沒辦法壓縮，你能寫出的最短程式就是把整段資料原封不動地塞進去。它的 Kolmogorov 複雜度幾乎等於它本身的長度。

三個例子說的是同一件事：壓縮能力等於理解能力。如果你能把一段資料壓得很小，代表你找到了資料背後的規律和結構。如果你壓不下去，要嘛是這段資料真的是隨機的，要嘛就是你還沒找到規律。

不過，Kolmogorov 複雜度有一個根本的限制：它是不可計算的（uncomputable）。沒有任何演算法能保證找到「最短的程式」，這個事實已經被嚴格證明，和圖靈的停機問題直接相關。你永遠無法確定自己找到的壓縮方式是不是最好的，總有可能存在更短的程式。但這不妨礙它作為理論框架的價值。就像物理學中的理想氣體方程式，沒有人期望它精確描述現實，但它提供了正確的思考方式。

MDL：從不可計算到可以動手做

如果 Kolmogorov 複雜度是一座燈塔，指出了「理解就是壓縮」的方向，那 Peter Grunwald 的 MDL（Minimum Description Length，最小描述長度）原則就是通往燈塔的那條路。

MDL 的主張很簡單：在所有能解釋你手上資料的統計模型中，最好的那個，就是能用最少的位元（bits）來描述「模型本身加上資料」的那個。注意，不只是資料壓得多小，而是模型加上資料的總長度。為什麼要把模型的成本也算進去？因為一個超級複雜的模型雖然能完美「解釋」資料，但如果模型本身就大得離譜，那你其實什麼都沒壓縮到。

舉個例子。假設你有一組散布在二維平面上的資料點，你想找一條曲線來擬合它們。一條直線很簡單，只需要兩個參數（斜率和截距），但它可能沒辦法很好地通過所有的點，剩餘的「殘差」很大。一個 100 次多項式可以完美通過每一個點，殘差為零，但你需要 101 個參數來描述這條曲線。

MDL 告訴你，要同時考慮兩邊的成本：描述模型需要多少位元，加上描述殘差需要多少位元。總和最小的那個，就是最好的模型。

這個框架直接回答了機器學習中一個老問題：過度擬合（overfitting）到底是怎麼回事？用 MDL 的語言來說，過度擬合就是你的模型比資料還長。你花了太多位元去描述一個極其複雜的模型，這些多出來的複雜度並沒有幫你更好地理解資料，只是在死記硬背雜訊。那個 100 次多項式看似完美擬合了每個資料點，但它只是把雜訊也一起記住了，拿去預測新資料就會一塌糊塗。

Grunwald 的教程之所以出現在蘇茨克維的清單裡，是因為它做了一件關鍵的事：把 Kolmogorov 複雜度那套「不可計算」的純理論，轉譯成統計學家和機器學習研究者可以實際操作的方法論。MDL 不需要找到「絕對最短的程式」（那是不可能的），它只需要在你定義的模型家族內，找到總描述長度最短的那個。壓縮理論因此從哲學命題變成了工程工具。

預測下一個 token，就是在壓縮

搞懂了 Kolmogorov 複雜度和 MDL，蘇茨克維為什麼把這兩項放進清單就很清楚了。因為大型語言模型做的事情，說到底就是壓縮。

一個語言模型在訓練時，任務是預測下一個 token。給它一段文字的前半部，它要猜後面會出現什麼字。「預測」和「壓縮」之間有嚴格的數學等價關係：如果一個模型能完美預測下一個 token，它就等於完美壓縮了整段文字，因為你不需要額外的位元來編碼任何「意料之外」的部分。反過來說，模型預測得越差，你需要越多額外的位元來記錄它猜錯的地方，壓縮效果就越差。

蘇茨克維在 2023 年 NVIDIA GTC 大會上，與 NVIDIA 創辦人暨執行長黃仁勳（Jensen Huang）的對談中，把這個邏輯講得非常清楚。他的論點是：要真正壓縮好網路上的文字資料，神經網路必須學到產生這些文字的底層過程。它不只是在記住字詞的排列順序，而是在建構某種「世界模型」。因為文字是人類寫的，人類寫文字是基於對現實世界的理解，所以要預測人類會寫出什麼字，你最終必須理解人類理解的那個世界。

在同年柏克萊大學 Simons Institute 的演講中，他把這個想法說得更直接：「壓縮和預測之間存在一對一的對應關係。」這不是比喻。在資訊理論中，這可以嚴格證明，根源可以追溯到資訊理論之父夏農（Claude Shannon）的奠基工作。一個好的壓縮器就是一個好的預測器，反之亦然。

所以，當我們訓練一個有數千億參數的語言模型去預測 token 時，我們其實是在訓練一台巨大的壓縮機。它學到的「知識」，就是它用來壓縮資料的那些規律。它有多「聰明」，等同於它壓縮資料的能力有多強。2024 年一篇研究論文〈Compression Represents Intelligence Linearly〉甚至發現，語言模型在各種基準測試上的分數，和它們壓縮外部文本語料庫的能力幾乎成正比。壓得越小，考得越好。

這塊地基撐起了整份清單

回到蘇茨克維的閱讀清單，現在可以用 Kolmogorov 複雜度的視角重新審視其他項目。

清單中的第 6 項，深度學習先驅辛頓（Geoffrey Hinton）的〈Keeping Neural Networks Simple by Minimizing the Description Length of the Weights〉，標題本身就是 MDL 原則在神經網路上的直接應用：讓權重的描述長度最小化，就是讓網路保持簡潔。第 18 項 Variational Lossy Autoencoder 研究的是有損壓縮，探討在允許一定資訊損失的情況下，如何找到最有效率的表示方式。第 23 項 Scaling Laws，描述的是模型規模與預測能力的關係。而預測能力等於壓縮能力，所以 Scaling Laws 描述的其實是壓縮能力如何隨規模增長。

甚至連看似無關的項目，都可以從壓縮的角度理解。Transformer 架構（第 14 項）之所以強大，是因為注意力機制讓模型能高效地捕捉長距離的依賴關係，從而更好地壓縮序列資料。ResNet（第 11 項）的殘差連接讓深層網路更容易訓練，等於讓更深的壓縮器變得可行。

蘇茨克維把 Kolmogorov 複雜度和 MDL 放進清單，不是因為研究者需要在日常工作中計算 Kolmogorov 複雜度。他給的是一個統一的思考框架：AI 在做什麼？它在壓縮。什麼是好的 AI？壓縮效率最高的那個。什麼是理解？找到最短的描述。什麼是過度擬合？描述比資料還長。什麼是泛化？壓縮規律可以套用到新資料上。

這就是為什麼這兩項是地基。你帶著這個框架去讀清單裡的其他 25 項，每一項都會變得更清晰。蘇茨克維推薦的不只是一本書和一篇教程，而是一副看 AI 的眼鏡。戴上它，你會開始用不同的方式理解語言模型在做什麼。它們不是在「學會說人話」，它們是在學會壓縮人類世界。壓縮得越好，理解得越深。

---

← 上一篇：那份消失的 Email → 下一篇：複雜性從哪裡來，又往哪裡去 📋 回到系列目錄：那份消失的 Email