從熵到Epiplexity：重新思考計算受限智能的信息

From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence

從熵到Epiplexity：重新思考計算受限智能的信息

https://arxiv.org/pdf/2601.03220

摘要
我們能否從數(shù)據(jù)中學(xué)到比其生成過程中原本包含的更多信息？僅通過對現(xiàn)有數(shù)據(jù)施加確定性變換，能否構(gòu)造出新穎且有用的信息？在不考慮下游任務(wù)的情況下，我們能否評估數(shù)據(jù)中可學(xué)習(xí)的內(nèi)容？在這些問題上，香農(nóng)信息論和柯爾莫哥洛夫復(fù)雜度幾乎束手無策，部分原因在于它們假設(shè)觀察者具有無限的計算能力，且未能聚焦于“有用的信息”內(nèi)容。

在本研究中，我們識別并舉例說明了信息論中的三個看似悖論的現(xiàn)象：
（1）確定性變換無法增加信息；
（2）信息與數(shù)據(jù)的順序無關(guān)；
（3）似然建模僅僅是分布匹配。

為闡明這些理論結(jié)果與現(xiàn)代機器學(xué)習(xí)實踐之間的張力，并量化數(shù)據(jù)的價值，我們提出了“epiplexity”（表征復(fù)雜度）——一種針對計算能力受限的觀察者所能從數(shù)據(jù)中學(xué)到的信息的形式化度量。Epiplexity 捕捉數(shù)據(jù)中的結(jié)構(gòu)性內(nèi)容，同時排除“時間受限熵”（time-bounded entropy），即由偽隨機數(shù)生成器和混沌動力系統(tǒng)所體現(xiàn)的、不可預(yù)測的隨機內(nèi)容。

借助這些概念，我們展示了：

• 信息如何通過計算被創(chuàng)造出來；
• 信息如何依賴于數(shù)據(jù)的順序；
• 似然建模如何能夠生成比原始數(shù)據(jù)生成過程中更復(fù)雜的程序。

我們還提出了若干實用的 epiplexity 估計方法，實驗證明這些方法能夠：

• 捕捉不同數(shù)據(jù)源之間的差異；
• 與下游任務(wù)性能相關(guān)聯(lián)；
• 揭示那些能提升分布外泛化能力的數(shù)據(jù)集干預(yù)措施。

與模型選擇原則不同，epiplexity 為數(shù)據(jù)選擇提供了理論基礎(chǔ)，指導(dǎo)我們?nèi)绾螢閷W(xué)習(xí)系統(tǒng)選擇、生成或變換數(shù)據(jù)。

1 引言

隨著人工智能研究朝著更通用的智能系統(tǒng)方向發(fā)展，現(xiàn)有用于奠定數(shù)學(xué)直覺基礎(chǔ)的機制開始顯現(xiàn)出裂痕。大量學(xué)習(xí)理論圍繞著控制模型在給定分布下的泛化誤差而構(gòu)建，將訓(xùn)練分布視為固定不變，并將優(yōu)化努力集中在模型的選擇上。然而，現(xiàn)代系統(tǒng)通常需要在訓(xùn)練時未指定的任務(wù)、領(lǐng)域和目標(biāo)之間進行遷移，往往是在大規(guī)模、多樣化且異構(gòu)的數(shù)據(jù)上進行預(yù)訓(xùn)練之后實現(xiàn)的。在這一范式下，成功或失敗往往較少取決于架構(gòu)選擇，而更多取決于模型最初接觸的是哪些數(shù)據(jù)。

追求對分布外任務(wù)的廣泛泛化，迫使我們轉(zhuǎn)變視角：不再將數(shù)據(jù)視為給定的、僅優(yōu)化模型以提升分布內(nèi)性能，而是需要主動選擇和整理數(shù)據(jù)，以促進對未見任務(wù)的泛化能力。這一轉(zhuǎn)變使得“數(shù)據(jù)本身的價值”成為一個核心問題——模型能從訓(xùn)練中獲得多少可用且可遷移的信息？換言之，與其關(guān)注模型選擇，我們應(yīng)如何進行數(shù)據(jù)選擇？對于這一問題，現(xiàn)有理論幾乎未提供指導(dǎo)，甚至常常與經(jīng)驗觀察結(jié)果天真地相矛盾。

請考慮合成數(shù)據(jù)——當(dāng)現(xiàn)有自然數(shù)據(jù)已被耗盡時，合成數(shù)據(jù)對于進一步提升模型能力至關(guān)重要（Abdin 等，2024；Maini 等，2024）。然而，信息論中的既有概念（如數(shù)據(jù)處理不等式）似乎暗示：合成數(shù)據(jù)并未帶來任何額外價值。關(guān)于“某一模型究竟從數(shù)據(jù)中獲得了何種信息”這類問題，表面上理應(yīng)屬于信息論的研究范疇，但使用現(xiàn)有工具對其進行量化卻出人意料地困難。甚至一些基本問題——例如 AlphaZero 博弈模型權(quán)重中所包含的信息來源（Silver 等，2018）——都令人意外地難以回答。AlphaZero 完全不使用任何人類數(shù)據(jù)，僅從游戲的確定性規(guī)則和 AlphaZero 強化學(xué)習(xí)算法中學(xué)習(xí)，而這兩者本身都很容易描述。然而，由此訓(xùn)練出的模型不僅規(guī)模龐大，而且達(dá)到了超越人類的性能水平。若據(jù)此斷言 AlphaZero 在這一過程中幾乎沒有學(xué)到任何信息，顯然嚴(yán)重偏離了事實；然而，香農(nóng)信息論和算法信息論似乎恰恰得出了這樣的結(jié)論。

在本文中，我們主張：“計算能力受限的觀察者能夠從數(shù)據(jù)集中提取的結(jié)構(gòu)性信息量”是一個根本性概念，它構(gòu)成了許多經(jīng)驗現(xiàn)象的基礎(chǔ)。正如我們將要展示的，當(dāng)試圖量化此類信息時，香農(nóng)信息論和算法信息論的既有概念是不足的。這些理論框架常常為某些直覺或數(shù)學(xué)信念提供支持，而這些信念實際上掩蓋了經(jīng)驗現(xiàn)象中的關(guān)鍵方面。為凸顯經(jīng)典框架的局限性，并闡明計算約束在信息量化中的核心作用，我們識別并展示了三個看似悖論的現(xiàn)象：這些陳述在香農(nóng)信息論和算法信息論中均可獲得數(shù)學(xué)上的正當(dāng)性，卻與我們的直覺及實際觀察到的經(jīng)驗現(xiàn)象相沖突。

悖論 1：信息無法通過確定性過程增加。
對于香農(nóng)熵和柯爾莫哥洛夫復(fù)雜度而言，確定性變換都無法有意義地增加一個對象的信息內(nèi)容。然而，我們卻使用偽隨機數(shù)生成器來制造隨機性，合成數(shù)據(jù)能夠提升模型能力，數(shù)學(xué)家可以從公理出發(fā)、不依賴外部信息推導(dǎo)出新知識，動力系統(tǒng)會產(chǎn)生涌現(xiàn)現(xiàn)象，而像 AlphaZero 這樣的自我對弈循環(huán)也能從游戲中學(xué)習(xí)到復(fù)雜的策略（Silver 等，2018）。

悖論 2：信息與因式分解順序無關(guān)。
香農(nóng)熵和柯爾莫哥洛夫復(fù)雜度的一個共同性質(zhì)是，總信息含量在因式分解順序上保持不變：先觀察 X 再觀察 Y 所獲得的信息，與先觀察 Y 再觀察 X 是相同的。另一方面，大語言模型（LLMs）在左至右排列的英文文本上學(xué)習(xí)效果更好，而非逆序文本，這揭示了一種“時間之箭”（Papadopoulos 等，2024；Bengio 等，2019）；同時，密碼學(xué)正是建立在某些函數(shù)在一個方向上計算困難、而在另一方向上容易預(yù)測的基礎(chǔ)之上。

悖論 3：似然建模僅僅是分布匹配。
最大化似然常被等同于匹配訓(xùn)練數(shù)據(jù)的生成過程：真實的數(shù)據(jù)生成過程本身就是自身最完美的模型，任何模型都不可能達(dá)到更高的期望似然值。因此，人們通常假設(shè)，在某數(shù)據(jù)集上訓(xùn)練的模型無法提取比數(shù)據(jù)生成過程本身更多的結(jié)構(gòu)或?qū)W習(xí)未用于生成數(shù)據(jù)的有用特征。然而，我們證明，一個計算能力受限的觀察者實際上能夠發(fā)現(xiàn)比數(shù)據(jù)生成過程中所包含的更多結(jié)構(gòu)。例如，在康威的生命游戲中，數(shù)據(jù)由作用于二維比特數(shù)組的簡單程序規(guī)則依次生成。應(yīng)用這些簡單規(guī)則后，我們看到涌現(xiàn)出的結(jié)構(gòu)——如不同種類的物體以可預(yù)測的方式移動和交互。雖然一個無限制的觀察者可以精確模擬環(huán)境的演化，但一個計算能力受限的觀察者則會利用這些涌現(xiàn)結(jié)構(gòu)，學(xué)習(xí)不同類型物體及其行為模式。

這些理論陳述與經(jīng)驗現(xiàn)象之間的張力，可以通過對觀察者施加計算約束，并將隨機內(nèi)容與結(jié)構(gòu)性內(nèi)容區(qū)分開來加以解決。借鑒密碼學(xué)、算法信息論以及上述尚未解釋的經(jīng)驗現(xiàn)象的思想，我們定義了一種新的信息度量——epiplexity（認(rèn)識復(fù)雜度），它形式化地定義了計算能力受限的觀察者能從數(shù)據(jù)中提取的結(jié)構(gòu)性信息量（第 3 節(jié)，定義 8）。簡言之，epiplexity 是在計算約束下使數(shù)據(jù)描述長度最小化的模型中所包含的信息。一種簡單的啟發(fā)式度量方法是損失曲線上最終損失以上的面積，而更嚴(yán)謹(jǐn)?shù)姆椒▌t是教師模型與學(xué)生模型之間的累積 KL 散度（第 4 節(jié)，圖 2）。

