On the Relationship Between Monotone and Squared Probabilistic Circuits

從單調到平方：概率電路的關系探秘

https://arxiv.org/pdf/2408.00876

摘要
概率電路是一種將函數表示為加權和與乘積的計算圖的統一體。它們的主要應用在于概率建模，其中具有非負權重的概率電路（單調電路）可以用來表示和學習密度/質量函數，并且能夠進行可追蹤的邊緣推理。最近，有人提出將密度表示為電路函數的平方（平方電路），這種方法允許使用負權重同時保持可追蹤性，并且在表達效率上可能比單調電路指數級更高效。然而，我們發現反過來也成立，這意味著單調電路和平方電路在一般情況下是無法比較的。這引發了一個問題：我們是否可以調和這兩種建模方法，并且確實能改進它們？通過提出Inception PCs，一種新型的電路模型，我們給出了肯定的回答。Inception PCs自然地包含了單調電路和平方電路作為特例，并采用了復數參數。從實驗上，我們驗證了Inception PCs可以在多種表格數據和圖像數據集上優于單調電路和平方電路。

代碼 — https://github.com/wangben88/InceptionPCs

1 引言

可追蹤概率建模（tractable probabilistic modeling）的理念主張通過設計支持對各種概率查詢進行精確且高效推理的模型架構，來建模高維概率分布。這一特性使得它們在概率推理中極為有用；例如，可追蹤模型已被廣泛應用于增強和控制不可追蹤生成模型（Zhang 等，2023；Liu, Niepert 和 Van den Broeck，2024），神經符號人工智能（Ahmed 等，2022；Ahmed, Chang 和 Van den Broeck，2023），以及因果發現與推理（Wang, Wicker 和 Kwiatkowska，2022；Wang 和 Kwiatkowska，2023）。

可追蹤模型的通用語言是概率電路框架（Probabilistic Circuits，簡稱 PC）（Choi, Vergari 和 Van den Broeck，2020），該框架使用加法和乘法的計算圖來定義函數，統一了許多先前的可追蹤模型，如算術電路（Arithmetic Circuits）（Darwiche，2003）、和積網絡（Sum-Product Networks）（Poon 和 Domingos，2011）以及割集網絡（Cutset Networks）（Rahman, Kothalkar 和 Gogate，2014）。標準的建模方法是直接使用一個PC來表示概率分布（密度/質量函數）。為了確保PC輸出的非負性，通常限制其參數為非負值；這些被稱為單調PC（Monotone PCs）（Darwiche，2003；Poon 和 Domingos，2011）。然而，最近的研究表明，存在許多可追蹤的概率分布類別是無法用這種方式表達的（Zhang, Holtzen 和 Van den Broeck，2020；Yu, Trapp 和 Kersting，2023；Broadrick, Zhang 和 Van den Broeck，2024）。

這促使人們探索新的實用方法來構建和學習廣義的可追蹤模型。為此，Loconte 等人（2024b）最近提出了平方電路（Squared Circuits），其中概率分布被定義為（正比于）電路函數的平方。在這種形式下，PC可以使用實數（甚至負數）參數，同時仍然定義一個有效的概率分布。理論上已經證明，在某些分布類別上，這種方法相比單調PC具有指數級的表達效率優勢。

在本文中，我們重新審視了單調電路和（結構可分解的）平方電路，并表明它們在一般情況下是不可比較的：任一者都可能比另一者在表達效率上指數級更優。受此觀察啟發，我們借鑒了PCs的潛在變量解釋（Peharz 等，2016），并揭示了這兩種電路之間的一種優雅聯系：它們分別對應于將潛變量求和操作放在平方外部或內部，即“深度的和的平方”或“平方的和”。通過結合這兩類潛變量，我們提出了一種新型的可追蹤模型——深度的和的平方的平方（deep sum-of-square-of-sums），我們稱之為 Inception PC（IncPC），它嚴格地推廣并擴展了（結構可分解的）單調PC和平方PC。

