在 2025 年，對齊研究中心 (ARC) 在概念和理論方面的進展，是我自 2022 年首次實習以來見過最快的一年。這些進展大多源於我們將目標重新定位於一個更具體的方向：在理解神經網路輸出方面超越隨機採樣 (outperforming random sampling)。與我們先前的目標相比，這個目標的優點在於更加具體，且與實際應用結合得更直接。

本篇文章的目的在於：

• 從防止災難性 AI 失調（misalignment）的角度，解釋並說明我們「超越採樣」議程的動機。
• 介紹我們稱之為「匹配採樣原則 (Matching Sampling Principle, MSP)」的概念，作為支撐我們研究議程之信念的半形式化表述，並討論我們為何相信這一原則。
• 討論我們在某些特定情境下（如隨機 MLP 和受訓過的雙層 MLP）實現匹配採樣所取得的進展。

另外：我們正在招聘！如果你對本文描述的研究方向感到興奮，歡迎申請加入 ARC！

超越採樣：防止 AI 失調的一步

考慮以下嘗試對齊 AI 模型 $M$ 的簡單方案，該模型將輸入 $x$ 映射到輸出 $y$：

• 建立一個「災難檢測器」$C$，將模型輸出 $y$ 分類為「災難性的」(1) 或「非災難性的」(0)。^([1]) 你可以透過例如將多個 GPT-5 組成的審議系統搭建在一起，仔細調查模型是否在做任何可疑的事情來實現這一點。
• 使用災難檢測器進行對抗訓練。具體而言，這意味著：
  • 優化輸入 $x$ 的機率分佈 $D$，以最大化 $E_{x \sim D}[C(M(x))]$。
  • 同時，優化 $M$ 以最小化 $E_{x \sim D}[C(M(x))]$。

我認為這是對齊計劃的一個很好的起點，但其本身並非一個完整的計劃。它至少存在兩個問題：

1. 即使工程做得再好，按上述方式建立的災難檢測器也會是不完美的。如果 $M$ 比 $C$ 更「聰明」，它就能找到方法欺騙 $C$，讓 $C$ 對災難性輸出給出低災難機率。
2. 即便災難檢測器是完美的，目前也不清楚如何足夠高效地計算 $E_{x \sim D}[C(M(x))]$ 以使該方案奏效。^([2]) 最直接的方法是透過隨機採樣 $x \sim D$ 來估計這個期望值，但如果災難在 $D$ 中極其罕見，這種方法會慢得驚人。

（還有其他技術問題，^([3]) 但這兩個似乎是最難克服的。）

我們相信 ARC 的技術研究議程能夠解決這兩個問題。然而，問題 #1 大多超出了本文的討論範圍（儘管我會在腳註中簡要描述我們計劃的方法^([4])）。本文的目的在於詳細解釋我們希望如何解決問題 #2。

理解結構有助於超越採樣

ARC 的目標是能夠比單純從 $D$ 中提取隨機樣本更準確地估計 $E_{x \sim D}[C(M(x))]$。我們相信這可以透過理解 $M$、$C$ 和 $D$ 的結構來實現。

這裡有一個簡單的例子來說明這一點。假設透過理解 $C$ 的內部機制，我們注意到 $C(y)$ 是三個謂詞 $P_1(y), P_2(y), P_3(y)$ 的交集——換句話說，$C$ 輸出 1 當且僅當 $P_1, P_2, P_3$ 對於 $M$ 的輸出皆為真。

並進一步假設，我們理解 $M$ 和 $D$ 的結構，從而得知對於 $x \sim D$ 而言，$P_1(M(x)), P_2(M(x)), P_3(M(x))$ 是獨立事件。^([5])

利用這種結構性理解，我們可以估計 $E_{x \sim D}[C(M(x))] = \prod_{i=1}^3 E_{x \sim D}[P_i(M(x))]$。如果每個 $P_i$ 在 $D$ 上為真的機率是百萬分之一 ($10^{-6}$)，那麼我們可以估計 $E_{x \sim D}[C(M(x))] \approx 10^{-18}$。若要透過採樣獲得此估計值，大約需要 $10^{18}$ 個樣本。相比之下，我們的結構性理解讓我們只需約 $3 \cdot 10^6$ 個樣本就能估計出這個機率；如果我們對 $P_i$ 本身也有結構性理解，甚至可能做得更好。因此，結構性理解讓我們能比採樣更高效地估計期望值。

當然，這個例子過於簡化：在實踐中，我們需要理解比「輸出是三個獨立謂詞的交集」複雜得多的結構。但這個例子說明了一個核心觀點：對神經網路有詳細的機制性理解，能讓我們比單純的黑箱方法更好地估計其輸出的性質。

非人類的理解

當我們談論「理解 $M$、$C$ 和 $D$ 的結構」時，我們指的不是人類的理解。雖然像上述那樣的交集結構可以被人類理解，但我們相信，神經網路通常由極其複雜的數學結構組成，人類無法完全理解。

相反，我們設想對神經網路結構的解釋是用某種形式語言編寫的。這種解釋可能與神經網路本身一樣龐大，對人類來說也可能同樣難以理解。因此，我們的目標不是讓人類觀察結構並估計 $C(M(x))$ 的期望值。相反，目標是發明一種算法，該算法以該解釋為輸入，並基於該解釋估計 $C(M(x))$ 的期望值。

這與幾乎所有其他神經網路可解釋性研究形成了對比，後者的目標是對神經網路達成部分的人類理解。而我們的研究目標則是全面的算法理解。

在下一節中，我將詳細闡述這意味著什麼。

匹配採樣原則 (Matching Sampling Principle)

在本節中，我將更正式地描述我們希望透過獲得神經網路的結構性理解來實現的目標。雖然上面我談到了「超越」採樣，但在完全通用的情況下，我們只能希望「匹配」採樣的性能。換句話說，我們預期我們的算法在受訓神經網路的實際環境中的表現，將大幅超過我們能夠陳述和證明的最壞情況界限。有關此點的進一步討論，請參見下文。

我將首先嘗試對匹配採樣原則 (MSP) 進行初步陳述。正如我們將討論的，它並不完全嚴謹，但它傳達了核心直覺。

嘗試陳述 MSP：初探

為了陳述 MSP，我們將定義幾個符號：

• 我們使用符號 $M_\theta$ 來描述一個神經網路（或來自參數化家族的其他函數）。這裡，$M$ 表示神經網路的架構，$\theta$ 表示參數。具體而言，$M_\theta: {0, 1}^n \to \mathbb{R}$ 是一個將 $n$ 位元輸入 $x$ 映射到實數的函數。（請注意，此符號與前一節使用的符號不同；這裡的 $M_\theta$ 描述了上述神經網路與災難檢測器的複合函數 $C \circ M$。）
• 我們感興趣的是估計 $E_{x \sim {0, 1}^n}[M_\theta(x)]$，其中 $x$ 是均勻採樣的。^([6])
• 我們使用符號 $\pi$ 來描述 $M_\theta$ 的機制性解釋；$\pi$ 為我們提供了對 $M_\theta$ 的結構性理解，並允許我們估計其期望輸出。（這反映了 ARC 歷來 使用 字母 $\pi$ 的方式。）
• 我們使用符號 $G_M$ 來表示一個估計器（下標 $M$ 旨在強調不同的架構可能有不同的估計器）：$G_M$ 的輸入為參數 $\theta$、機制性解釋 $\pi$ 以及一個容差參數 $\varepsilon$。（如下所述，容差參數越小，$G_M$ 的估計越準確，但允許 $G_M$ 運行的時間也越長。）

有了這些符號，我們進行 MSP 的第一次陳述嘗試：

