Sum of Squares Circuits

平方和概率電路

https://arxiv.org/pdf/2408.11778

https://github.com/april-tools/sos-npcs

摘要

設計能夠支持精確且高效推理 的表達能力強的生成模型 ，是概率機器學習中的一個核心問題。概率電路 （Probabilistic Circuits, PCs）為分析“可計算性 vs 表達能力”這一權衡提供了一個理論框架。

最近，一種被稱為平方概率電路 （squared PCs）的模型通過引入負參數來表示減法混合成分，在保持可計算性的前提下，其表達能力可以比僅使用正參數的單調概率電路（monotonic PCs）高出指數級。在本文中，我們對這些模型之間的表達能力關系進行了更精確的理論刻畫。

首先，我們證明了平方電路 有時可能不如單調電路表達能力強 。其次，我們提出了一類新的概率電路——平方和電路（sum of squares PCs），它在表達能力上可以比平方電路和單調電路都高出指數級。

圍繞“平方和電路”，我們建立了一個表達能力層級結構 ，從而統一并區分了包括 Born Machines、PSD 模型等在內的多種近期提出的可計算概率模型，并借助復數參數進一步擴展了該體系。最后，我們在實驗中展示了平方和電路在分布估計任務中的有效性，表明它們在張量化后可以擴展到現實世界的數據集。

引言

我們設計并學習具有強表達能力的概率模型，以緊湊地表示我們認為生成所處理數據的復雜分布。同時，為了能有效地對該分布進行推理，一個關鍵要求是：我們可以精確而高效地進行推理 ，即具備可計算性 （tractability）。這一點在需要可靠推理的安全關鍵型實際應用中尤為重要（Ahmed 等, 2022；Marconato 等, 2024b,a）。

在概率電路 （Probabilistic Circuits, PCs）框架內，可以對“可計算性與表達能力”的權衡進行量化分析（Vergari, Di Mauro, Van den Broeck, 2019）。概率電路是一種深度計算圖，它泛化了許多 ML 和 AI 中的可計算表示形式（Choi, Vergari, Van den Broeck, 2020）。

例如，在 PC 框架下，要保證某些推理任務（如邊緣推理、最大后驗推理或散度計算）的可計算性，可以直接轉化為確保這些計算圖滿足特定的結構屬性（Vergari 等, 2021）。另一方面，表達能力可以從理論上通過電路規模（以及因此的學習參數數量）來刻畫（Shpilka 和 Yehudayoff, 2010）。

此外，如果我們能在多項式時間內將一類模型歸約到另一類模型，則可以認為它們具有相同的表達能力。反之，若要從表達能力上區分兩類模型，就需要證明某類函數可以被某一類電路精確表示，而除非該類電路規模呈指數增長，否則不能由另一類電路表示（de Colnet 和 Mengel, 2021）。

為了確保電路輸出始終非負——這是建模有效密度的最低要求——傳統上 PC 只使用非負參數 進行建模和訓練，即它們是單調的 （Shpilka 和 Yehudayoff, 2010）。這種主流電路類別只能表示將各分量密度相加的混合模型。

為了彌補這一不足，Loconte 等（2024a）引入了一類特殊的非單調 PC ，即允許負參數的電路，從而實現對混合成分的減法操作。電路輸出的非負性通過對電路輸出取平方 來保障（Vergari 等, 2021）。

Loconte 等（2024a）證明了單調電路與非單調平方電路之間存在指數級的表達能力差異，說明后者可以比前者更具表達能力。然而，一個開放問題是：平方電路能否緊湊地表示所有由單調電路緊湊編碼的函數？

在本文中，我們給出了否定答案，通過證明反向方向上的另一個分離結果：某些可以用多項式大小的單調電路 表示的分布，必須用指數大小的平方電路 才能表示。為了克服這一限制，我們引入了一個更大的模型類：平方和電路 （sum of squares PCs），它在表達能力上可以超越兩者。

雖然平方和形式在建模非負多項式方面已有廣泛應用（Marshall, 2008），但關于它們何時以及如何導致緊湊的電路表示仍不明確。我們通過構建圍繞平方電路及其平方和的精細表達能力層級，填補了這一空白，如圖 1 所示。