我們進一步研究了如何有效地大規模學習Inception PC。沿襲PC學習的最新趨勢（Peharz 等，2020b,a；Liu 和 Van den Broeck，2021；Mari, Vessio 和 Vergari，2023），我們設計了一個高效的張量化實現方案，能夠統一處理張量化的（結構可分解的）單調PC和平方PC。實驗結果驗證了Inception PC在密度估計基準任務中表現出了更高的表達效率。

我們的貢獻可以總結如下：

• 理論上，我們展示了一個簡單的分布類別，在該類別中單調電路可能比平方電路小指數級，這意味著在表達效率方面，單調電路和平方電路在一般情況下是不可比較的（第3節）；

• 我們從潛在變量視角對單調電路和平方電路進行了分析，表明它們分別可以被解釋為“深度的和的平方”（sums-of-squares）和“平方的和”（squares-of-sums）。在此基礎上，我們提出了一種新型的可追蹤電路模型——Inception PCs（IncPC），它將這兩種電路統一起來并加以擴展，形成一種“深度的和的平方的平方”（deep sum-of-square-of-sums）結構，并可以使用復數參數（第4節）；

• 我們為 Inception PC 提出了一個高效的張量化架構設計，使其能夠應用于大規模數據集（第5節）；

• 實驗上，我們展示了：(i) 結合兩種類型的潛變量并引入復數參數可以提升模型性能；(ii) 在包括降尺度版 ImageNet 在內的多個具有挑戰性的基準任務上，即使考慮計算時間歸一化的情況下，Inception PC 也能優于單調電路和平方電路（第7節）。

在同期的研究工作中，Loconte、Mengel 和 Vergari（2025）也使用類似的函數族證明了單調電路與平方電路之間的指數級差異（即我們的定理2）。他們還提出了兩種新的模型類別——SOCS 和 μSOCS，用于推廣平方電路。我們在附錄A中詳細討論了這些模型與我們的 Inception PC 的聯系。

2 預備知識

記號：我們使用大寫字母表示變量，小寫字母表示它們的賦值/取值（例如，X，x）。我們使用粗體字母（例如，X，x）表示變量集合或賦值集合。

概率電路是一種計算圖，用于表示通過加權和與乘積的層次化組合所構建的函數。

其中每個和節點具有一組權重 {θ?,??}??∈in(n)，其中 θ?,?? ∈ ?。每個節點 n 都表示關于一組變量 sc(n) 的函數，我們稱 sc(n) 為該節點的作用域（scope）；對于內部節點，其作用域定義為 sc(n) = ∪??∈in(n) sc(n?)。整個概率電路 f_C 所表示的函數，即為其根節點所表示的函數。一個概率電路 |C| 的大小定義為其有向無環圖（DAG）中的邊的數量。

在本文中，我們假設和節點與積節點是交替出現的；這一假設不失一般性，因為可以通過最多線性增加電路大小的方式，使任意概率電路滿足這一性質。

概率電路的和-積結構的一個關鍵特性是，它允許高效地（線性時間）計算邊緣分布，例如配分函數，前提是電路是平滑（smooth）且可分解（decomposable）的：

定義 2（平滑性，可分解性）：一個概率電路是平滑的，如果對于每一個和節點 n，它的輸入節點 ni 具有相同的作用域（scope）。一個概率電路是可分解的，如果對于每一個積節點 n，它的輸入節點具有互不重疊的作用域。

我們還需要一種更強的可分解性形式，它使得多個電路可以被高效地相乘（Pipatsrisawat 和 Darwiche，2008；Vergari 等，2021）：

定義 3（結構化可分解性）：一個平滑且可分解的概率電路被稱為結構化可分解的，如果任意兩個作用域相同的積節點 n 和 n′ 以相同的方式進行分解。

在從數據中學習概率電路時（Liu 和 Van den Broeck，2021），以及從其他模型（如貝葉斯網絡）編譯生成電路時（Choi, Kisa 和 Darwiche，2013），通常都會施加結構化可分解性的約束。