• 對於所有架構 $M$（帶有參數 $\theta$），存在一個估計器 $G_M$，使得：
• 對於所有參數 $\theta$，存在一個短的^([7])解釋 $\pi$（我們要求 $|\pi| \le O(|\theta|)$），使得：
• 對於所有容差參數 $\varepsilon > 0$，$G_M(\theta, \pi, \varepsilon)$ 滿足以下三個性質：
  • 它的運行時間為 $O(\frac{1}{\varepsilon^2} \text{Time}(M_\theta))$。
  • 它的誤差與採樣相比具有競爭力：$(G_M(\theta, \pi, \varepsilon) - E_{x \sim {0, 1}^n}[M_\theta(x)])^2 \le \varepsilon^2 \text{Var}{x \sim {0, 1}^n}[M\theta(x)]$。
  • 它是機制性的 (mechanistic)。

讓我們解析這三個要求：

• $G_M$ 需要在 $O(\frac{1}{\varepsilon^2} \text{Time}(M_\theta))$ 時間內運行。這是透過將 $1/\varepsilon^2$ 個隨機採樣的 $x$ 值投入 $M_\theta$ 運行來估計 $E_{x \sim {0, 1}^n}[M_\theta(x)]$ 所需的時間。
• $G_M$ 的均方誤差必須很小。具體而言，右側代表透過取 $1/\varepsilon^2$ 個 $M_\theta(x)$ 樣本的經驗平均值所產生的預期均方誤差。
• $G_M$ 是機制性的。我們還沒有定義「機制性」，所以這一點需要詳細說明。

什麼使算法具有「機制性」？

我們沒有「機制性」的形式化定義。但通俗地說，我們是指 $G_M$ 基於 $M_\theta$ 的結構，演繹式地 (deductively) 估計 $M_\theta$ 的期望輸出。這與估計 $M_\theta$ 期望輸出的基於採樣的算法形成對比，後者基於歸納式 (inductive) 推理。機制性地估計期望輸出涉及尋找期望輸出之所以如此的原因；而基於採樣的算法僅僅是推斷原因的存在，而沒有學到任何關於原因的信息。

為了說明這種差異，假設給予 $G_M$ 的解釋 $\pi$ 是一個簡單的啟發式論點（例如均值傳播——參見 此處 的 §D.2），該論點表明 $E[M_\theta] = 0$，但在其他方面對 $M_\theta$ 的結構不具備信息量。進一步假設 $G_M$ 在一百個輸入 $x \in {0, 1}^n$ 上計算 $M_\theta(x)$，發現這一百個輸入的 $M_\theta(x)$ 均為 1。那麼 $G_M$ 應該返回 $100 / 2^n$：這是因為它知道在它檢查的一百個輸入上 $M_\theta(x) = 1$，但它沒有看到任何結構性證據表明 $M_\theta$ 在這一百個輸入上的行為與它尚未檢查的輸入有任何關聯。相比之下，一個檢查相同一百個輸入的基於採樣的估計器會返回 1，隱含地假設這些輸入具有代表性。

（如果 $M_\theta$ 確實總是返回 1，那麼我們相信存在一個關於此事實的簡短解釋；但除非給予 $G_M$ 這個解釋，否則它不能輸出 1。）

在我們之前的一些工作中，我們討論了協方差傳播 (covariance propagation)：將 $M_\theta$ 的每一層相繼建模為多元正態分佈。^([8]) 協方差傳播（以及相關方法，如均值傳播和累積量傳播）是機制性的，因為它根據 $M_\theta$ 的結構推導出估計值。^([9]) 更廣泛地說，演繹-投影估計器 (deduction-projection estimators)——即透過從某些參數化類別中尋找最佳擬合模型來相繼建模 $M_\theta$ 每一層的估計器——是機制性的。

一個簡單（雖然不完全正確）的判斷估計算法是否為演繹式的啟發式方法，是看它是否避免了任何隨機或偽隨機採樣。這個啟發式方法對於理解本文應該足夠了。

（關於機制性估計的更多內容，請參見我們早期的論文 "Formalizing the presumption of independence"^([10])，以及前 ARC 實習生 Gabe Wu 關於演繹-投影估計器的畢業論文。）

為什麼我們要求 $G_M$ 是機制性的？

這有多個原因；在之前的部落格文章中，我們討論了機制性估計如何幫助我們檢測機制性異常。但就本文而言，原因非常直接：在 $M_\theta$ 具有大量結構的情況下，我們認為如果給予解釋 $\pi$ 來解釋該結構，$G_M$ 可以大幅超越採樣（如上文所述）。

因此，通俗地說，我們的希望是，如果我們找到一個既 (a) 是機制性的，又 (b) 在所有 $\theta$ 情況下表現至少與採樣一樣好的 $G_M$，那麼對於具有大量結構的參數 $\theta$（如受訓過的神經網路），它將大幅超越採樣。

MSP 背後的直覺

採樣是一個非常強大的工具，因為（以高機率）隨機抽取的樣本具有代表性，因此基於採樣的估計值（以高機率）不會偏差太遠。鑑於此，為什麼我們認為機制性估計算法可以與採樣競爭？

假設 $M_\theta: {0, 1}^{100} \to {0, 1}$ 是一個布林電路。進一步假設，一個簡單的啟發式論點（如均值傳播）表明 $M_\theta$ 的平均輸出為 0.5，但實際上其平均輸出約為 0.49（與 0.5 的差距大到不可能是偶然發生的）。基於採樣的算法在大約 10,000 個樣本後可以發現這種差異；但機制性算法能做什麼呢？

既然這種差異不可能是偶然發生的，那麼一定存在解釋這種差異的結構。為了說明，讓我們考慮兩種結構。

第一種，也許這種差異是由於不同的門電路重複使用相同的輸入，從而導致電路不同部分之間存在非平凡的相關性。^([11]) 在這種情況下，$\pi$ 應該能夠指出這種結構，使 $G_M$ 理解這種差異（甚至不需要在 $M_\theta$ 上運行任何輸入）。

第二種，也許只有前 10 個輸入位元對電路的輸出有影響（或許 $M_\theta$ 完全忽略了最後 90 個輸入位元，或者由於複雜的結構原因，它們最終不影響輸出）。然後——純屬巧合——在 1024 個可能的 10 位元輸入中，$M_\theta$ 僅對 49% 的輸入輸出 1。在這種情況下，$\pi$ 指出 $M_\theta$ 僅取決於前 10 個輸入位元；它不會指出 $M_\theta$ 對其中的 49% 輸出 1，因為那是 $M_\theta$ 無法解釋的隨機性的一部分。^([12]) 相反，$G_M$ 必須利用其分配的時間來檢查這 1024 個輸入上的 $M_\theta$ 值，從而確定這一事實。

（如果 $\varepsilon$ 大到 $G_M$ 沒有足夠的運行時間來檢查所有 1024 個輸入怎麼辦？在這種情況下，它應該盡可能多地檢查，並將其餘部分估計為 50/50。這仍然會優於採樣！）

更廣泛地說，直覺是：了解 $M_\theta$ 的結構為 $G_M$ 提供了所需的信息，使其表現不遜於隨機採樣。如果 $G_M$ 在讀取 $\pi$ 後表現仍然不如隨機採樣，那只能是因為 $\pi$ 沒有提供對 $M_\theta$ 的完整結構性解釋。^([13])

為什麼只是「匹配」採樣？

既然有上述直覺認為理解結構可以超越採樣，為什麼我們只追求「匹配」採樣的性能？

考慮上述例子，其中 $M_\theta$ 的平均輸出取決於 1024 個有效的隨機計算，並假設 $1/\varepsilon^2 = 512$：這足以讓 $G_M$ 計算 1024 個輸入中 512 個輸入的 $M_\theta$ 輸出。在這種情況下，我們預期 $G_M$ 和採樣的均方誤差都在 $1/512$ 數量級：$G_M$ 的預期均方誤差會稍微低一些，但不會有戲劇性的差別。