我們不僅準確刻畫了其他可計算模型（如 PSD 模型（Rudi 和 Ciliberto, 2021）、Born Machines（Glasser 等, 2019）、平方神經族（Tsuchida, Ong, Sejdinovic, 2023）和 Inception PCs（Wang 和 Van den Broeck, 2024））屬于這一新型非單調電路類的方式，還通過分析某些 PC 無法被表示為平方和的情況，進一步拓展了這些新邊界。

最后，我們解決了關于復數參數對模型表達能力的作用 這一問題，證明了帶有復數參數的平方電路本質上就是平方和電路。

我們的理論貢獻總結見圖 1。

我們首先證明了單調電路在表達能力上可以比平方電路高出指數級（第 3 節）。接著，我們引入了平方和電路類，并通過兩個構造方法證明其表達能力可以比單調電路和平方電路都高出指數級（第 4 節）。在第 5 節中，我們將其與其它可計算形式系統聯系起來，并在第 6 節中進一步擴展。最后，在第 7 節中，我們通過實驗證明了平方和電路在分布估計中的表達能力提升，并展示其在張量化后能夠擴展到真實世界數據。

2 從電路到平方概率電路

表達效率 （也稱為簡潔性或表示能力）是指一類電路能夠在多項式大小的計算圖 中編碼一個（可能未歸一化的）分布的能力，即其規模隨輸入規模的增長呈多項式增長 。這與“表達能力”中所指的通用表示性 （universal representation）不同：所有具有布爾（Boolean）或高斯（Gaussian）輸入的 PC 都可以任意近似任何布爾函數（或連續分布），但這通常需要指數級的電路規模 。

當我們說某一類模型比另一類在表達上更“高效 ”或“簡潔 ”時，我們的意思是存在某個分布（也稱為“分離函數” separating function），該分布無法被屬于第二類的任意多項式規模電路 所表示。

例如，滿足更少或不同結構屬性的電路（如放寬定義 2 中的可分解性條件）可能在表達效率上比其他電路類高出指數級，也就是說它們可以在可計算的前提下表示更大類別的函數（Martens 和 Medabalimi, 2014）。

單調 PC 與非單調 PC 設計和學習一個作為概率電路（PC）的模型，通常是通過假設其參數和輸入函數都為非負的，從而得到一個 單調 PC（monotonic PC）（Shpilka 和 Yehudayoff, 2010）。而放松這一假設的電路——即 非單調 PC （non-monotonic PC）——已被證明在表達效率上比單調電路更強（Valiant, 1979）。然而，以一種 通用且靈活的方式 構建非單調電路仍然具有挑戰性（Dennis, 2016）。

對于具有單變量輸入的結構可分解 PC，這種劃分形成一棵樹，有時稱為 vtree （Pipatsrisawat 和 Darwiche, 2008）或 偽樹 （pseudo-tree）（Dechter 和 Mateescu, 2007）。

這類模型在量子物理與量子計算中非常流行，在這些領域中它們通常使用復數張量 進行操作。在我們的理論框架下，我們將清楚地看到：引入復數參數確實能帶來表達能力上的優勢，并解釋其原因（見第 5 節）。

然而，在此之前請注意，定理 0 并沒有說明平方概率電路能夠高效表示所有由單調 PC 緊湊編碼的非負函數。事實上，我們第一個理論貢獻就是證明了這一點并不成立：

接下來我們將證明另一個方向上的指數級分離結果（exponential separation）。

3 平方電路的一個局限性

我們的構造起源于 Glasser 等人（2019）的一個觀察：編碼非負分解的非負 MPSs（見公式 (2)），在分解我們提出的 SUM 函數的一個變體時，所需的秩 r 要比實值 Born 機（real BMs）小指數級。

我們的結果更強，因為它適用于所有平方結構可分解電路 ，這意味著它適用于所有可能的樹狀區域圖（region graph）。事實上，MPS 和 BM 只能表示具有特定區域圖的 PC，因為它們中的所有乘法單元都是一次只對一個變量進行條件分解其作用范圍（參見 Loconte 等, 2024a 中的命題 3）。

因此，我們的發現可以推廣到其他實數域上的平方張量網絡，如樹形結構的 Born 機（tree-shaped BMs）（Shi, Duan, Vidal, 2006；Cheng 等, 2019），以及更多具有樹狀區域圖的電路類（Mari, Vessio, Vergari, 2023）。

4 相容平方和電路（Sum of Compatible Squares Circuits）