我們的定義捕捉到這樣一個直覺：一個對象既包含隨機、本質(zhì)上不可預(yù)測的信息（熵），也包含可預(yù)測的結(jié)構(gòu)化信息——這種結(jié)構(gòu)化信息使觀察者能夠通過識別模式實現(xiàn)泛化（epiplexity）。在圖 1（左）中，我們展示了這種區(qū)分。在頂部一行，我們展示高度冗余且重復(fù)的代碼與簡單的顏色漸變，它們無論結(jié)構(gòu)還是隨機性方面都幾乎不含信息內(nèi)容。在中間一行，我們展示某個算法的內(nèi)部機制及動物圖片，它們呈現(xiàn)出元素間復(fù)雜的長程相互依賴關(guān)系，模型可從中學(xué)習(xí)復(fù)雜的特征和子電路，即使對不同任務(wù)也有幫助。相比之下，在底部一行，我們展示的是幾乎沒有結(jié)構(gòu)的隨機數(shù)據(jù)：隨機生成的 API 密鑰、文件路徑、哈希值、任意布爾標(biāo)志等，其可學(xué)習(xí)內(nèi)容微乎其微，不存在長程依賴或復(fù)雜電路結(jié)構(gòu)，因而在此類數(shù)據(jù)上訓(xùn)練無法產(chǎn)生任何復(fù)雜特征或電路。同樣，從動物圖片中均勻打亂像素所得的數(shù)據(jù)具有高熵，但本質(zhì)上不可預(yù)測，訓(xùn)練此類數(shù)據(jù)也不會產(chǎn)生任何復(fù)雜特征或電路。

我們這一框架的一個核心特性是：信息是依賴于觀察者的——同一個對象，根據(jù)觀察者所擁有的計算資源不同，可能表現(xiàn)為隨機的或結(jié)構(gòu)化的。例如，一個強偽隨機生成器的輸出，對于任何缺乏密鑰（種子）的多項式時間觀察者而言，無論其算法或函數(shù)類別如何，都與真正的隨機性無法區(qū)分。在其他情境中，如混沌動力系統(tǒng)，既會產(chǎn)生看似隨機的行為，也同時包含結(jié)構(gòu)：系統(tǒng)的狀態(tài)在長時間尺度上無法被精確預(yù)測，但這類觀察者仍可學(xué)習(xí)到有意義的預(yù)測分布，正如圖1（右上角）所示的不變測度所體現(xiàn)的那樣。

用于表示這些分布的模型本質(zhì)上是計算機程序，而這些程序中的子結(jié)構(gòu)——比如用于執(zhí)行特定任務(wù)的電路，或“歸納頭”（Olsson 等，2022）——即使面對看似無關(guān)的數(shù)據(jù)，也可被復(fù)用。這種觀點促使我們選擇高 epiplexity 的數(shù)據(jù)，因為這類數(shù)據(jù)能在模型中誘導(dǎo)出更多結(jié)構(gòu)性信息，而這些結(jié)構(gòu)隨后可用于未見過的分布外（OOD）任務(wù)，如圖1（右下角）所示。然而，我們強調(diào)，epiplexity 是一種信息度量，并不保證模型在特定 OOD 任務(wù)上的泛化能力。Epiplexity 量化的是模型提取的結(jié)構(gòu)性信息量，而不關(guān)心這些結(jié)構(gòu)是否與某個具體下游任務(wù)相關(guān)。

為建立直觀理解，我們探索了一系列現(xiàn)象，并提供了實驗證據(jù)，說明那些現(xiàn)有信息論工具難以解釋、卻能自然被 epiplexity 容納的行為。我們展示了信息可通過純粹的計算過程被創(chuàng)造出來，從而對合成數(shù)據(jù)提供新見解（第5.1小節(jié)）。我們考察了同一數(shù)據(jù)的不同因式分解方式如何增加結(jié)構(gòu)性信息及下游 OOD 性能——盡管它們可能導(dǎo)致訓(xùn)練損失更差（第5.2小節(jié)）。我們闡明為何似然建模不僅僅是分布匹配，并指出“歸納”和“涌現(xiàn)”是兩種場景，在其中觀察者能夠?qū)W到比原始數(shù)據(jù)生成過程中所含更多的信息（第5.3小節(jié)）。通過測量 epiplexity，我們可以更好地理解為何基于文本數(shù)據(jù)的預(yù)訓(xùn)練比圖像數(shù)據(jù)遷移范圍更廣，以及為何某些大語言模型的數(shù)據(jù)選擇策略在經(jīng)驗上取得成功（第6節(jié)）。綜合來看，我們的結(jié)果澄清了最初提出的幾個問題：數(shù)據(jù)的信息內(nèi)容可以在不依賴特定任務(wù)的前提下進行比較；新信息可通過計算被創(chuàng)造；模型可以學(xué)到比其生成過程本身所含更多的信息。

簡言之，我們指出了信息論現(xiàn)有概念與現(xiàn)代實踐之間的脫節(jié)，這體現(xiàn)在三個看似悖論的現(xiàn)象中；為此，我們引入 epiplexity，作為一種衡量計算能力受限的觀察者所能獲取的結(jié)構(gòu)性信息的指標(biāo)，以幫助解決這些悖論。我們在第3節(jié)（定義8）中正式定義 epiplexity，并在第4節(jié)中介紹其測量方法。在第5節(jié)中，我們展示 epiplexity 和時間受限熵如何揭示這些悖論的本質(zhì)，包括歸納和涌現(xiàn)現(xiàn)象。最后，在第6節(jié)中，我們證明 epiplexity 與分布外泛化能力相關(guān)，有助于解釋為何某些數(shù)據(jù)比其他數(shù)據(jù)更能支持廣泛的泛化能力。

2 背景

為了定義信息中那些有趣、結(jié)構(gòu)性且具有預(yù)測性的成分，我們必須將其與隨機信息區(qū)分開來——后者在給定觀察者計算約束的前提下，本質(zhì)上是不可預(yù)測的。在此過程中，我們將回顧算法信息論中發(fā)展的算法隨機性概念，以及密碼學(xué)中使用的偽隨機性概念，并闡明這些概念如何關(guān)鍵地依賴于觀察者。

2.1 一個對象“隨機”意味著什么？

隨機變量與香農(nóng)信息。關(guān)于隨機性的許多常見直覺源于隨機變量和香農(nóng)信息。隨機變量定義了一個從給定的可測概率空間到不同結(jié)果的映射，其概率對應(yīng)于導(dǎo)致某一特定結(jié)果的空間測度。香農(nóng)信息根據(jù)概率 P，為每個結(jié)果 x 分配一個自信息（或意外性）log 1/P(x)，并為隨機變量 X 定義熵 H(X) = E[log 1/P(X)]，該熵給出了向另一方傳遞樣本所需的平均編碼長度的下界（Shannon, 1948）。在香農(nóng)理論中，信息僅來源于分布和隨機變量。非隨機的對象必須不包含任何信息。因此，非隨機信息似乎自相矛盾，我們必須從更廣泛的數(shù)學(xué)視角來描述這些概念。

在20世紀(jì)中期，數(shù)學(xué)家們開始嘗試精確形式化“一個給定樣本是從某個分布中隨機抽取的”這一含義，以奠定概率論和隨機變量理論的基礎(chǔ)（Shafer and Vovk, 2006）。一個核心考慮是均勻采樣的二進制序列 u?:∞，從中可以構(gòu)造出其他感興趣的分布。這個序列也可以被解釋為區(qū)間 [0,1] 中某個數(shù)的二進制表達(dá)式。直觀上，人們可能認(rèn)為所有序列都應(yīng)被視為同等隨機，因為根據(jù)概率分布，它們的可能性均等：例如，111111… 與 10011101… 具有相同的概率質(zhì)量，也具有相同的自信息。然而，觀察這些序列的統(tǒng)計特性會揭示這一觀點所缺失的內(nèi)容；例如，根據(jù)大數(shù)定律，必須滿足 lim?→∞ (1/N) Σ???? u? =0.5，而全為1的第一個序列顯然不滿足此條件。

馬丁-洛夫隨機性：不存在能預(yù)測該序列的算法。最初有人試圖將隨機性形式化為通過所有統(tǒng)計隨機性檢驗的序列，例如針對選定子串的大數(shù)定律。然而，在此類定義下，所有序列都無法被認(rèn)為是隨機的，因為像 u?:∞ ≠ y?:∞ 這樣的測試對任何特定序列 y 都必須被包括在內(nèi)（Downey and Hirschfeldt, 2019）。這些問題的解決方案是將隨機序列定義為那些通過所有“可計算”隨機性檢驗的序列，這種形式化被稱為馬丁-洛夫隨機性（Martin-L?f, 1966）。事實證明，這一定義等價于若干看似不同的定義，例如：任何賭徒都無法利用序列的性質(zhì)獲利，或者隨機序列的所有前綴幾乎不可壓縮（Terwijn, 2016）。對于最后一個定義，我們必須引入柯爾莫哥洛夫復(fù)雜度——一種關(guān)于可壓縮性的概念，也是本文的一個關(guān)鍵概念。

可以將馬丁-洛夫隨機性擴展到有限序列。我們稱一個序列 x ∈ {0,1}? 是 c-隨機的，如果 K(x) > n ? c。等價地，隨機性偏差（randomness discrepancy）定義為 δ(x) = n ? K(x)，

它衡量的是 x 距離具有最大柯爾莫哥洛夫復(fù)雜度有多遠(yuǎn)。若序列 x 滿足 δ(x) < c，則稱其為 c-隨機序列。高柯爾莫哥洛夫復(fù)雜度、低隨機性偏差的序列，在從均勻隨機采樣的隨機變量中抽樣時出現(xiàn)的概率極高。根據(jù)克拉夫特不等式（Kraft, 1949; McMillan, 1956），長度 L ≤ n ? c 的（前綴無關(guān)）程序至多有 2??? 個；因此，在對 X ~ U? 進行均勻采樣所得的 2? 種可能性中，K(X) 的大小為 L 或更小的概率為 P(K(X) ≤ n ? c) = P(δ(X) ≥ c) < 2??。因此，序列的隨機性偏差可被視為一種檢驗統(tǒng)計量，據(jù)此人們可拒絕“給定對象 X 確實是從均勻分布中隨機采樣”的零假設(shè)（Grünwald 等，2008）。為了讓一個序列具有低隨機性偏差，它必須不存在任何可識別的模式，因此在客觀意義上，1001011100 比 0101010101 更“隨機”。