一般來說，我們預期通常會存在一個 $\varepsilon$ 值範圍，在該範圍內，最佳機制性估計僅比基於採樣的估計略好。^([14]) 因此，對於某些參數 $\theta$ 和容差參數 $\varepsilon$，我們只期望能夠匹配（或可能略微超越）採樣，而不是強烈超越採樣。

然而，如上文所述，我們預期如果我們的機制性估計器在所有情況下都能匹配採樣的性能，那麼在結構化情況（如受訓過的神經網路）下，它將大幅超越採樣，至少對於非極小的 $\varepsilon$ 值是如此。我們預期可以利用這一點來輔助引言中描述的那種對抗訓練過程。

一個問題：$\pi$ 可以直接告訴 $G_M$ 答案

如前所述，我們第一次嘗試陳述 MSP 並不完全嚴謹。MSP 的想法是讓 $\pi$ 描述 $M_\theta$ 的結構。然而，為了滿足上述 MSP 陳述，$\pi$ 可以直接寫下 $E_{x \sim {0, 1}^n}[M_\theta(x)]$ 的值。然後，$G_M$ 就可以直接輸出該值。

為了修正這個問題，我們觀察到，如果 $G_M$ 理解 $M_\theta$ 的結構，那麼它應該能夠至少像採樣一樣準確地回答關於 $M_\theta$ 的各種問題——而不僅僅是其期望值——只要這些問題不是被對抗性地選擇的。為了形式化這個想法，我們將修改 $M_\theta$ 的類型簽名，使其接受兩個輸入 $(c, x)$（這裡 $c$ 代表「上下文」），並要求 $G_M$ 能夠對於隨機選擇的 $c$ 準確估計 $E_x[M_\theta(c, x)]$。^([15]) 這一改變給了我們一個我們願意支持的 MSP 陳述。

我們實際的 MSP 陳述

這是 ARC 的核心「匹配採樣原則」(MSP)：

• 對於所有將對 $(c \in {0, 1}^{n_c}, x \in {0, 1}^{n_x})$ 映射到 $\mathbb{R}$ 的架構 $M$（帶有參數 $\theta$），存在一個將元組 $(\theta, \pi, c, \varepsilon)$ 映射到 $\mathbb{R}$ 的估計器 $G_M$，使得：
• 對於所有參數 $\theta$，存在一個短的解釋 $\pi$ ($|\pi| \le O(|\theta|)$)，使得：
• 對於所有容差參數 $\varepsilon > 0$，$G_M(\theta, \pi, c, \varepsilon)$ 滿足以下三個性質：
  • 它的運行時間為 $O(\frac{1}{\varepsilon^2} \text{Time}(M_\theta))$。
  • 它的誤差與採樣相比具有競爭力，在隨機 $c$ 的平均意義下：$E_c[(G_M(\theta, \pi, c, \varepsilon) - E_x[M_\theta(c, x)])^2] \le \varepsilon^2 E_c[\text{Var}x[M\theta(c, x)]]$，其中 $c \sim {0, 1}^{n_c}$ 且 $x \sim {0, 1}^{n_x}$。
  • 它是機制性的。

（就像之前一樣，這個陳述並非完全形式化，因為有非形式化的「機制性」限定詞。但在實踐中，我們對於什麼算作「機制性」有足夠強烈的見解，使得這個陳述足以指導我們的研究。）

MSP 的一個有趣特例是當 $M_\theta$ 編碼一個通用圖靈機時。參見附錄進行討論。

一個重要的變體：可尋找的解釋

雖然上述 MSP 陳述在理論上最為簡潔，但就其本身而言並非非常有用。這是因為它沒有提到能夠找到解釋 $\pi$；如果我們找不到充足的解釋，僅僅知道它存在又有什麼用呢？

這引導我們得出以下另一種陳述，我們稱之為 MSP 的「訓練與解釋 (train and explain)」表述：

• 對於所有將對 $(c \in {0, 1}^{n_c}, x \in {0, 1}^{n_x})$ 映射到 $\mathbb{R}$ 的架構 $M$（帶有參數 $\theta$），存在一個將元組 $(\theta, \pi, c, \varepsilon)$ 映射到 $\mathbb{R}$ 的估計器 $G_M$，使得：
• 對於所有將隨機種子 $s \in {0, 1}^r$ 映射到參數 $\theta$ 的「訓練」算法 $T$，存在一個將隨機種子 $s \in {0, 1}^r$ 映射到解釋 $\pi$ 的「解釋」算法 $E$，且 $\text{Time}(E) \le O(\text{Time}(T))$，使得：
• 對於所有容差參數 $\varepsilon > 0$，$G_M(\theta, \pi, c, \varepsilon)$ 滿足以下三個性質：
  • 它的運行時間為 $O(\frac{1}{\varepsilon^2} \text{Time}(M_\theta))$。
  • 它的誤差與採樣相比具有競爭力，在隨機 $c$ 和 $s$ 的平均意義下：$E_{c, s}[(G_M(T(s), E(s), c, \varepsilon) - E_x[M_{T(s)}(c, x)])^2] \le \varepsilon^2 E_{c, s}[\text{Var}x[M{T(s)}(c, x)]]$，其中 $s \sim {0, 1}^r, c \sim {0, 1}^{n_c}, x \sim {0, 1}^{n_x}$。
  • 它是機制性的。

在這個陳述中，將 $T$ 視為用於尋找 $\theta$ 的學習算法（例如 SGD），將 $s$ 視為訓練期間使用的隨機位元（隨機初始化和每一步訓練數據的隨機選擇）是很有幫助的。那麼，$E$ 就是用於尋找 $\theta$ 的機制性解釋的算法：直覺上，它與 $T$ 「並行」工作，觀察訓練過程並「構建」解釋 $\pi$，其方式反映了 $T$ 透過迭代修改 $\theta$ 以獲得越來越低的損失來「構建」$\theta$ 中的結構。

請注意，我們的核心 MSP 陳述是「訓練與解釋」表述的一個特例，其中 $T$ 和 $E$ 在計算上都是不受限的（因此 $T$ 可以選擇最壞的參數 $\theta$，而 $E$ 可以選擇最有幫助的建議 $\pi$）。

一般來說，我們認為對於施加在 $T$ 上的任何計算限制（例如時間或內存），都存在一個具有相同計算限制的相應 $E$，能夠找到充足的解釋 $\pi$。如果我們是正確的，那麼這可能為我們提供一種策略，在支付相對較小的對齊稅 (alignment tax) 的同時，高效地計算受訓神經網路的性質（如災難機率）。（如果尋找 $\pi$ 的時間與尋找 $\theta$ 的時間一樣長，那就是 100% 的對齊稅：為了避免災難，這是一個很小的代價。）

另一個修改：去掉 $\varepsilon$

事實證明，MSP 可以在不引用容差參數的情況下進行陳述，方法是將樣本數量納入架構中。詳情請參見此附錄。

我們目前的進展

在 2025 年期間，ARC 在 MSP 的幾個不同方向上取得了進展。具體而言：

• 我們有一種機制性算法，在估計隨機選擇的半空間交集的大小時，（在理論和實踐上）能與採樣競爭。^([16]) 我們還將算法推廣到解決其他一些問題，例如估計隨機 CNF 的滿足機率，或隨機矩陣的 積和式 (permanent)。
• 我們相信我們有一種機制性算法，在估計隨機 MLP 在高斯輸入上的期望輸出時，能與採樣競爭。（我們已有競爭力的經驗演示，以及一個正在擴展為完整證明的證明草稿。）
• 我們在開發一種機制性算法方面取得了實質性進展，該算法在估計高斯輸入下雙層 MLP 的期望輸出時能與採樣競爭，其中 MLP 的第二層是透過梯度下降訓練的。