我們提出的更具表達能力的電路類將采用平方和 （Sum of Squares, SOS）的形式。這是一個代數幾何中的經典概念，用于刻畫某些非負多項式（Benoist, 2017）。因此，我們可以推導出一類特殊的 SOS 多項式族，它支持可計算的推理。

因為電路也可以被理解為輸入函數作為變量的多項式的緊湊表示（Martens 和 Medabalimi, 2014），所以我們將這類電路視為這些多項式的結構化擴展。

在本節中，我們的目標是精確刻畫電路表達效率的邊界，因此我們要求所構造的 SOS 形式始終具有多項式規模 。這與關于 SOS 表示與非負多項式關系的“通用性”結果不同，在那些研究中，主要關注的是某個非負多項式是否可以寫成 SOS 的形式，而不考慮模型規模的大小。例如，請參見希爾伯特第十七問題以及 Marshall（2008）的相關綜述。

為了保持推理的可計算性，在我們定義的“平方和電路”類中，不僅要求每個單獨的電路是結構可分解 的（從而可以高效地進行平方運算），還要求它們彼此之間是相互兼容 的。

我們用 表示這類相容平方和電路 （SOCS）。

將多個（平方）概率電路通過正系數進行加權求和，等價于構建一個以這些（平方）概率電路為組件的有限混合模型（McLachlan, Lee 和 Rathnayake, 2019）。

盡管這種做法看似只是提升表達能力的一種簡單方式，但我們將證明，其帶來的優勢實際上是指數級的 。

5 SOCS 電路統一了多種模型類

我們現在將迄今為止所介紹的理論結果擴展到其他多個可計算模型類 ，這些模型可以歸約到 SOCS（相容平方和電路） 。

我們首先從具有復數參數 的模型開始。

復數參數在機器學習中的廣泛應用

復數參數在機器學習中被廣泛使用。首先，它們在建模波動現象方面具有語義意義，如在信號處理和物理學中的應用（Hirose 和 Yoshida, 2012；Tygert 等, 2015）。例如，在第 2 節中我們曾提到，矩陣乘積態（MPSs）和 Born 機（BMs）通常被定義為在復數域上進行分解 。

因此，在量子物理中，一個 Born 機建模的是波函數模長的平方

復數 Born 機已被用于分布估計任務（Han 等, 2018；Cheng 等, 2019）。

其次，已有研究表明，使用復數參數有助于穩定學習過程 （Arjovsky, Shah, Bengio, 2015），并提升包括概率電路在內的各種機器學習模型的表現（Trouillon 等, 2016；Sun 等, 2019；Loconte 等, 2023）。

在概率電路中，我們可以用一個精確的理論刻畫來支持這一觀點，并回答一個關鍵問題：在復數域中建模 PC 是否帶來了表達能力上的優勢？

復數平方電路

我們將實數域上的平方電路類 ±2R 進行擴展，并形式化地定義復數平方電路 （complex squared PC）為如下形式：

在附錄 B.5 中我們表明，類似于實值 Born 機可歸約到平方電路（Loconte 等, 2024a），復數 Born 機也可歸約到復數平方電路 ，因此其表達能力至少與實數版本一樣強。

更重要的是，我們證明了任何復數平方電路都可以高效地歸約到僅含實數參數的 Σ2cmp 類電路 。

這通過我們定理 2 的視角，徹底解答了“復數參數是否比實數參數帶來更強表達能力”的問題。

下面我們將形式化這一結論。

我們在附錄 B.8 中通過推廣 Loconte 等（2024a）中關于淺層 PSD 核模型的歸約方法，證明了這一結論。

Sladek、Trapp 和 Solin（2023）提出了另一種深度 PSD 模型的構造方式，其中 PSD 加法單元位于單調 PC 的輸入端，而不是輸出端。這樣一來，他們所求和的平方項數量隨著電路深度呈指數增長，這與我們的 μSOCSs（微小平方和電路）類似。

與此同時，Wang 和 Van den Broeck（2024）提出了Inception PC ，它與我們的 SOCS 是獨立提出的非單調 PC，旨在克服平方電路的表達能力限制，并在文中證明了我們定理 1 的一個變體形式。

一個 Inception PC 將變量 X 上的概率分布 p 表示為：

其中

是一個結構化電路，它在擴展變量集 X∪U∪W 上計算一個復值函數。