3 單調與平方結構化可分解電路的表達效率

概率電路的一個主要應用是作為概率分布的可追蹤表示。因此，我們通常要求電路輸出的函數值為非負實數。實現這一要求的常用方法是對權重和輸入函數施加非負性約束：

定義 4（單調 PC）：一個概率電路被稱為單調電路（Monotone PC），如果其所有權重均為非負實數，并且所有輸入函數的輸出也為非負實數。

這或許有些令人驚訝，因為對概率電路進行平方操作會生成具有可能為負的權重的結構化電路，這表明它們應該比單調結構化的概率電路更通用。

關鍵在于，并非所有表示正函數的電路（甚至并非所有單調結構化的電路）都可以通過對某個函數平方來生成。

綜合來看，這些結果有些令人不滿意，因為我們知道存在一些分布更適合用未平方的單調 PC 來表示，而另一些分布則更適合用平方后的實值 PC 來表示。

在下一節中，我們將探討如何調和這些不同的概率分布建模方法。

4 朝向深度和的平方的平方的統一模型

在本節中，我們深入探討單調電路與平方電路之間的關系。首先，我們展示如何為平方電路引入復數參數化（命題1）。其次，我們從一個新的角度解釋單調電路與平方電路：它們是邊緣化潛在變量的不同方式（圖1）；并在此基礎上提出一種新的可追蹤模型——Inception PCs，將這兩種方法結合起來（定理3）。

4.1 復數參數

我們首先指出，除了簡單的負參數之外，我們還可以允許使用復數權重和輸入函數2，即取值在復數域 ? 中。為了確保平方電路的非負性，我們將一個電路與其復共軛相乘。也就是說：

由于復共軛是復數域 ? 的一個域同構映射（field isomorphism），對一個電路取復共軛，就如同對其中的每一個權重和輸入函數分別取復共軛，同時保留原電路相同的有向無環圖（DAG）結構。這使得我們能夠高效地將概率分布 表示為一個（平滑且結構化可分解的）電路：

4.2 深度和的平方的平方：一種潛在變量視角

在概率電路的潛在變量解釋（Latent Variable Interpretation, LVI）中（Peharz 等人，2016），對于每一個和節點（sum node），我們分配一個分類潛變量（categorical latent variable），其中該潛變量的每一個狀態對應和節點的一個輸入；我們在圖1a中展示了一個示例。在這種解釋下，當在概率電路中進行推理時，我們事先對所有潛變量進行邊緣化（marginalize over）。

在電路具有結構化可分解性的前提下，我們可以為電路中出現的變量作用域（即變量集合）分配對應的潛變量。具體來說，對于兩個具有相同作用域 sc(n) = sc(n′) 的和節點 n 和 n′，它們共享同一個潛變量 Zsc(n)。設 Z 為所有潛變量的集合，則概率電路所表示的函數可以表達為：

其中，對于任意 z 的取值，fC(V,z) 是輸入函數的乘積。

換句話說，給定一個潛變量 z 的取值后，概率電路所表示的分布是完全可分解的（fully factorized）。

然而，當我們考慮由平方電路定義的概率分布時，對這些潛變量的解釋就變得復雜了。關鍵問題是：我們是在平方之前還是之后對潛變量進行邊緣化？

我們在圖1b和圖1c中展示了這兩種情況：

• 在圖1b中，我們在邊緣化潛變量 Z之前進行平方。在這種情況下，每個和節點的權重都與其共軛相乘，結果得到一個具有非負實數參數的和節點。

• 另一方面，如果我們在平方之前就對潛變量進行邊緣化（如圖1c所示），那么我們將面對一個具有四個子節點且權重為復數的和節點。

有趣的是，前一種情況與直接構造一個單調PC非常相似，而后一種情況則更像是在沒有潛變量的情況下進行顯式的平方操作。

這表明，我們可以通過決定是否將潛變量的求和放在平方的內部或外部，來在單調PC與平方PC之間切換。