我們的結果尚未準備好發表，但希望在未來幾個月內完成。在本節中，我將簡要總結這些結果，並討論未來工作中最有趣的方向。

隨機半空間的交集

我們在「匹配採樣」框架中解決的第一個問題是機制性地估計隨機半空間交集的體積。雖然這有點像是一個玩具問題，但解決它並非易事，我們從中學到了很多。

問題陳述

尋找一個算法 $G$，其輸入為單位向量 $v_1, \dots, v_k \in \mathbb{R}^n$ 和一個容差參數 $\varepsilon$，並機制性地估計隨機選擇的單位向量 $x$ 與所有 $v_1, \dots, v_k$ 的點積皆為非負的機率，使得：

• $G$ 的預期均方誤差（在隨機選擇的 $v_1, \dots, v_k$ 上）小於樸素採樣算法的預期均方誤差（即採樣 $1/\varepsilon^2$ 個隨機向量 $x$ 並輸出點積為非負的經驗比例）。
• $G$ 的運行時間與樸素採樣算法的運行時間相比具有競爭力，即 $O(kn/\varepsilon^2)$。^([17])

請注意，這是 MSP 的一個特定案例，其中 $\theta$ 是空字串；$c = (v_1, \dots, v_k)$；且 $M(c, x)$ 在對於所有 $t$ 都有 $x \cdot v_t \ge 0$ 時返回 1。（$x$ 和 $c$ 中每個向量的分佈在單位球面上是均勻的，而不是在位元字串上均勻分佈。）

由於 $\theta$ 是空的，在這種情況下沒有建議 $\pi$。儘管如此，我們認為我們對這個 MSP 實例的解決方案幫助我們朝著更廣泛地解決 MSP 邁進了一步。

（或者，這個問題可以被視為 MSP 的「訓練與解釋」版本的一個實例，其中 $\theta = (v_1, \dots, v_k)$，$c$ 為空，且訓練算法 $T$ 只是返回隨機向量。在這種情況下，解釋算法 $E$ 沒有時間進行任何有趣的計算，因此 $\pi$ 也可以是空的。）

解決方案草案

一句話總結，我們的解決方案是透過一次考慮一個向量 $v_t$ 來構建 $M(c, x)$ 的多項式逼近。

詳細來說，對於 $1 \le t \le k$，令 $h_t(x)$ 為當 $v_t \cdot x \ge 0$ 時輸出 1，否則輸出 0 的函數。讓我們定義 $H_{\le t}(x) := h_1(x) \dots h_t(x)$（因此 $M(c, x) = H_{\le k}(x)$）。我們將：

• 定義 $\tilde{H}_{\le 0}$ 為常數 1 函數。
• 對於所有 $1 \le t \le k$，計算 $\tilde{H}{\le t-1} h_t$ 的最佳低次多項式逼近 $\tilde{H}{\le t}$。最後，$\tilde{H}{\le k}$ 將是 $H{\le k}$ 的多項式逼近，我們將輸出精確期望值 $E[\tilde{H}_{\le k}]$ 作為我們對 $E_x[M(c, x)]$ 的估計。

更準確地說，這裡的「低次多項式」是指次數 $d$，其中 $d$ 是使得 $n^d \le 1/\varepsilon^2$ 的最大整數（事實證明，這是我們為了與採樣競爭所需的精度）。而「最佳低次多項式逼近」是指對於從單位球面抽取的 $x$，在均方誤差方面的最佳逼近。

為了使 $G$ 足夠高效，它需要能夠在 $n/\varepsilon^2$ 時間內計算出這個多項式逼近。將對 $\varepsilon$ 的依賴降低到 $1/\varepsilon^2$ 其實相當棘手。^([18]) 然而，我們透過在多項式的 埃爾米特基 (Hermite basis) 而非標準單項式基下工作，找到了一種足夠高效的算法。

我們還將這種方法推廣到比「隨機選擇的半空間交集」更廣泛的問題類別。粗略地說，我們可以應用我們的方法來估計對稱隨機函數的預期乘積（對於某種表示論意義上的對稱性）。我們用這種方法解決的具體問題包括：

• 估計 $k$-CNF 的滿足機率，其中每個文字 (literal) 都是隨機均勻選擇的。
• 估計矩陣的積和式，其中每個條目獨立地以 50% 的機率為 -1 或 1。

我們計劃在未來幾個月內發布算法細節及其推廣。

相關問題

雖然我們解決了這個特定的 MSP 實例，但對於一些相關的設定，我們還沒有解決方案：

• 非各向同性 (Non-isotropic) 半空間：如果 $v_1, \dots, v_k$ 不是從單位球面（或等效地，標準 $n$ 元正態分佈）中隨機均勻選擇，而是從某些其他 $n$ 元正態分佈中選擇呢？排除一些細節，我們相信如果 $v_1, \dots, v_k \sim N(\mu, aI_n + b\mu\mu^\top)$（對於標量 $a, b$ 和 $\mu \in \mathbb{R}^n$），我們已經解決了這個問題。但我們還沒有針對任意協方差矩陣 $\Sigma$ 的 $v_1, \dots, v_k \sim N(\mu, \Sigma)$ 的通用解決方案。
• 學習到的半空間：如果使用某種學習算法來訓練 $v_1, \dots, v_k$ 以最小化某個損失函數呢？是否存在一個我們可以與學習算法並行學習的解釋字串 $\pi$，能幫助我們估計半空間交集的大小？或者，也許設定仍然足夠簡單，即使半空間是學習到的，也不需要解釋？

隨機 MLP

在過去的幾個月裡，我們一直在處理一個更複雜的 MSP 實例：隨機 MLP。我們現在相信我們已經有了一個算法及其正確性和效率的證明，儘管我們仍在核實細節。我們也有經驗演示證明我們的算法與採樣相比具有競爭力。

問題陳述

考慮以下 MLP 架構：輸入大小為 $n$（假設 $n$ 非常大^([19])）；有 $k$ 個隱藏層（$k$ 是一個固定常數），每層寬度為 $n$；輸出是一個標量；每個隱藏層都有某種激活函數（例如 ReLU）。

尋找一個算法 $G$，其輸入為具有上述架構的 MLP 的權重 $W$ 和一個容差參數 $\varepsilon$，並機制性地估計該 MLP 在從 $N(0, I_n)$ 抽取的輸入上的期望輸出，使得：

• $G$ 的預期均方誤差（在獨立、正態分佈的^([20])權重上）小於樸素採樣算法的預期均方誤差（即採樣 $1/\varepsilon^2$ 個隨機輸入並輸出經驗平均輸出）。
• $G$ 的運行時間與樸素採樣算法的運行時間相比具有競爭力，即 $O(1/\varepsilon^2)$ 次前向傳播。

請注意，這是 MSP 的一個特定案例，其中 $\theta$ 是空字串；$c = W$；且 $M(W, x)$ 返回權重為 $W$ 的 MLP 在輸入 $x$ 上的輸出。（$x$ 和 $W$ 的每個分量均為高斯分佈。）

（與隨機半空間的情況類似，這個問題也可以被視為 MSP 的「訓練與解釋」版本的一個實例，其中 $\theta = W$，$c$ 為空，訓練算法 $T$ 只是返回隨機權重，且 $\pi$ 也可以是空的。）

解決方案草案

一句話總結，我們對這個問題的解決方案是累積量傳播 (cumulant propagation)，這是我們在 Formalizing the Presumption of Independence 附錄 D 中介紹的一種機制性估計算法。