根據(jù)馬丁-洛夫?qū)o限隨機序列的定義，每個隨機序列都是不可計算的；換句話說，不存在任何程序能夠?qū)崿F(xiàn)函數(shù) ? → {0,1} 來生成該序列的所有比特位。人們應(yīng)將此類隨機數(shù)與像 π/4 或 e/3 這類雖然超越但卻是可計算的數(shù)區(qū)分開來——因為確實存在程序可以計算它們二進制表達(dá)式的每一位比特。雖然區(qū)間 [0,1] 中的可計算數(shù)構(gòu)成一個可數(shù)集，但算法上隨機的數(shù)在 [0,1] 中數(shù)量不可數(shù)。考慮到隨機序列的不可計算性，我們可以理解馮·諾依曼的名言：

“任何考慮用算術(shù)方法產(chǎn)生隨機數(shù)字的人，當(dāng)然都處于罪惡的狀態(tài)。”（Von Neumann, 1951）

這句話預(yù)示了后來馬丁-洛夫的形式化理論。但這一觀點也忽略了一些關(guān)鍵內(nèi)容，正如偽隨機數(shù)生成、去隨機化和密碼學(xué)的成功所證明的那樣。

密碼學(xué)隨機性：不存在多項式時間算法能預(yù)測該序列。隨機數(shù)的一個重要實踐與理論發(fā)展來自密碼學(xué)界，其再次通過限制觀察者的計算模型來實現(xiàn)。

與馬丁-洛夫隨機性要求通過所有可計算檢驗不同，密碼學(xué)安全的偽隨機數(shù)生成器（CSPRNG 或 PRG）被定義為能生成通過所有“多項式時間”隨機性檢驗的序列的函數(shù)。

通過多項式時間檢驗所定義的不可區(qū)分性，等價于以下關(guān)于序列預(yù)測失敗的定義：不存在任何多項式時間的預(yù)測器，能夠以顯著優(yōu)于隨機猜測的概率，根據(jù)序列的前綴預(yù)測出下一個比特（Yao, 1982）。

根據(jù)不可區(qū)分性定義，在絕大多數(shù)實際情境中，這種隨機性可以替代馬丁-洛夫隨機性。2 例如，如果某個使用隨機性的應(yīng)用場景（如快速排序算法）在使用密碼學(xué)安全偽隨機數(shù)生成器（CSPRNG）序列時比使用真正隨機序列需要更多的迭代次數(shù)，并且這種差異可以在多項式時間內(nèi)被檢測到（例如通過測量快速排序的運行時間），那么該構(gòu)造就可以作為一個多項式時間區(qū)分器——但根據(jù) CSPRNG 的定義，這樣的區(qū)分器并不存在。因此，若 CSPRNG 存在，則快速排序在使用偽隨機數(shù)生成時的運行速度必須幾乎與使用真正隨機序列時一樣快。

CSPRNG 的存在依賴于單向函數(shù)的存在，而 CSPRNG 及其他密碼學(xué)原語正是基于單向函數(shù)構(gòu)建的，構(gòu)成了現(xiàn)代密碼學(xué)的基礎(chǔ)。例如，Jax 中用于并行隨機數(shù)生成的核心算法（Bradbury 等，2018），其工作原理是通過對數(shù)字 1, 2, …, N 進行加密來生成隨機數(shù) u?, u?, …, u?：u? = E(k, s)，其中加密密鑰 s 是隨機種子，E 是 Threefish 分組密碼（Salmon 等，2011）。分組密碼與其他密碼原理一樣，都是利用單向函數(shù)構(gòu)建的。

其中概率是針對 x 的均勻選擇（以及 A 內(nèi)部的隨機性）。

雖然密碼學(xué)家最關(guān)心的是多項式時間與非多項式時間計算分離在安全性方面的意義，但人們已構(gòu)建并相信存在相對于較弱計算分離的單向函數(shù)，例如針對二次時間（Merkle, 1978）、準(zhǔn)多項式時間（Liu and Pass, 2024），甚至對電路深度的限制（Applebaum, 2016）。盡管本文所證明的結(jié)果基于密碼學(xué)原語中多項式與非多項式計算分離，但在機器學(xué)習(xí)背景下，更廣泛的計算分離可能同樣相關(guān)——即使它們對密碼學(xué)的重要性較低。例如，二次或三次時間與更高階多項式之間的分離，可能與 Transformer 自注意力機制相關(guān)；或者固定電路深度與可變深度之間的差距，可能通過“思維鏈”或其他機制得以實現(xiàn)。

2.2 隨機信息 vs 結(jié)構(gòu)信息

有了上述關(guān)于隨機性的概念，我們便可以利用“什么是隨機的”來定義“什么不是隨機的”。在算法信息論中，有一個較少為人知的概念恰好捕捉了這一思想，稱為“復(fù)雜度”（sophistication）（Koppel, 1988），它在香農(nóng)信息論中沒有直接對應(yīng)的類似概念。盡管該定義有多個變體，但最直接的一種可能是如下：

定義 5（樸素復(fù)雜度）（Mota 等，2013）
復(fù)雜度與柯爾莫哥洛夫復(fù)雜度類似，定義于單個比特串之上，并使用馬丁-洛夫隨機性中的可壓縮性標(biāo)準(zhǔn)來剝離比特串中的隨機內(nèi)容。復(fù)雜度被定義為滿足以下條件的集合 S 的最小柯爾莫哥洛夫復(fù)雜度：x 是該集合中的一個隨機元素（在隨機性偏差 c 下）。

非正式地，復(fù)雜度（sophistication）描述了一個對象的結(jié)構(gòu)性成分；然而，令人驚訝的是，很難給出高復(fù)雜度對象的具體例子。尋找高復(fù)雜度對象的困難是柴廷不完備性定理（Chaitin, 1974）的一個結(jié)果。該定理指出，在給定的形式系統(tǒng)中，存在一個常數(shù) L，使得沒有任何證明能夠表明任何特定字符串 x 的柯爾莫哥洛夫復(fù)雜度 K(x) > L，盡管幾乎所有字符串都具有接近最大值的復(fù)雜度。由于 nsoph_c(x) > L 意味著 K(x) > L ? O(1)，因此也無法證明任何特定字符串的復(fù)雜度超過某個常數(shù)。已知通過對角化論證可以證明高復(fù)雜度字符串的存在（Antunes 等，2005），但我們無法確定任何具體具有高復(fù)雜度的字符串。在典型的圖靈機上，L 通常不超過幾千（Chaitin, 1998），遠(yuǎn)小于前沿 AI 模型所編碼的太字節(jié)級信息量。

我們傾向于將復(fù)雜系統(tǒng)和行為視為高復(fù)雜度對象的可能實例；然而，在許多情況下，這些對象理論上可通過更簡單的描述產(chǎn)生，只需消耗巨大的計算量即可。例如，兩種流體的混合可因流體動力學(xué)的復(fù)雜性而產(chǎn)生極其復(fù)雜的瞬態(tài)行為；但若擁有無限計算能力并選取適當(dāng)?shù)碾S機初始數(shù)據(jù)，人們應(yīng)能精確復(fù)現(xiàn)其動態(tài)過程（Aaronson 等，2014）。由于復(fù)雜度定義中允許程序擁有無界計算能力，許多原本復(fù)雜的對象會因此失去其“復(fù)雜性”。此外，對于確實具有高復(fù)雜度的字符串，最優(yōu)程序所需的計算步驟增長速度比任何具有該復(fù)雜度內(nèi)容的可計算函數(shù)都要快（Ay 等，2010）。對于計算能力受限的觀察者而言，加密消息或密碼學(xué)安全偽隨機數(shù)生成器（CSPRNG）的輸出是隨機的，那些未能識別這種隨機性的測量方法并不能反映該觀察者的實際處境。復(fù)雜度概念的這些局限性導(dǎo)致它與真實系統(tǒng)之間產(chǎn)生了脫節(jié)——真實系統(tǒng)的觀察者計算能力有限，而我們認(rèn)為這種脫節(jié)是本質(zhì)性的，且是涌現(xiàn)、歸納、混沌和密碼學(xué)等現(xiàn)象的核心所在。

2.3 最小描述長度原則

最后，我們回顧最小描述長度原則（MDL），該原則作為模型選擇的理論標(biāo)準(zhǔn)，將在定義 epiplexity 時被使用。該原則指出：在所有用于解釋數(shù)據(jù)的模型中，最佳解釋是使數(shù)據(jù)總描述長度最小化的模型，包括使用該模型對數(shù)據(jù)本身的描述以及模型自身的描述（Rissanen, 2004）。這一思想最常見的實現(xiàn)方式是統(tǒng)計二分碼 MDL。

我們在附錄 H 中回顧了 MDL 的現(xiàn)代發(fā)展。
雖然 MDL 是在給定固定數(shù)據(jù)集的前提下用于模型選擇的標(biāo)準(zhǔn)，但接下來我們將引入的 epiplexity 可被視為其對偶概念：在給定固定計算預(yù)算的前提下，用于數(shù)據(jù)選擇的標(biāo)準(zhǔn)。

3 Epiplexity：計算能力受限的觀察者可提取的結(jié)構(gòu)性信息

在牢記無界計算設(shè)定下結(jié)構(gòu)性信息與隨機信息之間的區(qū)分，以及密碼學(xué)中偽隨機性所具有的計算本質(zhì)的基礎(chǔ)上，我們現(xiàn)在引入 epiplexity。Epiplexity 捕捉的是計算能力受限的觀察者所能感知到的結(jié)構(gòu)性信息。隨著該觀察者計算約束的變化，隨機內(nèi)容與結(jié)構(gòu)化內(nèi)容之間的劃分也會隨之改變。

在本節(jié)中，我們首先引入 epiplexity 的定義；隨后在第 4 節(jié)中，我們將提出若干測量 epiplexity 的方法；在第 5 和第 6 節(jié)中，我們將展示 epiplexity 如何闡明信息論中圍繞數(shù)據(jù)價值和分布外（OOD）泛化的若干看似悖論的現(xiàn)象。