公式 (6) 已經是以SOCS形式 （平方和相容電路）表達的。與輸入為 PSD 的 PSD 電路以及我們的 μSOCSs 類似，將變量 U 放在平方之外，可以通過參數共享緊湊地表示指數數量級的平方項。

然而，與我們的 μSOCSs 不同的是，Inception PC 在計算未歸一化的對數似然時就存在二次級規模膨脹 ，因為它們無法將平方運算提到對數運算之外（見第 7 節）。

6 所有結構化 PC 都是 SOCS 電路嗎？

鑒于目前為止我們討論的 SOCS 電路在表達能力上的增強，一個自然的問題是：它們是否能夠高效地編碼其他可計算 PC 類所表示的任意分布？

顯然，我們需要將注意力限制在結構可分解 （structured-decomposable）的電路上，因為這是進行高效平方運算所需的結構性質。因此，我們排除了僅具有可分解性、或雖編碼多線性多項式但不滿足可分解性的電路類（參見 Agarwal 和 Bl?ser, 2024；Broadrick, Zhang 和 Van den Broeck, 2024）。

我們首先聚焦于 +sd 類中的概率電路，并展示由 SOCS 電路編碼這類函數時的規模上限。

命題 3

我們的結果類似于 Valiant (1979) 的一個經典結論，但我們考慮的是具有不同結構性質的電路：他們指出一個（不可分解的）非單調電路可以表示為兩個單調電路的差值；而我們關注的是將結構化電路重寫為 SOCS 電路的形式。

7 實驗評估

我們根據未見數據點上的平均對數似然值 來比較各類 PC 的性能。接下來我們簡要介紹我們構建 PC 的方法，更多細節請參見附錄 C。

構建張量化 SOCS 電路

我們借鑒 Mari、Vessio 和 Vergari（2023）的方法，通過將區域圖（region graph，見第 2 節）參數化為 CP 分解的形式，并結合向量化的輸入層（Loconte 等, 2024b），來構建張量化的概率電路。

這種構造方式允許我們通過控制各層中的單元數量來調節模型大小。

我們根據不同的數據類型使用兩種區域圖：

• 對于表格數據，我們沿用 Loconte 等（2024a）的做法，使用隨機二叉樹；

• 對于圖像數據，我們使用四叉樹（quad trees），它遞歸地將圖像劃分為圖像塊（見附錄 C.2）。

實現復數電路的方式是對張量類型進行上轉型（upcast），并實現一種針對復數的 log-sum-exp 技巧（見附錄 C.4）。

(A) 連續 UCI 數據集實驗

我們使用 Papamakarios、Pavlakou 和 Murray（2017）相同的預處理流程，對四個連續 UCI 數據集進行分布估計：Power、Gas、Hepmass、MiniBooNE（見表 C.1）。

我們比較了結構單調電路（structured monotonic PCs）和具有實數或復數參數的平方電路（squared PCs）。所有電路均使用高斯似然作為輸入單元，并確保它們的可訓練參數數量相差不超過 ±6%。

圖 2 和圖 C.1 顯示：除了 Gas 數據集外，單調電路在所有數據集上的測試對數似然都優于具有實數參數的單個平方電路，這與我們提出的理論一致——即單個實數平方電路存在表達能力限制（定理 1）。

相比之下，具有復數參數的平方電路始終優于具有實數參數的平方電路和單調電路，因為它們屬于 SOCS 類（推論 1）。

圖 C.2 展示了訓練過程中的對數似然變化情況。

圖 C.3 則表明，學習具有實數參數的單個平方電路通常較為困難，因為其損失函數不穩定；而復數平方電路則沒有這個問題。

(B) 增加平方項數量的影響

我們逐步增加 SOCS 電路中平方項的數量，從 4 個增加到 16 個，同時保持參數總數大致不變。作為基線，我們構建了由 4 至 16 個結構單調電路組成的混合模型。

我們在與 (A) 相同的數據集和設定下進行比較。

圖 2 表明，不僅 SOCS 電路在性能上優于單調電路，而且在這些數據集上，將平方電路的數量從 4 提升到更多并沒有帶來顯著提升（見圖 C.1 中 Power 和 Gas 的結果）。

此外，復數 SOCS 電路與實數 SOCS 電路表現相近，這也符合預期，因為復數 SOCS 電路屬于 Σ2cmp 類（推論 1）。

(A, C) 圖像數據實驗