累積量 (Cumulants) 是機率分佈的一種摘要統計量。粗略地說，累積量算子 $\kappa$ 接受一組隨機變數，並告訴你類似於它們的「多路相關性 (multi-way correlation)」的信息。例如，$\kappa(X)$ 是 $X$ 的均值；$\kappa(X, X)$ 是方差；$\kappa(X_1, X_2)$ 是 $X_1$ 和 $X_2$ 的協方差。

累積量傳播是一種方法，讓我們能根據第 $\ell-1$ 層的部分累積量列表，對神經網路第 $\ell$ 層的累積量做出猜測。（累積量列表越完整，猜測就越準確。）因此，我們的算法大致如下：

• 從輸入的累積量列表開始（這很容易，因為輸入是高斯的：每個輸入 $i$ 的 $\kappa(x_i, x_i) = 1$，所有其他累積量均為 0）。
• 使用累積量傳播對第 1 層激活值的累積量做出猜測，^([21]) 最高達到 $d$ 階累積量，^([22]) 其中 $d$ 是使得 $n^d < 1/\varepsilon^2$ 的最大整數。然後對第 2 層激活值執行相同操作，依此類推。
• 輸出我們對輸出均值（即一階累積量）的猜測。

（這個描述省略了許多細節，但傳達了主要思想。）

相關問題

我們非常有興趣找到一種方法來機制性地估計隨機循環神經網路 (RNN) 的平均輸出。我們相信這將比 MLP 設定困難得多，因為存在權重共享。（我們認為隨機 RNN 中可能出現有趣的結構，其機率遠高於隨機 MLP；這與 RNN 是圖靈完備的 這一事實有關。）我們認為，找到一個能解決 MSP「隨機 RNN」實例的算法，將構成朝著全方位解決 MSP 邁出的重大進展（更多討論見附錄）。

一個較短期的項目可能是將我們的解決方案適配到其他架構。我們能否解決窄 MLP（相對於無限寬度極限）的情況？隨機 CNN 呢？隨機 Transformer 呢？

訓練過第二層的雙層 MLP

在處理隨機 MLP 的同時，我們也一直在研究隱藏層非常寬且第二層權重經過訓練的雙層 MLP。這是我們首次認真嘗試受訓過的和/或最壞情況的實例——雖然我們還沒有完全解決它，但已經取得了實質性進展。

問題陳述

考慮以下 MLP 架構：輸入大小為 $n_0$；有一個大小為 $n_1$ 的隱藏層，其中 $n_1$ 非常大；輸出是一個標量；隱藏層和輸出層都有激活函數。

問題 1： 尋找一個算法 $G$，其輸入為上述架構 MLP 的權重 $(W, v)$（$W \in \mathbb{R}^{n_1 \times n_0}$ 包含第一層權重；$v \in \mathbb{R}^{n_1}$ 包含第二層權重）、一個解釋 $\pi$ 和一個容差參數 $\varepsilon$，並機制性地估計該 MLP 在從 $N(0, I_n)$ 抽取的輸入上的期望輸出，使得：

• 對於所有 $v$，$G$ 的預期均方誤差（在 $W$ 中獨立、正態分佈的權重上）小於樸素採樣算法的預期均方誤差（即採樣 $1/\varepsilon^2$ 個隨機輸入並輸出經驗平均輸出）。
• $G$ 的運行時間與樸素採樣算法的運行時間相比具有競爭力，即 $O(1/\varepsilon^2)$ 次前向傳播。

請注意，這是 MSP 的一個特定案例，其中 $\theta = v$；$c = W$；且 $M((W, v), x)$ 返回權重為 $(W, v)$ 的 MLP 在輸入 $x$ 上的輸出。

問題 2： 現在，假設 $v$ 透過 SGD 訓練以使 MLP 匹配某個目標函數。透過尋找一個輸入為 SGD 完整記錄並輸出 $\pi$ 的線性時間算法，來擴展問題 1 的解決方案。

這是 MSP 的「訓練與解釋」版本的一個特定案例，其中 $\theta = v$，且訓練算法 $T$ 是對任意目標函數使用平方損失的 SGD。

目前進展概覽

與隨機 MLP 的情況不同，我們不預期累積量傳播能奏效。這是因為對於最壞情況下的 $v$，最大的累積量不一定是低階的；因此，捨棄高階累積量可能無法產生良好的逼近。那麼我們能做什麼呢？

考慮將輸入映射到最終預激活值（即輸出，但在應用最終激活函數之前）的函數 $f: \mathbb{R}^{n_0} \to \mathbb{R}$。如果我們能找到 $f(x)$ 的累積量（即隨機輸入下最終預激活值的均值、方差等），那麼我們就能找到 MLP 輸出的均值。那麼我們如何估計這些累積量呢？

函數 $f$ 可以用輸入的高次、$n_0$ 元多項式很好地逼近。事實證明，有一種巧妙的方法可以將多元多項式的累積量表示為其在 埃爾米特基 下係數的無窮和。特別是，對於每個 $d$，$d$ 次係數可以寫在一個 $d$ 維的 $n_0 \times \dots \times n_0$ 張量中。（由於羅馬和希臘字母都用完了，我們決定將這個張量稱為 $\text{\huge ש}_d$。^([23])）那麼第 $d$ 個累積量就是由 $\text{\huge ש}_d$ 的副本組成的張量網絡中所有張量收縮 (tensor contractions) 的總和。這給我們留下了兩個問題：

• 計算 $\text{\huge ש}$ 張量。
• 在給定 $\text{\huge ש}$ 張量的情況下，逼近無窮和。

我們對第一個問題的解決方案是將 $\text{\huge ש}$ 張量作為建議接收。事實證明，只要 $1/\varepsilon^2 < n_1$（即在隱藏層的無限寬度極限下），我們在 $\pi$ 中就有足夠的空間寫下我們需要的所有 $\text{\huge ש}$ 張量。（對於問題的「訓練與解釋」版本，我們相信我們可以與 SGD 並行學習 $\text{\huge ש}$ 張量。）

我們目前正在處理第二個問題（加總張量網絡），並取得了實質性的部分進展。如果隱藏層寬度相對於輸入大小確實巨大，那麼就有足夠的時間透過暴力法來逼近總和。如果隱藏層很大但不是巨大，則需要更高效的算法。我們正在努力尋找收縮任意張量網絡的高效方法，並能夠察覺張量網絡何時對總和的貢獻可以忽略不計（以便我們可以將其從總和中剔除）。^([24])

相關問題

一旦我們有了紙面上的解決方案，我們將有興趣看看該解決方案在實踐中的效果如何。有一些理由相信它會比採樣慢（算法可能相當複雜），但也有一些理由相信它會比採樣快（在紙面上，它在最壞情況下能匹配採樣的性能；在典型情況下，它可能超越採樣）。

此外，儘管我們對這個問題的進展感到興奮，但「隱藏層非常大且僅訓練第二層的雙層 MLP」最終是一個相當狹窄的設定。我們可以在許多方向上嘗試推廣我們的方法：更深的 MLP；與輸入層大小相近的隱藏層；訓練兩層；輸入數據的其他分佈；等等。

結語

我認為 MSP 是 ARC 向前邁出的重要一步。以前，我們對產生數學量的機制性估計感興趣，但沒有特定的基準來判斷我們的進展或認定我們的方法「足夠好」。現在，我們正以一個在哲學上合理（我們相信機制性估計應該有可能與採樣競爭）、具體（我們可以透過經驗測試或正式證明來檢查我們的方法是否與採樣競爭）且與實用掛鉤（估計神經網路的性質，如災難機率）的標準來要求自己。