首先，我們將定義一個概率分布何時具有“高效實現(xiàn)”（efficient implementation）：要求該分布能在一臺前綴無關(guān)的通用圖靈機（UTM）上實現(xiàn)，并在固定步數(shù)內(nèi)停機。

此處，n 表示底層樣本空間的維度（例如，二進制字符串的長度）。
該定義使我們能夠約束函數(shù)類所能使用的計算量。此類模型類強制要求所關(guān)注的函數(shù)既可高效采樣，又可高效評估，這涵蓋了大多數(shù)序列模型。雖然在本研究中，我們主要聚焦于我們認(rèn)為最基礎(chǔ)的計算約束，但其他約束（如內(nèi)存限制或限定于某個特定函數(shù)類 ）也可通過將 ? 替換為 來納入考慮，并可能對理解某些特定現(xiàn)象至關(guān)重要。3 在有了這些預(yù)備知識之后，我們現(xiàn)在可以將信息中的隨機成分與結(jié)構(gòu)成分區(qū)分開來。

我們以實現(xiàn)隨機變量 X 最佳期望壓縮效果的程序為基準(zhǔn)，在給定運行時間約束下，用該程序最小化兩部分編碼長度（模型本身和在給定模型下的數(shù)據(jù)比特），從而定義 epiplexity 與時間受限熵。

時間受限熵 H? 捕捉的是隨機變量中那些隨機且不可預(yù)測的信息量，而 epiplexity S? 則捕捉在給定計算水平下對象內(nèi)部可見的結(jié)構(gòu)與規(guī)律性信息量。均勻隨機變量具有平凡的 epiplexity，因為一個像均勻分布一樣簡單的模型即可實現(xiàn)較小的兩部分編碼長度，盡管其時間受限熵較大。具體而言，對于定義在 {0,1}? 上的均勻隨機變量 U?，即使時間約束 T(n) ≥ c? 為常數(shù)，也有 S?(U?) + H?(U?) ≤ n + c?，其中 c? 是運行時間為 c? 的均勻分布程序的長度；又因 H?(U?) ≥ H(U?) = n，故必有 S?(U?) ≤ c?。具有非常簡單模式的隨機變量（例如以 1/2 概率出現(xiàn)的 0101010101… 和以 1/2 概率出現(xiàn)的 1010101010…）同樣具有低 epiplexity，因為其時間受限 MDL 最優(yōu)模型是簡單的。在此線性時間約束 T(n) = Θ(n) 的情況下，S?(X) = O(1) 且 H?(X) = O(1)。因此，我們將簡記 MDL?(X) := S?(X) + H?(X)，即總的時間受限信息含量。接下來，我們將列舉這些定義的一些基本推論。

命題4（針對在固定時間內(nèi)運行并實現(xiàn)雙射的程序 f）是信息不增性質(zhì) K(f(x)) ≤ K(x) + K(f) + c 的一個類比。然而請注意，在我們設(shè)定的固定計算預(yù)算下，雖然函數(shù) f 及其逆函數(shù) f?1 的柯爾莫哥洛夫復(fù)雜度 K(f) 與 K(f?1) 在加性常數(shù)內(nèi)相等，但擁有一個關(guān)于 f?1 的簡短程序并不意味著也存在一個關(guān)于 f 的簡短程序，反之亦然。這種函數(shù)與其逆函數(shù)之間的差距，對后文第5節(jié)中將討論的三個悖論具有重要影響。

偽隨機數(shù)序列具有高隨機內(nèi)容和極少結(jié)構(gòu)。
不同于香農(nóng)熵、柯爾莫哥洛夫復(fù)雜度，甚至資源受限形式的柯爾莫哥洛夫復(fù)雜度（Allender 等，2011），我們證明：對于多項式時間觀察者而言，密碼學(xué)安全偽隨機數(shù)生成器（CSPRNGs）具有接近最大的時間受限熵。此外，盡管 CSPRNGs 產(chǎn)生的是隨機內(nèi)容，它們并不產(chǎn)生結(jié)構(gòu)性內(nèi)容，因為其 epiplexity 僅略大于某個常數(shù)。形式上，令 U? 表示 k 比特上的均勻分布。

相比之下，香農(nóng)熵為 H(G(U?)) = k；在多項式時間約束下，柯爾莫哥洛夫復(fù)雜度最多為 k + c（假設(shè) n 是固定的或預(yù)先指定的），因為存在一個簡短且可高效運行的程序 G 能夠生成輸出；類似地，對于其他概念如 Levin 復(fù)雜度（Li and Vitányi, 2008）或時間受限的柯爾莫哥洛夫復(fù)雜度（Allender 等, 2011）也是如此。綜合來看，這些結(jié)果表明：epiplexity 恰當(dāng)?shù)乜坍嬃藗坞S機數(shù)——它們攜帶大量時間受限的隨機性，但本質(zhì)上幾乎不包含任何可學(xué)習(xí)的結(jié)構(gòu)，這與直覺完全一致。

高 epiplexity 隨機變量的存在性。人們可能會質(zhì)疑：是否真的存在任何具有高 epiplexity 的隨機變量？事實上，在單向函數(shù)存在的前提下，我們可以通過計數(shù)論證證明：存在一系列隨機變量，其 epiplexity 至少隨維度呈對數(shù)增長。

從這一結(jié)果中我們得知，至少確實存在具有任意大的 epiplexity 的隨機變量；然而，這種對數(shù)增長的信息含量僅包含非常有限的信息量，仍遠(yuǎn)未達(dá)到我們在某些自然數(shù)據(jù)中觀察到的冪律縮放現(xiàn)象。

條件熵與 epiplexity。為了描述圖像分類等場景——在這些場景中，我們只關(guān)心一個能根據(jù)圖像預(yù)測標(biāo)簽的函數(shù)，而不關(guān)心生成圖像本身所包含的信息——我們定義了“條件時間受限熵”和“條件 epiplexity”。

在機器學(xué)習(xí)場景中，我們用隨機變量 X 表示所關(guān)注的整個數(shù)據(jù)集，即通常是從某個給定分布中抽取的大量獨立同分布（iid）樣本的集合 [X?, X?, ...]，而非單個樣本；且期望值 [log 1/P(X)] 隨數(shù)據(jù)集規(guī)模增長。Epiplexity 通常隨數(shù)據(jù)集規(guī)模增大而增長（詳見附錄 B.4 中關(guān)于此現(xiàn)象的詳細(xì)論證），因為更大的數(shù)據(jù)集允許識別并提取更復(fù)雜精細(xì)的結(jié)構(gòu)與模式，這與機器學(xué)習(xí)訓(xùn)練實踐相吻合。此外，正如我們后文將看到的，一個典型數(shù)據(jù)集的 epiplexity 比其隨機信息含量小幾個數(shù)量級。雖然本文并不聚焦于此，但對確定性字符串進行條件化處理，可以打開理解“哪些額外數(shù)據(jù)對特定機器學(xué)習(xí)模型最有用”的可能性，例如用于預(yù)訓(xùn)練大語言模型（LLM）后的微調(diào)階段。

4 測量 Epiplexity 和時間受限熵

我們現(xiàn)已引入 epiplexity 和時間受限熵作為衡量數(shù)據(jù)中結(jié)構(gòu)性和隨機性信息的指標(biāo)。在本節(jié)中，我們將介紹用于估計這些量的上界及經(jīng)驗代理指標(biāo)的實際方法。直觀上，我們希望找到一個概率模型 P(·)，它能對數(shù)據(jù) X 實現(xiàn)較低的期望損失 [log 1/P(X)]，該模型由一個簡短程序 P 描述，且評估 P(X) 所需時間至多為 T(|X|)，我們將其簡記為 T。利用這個模型，我們便可將數(shù)據(jù)的信息分解為其結(jié)構(gòu)性成分與隨機性成分，即：

（1）epiplexity S?(X)：程序 |P| 的長度，代表用于建模數(shù)據(jù)分布所需的比特數(shù)；

（2）時間受限熵 H?(X)：使用該模型對數(shù)據(jù)進行熵編碼時的期望長度，代表指定該分布下 X 的具體實現(xiàn)所需的比特數(shù)。

我們以類似方式估計條件 epiplexity，即將隨機變量作為輸入提供給模型。

由于直接在程序空間中搜索是不可行的，我們將注意力集中在由神經(jīng)網(wǎng)絡(luò)參數(shù)化的概率模型上，因為它們在各類數(shù)據(jù)模態(tài)上均表現(xiàn)出強大的經(jīng)驗壓縮能力（MacKay, 2003; Goldblum 等, 2023; Delétang 等, 2023; Ballé 等, 2018），并能捕捉最相關(guān)的機器學(xué)習(xí)現(xiàn)象。一種樸素的方法是讓 P 直接存儲神經(jīng)網(wǎng)絡(luò)的架構(gòu)與權(quán)重，并在給定數(shù)據(jù)上對其進行評估，但這種方法會顯著高估權(quán)重中的信息含量，尤其對于在相對少量數(shù)據(jù)上訓(xùn)練的大模型而言。取而代之的是，我們將采用一種更高效的方法，通過編碼生成權(quán)重的訓(xùn)練過程來實現(xiàn)。我們將討論兩種編碼神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程的方法，分別基于 前序編碼（prequential coding）（Dawid, 1984）和 序列編碼（requential coding）（Finzi 等, 2026）。前者更容易理解和評估，但依賴于啟發(fā)式方法來分離結(jié)構(gòu)比特與噪聲比特；后者則更為嚴(yán)謹(jǐn)，代價是評估起來更困難。幸運的是，這兩種方法在不同數(shù)據(jù)集上的 epiplexity 排名通常相當(dāng)接近（見第 4.3 節(jié)）。

接下來，我們將以浮點運算次數(shù)（FLOPs）來衡量時間，以 token 數(shù)量來衡量數(shù)據(jù)集規(guī)模。因此，訓(xùn)練一個擁有 N 個參數(shù)的模型在 D 個 token 上所需時間約為 6ND（Kaplan 等，2020），而在數(shù)據(jù)集 X 上評估該模型所需時間為 2ND，其中 D = |X| 表示 X 中的 token 總數(shù)。為區(qū)分 X 與訓(xùn)練數(shù)據(jù)集（我們可以自由選擇），我們將 X 稱為測試數(shù)據(jù)集，因為它是我們需要進行推理的數(shù)據(jù)。

