From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence

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

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è)觀察者具有無限的計(jì)算能力，且未能聚焦于“有用的信息”內(nèi)容。

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

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

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

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

我們還提出了若干實(shí)用的 epiplexity 估計(jì)方法，實(shí)驗(yàn)證明這些方法能夠：

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

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

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

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

悖論 1：信息無法通過確定性過程增加。
對于香農(nóng)熵和柯爾莫哥洛夫復(fù)雜度而言，確定性變換都無法有意義地增加一個(gè)對象的信息內(nèi)容。然而，我們卻使用偽隨機(jī)數(shù)生成器來制造隨機(jī)性，合成數(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ù)雜度的一個(gè)共同性質(zhì)是，總信息含量在因式分解順序上保持不變：先觀察 X 再觀察 Y 所獲得的信息，與先觀察 Y 再觀察 X 是相同的。另一方面，大語言模型（LLMs）在左至右排列的英文文本上學(xué)習(xí)效果更好，而非逆序文本，這揭示了一種“時(shí)間之箭”（Papadopoulos 等，2024；Bengio 等，2019）；同時(shí)，密碼學(xué)正是建立在某些函數(shù)在一個(gè)方向上計(jì)算困難、而在另一方向上容易預(yù)測的基礎(chǔ)之上。

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

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

我們的定義捕捉到這樣一個(gè)直覺：一個(gè)對象既包含隨機(jī)、本質(zhì)上不可預(yù)測的信息（熵），也包含可預(yù)測的結(jié)構(gòu)化信息——這種結(jié)構(gòu)化信息使觀察者能夠通過識別模式實(shí)現(xiàn)泛化（epiplexity）。在圖 1（左）中，我們展示了這種區(qū)分。在頂部一行，我們展示高度冗余且重復(fù)的代碼與簡單的顏色漸變，它們無論結(jié)構(gòu)還是隨機(jī)性方面都幾乎不含信息內(nèi)容。在中間一行，我們展示某個(gè)算法的內(nèi)部機(jī)制及動物圖片，它們呈現(xiàn)出元素間復(fù)雜的長程相互依賴關(guān)系，模型可從中學(xué)習(xí)復(fù)雜的特征和子電路，即使對不同任務(wù)也有幫助。相比之下，在底部一行，我們展示的是幾乎沒有結(jié)構(gòu)的隨機(jī)數(shù)據(jù)：隨機(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ù)雜特征或電路。

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

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

為建立直觀理解，我們探索了一系列現(xiàn)象，并提供了實(shí)驗(yàn)證據(jù)，說明那些現(xiàn)有信息論工具難以解釋、卻能自然被 epiplexity 容納的行為。我們展示了信息可通過純粹的計(jì)算過程被創(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)驗(yàn)上取得成功（第6節(jié)）。綜合來看，我們的結(jié)果澄清了最初提出的幾個(gè)問題：數(shù)據(jù)的信息內(nèi)容可以在不依賴特定任務(wù)的前提下進(jìn)行比較；新信息可通過計(jì)算被創(chuàng)造；模型可以學(xué)到比其生成過程本身所含更多的信息。

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

2 背景

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

2.1 一個(gè)對象“隨機(jī)”意味著什么？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 最小描述長度原則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 測量 Epiplexity 和時(shí)間受限熵

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

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

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

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

由于直接在程序空間中搜索是不可行的，我們將注意力集中在由神經(jīng)網(wǎng)絡(luò)參數(shù)化的概率模型上，因?yàn)樗鼈冊诟黝悢?shù)據(jù)模態(tài)上均表現(xiàn)出強(qiáng)大的經(jīng)驗(yàn)壓縮能力（MacKay, 2003; Goldblum 等, 2023; Delétang 等, 2023; Ballé 等, 2018），并能捕捉最相關(guān)的機(jī)器學(xué)習(xí)現(xiàn)象。一種樸素的方法是讓 P 直接存儲神經(jīng)網(wǎng)絡(luò)的架構(gòu)與權(quán)重，并在給定數(shù)據(jù)上對其進(jìn)行評估，但這種方法會顯著高估權(quán)重中的信息含量，尤其對于在相對少量數(shù)據(jù)上訓(xùn)練的大模型而言。取而代之的是，我們將采用一種更高效的方法，通過編碼生成權(quán)重的訓(xùn)練過程來實(shí)現(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)，代價(jià)是評估起來更困難。幸運(yùn)的是，這兩種方法在不同數(shù)據(jù)集上的 epiplexity 排名通常相當(dāng)接近（見第 4.3 節(jié)）。

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

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

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

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