制定 MSP 讓我們能夠提出更具體的問題（例如「我們如何構建一個機制性算法，在估計受訓雙層 MLP 的平均輸出時能與採樣競爭？」）。我們已經解決了其中的一些問題，在其他問題上取得了進展，並正在繼續取得進展。

我們計劃繼續從多個方向攻克 MSP：

• 嘗試針對特定實例（如本文描述的實例）在「紙面上」（即使用數學工具）解決 MSP。
• 利用我們的理論方法為估計問題創建最先進的算法。
• 從更高層次或哲學角度探討問題，以辨別什麼樣的機制性算法能在完全通用的情況下與採樣競爭。

如果你有興趣在這些方向上與我們合作，可以在此申請！

附錄

關於建議可驗證性的說明

在我們的各種 MSP 陳述中，我們不要求 $G_M$ 能夠「驗證」解釋 $\pi$ 是否「準確」（即正確描述了 $M_\theta$ 的結構，而不是做出虛假陳述）。這沒問題嗎？還是我們應該要求 $\pi$ 對 $G_M$ 來說是可驗證的？

至少在 MSP 的「訓練與解釋」版本中，我們不認為建議需要是可驗證的。這有兩個原因：

• 我們的最終目標是在實際的神經網絡中實施任何 MSP 解決方案，並擁有強大的準確性保證（在訓練隨機性的平均意義下）。解決給定神經架構的 MSP「訓練與解釋」版本已經附帶了準確性保證，即使沒有能力驗證解釋算法 $E$ 產生的解釋。
• 假設訓練算法 $T$ 透過檢查許多隨機候選 $\theta$ 值來尋找 $\theta$，直到找到一個特別倒霉的 $\theta$（例如，由於偶然原因，$E[M_\theta]$ 遠大於對 $\theta$ 的完整結構性理解所暗示的值）。透過觀察 $T$ 進行的計算，$E$ 可以注意到 $\theta$ 是倒霉的，但它無法以可驗證的方式簡潔地解釋這一事實。它所能做的就是在其解釋 $\pi$ 中斷言 $\theta$ 是倒霉的，而 $G_M$ 所能做的就是相信 $E$ 的斷言。

最後一點似乎與我早先的斷言（即 $\pi$ 僅對 $\theta$ 的結構而非隨機性做出陳述）有些矛盾。該斷言的更精確版本應該是：$\pi$ 不應斷言 $\theta$ 中偶然發生的任何隨機性；但如果 $\theta$ 由於訓練過程的某些事實而具有奇怪的隨機性，那麼 $\pi$ 應該反映這一事實。

那麼我們的核心 MSP 陳述呢？在那裡沒有解釋算法來追蹤訓練期間完成的優化。如果 $\pi$ 是「憑空而來」的，我們是否能接受 $\pi$ 在沒有驗證可能性的情況下斷言關於 $\theta$ 的事實？

在我看來，$\pi$ 不可驗證是可以接受的，原因基本相同。如果在 MSP 的「訓練與解釋」版本中，$\pi$ 可以聲稱 $\theta$ 是透過暴力搜索被選擇為盡可能對抗的，那麼如果 $\theta$ 是由全知先知選擇的，$\pi$ 聲稱 $\theta$ 被選擇為盡可能對抗似乎也是可以接受的。

例如，想像我們可以將 $M_\theta$ 建模為一個隨機預言機 (random oracle)——對於每個 $\theta$ 都是一個完全不同的隨機函數——而所選的特定 $M_\theta$ 恰好是平均輸出偏離 50/50 最遠的那一個。那麼 $\pi$ 斷言 $\theta$ 是一個隨機預言機，其平均輸出恰好偏離 50/50 許多個標準差，似乎也是可以接受的。

可能存在要求建議可驗證的自然版 MSP。然而，這樣的陳述將需要給予 $G_M$ 更多的運行時間。具體來說，在核心 MSP 陳述中，我們會要求 $G_M$ 在 $O(|\theta| \frac{1}{\varepsilon^2} \text{Time}(M_\theta))$ 時間內運行，其中額外的 $|\theta|$ 因子減輕了選擇 $\theta$ 時產生的選擇壓力。在 $M_\theta$ 是隨機預言機的情況下，如果 $\pi$ 可以傳達 $M_\theta$ 是隨機預言機，但不能斷言關於 $M_\theta$ 是一個特別倒霉的隨機預言機的任何信息，這正是 $G_M$ 與採樣競爭所需的計算量。我不那麼喜歡這個版本，部分原因是我們不預期在實踐中支付額外的 $|\theta|$ 因子是可行的。

MSP 的一個特例：通用圖靈機

MSP 的一個有趣案例是當架構 $M$ 是一個通用圖靈機 $U$ 時。換句話說，$U_\theta(c, x)$ 將 $\theta$ 解釋為圖靈機的編碼，並在輸入 $(c, x)$ 上運行 $\theta$——除了我們會說 $\theta$ 被強制在一百萬步後停止（這樣我們就不需要擔心運行時間）。將 MSP 應用於這個特例會得到以下斷言：

• 存在一個估計器 $G(\theta, \pi, c, \varepsilon)$，使得：
• 對於所有圖靈機 $\theta$，存在一個解釋 $\pi$ ($|\pi| \le O(|\theta|)$)，使得：
• 對於所有容差參數 $\varepsilon > 0$，$G$ 滿足以下三個性質：
  • 它的運行時間為 $O(1/\varepsilon^2)$。
  • 在隨機 $c$ 的平均意義下，其誤差與採樣相比具有競爭力：$E_c[(G(\theta, \pi, c, \varepsilon) - E_{x \sim {0, 1}^n}[\theta(c, x)])^2] \le \varepsilon^2 E_c[\text{Var}_{x \sim {0, 1}^n}[\theta(c, x)]]$。
  • 它是機制性的。

換句話說，存在一個單一的、通用的 $G$，如果給予解釋圖靈機結構的建議，它就能機制性地估計任何（時間受限）圖靈機的平均輸出。