4.1 使用前序編碼近似模型描述長度

前序編碼提供了一種經(jīng)典的壓縮神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程的方法。為簡化起見，我們假設(shè)批大小為 1，但將其推廣到更大的批大小是直接可行的。我們從一個隨機初始化的網(wǎng)絡(luò) P? 開始（下標(biāo)表示時間步），然后迭代進行：在每一步 i，我們使用 log 1/P?(Z?) 比特對當(dāng)前訓(xùn)練 token Z? 進行熵編碼，然后用該 token 訓(xùn)練模型以產(chǎn)生下一個模型 P???。通常，Z? 是從與 X 相同分布中獨立同分布（i.i.d.）抽取的。在解碼器一側(cè)，維護一個同步的模型；該模型使用 P? 解碼 Z?，然后對其進行訓(xùn)練以產(chǎn)生相同的 P???。忽略指定隨機初始化、架構(gòu)和訓(xùn)練算法所需的微小常數(shù)開銷，總編碼長度 L(Z:M, P?) = Σ?????1 log 1/P?(Z?) 比特，即可同時為訓(xùn)練數(shù)據(jù) Z:M = {Z?, ..., Z???} 和最終模型權(quán)重 P? 提供一個顯式編碼。對于一個在 D個 token 上訓(xùn)練、擁有 N個參數(shù)的模型（通常 D > M，因為每個樣本包含多個 token），該編碼可在6ND 時間內(nèi)完成解碼。

4.2 使用序列化編碼顯式編碼模型

4.3 兩種方法的比較與實用建議

圖2c比較了本工作所用四組數(shù)據(jù)集上通過兩種方法獲得的估計表征復(fù)雜度：ECA（第5.1節(jié)）、簡單與困難歸納（第5.3.1節(jié)）以及自然數(shù)據(jù)集（第6.2節(jié)）。雖然序貫估計通常比前序估計大數(shù)倍，但兩者相關(guān)性良好，尤其是在每組內(nèi)數(shù)據(jù)集具有相似學(xué)習(xí)動態(tài)的情況下。我們在附錄C.7中詳細(xì)說明所用數(shù)據(jù)集和時間約束。這種總體一致性是預(yù)期的，因為前序估計可被視為使用靜態(tài)教師模型的序貫編碼的一種近似（附錄B.2）。然而，一般而言，兩種估計之間的差異將取決于特定數(shù)據(jù)集和訓(xùn)練配置，二者之間良好的相關(guān)性并不能保證。

盡管序貫編碼是更嚴(yán)謹(jǐn)?shù)姆椒ǎǔ１惹靶蚓幋a慢2至10倍，而前序編碼僅需標(biāo)準(zhǔn)訓(xùn)練。開銷取決于批量大小、序列長度和推理實現(xiàn)方式（大批量和短序列時開銷較小），因為序貫編碼需要反復(fù)從教師模型采樣，盡管通過更高效的算法有可能降低開銷。因此，我們建議在粗略估計表征復(fù)雜度及對不同數(shù)據(jù)集的表征復(fù)雜度進行排序時使用前序編碼，特別是當(dāng)已能獲取現(xiàn)有昂貴訓(xùn)練運行的損失曲線時（例如，參見第6.2節(jié)中的應(yīng)用）；而在其他情況下，為獲得最精確的估計，則應(yīng)使用序貫編碼。

4.4 表征復(fù)雜度與時間約束熵如何隨計算量和數(shù)據(jù)規(guī)模變化

5 信息的三個表面悖論

為了說明現(xiàn)有信息理論視角中的空白，我們強調(diào)了信息的三個“表面悖論”：(1) 信息不能通過確定性變換產(chǎn)生；(2) 一個對象的總信息量與其分解方式無關(guān)；(3) 似然建模只能學(xué)會匹配數(shù)據(jù)生成過程。每一條陳述都捕捉到了機器學(xué)習(xí)社區(qū)內(nèi)現(xiàn)有的某種共識，可以從香農(nóng)信息論和算法信息論中得到數(shù)學(xué)上的支持，但似乎又與直覺和實驗觀察相沖突。在本節(jié)中，我們將通過理論結(jié)果和實證證據(jù)表明，時間約束和表征復(fù)雜度有助于解決這些表面悖論。

5.1 悖論一：信息不能由確定性變換產(chǎn)生