基于這一視角，我們提出了以下模型，它顯式地將兩種類型的潛變量引入到電路中，從而生成一個深度的和的平方的平方（deep sum-of-square-of-sums）結構：

由于U-潛變量（U-latents）位于平方之外，而W-潛變量（W-latents）位于平方之內，我們將它們分別稱為1-范數潛變量和2-范數潛變量。

接下來的定理表明，給定一個 Inception PC，我們可以高效地將其“具體化”為一個僅作用于觀測變量 V 上的可追蹤概率電路，該電路表示 Inception PC 的分布：

在圖2中，我們展示了一個示例性的 Inception PC（的一部分），以及通過定理3進行“具體化”后的形式。在本文的其余部分，我們將這種形式稱為materialized Inception PC（具體化的 Inception PC）。關鍵在于：我們可以通過對 materialized IncPC 使用標準的 PC 推理過程，來高效地對 Inception PC 的分布進行推理。

雖然這不是必須的，但我們假設（與單調PC和平方PC的LVI一致）W 和 U 是分類變量（categoricals），并且作用域覆蓋這些變量的輸入節點是指示函數（indicator），例如

然而，當我們同時使用兩種類型的潛變量時，我們就得到了一個廣義的PC模型，其表達效率嚴格優于單獨使用任一類型。

推論 1（Inception PCs 的表達效率）：
Inception PCs 在表達效率上嚴格優于（結構化可分解的）單調PC和平方PC。

5 張量化 Inception PCs

到目前為止，我們已經描述了 Inception PCs 的一個通用形式，它只要求電路具有平滑性和結構化可分解性。在實際應用中，我們希望設計特定的電路架構以用于學習與推理。

本節的目的有兩個：

(i) 提出一種適合在 GPU 上進行學習與推理的 Inception PC 架構；
(ii) 從另一個角度——即層級張量收縮（hierarchical tensor contractions）——來重新理解 Inception PCs。

我們在圖3中展示了這一和節點區域的結構。從高層次來看，圖3中各節點組之間的連接可以看作是一個標準的單調PC；特別是，每個和節點組的值就是其子節點的加權和。然而，與傳統的標量節點之間的加權邊不同，這里的每條加權邊連接的是兩組二維的“平方”節點（"squared" nodes）。

前向傳播的復雜度可以從公式（5）中的張量收縮中推導出來。在表1中，我們比較了單調PC、平方PC和Inception PC在每個區域上的參數數量（即內存開銷）以及前向傳播時間復雜度，其中 B 表示數據批次的大小。

可以看出，當設置 ，Inception PC 的參數數量 / 復雜度分別與單調PC和平方PC相同，只是在平方PC的情況下復雜度略有不同：這是因為在這一特殊情況下，平方操作可以在每批次中僅執行一次（Loconte 等人，2024b）。

與之前的工作（Peharz 等人，2020a）一樣，我們將電路組織成層（即可以同時計算的一組區域），以進一步利用GPU的并行計算能力。在訓練過程中，我們對訓練集的負對數似然使用梯度下降法進行優化。在使用復數參數的情況下，我們采用Wirtinger 導數（Kreutz-Delgado, 2009）來優化復數權重和輸入函數。為了實現數值穩定性，我們使用了一種針對復數的 log-sum-exp 技巧的變體，具體描述見附錄D。

6 相關工作

概率模型的空間可以通過可追蹤性（tractability）和表達效率（expressive efficiency）的視角來有效刻畫（Choi, Vergari 和 Van den Broeck，2020）。可追蹤性是一個連續譜系，從不可追蹤的模型（如擴散模型 Ho, Jain 和 Abbeel，2020；變分自編碼器 Kingma 和 Welling，2014），到允許可追蹤似然的模型（如歸一化流 Papamakarios 等人，2021），再到允許可追蹤邊緣分布及更復雜查詢的模型（如概率電路 Vergari 等人，2021；Wang 等人，2024）。