4.3 兩種方法的比較與實(shí)用建議

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

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

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

5 信息的三個(gè)表面悖論

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

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

那么，我們?nèi)绾握{(diào)和這一事實(shí)與像 AlphaZero (Silver 等, 2018) 這樣的算法？AlphaZero 能在一個(gè)封閉環(huán)境中僅靠一個(gè)小的確定性程序運(yùn)行國際象棋游戲，從中提取出關(guān)于游戲、不同開局、棋子在不同位置的相對價(jià)值、戰(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ù)的過程原則上可以在大型計(jì)算機(jī)上被模擬到足夠精度，那么所有數(shù)據(jù)都可以被等價(jià)地替換為合成數(shù)據(jù)。對于從給定模型和提示中采樣并經(jīng)過變換產(chǎn)生的實(shí)用合成數(shù)據(jù)，這種采樣是通過偽隨機(jī)數(shù)生成器完成的，從而使整個(gè)變換過程成為確定性的。如果我們把 f f 視為我們用來生成合成數(shù)據(jù)的變換，而 x x 是我們最初擁有的有限真實(shí)數(shù)據(jù)，這些不等式似乎非常具體地指出：我們的合成數(shù)據(jù)除了模型和訓(xùn)練數(shù)據(jù)外，沒有添加任何額外信息。

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

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

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

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

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

作為一個(gè)推論，我們證明不存在任何多項(xiàng)式時(shí)間的概率模型，能夠滿足單向函數(shù)前向方向的貝葉斯定理（見定理26）。在這些理論結(jié)果的基礎(chǔ)上，我們實(shí)證地考察了單向函數(shù)在時(shí)間約束熵上的差距，以及在預(yù)測國際象棋數(shù)據(jù)時(shí)兩種排序方式下熵和表征復(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)建一個(gè)顯式的RASP-L (Zhou et al., 2023; Weiss et al., 2021) 程序來證明這一點(diǎn)。如圖4(a)所示，該模型在前向方向上達(dá)到了香農(nóng)熵（灰色），但在反向方向上存在持續(xù)的差距。

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

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

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

5.3.1 歸納（Induction）

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

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

“你正在讀一部謀殺懸疑小說，文本在某個(gè)時(shí)刻揭示了兇手的身份?！绻Ｐ湍軌蝾A(yù)測出[這個(gè)姓名]，那么它必定已經(jīng)從所提供的證據(jù)中推斷出[誰是兇手]?！保⊿utskever, 2019）

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

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

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

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

歸納容易：隨機(jī)馬爾可夫鏈

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

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

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

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

在圖6中，我們通過訓(xùn)練一個(gè)變換器模型來預(yù)測ECA規(guī)則54（一種產(chǎn)生復(fù)雜模式的IV類規(guī)則）的迭代動力學(xué)，實(shí)證地展示了涌現(xiàn)現(xiàn)象。與康威生命游戲類似，計(jì)算能力充足的模型可以通過直接迭代每一步規(guī)則來精確模擬動力學(xué)——這是一種描述長度很短的暴力求解方案。然而，計(jì)算資源受限的模型無法承擔(dān)這種方法，而必須轉(zhuǎn)而學(xué)習(xí)涌現(xiàn)的模式（例如滑翔機(jī)及其碰撞規(guī)則），從而近似地繞過不可行的精確模擬。暴力求解方案可以通過學(xué)習(xí)自回歸展開中間ECA狀態(tài)（而非直接預(yù)測最終狀態(tài)）自然實(shí)現(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é)提供了實(shí)驗(yàn)細(xì)節(jié)。

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

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

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

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

在互聯(lián)網(wǎng)規(guī)模數(shù)據(jù)上進(jìn)行預(yù)訓(xùn)練已帶來了顯著的分布外（OOD）泛化能力，然而對這一現(xiàn)象的深入理解仍然不足。什么樣的數(shù)據(jù)能提供最佳信號以實(shí)現(xiàn)廣泛泛化？為什么在文本數(shù)據(jù)上進(jìn)行預(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ù)測得有多好。兩個(gè)在不同語料庫上訓(xùn)練的模型可能達(dá)到相同的分布內(nèi)損失，但在遷移到OOD任務(wù)時(shí)的能力卻大相徑庭。這是因?yàn)閾p失僅捕捉了殘余的不可預(yù)測性——對應(yīng)于時(shí)間約束熵——而并未反映模型為達(dá)到該損失所內(nèi)化的可復(fù)用結(jié)構(gòu)量。表征復(fù)雜度恰好衡量了這一缺失的成分：即學(xué)習(xí)到的程序中所包含的信息量。直觀地說，損失反映了數(shù)據(jù)在模型眼中看起來有多“隨機(jī)”，而表征復(fù)雜度則反映了模型必須習(xí)得多少結(jié)構(gòu)才能解釋掉其中的非隨機(jī)部分。如果OOD泛化依賴于復(fù)用所學(xué)機(jī)制，而非僅僅記憶表面統(tǒng)計(jì)特征，那么表征復(fù)雜度就自然成為理解預(yù)訓(xùn)練數(shù)據(jù)與OOD遷移之間關(guān)系的一個(gè)恰當(dāng)視角。