那么，我們?nèi)绾握{(diào)和這一事實與像 AlphaZero (Silver 等, 2018) 這樣的算法？AlphaZero 能在一個封閉環(huán)境中僅靠一個小的確定性程序運行國際象棋游戲，從中提取出關(guān)于游戲、不同開局、棋子在不同位置的相對價值、戰(zhàn)術(shù)和高層策略的洞見，并需要將兆字節(jié)的信息存儲在權(quán)重中？類似地，我們也擁有具有簡單底層規(guī)律描述的動態(tài)系統(tǒng)，卻能產(chǎn)生豐富且意想不到的結(jié)構(gòu)，我們可從中學(xué)習(xí)到關(guān)于它們和數(shù)學(xué)的新知識。

我們也有證據(jù)表明合成數(shù)據(jù)是有用的 (Liu 等, 2024; Gerstgrasser 等, 2024; Maini 等, 2024; OpenAI, 2025)，它有助于提升模型能力；而且，如果我們相信生成自然數(shù)據(jù)的過程原則上可以在大型計算機上被模擬到足夠精度，那么所有數(shù)據(jù)都可以被等價地替換為合成數(shù)據(jù)。對于從給定模型和提示中采樣并經(jīng)過變換產(chǎn)生的實用合成數(shù)據(jù)，這種采樣是通過偽隨機數(shù)生成器完成的，從而使整個變換過程成為確定性的。如果我們把 f f 視為我們用來生成合成數(shù)據(jù)的變換，而 x x 是我們最初擁有的有限真實數(shù)據(jù)，這些不等式似乎非常具體地指出：我們的合成數(shù)據(jù)除了模型和訓(xùn)練數(shù)據(jù)外，沒有添加任何額外信息。

無論當(dāng)我們說 AlphaZero 在國際象棋中產(chǎn)生了新的、出人意料的洞見，或在數(shù)學(xué)中獲得了新的理論結(jié)果，或使用合成數(shù)據(jù)時所指的“信息”是什么，它都不是香農(nóng)信息或算法信息。我們認(rèn)為，信息理論中這些違反直覺的特性，源于假設(shè)觀察者擁有無限計算能力。在計算能力受限的情況下，對 AlphaZero 算法的描述與運行 AlphaZero 數(shù)千 TPU 小時后得到的結(jié)果是截然不同的。為了建立直覺，我們從簡單的 CSPRNG 開始，它同樣通過計算（盡管是隨機信息）創(chuàng)造出時間約束信息。

我們可以得到截然不同的結(jié)果：產(chǎn)生簡單對象、僅產(chǎn)生隨機內(nèi)容，或產(chǎn)生隨機與結(jié)構(gòu)化內(nèi)容的混合。

5.2 悖論二：信息含量獨立于分解方式

另一方面，多項研究已觀察到，當(dāng)自然文本（如英文）按從左到右順序建模時，比按反向順序建模時壓縮效果更好（最終模型達(dá)到更高的似然值）(Papadopoulos et al., 2024; Bengio et al., 2019)，這揭示了大語言模型中存在“時間之箭”，即一種方向上的建模優(yōu)于另一種。似乎對于許多文檔而言，其他排序方式可能導(dǎo)致大語言模型提取出更多不同的信息以及下游性能差異。類似地，正如我們稍后將展示的那樣，數(shù)據(jù)的微小重排也可能導(dǎo)致顯著不同的損失和下游性能。密碼學(xué)原語（如單向函數(shù)和分組密碼）同樣提供了例子，表明條件化的順序會對數(shù)據(jù)的熵表現(xiàn)產(chǎn)生決定性影響，例如考慮對兩個素數(shù)及其乘積進行自回歸建模，與采用相反順序建模的情況。這些實驗結(jié)果和密碼學(xué)思想表明，可以學(xué)到的內(nèi)容依賴于數(shù)據(jù)的排序方式，這反過來又暗示從不同排序方式中提取出的“信息”量是不同的。

我們的時間約束定義捕捉到了這一差異。在存在單向置換的情況下，我們可以證明，對于時間約束熵，不同分解方式之間存在預(yù)測差距。

作為一個推論，我們證明不存在任何多項式時間的概率模型，能夠滿足單向函數(shù)前向方向的貝葉斯定理（見定理26）。在這些理論結(jié)果的基礎(chǔ)上，我們實證地考察了單向函數(shù)在時間約束熵上的差距，以及在預(yù)測國際象棋數(shù)據(jù)時兩種排序方式下熵和表征復(fù)雜度的差距。

在圖4(a)中，我們選擇 f f 為具有大小為 n n 的狀態(tài)和周期性邊界條件的ECA規(guī)則30演化8步的結(jié)果 (Wolfram and Gad-el Hak, 2003)。盡管與密碼學(xué)中使用的單向函數(shù)不同，規(guī)則30被認(rèn)為是一種單向函數(shù) (Wolfram and Gad-el Hak, 2003)，并且與典型的單向函數(shù)不同的是，規(guī)則30的前向傳遞可以通過自回歸變換器建模，我們通過在附錄D中構(gòu)建一個顯式的RASP-L (Zhou et al., 2023; Weiss et al., 2021) 程序來證明這一點。如圖4(a)所示，該模型在前向方向上達(dá)到了香農(nóng)熵（灰色），但在反向方向上存在持續(xù)的差距。

除了隨機信息如何隨排序方式變化之外，結(jié)構(gòu)信息也可能有所不同，正如我們接下來將展示的那樣。我們通過在Lichess數(shù)據(jù)集上訓(xùn)練自回歸變換器模型來證明這一事實，該數(shù)據(jù)集是一個大型的國際象棋對局集合，其中走法以代數(shù)記譜法記錄。我們考慮該數(shù)據(jù)集的兩個變體：(1) 將每局棋按走法序列后接最終棋盤狀態(tài)（FEN記譜法）的形式進行格式化；(2) 將每局棋按最終棋盤狀態(tài)后接走法序列的形式進行格式化，如圖4b所示。我們在第C.4節(jié)中提供了完整的實驗細(xì)節(jié)。雖然在此設(shè)置中沒有明確的多項式與非多項式時間分離，但第一種排序方式類似于前向方向，因為最終棋盤狀態(tài)可以通過一個簡單函數(shù)直接從走法映射得到，而后者排序方式則類似于反向方向，因為從最終棋盤狀態(tài)恢復(fù)走法需要逆函數(shù)來推斷中間步驟。我們假設(shè)反向方向是一個更復(fù)雜的任務(wù)，將引導(dǎo)模型獲取更多結(jié)構(gòu)信息，例如對棋盤狀態(tài)更深入的理解。圖4c證實了這一假設(shè)，顯示反向排序方式具有更高的時間約束熵和表征復(fù)雜度。當(dāng)計算預(yù)算較小時，這種差距會消失，此時模型可能僅學(xué)習(xí)到兩種排序方式共有的表面統(tǒng)計特征，而在額外的反向任務(wù)復(fù)雜性迫使模型發(fā)展出更豐富的棋盤狀態(tài)表示之前。

5.3 悖論三：似然建模僅僅是分布匹配

有一種普遍的觀點認(rèn)為，從特定的訓(xùn)練分布出發(fā)，我們最多只能期望匹配數(shù)據(jù)生成過程。如果某個屬性或函數(shù)不在數(shù)據(jù)生成過程中，則我們不應(yīng)期望在模型中學(xué)習(xí)到它。作為一種延伸，如果生成過程很簡單，那么試圖匹配它的模型也應(yīng)同樣簡單。這種觀點可以通過抽象地考慮似然最大化過程 arg ? min ? P E X ～ Q [ ? log ? P ( X ) ] = Q來支持：當(dāng)兩個分布匹配時，測試負(fù)對數(shù)似然（NLL）達(dá)到最小值。分布之間的差異程度被視為由于函數(shù)類過于受限或數(shù)據(jù)不足導(dǎo)致泛化失敗。從這些論證出發(fā)，我們有理由相信，AI模型在人類數(shù)據(jù)上預(yù)訓(xùn)練時無法超越人類智能。在這里，我們提供兩類似乎與此觀點相矛盾的現(xiàn)象：歸納和涌現(xiàn)。在這兩種情況下，限制提供給AI模型的計算量會導(dǎo)致它們提取比實現(xiàn)生成過程本身所需更多的結(jié)構(gòu)信息。

5.3.1 歸納（Induction）

生成建模領(lǐng)域常常面臨一個挑戰(zhàn)：既希望采樣過程易于處理，又希望似然評估也易于計算。自回歸模型、擴散模型、變分自編碼器（VAE）、生成對抗網(wǎng)絡(luò)（GAN）和標(biāo)準(zhǔn)化流（normalizing flows）等方法各自提供了不同的解決路徑。對于自然的生成過程而言，通常其中一個方向（采樣或似然計算）會比另一個方向簡單得多。在此，我們研究一類生成過程：它們通過變換隱變量構(gòu)造而成，而要計算其似然，就需要對這些隱變量的取值進行歸納推理。

這一現(xiàn)象可從 Ilya Sutskever 的一段引述中獲得直觀理解：

“你正在讀一部謀殺懸疑小說，文本在某個時刻揭示了兇手的身份。……如果模型能夠預(yù)測出[這個姓名]，那么它必定已經(jīng)從所提供的證據(jù)中推斷出[誰是兇手]。”（Sutskever, 2019）

然而，書的作者卻未必需要進行同樣的歸納推理。相反，作者可能先選定兇手，然后再精心編織一個關(guān)于其行為的引人入勝的故事。這個例子突顯了生成過程與預(yù)測模型所需能力之間的差距——這正是我們接下來通過以下更數(shù)學(xué)化的設(shè)定所要探討的。

另一方面，書的作者無需進行相同的歸納推理。相反，他們可能先選定兇手，然后編織一個關(guān)于其行為的引人入勝的故事。這個例子突顯了生成過程與預(yù)測模型所需能力之間的差距——我們將在以下更數(shù)學(xué)化的設(shè)定中探討這一差距。

歸納困難：規(guī)則30 ECA

以及通過掩碼進行簡單后處理來移除比特。這一圖像被測量的表征復(fù)雜度所鏡像：隨著模型被迫對缺失比特進行歸納，表征復(fù)雜度隨之增長。

歸納容易：隨機馬爾可夫鏈

在歸納困難和歸納容易的兩個例子中，執(zhí)行歸納策略所需的程序規(guī)模都大于生成數(shù)據(jù)所需的程序規(guī)模。我們可以預(yù)期，在計算資源受限的情況下，通常無法通過暴力窮舉法逆轉(zhuǎn)生成過程；因此，在存在替代性逆向策略的情形下（例如統(tǒng)計歸納頭的簡單歸納示例），這些額外的策略會增加表征復(fù)雜度。鑒于很可能不存在適用于所有問題的單一通用逆向策略，這些策略很可能會成為表征復(fù)雜度的一個來源。

為了使上述陳述更精確，似乎不太可能存在常數(shù) ，使得以下性質(zhì)成立：

對“分布匹配”觀點最引人注目的反例之一是“涌現(xiàn)”（emergence）。即使一個系統(tǒng)的底層動力學(xué)可以用簡單的描述來刻畫，一個計算能力有限的觀察者也可能需要學(xué)習(xí)一套更豐富、看似無關(guān)的概念集合，才能預(yù)測或解釋其行為。正如 Anderson (1972) 所闡述的，還原論——即復(fù)雜物體的行為源于其組成部分——并不能保證：僅僅了解這些部分就足以讓我們預(yù)測整體。在生物學(xué)和物理學(xué)中，多體相互作用會產(chǎn)生一些行為（例如鳥群、康威生命游戲中的模式、分子化學(xué)、超導(dǎo)性），這些行為無法僅從微觀定律中直接看出。在此，我們簡要說明“涌現(xiàn)”如何與觀察者的計算約束密切相關(guān)，并展示那些預(yù)測未來狀態(tài)的觀察者，可能需要比能夠完整執(zhí)行生成過程的無約束對應(yīng)者學(xué)習(xí)更多知識。

考慮 Carroll 和 Parola (2024) 分類中的 IIb 型涌現(xiàn)，在該分類中，高層模式由局部規(guī)則產(chǎn)生，卻抵抗從這些規(guī)則進行預(yù)測。一個典型例子是康威生命游戲（參見附錄 E 以獲取定義），其中在一個二維網(wǎng)格上迭代一個簡單的計算規(guī)則 Φ 會導(dǎo)致復(fù)雜的涌現(xiàn)行為。對于缺乏足夠計算資源以直接計算迭代演化 的觀察者，必須找到一種替代性的描述方式。在狀態(tài)演化過程中，可以識別出局部化的“物種”（靜態(tài)塊、振蕩器、滑翔機、槍），它們在空間和時間中傳播。通過將這些物種分類，學(xué)習(xí)它們的速度，以及它們在與其他物種碰撞時如何被改變，計算能力受限的觀察者便能對系統(tǒng)的未來狀態(tài)做出預(yù)測。然而，這樣做在描述長度的意義上需要一個更復(fù)雜的程序，因此表征復(fù)雜度會更高。我們可以將這一直覺形式化為以下關(guān)于“涌現(xiàn)”的定義。

在圖6中，我們通過訓(xùn)練一個變換器模型來預(yù)測ECA規(guī)則54（一種產(chǎn)生復(fù)雜模式的IV類規(guī)則）的迭代動力學(xué)，實證地展示了涌現(xiàn)現(xiàn)象。與康威生命游戲類似，計算能力充足的模型可以通過直接迭代每一步規(guī)則來精確模擬動力學(xué)——這是一種描述長度很短的暴力求解方案。然而，計算資源受限的模型無法承擔(dān)這種方法，而必須轉(zhuǎn)而學(xué)習(xí)涌現(xiàn)的模式（例如滑翔機及其碰撞規(guī)則），從而近似地繞過不可行的精確模擬。暴力求解方案可以通過學(xué)習(xí)自回歸展開中間ECA狀態(tài)（而非直接預(yù)測最終狀態(tài)）自然實現(xiàn)，這類似于“思維鏈”（Wei et al., 2022）或“循環(huán)式變換器”（Dehghani et al., 2018; Giannou et al., 2023; Saunshi et al., 2025）的應(yīng)用。我們在第C.8節(jié)提供了實驗細(xì)節(jié)。

盡管最初，非循環(huán)模型（直接預(yù)測最終狀態(tài)）隨著計算量增加會逐漸獲得更好的MDL和更高的表征復(fù)雜度，但我們識別出一個關(guān)鍵的計算閾值：超過該閾值后，循環(huán)模型突然變得更有利，導(dǎo)致MDL和表征復(fù)雜度驟降，這很可能是因為模型學(xué)會了簡單的暴力求解方案。低于此閾值時，循環(huán)模型表現(xiàn)不佳，可能是因為其缺乏足夠計算力以完整展開動力學(xué)過程。而非循環(huán)模型由于無法依賴暴力模擬，必須轉(zhuǎn)而學(xué)習(xí)日益復(fù)雜的涌現(xiàn)規(guī)則，識別出更多“物種”及其相互作用，因此表征復(fù)雜度起初隨計算量增加而上升，之后才下降。

雖然本實驗清晰地證明了計算受限的模型如何從數(shù)據(jù)中學(xué)習(xí)更豐富的結(jié)構(gòu)，但它是一個罕見的例子：暴力求解方案在實驗上是可及的，因此增加計算量反而可能適得其反。在大多數(shù)實際場景中（如AlphaZero或建模自然數(shù)據(jù)），對應(yīng)的簡單暴力求解方案在計算上是不可行的，例如對天文級規(guī)模的游戲樹進行窮舉搜索，或通過模擬物理定律來預(yù)測自然數(shù)據(jù)。因此，在大多數(shù)情況下，使用更多計算量訓(xùn)練的模型確實會繼續(xù)學(xué)習(xí)到更多結(jié)構(gòu)，因為暴力求解變得可行的階段仍遙不可及。

我們在附錄F中探討了其他類型的涌現(xiàn)現(xiàn)象，例如在混沌動力系統(tǒng)中或在博弈智能體最優(yōu)策略中的涌現(xiàn)。這些例子均提供了明確證據(jù)：為了追求能最好解釋數(shù)據(jù)的概率分布，計算能力有限的觀察者需要比最小數(shù)據(jù)生成過程具有更長描述長度的模型，才能達(dá)到相當(dāng)?shù)念A(yù)測性能（Martínez et al., 2006; Redeker, 2010）。表征復(fù)雜度提供了一個通用工具，用于理解和量化這些涌現(xiàn)現(xiàn)象，以及理解簡單規(guī)則如何創(chuàng)造出有意義且復(fù)雜的結(jié)構(gòu)，供AI模型從中學(xué)習(xí)——Zhang等人（2024）最近已對此進行了實證驗證。