然而，由于計算圖中施加了特定結構，概率電路在實踐中通常比那些可追蹤性較低的模型表達能力弱。因此，已有大量研究致力于在保持可追蹤性的前提下提升概率電路的表達效率（Sidheekh 和 Natarajan，2024）。

我們的工作建立在電路領域長期的研究基礎上，這些研究考察了放寬電路中單調性條件的影響。理論上已知，在算術電路中引入負參數可以在簡潔性上帶來指數級的提升（Valiant，1979），盡管這一結論并不適用于所有類型的子電路（de Colnet 和 Mengel，2021）。在實際應用中，近期的研究也嘗試在概率建模中利用負參數（Zhang, Holtzen 和 Van den Broeck，2020；Zhang, Juba 和 Van den Broeck，2021；Sladek, Trapp 和 Solin，2023；Loconte 等人，2024b）。

Yu、Trapp 和 Kersting（2023）設計了用于表示分布特征函數的電路，該函數可以取復數值（特別是使用復數葉子節點）。與我們工作同期，Loconte、Mengel 和 Vergari（2025）提出使用多個平方電路的和來克服我們在本文中觀察到的類似限制。

此外，還存在一系列其他采用負參數化和/或平方機制的概率模型：

• 張量網絡

  （tensor networks），例如流行的矩陣乘積態（Matrix Product States, MPS）（Perez-Garcia 等人，2007），通過稀疏張量收縮緊湊地編碼函數。它們常用于建模量子態，其中觀測的概率是通過對波函數平方得到的（即 Born 規則，Dirac，1981）；最近也被用于概率建模（Cheng 等人，2019；Glasser 等人，2019）。

• 在核方法文獻中，半正定模型（positive semidefinite models）（Rudi 和 Ciliberto，2021）使用淺層的平方和來定義未歸一化的分布。

• Tsuchida、Ong 和 Sejdinovic（2023, 2024）最近提出了平方神經族（squared neural families），其密度函數中使用了神經網絡的平方 L2 范數，并嚴格推廣了指數族模型。

我們在附錄A中詳細討論了這些模型與我們提出的 Inception PC 的技術聯系。

7 實驗

在我們的實驗中，我們旨在回答以下研究問題：

1. Inception PCs 是否在表達能力和建模性能上優于單調PC和平方PC？

2. 在建模性能和計算成本之間，1-范數潛變量（one-norm latents）與2-范數潛變量（two-norm latents）的數量權衡如何？

3. Inception PCs 的復數參數化與非負參數化和實數參數化相比表現如何？

在所有實驗中，我們都使用了隱藏 Chow-Liu 樹（Hidden Chow-Liu Trees, HCLT）作為概率電路的 vtree（Liu 和 Van den Broeck，2021），因為它滿足所需的結構化可分解性，并且已被證明可以為概率電路提供最先進的似然性能。

更多實驗細節請參見附錄 E。

7.1 二值數據集

我們首先在20 個二值數據集上進行評估，這些數據集被廣泛用作密度估計的基準測試數據（Rooshenas 和 Lowd，2014；Peharz 等人，2020b）。

我們的目標是研究在這組數據集中：

1. 非負參數化、實數參數化和復數參數化

   之間有何差異；

2. Inception PCs

   是否能夠有效利用兩種類型的潛變量，通過與單調PC和平方PC的對比來驗證這一點。

具體來說，我們為不同模型設定了以下參數規模：

• 單調 PC：(N?, N?) = (8, 1)

• 平方 PC：(N?, N?) = (1, 8)

• Inception PC：(N?, N?) = (8, 8)

我們使用 Adam 優化器（Kingma 和 Ba，2015），以學習率 0.01，對每個模型訓練 100 輪，優化其負對數似然。每種配置下我們都進行了 5 次實驗并取平均結果。

實驗結果見表2。可以看到，在 20 個數據集中，Inception PCs 在 14 個上取得了最佳似然表現，這證實了它相比僅使用平方機制具有更強的建模能力。