另請注意，解決這個特例將產生完整 MSP 的解決方案：假設我們有一個用於通用圖靈機的估計器 $G$，並考慮某個其他架構 $M$。那麼 $M_\theta = U_{\theta'}$，其中 $\theta'$ 是一個圖靈機，其大小為 $|\theta|$ 加上某個僅取決於 $M$ 的常數。考慮估計器 $G_M$，它在輸入 $(\theta, \pi, c, \varepsilon)$ 時，寫下使得 $M_\theta = U_{\theta'}$ 的 $\theta'$ 並返回 $G(\theta', \pi, c, \varepsilon)$。如果某些 $\pi$ 導致 $G$ 對 $U_{\theta'}$ 輸出準確的估計，那麼 $\pi$ 也將導致 $G_M$ 對 $M_\theta$ 輸出準確的估計。因此，這個估計器 $G_M$ 解決了我們針對 $M$ 的核心 MSP。

MSP 陳述也可用於獲得關於機制性估計隨機圖靈機但不帶建議的聲稱。具體來說，我們令 $\theta$ 為空字串，並改為說 $M_\theta(c, x) := M(c, x)$ 將 $c$ 解釋為圖靈機的編碼，並在輸入 $x$ 上運行 $c$。（如前所述，我們強制 $c$ 在一百萬步後停止。）將 MSP 應用於這個特例會得到以下斷言：

• 存在一個估計器 $G(c, \varepsilon)$，使得：
• 對於所有容差參數 $\varepsilon > 0$，$G$ 滿足以下三個性質：
  • 它的運行時間為 $O(1/\varepsilon^2)$。
  • 其誤差與採樣相比具有競爭力，在隨機 $c$ 的平均意義下：$E_c[(G(c, \varepsilon) - E_x[c(x)])^2] \le \varepsilon^2 E_c[\text{Var}_x[c(x)]]$。
  • 它是機制性的。

這是一個有趣且可以說是大膽的聲明：它表示隨著 $G$ 獲得更多的運行時間，它能夠對圖靈機 $c$ 的平均輸出獲得越來越準確的機制性估計。對於沒有有趣結構的圖靈機（大多數隨機圖靈機都是如此），這足夠直觀。然而，為了滿足上述準確性保證，$G$ 必須對所有圖靈機收斂到正確答案（即使對於具有更複雜結構的圖靈機，收斂速度較慢）。這樣的 $G$ 可能涉及對結構的系統搜索：粗略地說，既然沒有給予它解釋，它必須自己尋找解釋。

去掉 $\varepsilon$

排除一個注意事項（見下文），可以修改 MSP 陳述以去掉容差參數 $\varepsilon$。具體來說，假設以下聲明——將我們的核心 MSP 陳述特化為 $\varepsilon = 1$ 的情況——為真：

• 對於所有將對 $(c \in {0, 1}^{n_c}, x \in {0, 1}^{n_x})$ 映射到 $\mathbb{R}$ 的架構 $M$（帶有參數 $\theta$），存在一個將元組 $(\theta, \pi, c)$ 映射到 $\mathbb{R}$ 的估計器 $G_M$，使得：
• 對於所有參數 $\theta$，存在一個短的解釋 $\pi$ ($|\pi| \le O(|\theta|)$)，使得：
• $G_M(\theta, \pi, c)$ 滿足以下三個性質：
  • 它的運行時間為 $O(\text{Time}(M_\theta))$。
  • 它的誤差與採樣相比具有競爭力，在隨機 $c$ 的平均意義下：$E_c[(G_M(\theta, \pi, c) - E_x[M_\theta(c, x)])^2] \le E_c[\text{Var}x[M\theta(c, x)]]$，其中 $c \sim {0, 1}^{n_c}$ 且 $x \sim {0, 1}^{n_x}$。
  • 它是機制性的。

我們聲稱我們的核心 MSP 陳述幾乎可以從這個無 $\varepsilon$ 版本推導出來。為了看到這一點，考慮一個任意架構 $M$，並固定一個正整數 $m$。我們將定義一個修改後的架構 $M'$，它具有與 $M$ 相同的參數空間。具體來說，$M'\theta$ 的工作方式如下：它接受 $M\theta$ 的輸入列表 $x_1, \dots, x_m$ 作為輸入，在所有輸入上運行 $M_\theta$，並輸出 $M_\theta(x_i)$ 對於 $i \in {1, \dots, m}$ 的平均值。我們聲稱，如果某個估計器 $G_{M'}$ 無論 $m$ 的特定值為何都能解決上述 $M'$ 的 MSP，那麼 $G_{M'}$ 也解決了 $M$ 的核心 MSP。

為了看到這一點，假設我們有一個估計器 $G_{M'}$ 解決了上述 $M'$ 在 $\varepsilon = 1$ 情況下的 MSP。這意味著對於任何 $\theta$，都存在一個解釋 $\pi$ 使得 $G_{M'}$：

• 運行時間為 $O(\text{Time}(M'_\theta))$。
• 在隨機 $c$ 的平均意義下具有低誤差：$E_c[(G_{M'}(\theta, \pi, c) - E_{x = (x_1, \dots, x_m)}[M'\theta(c, x)])^2] \le E_c[\text{Var}{x = (x_1, \dots, x_m)}[M'_\theta(c, x)]]$。
• 是機制性的。

請注意 $E_{(x_1, \dots, x_m)}[M'\theta(c, (x_1, \dots, x_m))] = E_x[M\theta(c, x)]$ 且 $\text{Var}{(x_1, \dots, x_m)}[M'\theta(c, (x_1, \dots, x_m))] = \frac{1}{m} \text{Var}x[M\theta(c, x)]$。另請注意 $G_{M'}$ 的運行時間為 $O(m \cdot \text{Time}(M_\theta))$。這意味著如果 $\varepsilon^2 = 1/m$，則 $G_{M'}$ 也解決了架構 $M$ 的核心 MSP。

現在，如果存在一個單一的 $G_{M'}$ 無論 $m$ 為何都能解決 $M'$ 的 MSP，那麼 $G_{M'}$ 將對所有 $\varepsilon$ 解決 $M$ 的核心 MSP。

我們需要一個不隨 $m$ 變化的統一 $G_{M'}$，這一事實意味著我們還沒有一個完全的歸約；然而，上述無 $\varepsilon$ 的 MSP 陳述是 MSP 的另一個有趣的變體，它與原版幾乎相同。我們決定讓核心 MSP 陳述包含一個容差參數 $\varepsilon$，是為了使與匹配採樣想法的聯繫更加直觀。

壓縮作為一種可能的 MSP 方法

在本節中，我將概述一種解決 MSP 的可能方法。為了具體起見，我將考慮 $M$ 是通用圖靈機的情況（如上文所述）。提醒一下，這意味著 $M_\theta(c, x)$ 將 $\theta$ 解釋為圖靈機的編碼，然後在輸入 $(c, x)$ 上運行 $\theta$。

如果存在一個顯著更短的圖靈機 $\theta'$，它在任何輸入 $x$ 上都能在 $O(|\theta|)$ 時間內構造出 $\theta$，然後在輸入 $x$ 上運行 $\theta$，我們就說圖靈機 $\theta$ 是可高效壓縮的。（我們稱 $\theta'$ 為 $\theta$ 的高效壓縮。）解決 MSP 的一種可能方法看起來像這樣：

• 我們解決不可高效壓縮實例的 MSP。具體來說，我們找到一個估計算法 $G^{inc}_M(\theta, c, \varepsilon)$，它適用於任何不可高效壓縮的 $\theta$，且不需要任何解釋 $\pi$。
• 我們定義估計算法 $G_M(\theta, \pi, c, \varepsilon)$ 來檢查 $\pi$ 是否是 $\theta$ 的高效壓縮，如果是，則返回 $G^{inc}_M(\pi, c, \varepsilon)$。
• 如果 $\pi$ 不可高效壓縮，那麼 $G_M$ 的輸出將是準確的（因為 $G^{inc}_M$ 解決了不可高效壓縮實例的 MSP）。

步驟 1 的希望是：在平均情況（在隨機參數上）奏效的估計方法，將適用於所有不可高效壓縮的參數。

支撐這一希望的直覺是：結構意味著高效壓縮。 換句話說，如果 $\theta$ 具有會使機制性估計器錯誤估計其平均輸出的結構，那麼理解該結構將使我們能夠更緊湊地表示 $\theta$（並且能夠從該表示中快速恢復 $\theta$）。

那麼 MSP 的「訓練與解釋」版本呢？為了使這種方法適配該設定，我們還需要能夠在學習 $\theta$ 本身的同時學習高效壓縮。如果訓練過程有足夠的時間找到具有特殊結構的 $\theta$，那麼是否存在一個「解釋過程」有足夠的時間找到相應的壓縮？這對我來說還不清楚，但我認為這個方向非常有前景，值得探索。

如果這種方法可行，那麼在平均情況下解決某些圖靈完備架構 $M$（如 RNN）的 MSP 將是一個重大進步。

---

• ^(^) 我們也可以想像 $C$ 輸出災難機率，但為了敘述簡單，我們將 $C$ 的範圍限制在 ${0, 1}$。
• ^(^) 運行 $C$ 可能比運行 $M$ 花費更長的時間，這就是為什麼我們不能在部署期間對每個輸入都運行 $C$。
• ^(^) 例如，分佈 $D$ 的參數化需要非常靈活，以便允許在計算上難以採樣的分佈。例如，如果 $M$ 在遇到 RSA-2048 的分解時表現出災難性行為，即使我們無法分解 RSA-2048，我們也希望能夠從 $M$ 中訓練掉這種行為。（更多討論見此處。）
• ^(^) 簡而言之，我們希望透過機制性異常檢測來解決問題 #1。更具體地說，我們的計劃是：
  • 將 $C$ 構建得足夠聰明且強健，使得 $M$ 只能透過深思熟慮如何欺騙 $C$ 來欺騙 $C$。在保險庫中的鑽石類比中，這意味著攝像頭足夠強健，使得 SmartVault 只能故意欺騙它們。
  • 建立一個機制性解釋，說明為什麼 $C(M(x))$ 在訓練分佈上傾向於為 0。這將讓我們標記出那些 $C(M(x^)) = 0$ 是出於異常原因的輸入 $x^$。令 $A(x)$ 為此異常檢測器，即如果 $C(M(x)) = 0$ 是出於異常原因，則 $A(x) = 1$。
  • 與其訓練 $M$ 以最小化 $E_{x \sim D}[C(M(x))]$，不如訓練 $M$ 以最小化 $E_{x \sim D}[\max{C(M(x)), A(x)}]$（即最大化 $C(M(x)) = 0$ 是出於正常原因的機率）。並與上述類似，訓練 $D$ 以最大化此期望值。
    這留下了許多細節未解釋，但這是基本概念。
• ^(^) 或者更確切地說，除了僅透過理解 $M$ 和 $D$ 的結構無法預測的小隨機變化之外，它們是獨立的。
• ^(^) 在實踐中，我們對神經網路在結構化（而非均勻隨機）輸入上的行為感興趣。然而，請注意，可以透過生成模型從隨機輸入中創建結構化輸入。例如，如果我們對分類模型在動物圖片上的行為感興趣，我們可以讓 $M_\theta$ 由兩部分組成：首先，一個從隨機噪聲生成動物圖像的生成模型，其次，一個以動物圖像為輸入的分類器。
• ^(^) 為什麼我們要求 $\pi$ 很短？基本原因是，正如我們稍後討論的，我們將有興趣在學習參數 $\theta$ 的同時學習 $\pi$，因此我們希望能夠像對 $\theta$ 進行反向傳播一樣快地對 $\pi$ 進行反向傳播。我們在哲學上也有一定理由相信與 $\theta$ 大小相當的解釋是足夠的。本質上，我們認為任何對象的結構都可以被緊湊地描述，因為如果一個對象中的（非冗餘）結構量遠大於對象本身的大小，那將構成一個「離譜的巧合」。
• ^(^) 這是透過採用我們對第 $k-1$ 層的（高斯）模型，然後透過尋找能最小化與第 $k-1$ 層模型推廣 (pushforward) 的 KL 散度的正態分佈來對第 $k$ 層進行建模。
• ^(^) 協方差傳播不需要解釋 $\pi$。然而，協方差傳播的一些修改可能需要建議。例如，如果 $\varepsilon$ 太大而無法讓 $G_M$ 計算所有協方差，那麼 $\pi$ 可以建議 $G_M$ 僅追蹤某些特定的協方差。或者，$\pi$ 可以告訴 $G_M$ 一些需要追蹤的重要三階相關性。
• ^(^) 請注意，我們在該論文中使用「啟發式 (heuristic)」一詞代替「機制性 (mechanistic)」。我認為「機制性」一詞能稍微更好地傳達我們的目標。
• ^(^) 作為一個非常簡單的例子，考慮電路 $(x_1 \land x_2) \land (x_2 \land x_3)$。均值傳播估計該電路的平均輸出為 1/16 而非 1/8，因為它未能注意到兩個合取子句中 $x_2$ 的存在所引起的相關性。
• ^(^) 不過，關於這一點的一些細微差別，請參見關於建議可驗證性的附錄。
• ^(^) Eliezer Yudkowsky 的 Worse Than Random 提出了類似的觀點：

  作為一個普遍原則，對於任何你已知某個特定的非隨機化算法異常愚蠢的問題——以至於隨機化算法似乎更明智——你應該能夠使用相同的知識來產生一個優越的去隨機化算法。

• ^(^) 粗略地說，這是 $1/\varepsilon^2$ 佔完整估計 $M_\theta$ 無結構隨機性所需運行次數的很大一部分的範圍。
• ^(^) 我們不能要求 $G_M$ 對所有 $c$ 都準確。例如，假設 $M_\theta(c, x)$ 將 $c$ 解釋為圖靈機並在圖靈機 $c$ 上運行 $x$。要求 $G_M$ 對所有 $c$ 都準確，意味著期望 $G_M$ 能夠在完全沒有任何結構性建議的情況下機制性地估計最壞情況圖靈機的輸出。（畢竟，$\pi$ 不能依賴於 $c$。）這要求太高了。
• ^(^) 請注意，這個問題等價於估計單層 ReLU 網絡在隨機輸入上輸出全零的機率。具體來說，如果網絡是 $\text{ReLU}(Wx)$，那麼當且僅當對於 $W$ 的每一行 $w_i$ 都有 $w_i \cdot x \le 0$ 時，輸出才全為零。
• ^(^) 我們算法的運行時間是 $O(k (\log 1/\varepsilon)^2 / \varepsilon^2)$，在 $1/\varepsilon > 2^{\sqrt{n}}$ 的情況下技術上太慢了。然而，我們對 $\varepsilon = \text{poly}(n)$ 的情況最感興趣。
• ^(^) 樸素的方法是將其視為線性回歸問題，其中兩個多項式 $p_1$ 和 $p_2$ 之間的協方差（內積）定義為對於從單位球面抽取的 $x$，$p_1(x)p_2(x)$ 的期望值。然而，這樣做涉及將一個 $1/\varepsilon^2 \times 1/\varepsilon^2$ 矩陣乘以一個 $1/\varepsilon^2$ 向量，因此該算法對 $\varepsilon$ 的依賴看起來像 $1/\varepsilon^4$：不夠快。
• ^(^) 我們相信我們對正確性和效率的證明在 $n \to \infty$ 的極限下有效，其中 MLP 深度是常數且 $1/\varepsilon = \text{poly}(n)$。
• ^(^) 均值為零；選擇標準差以使所有激活值具有相同的方差。
• ^(^) 這種情況的一個複雜之處在於，雖然我們已經為隨機變數的和與積定義了累積量傳播，但尚不清楚將累積量傳播應用於像 ReLU 這樣的激活函數意味著什麼：給定 $X$ 的累積量，如何估計 $\text{ReLU}(X)$ 的累積量？我們的策略是找到 ReLU 函數的多項式逼近（詳見本腳註的下一段）。一旦我們做到了這一點，我們就可以應用我們已經為和與積定義的累積量傳播。什麼是合適的多項式逼近概念？事實證明，如果假設 $X$ 是正態分佈的，其均值等於我們對 $\kappa(X)$ 的估計，協方差等於我們對 $\kappa(X, X)$ 的估計，我們可以採用最小化均方誤差的多項式。這相當於採用 ReLU 的 埃爾米特展開 (Hermite expansion) 的前幾項（經過適當的中心化和縮放）。
• ^(^) 實際上，追蹤同一個激活值多次出現的累積量更為重要，因此我們需要追蹤一些涉及重複索引的高於 $d$ 階的累積量。
• ^(^) 那是希伯來字母 shin。
• ^(^) 具體來說，只有當網絡中的每個張量都具有較大的算子範數 (operator norm) 時，張量網絡才能對總和做出實質性貢獻。因此，如果在收縮張量網絡的過程中，我們發現一個算子範數很小的張量，我們就可以切斷計算並轉向下一個張量網絡。