6 表征復(fù)雜度、預(yù)訓(xùn)練與分布外泛化

在互聯(lián)網(wǎng)規(guī)模數(shù)據(jù)上進行預(yù)訓(xùn)練已帶來了顯著的分布外（OOD）泛化能力，然而對這一現(xiàn)象的深入理解仍然不足。什么樣的數(shù)據(jù)能提供最佳信號以實現(xiàn)廣泛泛化？為什么在文本數(shù)據(jù)上進行預(yù)訓(xùn)練所獲得的能力可以跨領(lǐng)域遷移，而圖像數(shù)據(jù)卻不行？隨著高質(zhì)量互聯(lián)網(wǎng)數(shù)據(jù)逐漸耗盡，我們應(yīng)依據(jù)何種指標(biāo)來指導(dǎo)新預(yù)訓(xùn)練數(shù)據(jù)的選擇或合成？在本節(jié)中，我們將展示表征復(fù)雜度（epiplexity）如何幫助回答這些基礎(chǔ)性問題。

分布外泛化的本質(zhì)在于模型習(xí)得了多少可復(fù)用的結(jié)構(gòu)，而非其在分布內(nèi)預(yù)測得有多好。兩個在不同語料庫上訓(xùn)練的模型可能達(dá)到相同的分布內(nèi)損失，但在遷移到OOD任務(wù)時的能力卻大相徑庭。這是因為損失僅捕捉了殘余的不可預(yù)測性——對應(yīng)于時間約束熵——而并未反映模型為達(dá)到該損失所內(nèi)化的可復(fù)用結(jié)構(gòu)量。表征復(fù)雜度恰好衡量了這一缺失的成分：即學(xué)習(xí)到的程序中所包含的信息量。直觀地說，損失反映了數(shù)據(jù)在模型眼中看起來有多“隨機”，而表征復(fù)雜度則反映了模型必須習(xí)得多少結(jié)構(gòu)才能解釋掉其中的非隨機部分。如果OOD泛化依賴于復(fù)用所學(xué)機制，而非僅僅記憶表面統(tǒng)計特征，那么表征復(fù)雜度就自然成為理解預(yù)訓(xùn)練數(shù)據(jù)與OOD遷移之間關(guān)系的一個恰當(dāng)視角。

作為一個啟發(fā)性的玩具示例，Zhang 等人（2024）觀察到，IV類ECA規(guī)則往往對下游任務(wù)更有益，這與我們在圖3中展示的結(jié)果一致：規(guī)則54（一種IV類規(guī)則）所誘導(dǎo)的表征復(fù)雜度遠(yuǎn)高于其他類型的ECA規(guī)則。

6.1 表征復(fù)雜度與國際象棋中的分布外泛化呈正相關(guān)

我們在第5.2節(jié)所述的兩種排序方式（走法在前 vs. 棋盤狀態(tài)在前）上訓(xùn)練的模型基礎(chǔ)上，對兩個下游任務(wù)進行微調(diào)：(1) 解國際象棋殘局題（chess puzzles），即給定一個棋盤局面，模型需預(yù)測最優(yōu)的下一步走法（Burns 等, 2023）；(2) 預(yù)測“厘兵”（centipawn）評估值，即模型根據(jù)FEN記譜法對局面優(yōu)勢進行量化評估——這相比預(yù)訓(xùn)練中學(xué)到的“預(yù)測下一步走法”任務(wù)構(gòu)成了更顯著的分布偏移。實驗細(xì)節(jié)見第C.4節(jié)。

如圖7所示，反向排序（先棋盤狀態(tài)、后走法序列）產(chǎn)生了更高的表征復(fù)雜度，并帶來了更好的下游任務(wù)表現(xiàn)：在國際象棋殘局題上的準(zhǔn)確率相當(dāng)，但在厘兵評估任務(wù)上的準(zhǔn)確率顯著更高。這一結(jié)果支持了我們的假設(shè)：反向排序迫使模型發(fā)展出更豐富的棋盤狀態(tài)表征，以推斷中間走法；而這些表征能夠遷移到同樣需要理解棋盤狀態(tài)的OOD任務(wù)（如厘兵評估）中。

該例子反映了一個更普遍的原則：表征復(fù)雜度衡量的是模型從數(shù)據(jù)中提取并編碼到權(quán)重中的可學(xué)習(xí)結(jié)構(gòu)信息量，而這正是可遷移到新任務(wù)的信息來源，因此表征復(fù)雜度是衡量OOD泛化潛力的一個合理指標(biāo)。然而，我們強調(diào)，更高的表征復(fù)雜度并不能保證在任意特定任務(wù)上獲得更好的泛化效果：表征復(fù)雜度衡量的是結(jié)構(gòu)信息的總量，而不涉及其具體內(nèi)容。一個在高表征復(fù)雜度數(shù)據(jù)上訓(xùn)練的模型可能學(xué)到大量結(jié)構(gòu)，但這些結(jié)構(gòu)是否與特定下游任務(wù)相關(guān)，則另當(dāng)別論。

6.2 自然數(shù)據(jù)中結(jié)構(gòu)信息的度量

在各類自然數(shù)據(jù)模態(tài)中，語言被證明在預(yù)訓(xùn)練方面具有獨特的優(yōu)勢：不僅有助于提升分布內(nèi)性能（如語言理解能力，Radford 等, 2019），還能有效遷移到分布外任務(wù)，例如機器人控制（Ahn 等, 2022）、形式化定理證明（Song 等, 2024）以及時間序列預(yù)測（Gruver 等, 2023）。盡管其他模態(tài)（如圖像和視頻）也提供了同樣海量的信息（以原始字節(jié)數(shù)衡量），但在這些數(shù)據(jù)上進行預(yù)訓(xùn)練通常無法帶來類似廣泛的能力提升。

我們現(xiàn)在展示，表征復(fù)雜度（epiplexity）有助于解釋這種不對稱性，因為它揭示了不同數(shù)據(jù)集中結(jié)構(gòu)信息的差異。在圖8a中，我們展示了使用序貫編碼（requential coding）對 OpenWebText、Lichess 和 CIFAR-5M（Nakkiran 等, 2020）三個數(shù)據(jù)集各50億（5B）個標(biāo)記（tokens）所估計的信息分解結(jié)果——將總信息分解為表征復(fù)雜度（結(jié)構(gòu)部分）和時間約束熵（隨機部分），計算時間上限設(shè)為

FLOPs，所用模型最大參數(shù)量為1.6億（160M），且每個數(shù)據(jù)集最多使用50億個標(biāo)記進行訓(xùn)練。

在所有情況下，表征復(fù)雜度僅占總信息的極小一部分：其中 OpenWebText 數(shù)據(jù)包含最多的表征復(fù)雜度，其次是國際象棋（Lichess）數(shù)據(jù)。盡管 CIFAR-5M 數(shù)據(jù)的總信息量最大，但其表征復(fù)雜度卻最低——超過99%的信息屬于隨機成分（例如，具體像素值的不可預(yù)測性）。

6.4 語言模型的預(yù)訓(xùn)練數(shù)據(jù)選擇與課程設(shè)計

預(yù)訓(xùn)練語言模型的一個關(guān)鍵步驟是設(shè)計預(yù)訓(xùn)練數(shù)據(jù)的構(gòu)成，但目前尚缺乏對此步驟的明確指導(dǎo)原則。現(xiàn)有的數(shù)據(jù)混合方案通常通過大量試錯法設(shè)計，并依賴于“多樣性”或“高質(zhì)量”等啟發(fā)式準(zhǔn)則。更重要的是，比較不同訓(xùn)練數(shù)據(jù)的主要方式是通過保留數(shù)據(jù)集的困惑度指標(biāo)以及下游任務(wù)表現(xiàn)。然而，這些程序極易受到數(shù)據(jù)污染、對有限下游評估任務(wù)的過擬合以及古德哈特法則的影響。畢竟，沒有任何一套下游評估任務(wù)能夠足夠全面地真實捕捉通用語言模型在現(xiàn)實世界中會遇到的任務(wù)范圍。

正如我們上文所述，表征復(fù)雜度衡量的是模型所學(xué)習(xí)到的結(jié)構(gòu)信息，而這可能會受到數(shù)據(jù)選擇策略的影響。Jiang 等人（2025）證明，不同數(shù)據(jù)子集的損失曲線可用于在線動態(tài)調(diào)整數(shù)據(jù)分布，以優(yōu)先選擇那些訓(xùn)練損失下降更快的數(shù)據(jù)子集。直觀上，這一目標(biāo)與第4.3節(jié)中描述的前序近似表征復(fù)雜度是一致的，因為它導(dǎo)致?lián)p失曲線下方的面積更大。我們假設(shè)，他們提出的算法——自適應(yīng)數(shù)據(jù)優(yōu)化（ADO）——無意中實現(xiàn)了更高的表征復(fù)雜度。Jiang 等人（2025）的實驗是在僅解碼器的變換器模型上進行的，該模型擁有13億（1.3B）參數(shù)，在來自 Pile 數(shù)據(jù)集（Gao 等, 2020）的1250億（125B）個標(biāo)記上進行訓(xùn)練。模型在一套包含7項零樣本下游任務(wù)以及兩個OOD驗證數(shù)據(jù)集（SlimPajama（Soboleva 等, 2023）和 FineWeb（Penedo 等, 2024））上進行評估。