與現有模型相比，Inception PCs 的表現也非常優異，包括可追蹤模型如 RAT-SPNs（Peharz 等人，2020b），以及不可追蹤模型如重要性加權自編碼器（IWAE）（Burda, Grosse 和 Salakhutdinov，2016）。

有趣的是，即使平方PC使用的是非負參數，它們的表現也優于具有相同參數數量的單調PC——這一現象也在 Loconte 等人（2024b）圖3中被觀察到。

更值得注意的是，盡管邊緣權重的復數參數化嚴格地推廣了實數和非負參數化，但在性能上并沒有明顯的優勢趨勢。在許多情況下，非負參數化反而能取得與實數或復數參數化相當甚至更好的似然表現。

我們發現，這（至少部分原因）是因為復數和負參數化更容易過擬合（參見附錄F中的訓練似然結果）。

7.2 擴展到大規模圖像數據集

在本節中，我們在大規模圖像數據集上進行實驗，特別是將 ImageNet（Deng 等人，2009）降尺度為32×32和64×64的版本。

我們遵循近期在這些圖像數據集上構建概率電路模型的相關工作（Liu, Zhang 和 Van den Broeck，2023；Liu 等人，2023；Liu, Ahmed 和 Van den Broeck，2024），使用有損的YCoCg 色彩空間變換對原始 RGB 數據進行轉換。需要注意的是，因此在 YCoCg 轉換后的數據上獲得的似然值不能直接與原始 RGB 數據上的似然值進行比較。

此外，為了提高訓練效率，我們僅在原始圖像的16×16 像素塊上進行訓練，使得每個 PC 模型建模16×16×3 = 768 個變量，每個變量具有256 個類別（對應像素顏色值）。

我們仍然使用 Adam 優化器以學習率 0.01 來最小化負對數似然函數進行訓練，并使用測試集上的每維度比特數（bits-per-dimension,bpd）作為評估指標。

我們首先考察兩種潛變量之間的權衡關系。為此，在圖4中，我們在 ImageNet32 數據集上繪制了不同 (N?, N?) 配置下的測試 bpd 曲線。這些配置是基于對 N?, N? ∈ {1, 2, 4, 8, 16, 32, 64} 的搜索結果確定的，同時受限于每個區域最多允許21? = 262,144 FLOPS（浮點運算次數/秒）的計算預算（參見表1）。

可以看出，在這些限制條件下最優的配置是(N? = 32, N? = 4)，對應的測試 bpd 為4.19。該配置結合了1-范數潛變量和2-范數潛變量，而不是單純使用單調結構（N? = 1）或平方結構（N? = 1）。

在表3中，我們總結了在ImageNet32和ImageNet64數據集上的實驗結果：

• MPC

  表示一個單調PC，配置為 (N?, N?) = (64, 1)

• SQC

  表示一個平方PC，配置為 (N?, N?) = (1, 64)

• IncPC

  表示一個張量化的 Inception PC，在給定計算時間約束下采用最優配置 (N?, N?)

作為對比，我們還列出了使用期望最大化算法（EM）訓練的單調 HCLT PC，以及使用潛變量蒸餾（LVD）方法訓練的模型——后者通過從現有的深度生成模型中提取信息來指導 PC 的潛空間學習（Liu, Zhang 和 Van den Broeck，2023）。

實驗結果顯示：通過 Adam 初始化即可有效地訓練可追蹤的概率電路模型，其 bpd 性能可以達到當前最先進的水平。

8 結論

總而言之，我們展示了兩類重要的可追蹤概率模型——單調結構化可分解PC與平方實數結構化可分解PC——在表達效率上通常是不可比較的。因此，我們提出了一種新的概率電路模型——Inception PCs，它基于“深度和的平方的平方”（deep sums-of-squares-of-sums）結構，統一并推廣了上述兩種方法，并且可以使用復數參數。

我們還通過實驗驗證了 Inception PCs 在多種表格數據集和圖像數據集上能夠提供更優的性能。

未來值得探索的方向包括：改進 Inception PCs 中復數參數的優化方法；以及通過設計更高效的架構來降低訓練的計算成本。

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