我們進一步對 MNIST、FashionMNIST 和 CelebA 圖像數據集（見表 C.2）進行概率分布估計，并比較以下幾種模型：

• 單個結構單調電路，

• 具有實數和復數參數的單個平方電路，

• 一個 μSOCS 電路，它是通過將一個單調電路與一個復數平方電路相乘得到的（+sd · ±2?）。

模型構建詳見附錄 C.2 和 C.3。

對于單調電路，我們使用分類分布作為輸入單元；對于實數（復數）平方電路，我們分別使用實數（復數）向量嵌入。

圖 3 給出了以“每維度比特數”（bits-per-dimension, BPD）衡量的標準化負對數似然結果。

可以看到，復數平方電路在圖像分布估計方面明顯優于單調電路和實數平方電路。而 μSOCS 模型比單個復數平方電路表現更好，且參數更少。

相反，實數平方電路的表現趨于飽和，最終與單調電路相當。

圖 C.4 顯示了在 FashionMNIST 上的相似趨勢，以及訓練過程中 BPD 的變化。

雖然實數和復數平方電路都傾向于過擬合，但復數平方電路和 μSOCS 的泛化能力更強。

附錄 C.6 對復數平方電路與 μSOCS 在訓練時間和空間開銷方面進行了比較。

8 結論

我們統一并區分了多個圍繞“電路平方”操作構建的近期可計算模型。我們的理論分析為許多目前僅依賴于實驗支持的主張提供了理論依據，例如使用復數參數 的有效性。

我們提出的 SOCS 電路 （平方和相容電路）不僅能夠構建可擴展且高精度的模型 ，還使得其與平方和多項式（SOS polynomials）相關文獻建立了聯系。我們的 SOCS 表達能力結果也可以遷移到非線性矩陣分解 的文獻中（Lefebvre, Vandaele 和 Gillis, 2024；Awari 等, 2024）。

作為未來的研究方向，我們計劃為 SOCS 建立一個嚴格的潛在變量解釋 （Peharz 等, 2016），從而開發出新的參數學習和結構學習方法（Gens 和 Domingos, 2013；Di Mauro 等, 2017）。

此外，我們還計劃將 SOCS 擴展到具有連續潛在變量 的情形（Gala 等, 2024a,b），并使用神經網絡 對其進行參數化（Shao 等, 2020），以進一步提升其表達能力。

A 電路（Circuits）

圖 A.1 展示了一個關于四個布爾變量的電路示例，該電路是結構可分解的 （structured-decomposable），即它與自身兼容（Definition 3）。

給定一個平滑且可分解 （smooth and decomposable）的電路 c，并且其輸入單元可以高效積分，我們可以在線性于電路規模的時間內 精確計算任何關于 c 的定積分，如下命題所述。

命題 A.1（可計算性）（Choi, Vergari 和 Van den Broeck, 2020）

B 證明 B.1 預備知識

在給出具體證明之前，我們首先推廣 Martens 和 Medabalimi（2014）中的定理 38，該定理刻畫了由平滑且可分解的單調電路 所計算的多線性多項式的形式。

具體來說，一個平滑且可分解的電路計算的是“弱積”（weak product）的和，其中每個“弱積”是定義在兩個互不相交的變量集上的函數的乘積。

為了證明定理 1，我們需要將變量劃分為若干子集，并使得其中某個特定的真子集誘導出一個平衡劃分（balanced partitioning）（見下文定義）。

此外，我們還給出了在結構可分解電路 情形下所計算函數的一個顯式電路表示形式 ，這對于證明定理 5 是必要的。

最后，由于我們在定理 1 和定理 2 中對非單調平方電路的規模進行了下界估計，因此我們對 Martens 和 Medabalimi（2014）中的定理 38 進行了一個平凡推廣，使其適用于非單調電路 的情形。

此時，電路 c 所計算的函數可以表示為一個 望遠鏡型差值和 （telescoping sum of differences），即：

C 實驗細節 C.1 數據集與評估指標

UCI 倉庫數據集 （Dua 和 Graff, 2017）
我們使用了以下四個 UCI 數據集進行實驗：Power（Hebrail 和 Berard, 2012）、Gas（Fonollosa 等, 2015）、Hepmass（Baldi 等, 2016）和 MiniBooNE（Roe 等, 2004）。我們采用了 Papamakarios、Pavlakou 和 Murray（2017）所使用的相同預處理方式。表 C.1 報告了預處理后訓練集、驗證集和測試集的數據統計信息。