作為一個(gè)啟發(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ǔ)上，對兩個(gè)下游任務(wù)進(jìn)行微調(diào)：(1) 解國際象棋殘局題（chess puzzles），即給定一個(gè)棋盤局面，模型需預(yù)測最優(yōu)的下一步走法（Burns 等, 2023）；(2) 預(yù)測“厘兵”（centipawn）評估值，即模型根據(jù)FEN記譜法對局面優(yōu)勢進(jìn)行量化評估——這相比預(yù)訓(xùn)練中學(xué)到的“預(yù)測下一步走法”任務(wù)構(gòu)成了更顯著的分布偏移。實(shí)驗(yàn)細(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ù)（如厘兵評估）中。

該例子反映了一個(gè)更普遍的原則：表征復(fù)雜度衡量的是模型從數(shù)據(jù)中提取并編碼到權(quán)重中的可學(xué)習(xí)結(jié)構(gòu)信息量，而這正是可遷移到新任務(wù)的信息來源，因此表征復(fù)雜度是衡量OOD泛化潛力的一個(gè)合理指標(biāo)。然而，我們強(qiáng)調(diào)，更高的表征復(fù)雜度并不能保證在任意特定任務(wù)上獲得更好的泛化效果：表征復(fù)雜度衡量的是結(jié)構(gòu)信息的總量，而不涉及其具體內(nèi)容。一個(gè)在高表征復(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)練方面具有獨(dú)特的優(yōu)勢：不僅有助于提升分布內(nèi)性能（如語言理解能力，Radford 等, 2019），還能有效遷移到分布外任務(wù)，例如機(jī)器人控制（Ahn 等, 2022）、形式化定理證明（Song 等, 2024）以及時(shí)間序列預(yù)測（Gruver 等, 2023）。盡管其他模態(tài)（如圖像和視頻）也提供了同樣海量的信息（以原始字節(jié)數(shù)衡量），但在這些數(shù)據(jù)上進(jìn)行預(yù)訓(xùn)練通常無法帶來類似廣泛的能力提升。

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

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

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

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

預(yù)訓(xùn)練語言模型的一個(gè)關(guān)鍵步驟是設(shè)計(jì)預(yù)訓(xùn)練數(shù)據(jù)的構(gòu)成，但目前尚缺乏對此步驟的明確指導(dǎo)原則?，F(xiàn)有的數(shù)據(jù)混合方案通常通過大量試錯(cuò)法設(shè)計(jì)，并依賴于“多樣性”或“高質(zhì)量”等啟發(fā)式準(zhǔn)則。更重要的是，比較不同訓(xùn)練數(shù)據(jù)的主要方式是通過保留數(shù)據(jù)集的困惑度指標(biāo)以及下游任務(wù)表現(xiàn)。然而，這些程序極易受到數(shù)據(jù)污染、對有限下游評估任務(wù)的過擬合以及古德哈特法則的影響。畢竟，沒有任何一套下游評估任務(wù)能夠足夠全面地真實(shí)捕捉通用語言模型在現(xiàn)實(shí)世界中會遇到的任務(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ù)雜度是一致的，因?yàn)樗鼘?dǎo)致?lián)p失曲線下方的面積更大。我們假設(shè)，他們提出的算法——自適應(yīng)數(shù)據(jù)優(yōu)化（ADO）——無意中實(shí)現(xiàn)了更高的表征復(fù)雜度。Jiang 等人（2025）的實(shí)驗(yàn)是在僅解碼器的變換器模型上進(jìn)行的，該模型擁有13億（1.3B）參數(shù)，在來自 Pile 數(shù)據(jù)集（Gao 等, 2020）的1250億（125B）個(gè)標(biāo)記上進(jìn)行訓(xùn)練。模型在一套包含7項(xiàng)零樣本下游任務(wù)以及兩個(gè)OOD驗(yàn)證數(shù)據(jù)集（SlimPajama（Soboleva 等, 2023）和 FineWeb（Penedo 等, 2024））上進(jìn)行評估。

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

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

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

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

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

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

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

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

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

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

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

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

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