在圖8c(c)中，我們展示了基于 Jiang 等人（2025）改編的兩個OOD數(shù)據(jù)集上的估計表征復(fù)雜度、下游性能以及困惑度。如 Jiang 等人（2025）所示，ADO 在下游性能上優(yōu)于一種標(biāo)準(zhǔn)的數(shù)據(jù)采樣策略（即從整個數(shù)據(jù)集中均勻采樣，在圖8c中記為 Natural），盡管它并未針對這些指標(biāo)中的任何一個進行優(yōu)化。有趣的是，我們看到 ADO 確實通過前序編碼測量獲得了更高的表征復(fù)雜度。雖然這些下游評估無法完全捕捉預(yù)訓(xùn)練模型的所有特性，但它們確實提供了證據(jù)，表明表征復(fù)雜度是一個潛在有用的工具，可用于理解預(yù)訓(xùn)練數(shù)據(jù)的內(nèi)在價值，而無需依賴特定的下游評估任務(wù)。

7 相關(guān)工作補充

表征復(fù)雜度（Epiplexity）建立在算法信息論與復(fù)雜性科學(xué)中若干相關(guān)思想的基礎(chǔ)之上，這些思想試圖從理論上刻畫“有意義的信息”。一組密切相關(guān)的核心概念包括精巧度（sophistication，見2.2小節(jié)）、有效復(fù)雜度（effective complexity）和邏輯深度（logical depth）。與精巧度類似，有效復(fù)雜度旨在將隨機成分與結(jié)構(gòu)成分分離開來（Gell-Mann 和 Lloyd, 1996）。從另一個出發(fā)點，Bennett（1988）提出了邏輯深度，用以衡量一個接近最優(yōu)的程序生成給定字符串所需的計算步數(shù)；后來研究通過“忙海貍函數(shù)”（busy beaver function）證明了邏輯深度與精巧度等價（Antunes 等, 2005；Ay 等, 2010）。

此外，還有若干其他形式化度量被提出，用于量化結(jié)構(gòu)化或有意義的復(fù)雜性。算法統(tǒng)計學(xué)（Algorithmic statistics）通過引入“算法充分統(tǒng)計量”（algorithmic sufficient statistic）的概念，為數(shù)據(jù)提供了規(guī)則成分與隨機成分的原理性分解（Vereshchagin 和 Vitányi, 2004），這一概念與精巧度緊密相關(guān)。類似地，計算力學(xué)中的統(tǒng)計復(fù)雜度（statistical complexity）（Shalizi 和 Crutchfield, 2001）衡量的是在最優(yōu)預(yù)測模型中因果狀態(tài)的熵，從而捕捉時間序列數(shù)據(jù)中的結(jié)構(gòu)。

正如我們前文所論證的，這些現(xiàn)有的復(fù)雜性概念未能考慮觀察者所擁有的有限計算能力——而這一點對于理解機器學(xué)習(xí)算法至關(guān)重要。由于對計算限制視而不見，這些理論無法將密碼學(xué)安全偽隨機數(shù)生成器（CSPRNG）或加密對象視為“隨機”的。有人或許會認(rèn)為這些缺陷只是表面問題；例如，一種看似合理的策略是在精巧度定義中（定義5）將柯爾莫哥洛夫復(fù)雜度替換為時間約束下的柯爾莫哥洛夫復(fù)雜度。然而，這種方法存在多個問題，最明顯的是：CSPRNG 的輸出確實存在短且可高效運行的生成程序，因此其時間約束柯爾莫哥洛夫復(fù)雜度很小。更微妙的原因是，這樣做會導(dǎo)致所有字符串的精巧度退化為平凡值（trivial sophistication），我們在附錄 A.6 中對此有更詳細(xì)的討論。

我們的工作也與若干試圖刻畫“觀察者依賴型信息”（observer-dependent notions of information）的研究密切相關(guān)。在密碼學(xué)中，Barak 等（2003）和 Hsiao 等（2007）討論了計算偽熵（computational pseudoentropy）的幾種可能定義，這是熵的一種觀察者依賴型類比。HILL-偽熵（H?stad 等, 1999）相對于某一類測試函數(shù)定義：若該類中沒有任何測試能以非平凡優(yōu)勢區(qū)分某信源與高熵分布，則該信源被視為隨機；Yao-偽熵則通過對象的壓縮與解壓縮過程定義。這兩種定義都與時間約束熵密切相關(guān)——后者衡量的是在給定計算受限觀察者眼中數(shù)據(jù)的隨機成分。然而，我們的表述直接映射到機器學(xué)習(xí)實踐，并且能夠分離出結(jié)構(gòu)信息成分，這是我們工作的關(guān)鍵貢獻(xiàn)。

最近，Xu 等（2020）提出了 V-熵（V-entropy），它是香農(nóng)熵在給定概率模型族（如具有特定計算約束的模型）下的最小期望負(fù)對數(shù)概率的推廣。在 V-熵框架下，信息對稱性和數(shù)據(jù)處理不等式均可被違反，盡管論文中并未明確證明這兩點。與時間約束熵不同，V-熵中的計算約束僅限制推理時間，而不考慮尋找該模型所需的時間。因此，其最小化器可能遠(yuǎn)離實際評估的區(qū)域（例如在無限數(shù)據(jù)或無限計算下訓(xùn)練的模型）。雖然通過施加額外的數(shù)據(jù)約束可以克服這些不良行為，但我們認(rèn)為，對訓(xùn)練和推理時間施加單一統(tǒng)一的計算上限，能帶來更少的概念復(fù)雜性。

更重要的是，無論是偽熵還是 V-熵，與時間約束熵一樣，它們僅捕捉信息的隨機成分，因為它們?nèi)匀缓饬康氖窃谧罴芽尚心Ｐ拖码S機變量的不可預(yù)測性。而要理解模型究竟學(xué)到了哪些有用信息，我們更關(guān)注的是由表征復(fù)雜度所度量的非隨機成分。

利用現(xiàn)有的數(shù)據(jù)復(fù)雜性度量（如 Lempel-Ziv 復(fù)雜度和 Wolfram 分類），Zhang 等（2024）表明，在 IV 類 ECA 規(guī)則等復(fù)雜數(shù)據(jù)上訓(xùn)練的模型往往在下游任務(wù)中表現(xiàn)更好。

另有若干研究探索了如何量化數(shù)據(jù)復(fù)雜性。Dziugaite 和 Roy（2025）提出，在 PAC-Bayes 框架下，一個近似最優(yōu)參考模型的最小復(fù)雜度可視為數(shù)據(jù)復(fù)雜性的度量，并說明這種數(shù)據(jù)復(fù)雜性如何導(dǎo)致經(jīng)驗縮放律。這一視角與表征復(fù)雜度相關(guān)，因為兩者都將數(shù)據(jù)復(fù)雜性與能良好解釋數(shù)據(jù)的緊湊模型的規(guī)模聯(lián)系起來。但二者在關(guān)鍵方面存在差異：PAC-Bayes 表述關(guān)注的是存在某個小型參考模型能在分布內(nèi)取得良好性能，而表征復(fù)雜度則刻畫了計算受限觀察者可提取的結(jié)構(gòu)信息量，并通過一個顯式計入模型獲取成本的兩部分碼進行形式化。此外，我們的主要興趣并非刻畫分布內(nèi)泛化，而是利用表征復(fù)雜度來衡量數(shù)據(jù)在超越監(jiān)督學(xué)習(xí)場景中的內(nèi)在價值。

相關(guān)地，Hutter（2021）表明，在對數(shù)據(jù)生成分布做出特定假設(shè)時，冪律學(xué)習(xí)曲線會自然出現(xiàn)，這說明數(shù)據(jù)本身的屬性可塑造經(jīng)驗縮放行為。盡管這類工作側(cè)重于解釋觀察到的學(xué)習(xí)動態(tài)而非定義復(fù)雜性度量，但它同樣強調(diào)了數(shù)據(jù)結(jié)構(gòu)在決定學(xué)習(xí)結(jié)果中的作用。

這些關(guān)于數(shù)據(jù)復(fù)雜性的視角可視為“粗粒化”（coarse graining）的實例，即尋求一種壓縮表示，同時保留某種“相關(guān)”結(jié)構(gòu)。典型例子是信息瓶頸（Information Bottleneck）框架，它將粗粒化形式化為壓縮與保留關(guān)于相關(guān)變量信息之間的權(quán)衡（Tishby 等, 2000）。表征復(fù)雜度與此視角一致，但不同于通過任務(wù)變量或測試可區(qū)分性來定義“相關(guān)性”，它衡量的是計算受限學(xué)習(xí)者可提取的結(jié)構(gòu)信息量，并顯式計入獲取模型的成本。

更廣泛地說，我們的工作與若干探討資源約束如何根本性改變“簡潔性”與“可學(xué)習(xí)性”概念的研究相關(guān)。在算法信息論中，Schmidhuber（2002）提出了“速度先驗”（speed prior），用一個可計算的半測度替代 Solomonoff 的通用先驗，該半測度同時偏好更短的程序長度和更小的計算時間，從而將計算資源直接納入簡潔性的定義。在學(xué)習(xí)理論中，相關(guān)研究表明，計算限制可直接影響從數(shù)據(jù)中能學(xué)到什么。例如，在稀疏 PCA 檢測問題中，Berthet 和 Rigollet（2013）證明：盡管存在信息論意義上樣本效率最優(yōu)的算法，但在廣泛采用的平均情況硬度假設(shè)下，任何多項式時間算法必然需要更多數(shù)據(jù)。僅內(nèi)存和空間約束本身也能定性地改變可學(xué)習(xí)性。Steinhardt 等（2016）表明，即使目標(biāo)概念本身具有非常簡潔的描述，限制學(xué)習(xí)者的內(nèi)存也會顯著增加所需數(shù)據(jù)量。他們指出奇偶函數(shù)（parity functions）是這種張力的一個典型例子。Raz（2018）后來通過證明：任何內(nèi)存低于二次方的學(xué)習(xí)者都需要指數(shù)級樣本才能從隨機樣例中學(xué)習(xí)奇偶函數(shù)，從而解決了這一猜想。

原文鏈接： https://arxiv.org/pdf/2601.03220