圖像數據集
我們對以下圖像數據集進行了實驗：MNIST（LeCun、Cortes 和 Burges, 2010）、FashionMNIST（Xiao、Rasul 和 Vollgraf, 2017），以及 CelebA（Liu 等, 2015）。

對于 MNIST 和 FashionMNIST，我們從訓練集中抽取 5% 的樣本作為驗證集。表 C.2 報告了這些數據集在預處理后的訓練、驗證和測試集的統計數據。

根據 Gala 等（2024b）的做法，對于 CelebA 數據集，我們通過一個保持體積的變換 （volume-preserving transformation）將 RGB 顏色空間轉換為 YCoCg 顏色空間。更多細節請參見 Gala 等（2024b）。

評估指標

對于 UCI 數據集 ，我們在圖 2 和圖 C.1 中報告了模型在測試數據上的平均對數似然值 （average log-likelihood）。

對于 圖像數據集 ，我們在圖 3 中報告了“每維度比特數”（bits-per-dimension, BPD），該指標定義為測試集上歸一化的負對數似然值 。

C.2 模型配置與超參數 UCI 數據集上的實驗

我們在 UCI 數據集上評估了以下幾類概率電路（PC）：

• 單個結構可分解單調電路（structured-decomposable monotonic PC），

• 單個實數平方電路（real squared PC），

• 單個復數平方電路（complex squared PC），

• 實數或復數參數的 SOCS 電路（sum of squares PCs）。

作為基線模型，我們還評估了一個由多個兼容且結構化單調電路 組成的正混合模型。

張量化 PC 的構造

我們借鑒 Mari、Vessio 和 Vergari（2023）的方法，通過將區域圖（region graph，見第 2 節）參數化為包含加法層、乘法層和輸入層的張量結構，來構建張量化 PC 架構。這些張量化的層分別由加法單元、乘法單元和輸入單元組成（Loconte 等, 2024a）。

這種張量化電路構造方式使我們能夠通過簡單地控制每層中計算單元的數量（即“層大小”）來調節電路規模。

按照 Loconte 等（2024a）的做法，我們通過遞歸地將變量集合大致均勻劃分為子集，直到無法進一步劃分為止，從而構造出隨機二叉樹形式的區域圖。

然后我們通過組合加法層和乘法層對該區域圖進行參數化，使得每一層都編碼 CANDECOMP/PARAFAC 分解（Carroll 和 Chang, 1970；Kolda 和 Bader, 2009），即每個變量劃分對應一個乘法層，該層對其輸入層執行逐元素相乘操作。

這種構造方式最終得到的是結構可分解電路 。

關于該電路構造流程的更多細節，請參見 Mari、Vessio 和 Vergari（2023）以及 Loconte 等（2024a）。

由于不同 UCI 數據集的樣本數量不同，我們選擇了不同的層大小以避免過擬合。

然而，在所有 UCI 數據集的實驗中，我們評估的所有 PC 在加法單元參數數量方面保持一致，最多僅相差 ±6%。

此外，所有 PC 在每一層輸入層中使用相同數量的高斯似然函數。

表 C.3 報告了根據不同數據集和 PC 類別，各層中加法單元（因此也是乘法單元）和輸入單元的具體數量。

從數據中學習

所有 PC 都是通過對訓練集的負對數似然函數進行最小化，并使用批量梯度下降法進行訓練，批量大小設為 512，優化器為 Adam（Kingma 和 Ba, 2015），使用默認超參數，并嘗試三種不同的學習率：

我們持續訓練，直到驗證集上的對數似然值在連續 25 個 epoch 內不再有明顯提升為止。

每次實驗重復 5 次，使用不同的隨機種子，從而生成不同的隨機電路結構，并將結果以箱形圖（box plot）形式展示（見圖 2、C.1 和 C.2）。

在這些箱形圖中，我們將那些與四分位距（IQR）之差超過兩倍 IQR 的結果標記為異常值（用十字符號表示）。

圖像數據集上的實驗

我們在圖像數據集上評估了以下幾類概率電路（PC）：

• 單個結構可分解單調電路（structured-decomposable monotonic PC），

• 單個實數平方電路（real squared PC），

• 單個復數平方電路（complex squared PC）。

此外，我們還對一個 μSOCS 電路進行了實驗，其構造細節將在附錄 C.3 中進一步說明。

張量化 PC 的構建

為了構建張量化 PC，我們使用了與 UCI 數據集相同的電路構造流程。然而，主要區別在于我們參數化了一個專為圖像數據設計的固定區域圖——四叉樹 （quad-tree），如 Mari、Vessio 和 Vergari（2023）所述。

具體來說，每個像素值（或像素通道，如果有的話）都被視為一個取值在 {0,…,255} 范圍內的隨機變量。四叉樹 以遞歸且均勻的方式將圖像劃分為四個圖像塊（patches），即大致相同數量的變量集合，直到每一部分僅包含一個變量為止。

接著，我們通過引入執行 CANDECOMP/PARAFAC 分解的加法層和乘法層對該區域圖進行參數化，方式與我們在 UCI 數據集上的實驗一致。

關于該構造方法的更多細節，請參見 Mari、Vessio 和 Vergari（2023）。

對于單調電路，其輸入單元計算的是分類分布似然函數（Categorical likelihoods）。

從數據中學習

所有 PC 模型都通過對訓練集的負對數似然進行最小化，并使用批量大小為 256 的梯度下降進行優化，優化器為 Adam（Kingma 和 Ba, 2015），學習率設為 ，并采用默認超參數。

我們持續訓練模型，直到驗證集上的 BPD（每維度比特數）在連續 20 個 epoch （用于 MNIST 和 FashionMNIST）或 5 個 epoch （用于 CelebA）內不再有顯著提升為止。

C.5 附加實驗結果 UCI 數據集上的實驗

圖 C.1 展示了單調電路（monotonic PCs）、平方電路（squared PCs）和 SOCS 電路在 Power 和 Gas 這兩個 UCI 數據集上取得的對數似然值（見附錄 C.1）。

在我們所有的實驗中，Gas 數據集是唯一一個 ：單個實數平方電路在平均表現上優于單個結構可分解單調電路的情況。

為了排除可能的過擬合現象，我們在圖 C.2 中展示了相同模型在四個 UCI 數據集的訓練集上的對數似然表現（見附錄 C.1），其中趨勢一致（也見第 7 節中的討論）。

訓練損失的穩定性

我們發現，單個結構化單調電路和單個復數平方電路的訓練損失比單個實數平方電路穩定得多。

圖 C.3 比較了使用隨機梯度下降訓練過程中（見附錄 C.2）三種模型的負對數似然曲線，并考慮了我們嘗試過的三種不同的學習率。

即使使用最低的學習率，訓練單個實數平方電路時損失曲線仍出現大量尖峰（spikes）。相比之下，即使是較高的學習率下，訓練單個復數平方電路的損失曲線也更加平滑。

圖像數據集上的實驗

圖 C.4 展示了在 MNIST、FashionMNIST 和 CelebA 數據集上，隨著可學習參數數量的增加，各類 PC 所達到的 BPD 指標（見附錄 C.1）。

在 MNIST 和 FashionMNIST 數據集上，我們觀察到：

• 實數平方電路、復數平方電路以及 μSOCS 電路（見附錄 C.3）傾向于過擬合；

• 它們在訓練數據上達到了非常相近且顯著低于測試數據的 BPD 值。

然而，復數平方電路和 μSOCS 電路的泛化能力明顯優于實數平方電路。

C.6 基準測試

我們所有的實驗都在一塊具有 48 GiB 內存的 NVIDIA RTX A6000 上進行。

我們對用于圖像數據集實驗中的概率電路（見圖 3）進行了基準測試，包括：

• 結構化單調電路，

• 實數平方電路和復數平方電路，

• μSOCS 電路。

詳見附錄 C.2 和 C.3。

我們在 MNIST 和 CelebA 數據集上，評估了所有這些 PC 模型完成一次優化步驟所需的時間和 GPU 顯存占用情況（見附錄 C.1）。此外，我們也比較了各模型在達到的 BPD 指標與時間和顯存消耗之間的權衡。

圖 C.5 表明，在執行一次優化步驟時，使用復數平方電路所需的計算資源與單調電路相當，但其在 MNIST 上取得了更優的 BPD 表現。

此外，我們還發現訓練 μSOCS 電路在計算成本上與訓練單個復數平方電路或結構化單調電路相近或略高 。然而，μSOCS 電路在 CelebA 數據集上實現了顯著更低的 BPD（見圖 3）。

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