Restructuring Tractable Probabilistic Circuits

概率電路的結構重構

https://arxiv.org/pdf/2411.12256

摘要

概率電路（Probabilistic circuits, PCs）是一種統一的概率模型表示方法，能夠支持可高效推理的概率推斷。許多概率電路的應用，例如可控文本生成，依賴于高效地將兩個電路相乘的能力。現有的乘法算法要求這兩個電路遵循相同的結構，即它們的變量作用域（variable scopes）要根據相同的 vtree（變量樹）進行分解。在本研究中，我們提出并探討了重構結構化（結構-分解式）概率電路的任務，即將一個結構化的概率電路轉換為符合目標 vtree 的形式。我們提出了一個通用的方法來解決這個問題，并展示了這種方法可以導出新的多項式時間算法，用于對遵循不同 vtree 的電路進行乘法運算。此外，我們還提出了一種實用的深度縮減算法，能夠在保持結構可分解性的同時減少電路的深度。我們的工作為高效的概率電路推理開辟了新的途徑，表明可以在訓練時使用限制較少的概率電路結構，而在推理階段通過改變其結構來實現高效的推理。

1 引言

深度生成建模中的一個關鍵挑戰是概率推理的不可行性 （intractability）（Roth, 1996；Geh 等，2024）。為了解決這一挑戰，概率電路（Probabilistic circuits, PCs）（Darwiche, 2003；Poon 與 Domingos, 2011；Choi 等，2020）作為一種統一表示方法逐漸興起，用于表示高維概率分布下的可高效推理的生成模型。特別地，PCs 支持對各種推理查詢（如邊緣化）進行高效且精確的計算。

PCs 的可推理性在多個應用中被證明至關重要，例如因果推理（Ze?evi? 等，2021；Wang 與 Kwiatkowska, 2023；Busch 等，2024）、知識圖譜學習（Loconte 等，2023）以及確保決策過程中的公平性（Choi 等，2021）。

概率電路將概率分布表示為加法和乘法構成的計算圖 。設計 PC 的一個關鍵方面是其計算圖的結構，即分布如何被分解為（條件）獨立的組成部分。PC 的結構會影響其推理的可行性、建模性能以及計算效率。

在本研究中，我們考慮重構 PC 的問題：構建一個新的 PC，使其遵循特定（目標）結構，同時表示相同的概率分布。我們提出了一種通用算法來重構結構可分解的電路，通過考慮它們的圖模型表示來進行。具體來說，我們利用圖模型來分析條件獨立性，并遞歸地構造出符合目標結構的新 PC。

隨后，我們研究了 PC 重構的兩個關鍵應用：電路乘法 和深度縮減 。電路乘法是一種基礎操作，用于回答各種推理查詢（Vergari 等，2021），例如在邏輯約束下進行條件推理（Choi 等，2015；Ahmed 等，2022；Liu 等，2024b；Zhang 等，2023, 2024）、計算分類器的期望預測值（Khosravi 等，2019）、因果后門調整（Wang 與 Kwiatkowska, 2023），以及通過平方提升電路的表達能力（Loconte 等，2024c,b；Wang 與 Van den Broeck, 2024）。

盡管在不同結構之間進行電路相乘的問題在一般情況下是 #P-難的（Vergari 等，2021），但我們識別出一類新的 PC，稱為連續電路 （contiguous circuits），在這些電路中，使用我們的算法可以在多項式（或擬多項式）時間內完成不同結構之間的乘法運算。

我們也考慮了深度縮減 （depth reduction），這是一個成熟的理論工具，用于降低電路的深度（Valiant 等，1983；Raz 與 Yehudayoff, 2008）。最近的 PC 實現主要關注通過現代 GPU 對 PC 推理進行逐層并行化，而深度縮減可以實現更高的并行性（Peharz 等，2020；Dang 等，2021；Liu 等，2024a；Loconte 等，2024a）。在本文中，我們展示了我們的重構算法可用于將一個結構可分解的電路轉換為等效的對數深度 （log-depth）電路，其上界遠比之前的工作更緊致。這為實際應用深度縮減技術以加速 PC 推理提供了新的可能性。

綜上所述，我們的主要貢獻包括：

1. 我們提出了 重構問題 ，它涉及在不同可推理 PC 結構之間轉換的計算復雜度；

2. 我們提出了一種在任意兩種結構之間映射的 通用算法 （第 3 節）；

3. 我們展示了對于一類 連續結構 （contiguous structures），重構可以在（擬）多項式復雜度內完成（第 4 節）；

4. 我們說明了重構在兩個重要問題上的應用： 概率分布相乘 （第 4 節）和 模型結構深度縮減 （第 5 節），并在其中推導出了關于可推理性的新結果。

2 概率電路

記號說明
我們將使用大寫字母表示變量（例如 X），使用小寫字母表示這些變量的取值（例如 x）。我們使用粗體字母表示變量集合或取值集合（例如 X,x）。

定義 2.1（概率電路）
一個概率電路（Probabilistic Circuit，PC）A=(G,w) 是通過一個帶權的根有向無環（計算）圖（DAG）來表示隨機變量 X 上的聯合概率分布。該圖由加法節點（⊕）、乘法節點（?）和葉節點（L）組成，并由參數 w 進行參數化。每個節點 t 表示一個概率分布 pt(X)，其定義是遞歸進行的：

直觀上，乘法節點表示其子節點分布的因子化乘積，而加法節點表示其子節點分布的加權混合。為了簡化，在本文其余部分我們假設加法/葉節點與乘法節點交替出現（即加法節點的子節點是乘法節點，乘法節點的子節點是葉節點或加法節點），并且每個乘法節點恰好有兩個子節點。

PCs 的關鍵特性是它們的可推理性 （tractability），即能夠以精確且多項式時間內回答關于其所表示分布的各種查詢。兩個常見的性質——平滑性 （smoothness）和可分解性 （decomposability）可以確保高效的邊緣化能力：

定義 2.2（平滑性與可分解性）
如果一個加法節點的所有子節點具有相同的作用域，則稱該加法節點是平滑的 。如果一個乘法節點的各個子節點具有互不重疊的作用域，則稱該乘法節點是可分解的 。如果一個 PC 中所有的加法節點都是平滑的（對應地，所有的乘法節點都是可分解的），則稱該 PC 是平滑的（對應地，是可分解的）。

直觀上，可分解性要求一個乘法節點將其作用域劃分給它的各個子節點。對于許多其他重要的查詢任務，使用一種更強的可分解性形式是有益的，稱為結構化可分解性 （structured-decomposability），它要求具有相同作用域的乘法節點必須按照相同的方式進行分解。

結構化可分解性的主要優勢在于，它能夠對兩個遵循相同 vtree 的電路進行可高效計算的電路乘法，而這是許多應用中的核心子程序。然而，總體而言，結構化可分解電路在表達效率上可能較差（de Colnet 和 Mengel，2021）。

3 PC 重構（PC Restructuring）

在本節中，我們描述一種通用方法 ，用于將任意結構化可分解的概率電路（PC）重構為符合目標 vtree 的形式。該方法包括三個步驟：

1. 構建該概率電路的貝葉斯網絡表示；

2. 在貝葉斯網絡中找出一組潛在變量，它們能夠誘導出目標 vtree 所需的條件獨立性；

3. 利用第（2）步中得出的條件獨立性，遞歸地構建一個新的結構化概率電路。

已知可以高效地將一個樹形結構的貝葉斯網絡 編譯成一個等效的概率電路（Darwiche, 2003；Poon 與 Domingos, 2011；Dang 等，2020；Liu 與 Van den Broeck, 2021）。在本小節中，我們將描述如何進行相反方向的轉換，即將任意一個結構化可分解的 PC 轉換為具有線性數量變量的樹形貝葉斯網絡。

由于我們已經證明了 pA 和 pG 在觀測變量 X 上表示相同的分布，因此在不會引起歧義的情況下，我們將省略下標。

3.2 遞歸式 PC 重構

假設我們有一個概率電路 A，它具有對應的貝葉斯網絡表示 GA 和 vtree V，并設 W 是另一個 vtree。我們現在展示如何構建一個新的、符合 W 結構的概率電路，使其與 A 表示相同的分布。

其大致思路是：為 W 中的每一個 vtree 節點 w∈W 標注一個潛在變量的子集 Cw?GA，使得在給定 Cw的條件下，Xw 與 X?Xw 是條件獨立的。為了刻畫這種性質，我們引入“覆蓋”（covers）的概念：

其中，第一步是由性質 2 和 3 得出，第二步則是由定義 3.7 中的所有性質得出。

該遞推關系在概率電路中的具體實現如圖 2 所示。注意，如果 w 是根節點，則 p(Xw∣Cw) 就變成了 p(X)，即一個表示概率電路 A 分布的單一加法節點。

完整的遞歸過程由算法 1 給出。

3.3 計算 Vtree 的標注（Labelling）

接下來一個自然而然的問題是：如何相對于貝葉斯網絡 GA，為 vtree W 計算出一個有效的標注（labelling）。

命題 3.10算法 2 能夠相對于 GA 計算出一個有效的標注。

盡管如此，我們證明了 算法 1 為概率電路（PC）的 乘法 和 深度縮減 任務提供了新的 多項式時間算法 。具體來說，我們展示了對于一些重要的 PC 子類，我們可以計算出具有 常數大小 或 O(log n) 大小的 vtree 標注。更多細節請參見第 4 節和第 5 節。

3.4 推論

在我們掌握了重構算法之后，我們現在來考察對另外兩類電路的重構問題：即確定性概率電路 （deterministic PCs）和邏輯電路 （logical circuits）。

定義 3.11（確定性）
一個加法節點是確定性的 ，如果對于變量集合 X 的每一個取值 x，最多只有一個子節點 c 返回非零值（即 pc(x)>0）。
如果一個概率電路中所有的加法節點都是確定性的，則稱這個概率電路是確定性的 。

確定性 對于許多推理任務的可推理性至關重要，例如計算最可能的狀態（MAP）（Peharz 等，2016；Conaty 等，2017），或計算概率電路分布的熵（Shih 與 Ermon，2020；Vergari 等，2021）。因此，我們自然會問：使用我們的重構算法是否能夠保持這種確定性。

斷言 3.12
算法 1 保留確定性。

證明 如果原始電路是確定性的，那么對觀測變量的每一個賦值都會唯一確定所有潛在變量的取值（因此這些潛在變量在重構過程中也是被確定的）。所以構造出的加法節點也是確定性的。

雖然到目前為止我們主要關注的是概率電路，但我們的重構算法也適用于邏輯電路 ——特別是結構化可分解否定范式電路 （Structured-Decomposable Negation Normal Form circuits，簡稱 SDNNF）3（Pipatsrisawat 與 Darwiche，2008）。

要看到這一點，我們可以使用一個簡單的技巧：

1. 將邏輯電路轉換為概率電:將邏輯中的 ∨ 替換為 ⊕，∧ 替換為 ?，并為 ⊕ 邊分配正權重；

2. 對該概率電路進行重構；

3. 再將概率電路轉換回邏輯電路：將 ⊕ 替換為 ∨，? 替換為 ∧，并去除權重。

可以立刻看出，在整個過程中，邏輯電路與其對應的概率電路具有相同的支持集（support）。

此外，也不難看出，這一過程在邏輯電路上同樣保留了確定性。例如，一個有序二元決策圖（OBDD）可以被高效地重構為具有逆序結構 的確定性 SDNNF，同時仍能執行模型計數（model counting）（Darwiche 與 Marquis，2002）。

4 概率電路乘法（PC Multiplication）

重構概率電路（PC）的一個重要應用是電路乘法 ：給定兩個概率電路 A 和 B，目標是構造一個可高效推理的概率電路 C，使得之前關于概率電路乘法的研究僅限于遵循相同 vtree 的結構化電路 （Shen 等，2016；Vergari 等，2021）。
電路重構為我們提供了一種直接的方法來實現不同 vtree 下的兩個結構化電路之間的乘法 ，因為我們只需將其中一個電路重構為與另一個兼容的結構即可。

盡管重構后的電路在一般情況下可能具有指數級的大小，但在本節中，我們將探討一些實際情況下，即使在不同 vtree 下進行電路乘法也是可行的（tractable）。

此外，我們還將展示如何通過“即時重構 ”（on-the-fly restructuring），即使其中一個電路不是結構化可分解的 ，也能實現電路乘法。

我們首先介紹一個關于可推理概率電路的新結構性質——連續性 （Contiguity）。

定義 4.1（連續性）

4.2 推廣到非結構化概率電路

到目前為止，我們一直假設 A 和 B 都是結構化的概率電路 。但我們認為可以進一步推廣我們的結果，去掉 B必須是結構化電路這一限制，定理 4.4 和 4.6 仍然成立。

我們通過一個例子來說明這個想法：展示如何將一個遵循線性 vtree 的連續結構化 PC A與一個任意的連續 PC B相乘。

由于 B 不是結構化可分解的，我們無法將 A 重構為與 B 的 vtree 一致的結構。然而，我們可以使用與算法 1 類似的思想，在自底向上地將 A 與 B 相乘的過程中，即時重構 （on-the-fly）A 的結構。

具體來說，對于 B 中出現的每一個可能的作用域 Xa:b，我們遞歸地構造出如下函數的電路表示：

該遞推關系與算法 1 類似，感興趣的讀者可參考附錄了解詳細內容。

定理 4.9
設 A 和 B 是兩個連續型概率電路，其中 B 不一定是結構化的。如果 A 是遵循線性 vtree 的結構化電路，則 A與 B 可以在多項式時間內相乘 ，且乘積電路的大小被限制為 O(∣A∣2?∣B∣)。

作為電路乘法的一個明確應用，我們可以考慮受約束的文本生成 問題，其中線性結構的概率電路（如 HMM）與表示邏輯約束的確定性有限自動機（DFA）相乘（Zhang 等，2024）。

我們的結果表明，HMM 還可以與諸如句子決策圖 （SDDs）（Darwiche，2011）這樣的連續型邏輯電路 相乘。SDDs 被證明具有更強的表達能力效率（Bova，2016）。

此外，根據定理 4.2，我們還可以高效地將 HMM 與（概率）上下文無關文法（(P)CFGs）相乘，這包含了最近的一項成果：HMM 可以在無歧義 CFG 上進行高效邊緣化（Marzouk 與 de La Higuera，2022）。

我們關于連續型概率電路相乘的研究結果，為將 Zhang 等人（2024）的方法推廣到更廣泛的電路和約束類型提供了新的可能性。

5 概率電路的深度縮減（PC Depth Reduction）

概率電路的深度縮減 是指構造一個與原電路等效、但深度更小的新電路，例如將深度縮減為變量數量的對數級別。

目前已知存在一種適用于一般電路的深度縮減算法（Valiant 等，1983；Raz 與 Yehudayoff，2008；Yin 與 Zhao，2024），但它沒有利用結構化這一特性。

在本文中，我們展示了如何通過重構 ，將一個結構化可分解電路 縮減為一個等效的對數深度電路 。

與乘法任務不同的是，在深度縮減中我們并不關心要重構到哪一個具體的 vtree，而是只要是一個具有對數深度的 vtree 即可。

因此，關鍵步驟是找到一個具有對數深度的 vtree，并使用算法 1 （以及某種有效的標簽選擇方式）進行重構，使得電路大小最多只增加多項式倍。

算法 4 構造了一個具有常數大小標注的對數深度 vtree。

6 相關工作

概率電路（Probabilistic Circuits, PCs）已經成為可高效推理的概率模型 的一種統一表示形式（Choi 等，2020；Sidheekh 與 Natarajan，2024），包括諸如：

• 和積網絡（Sum-Product Networks，Poon 與 Domingos，2011），

• 割集網絡（Cutset Networks，Rahman 等，2014），

• 概率句子決策圖（Probabilistic Sentential Decision Diagrams，Kisa 等，2014），

• 概率生成電路（Probabilistic Generating Circuits，Zhang 等，2021；Harviainen 等，2023；Agarwal 與 Bl?ser，2024；Broadrick 等，2024）。

大量研究致力于學習適合數據的 PC 結構（Liang 等，2017；Dang 等，2020；Yang 等，2023），但對結構依賴型查詢的影響研究相對較少。我們通過提供一個通用的重構算法填補了這一空白，并給出了在特定情況下具有（擬）多項式復雜度的具體應用。

作為分布的可高效表示形式，PC 被廣泛用作圖模型中推理任務的目標編譯形式（Darwiche，2003；Chavira 與 Darwiche，2008；Rooshenas 與 Lowd，2014）。隱藏樹結構的貝葉斯網絡也被用作學習概率電路的起點（Dang 等，2020；Liu 與 Van den Broeck，2021；Dang 等，2022a）。

一種特別有用的分析學習概率電路的方法是將其解釋為潛在變量模型 （latent variable models）（Peharz 等，2016）。通過為每個加法節點引入一個潛在變量，可將可分解且平滑的 PC 解釋為貝葉斯網絡（Zhao 等，2015）。

我們將結構化 PC 轉換為貝葉斯網絡的過程最接近于 Butz 等人（2020）和 Papantonis 與 Belle（2023）提出的“反編譯”方法，但我們并不假設該 PC 是從貝葉斯網絡中編譯而來的。

Valiant 等人（1983）的開創性研究表明，任何多項式大小的算術電路都可以轉換為等效的、深度為多對數級（polylogarithmic）的電路。
Raz 與 Yehudayoff（2008）表明，這一過程可以保持語法上的多線性（即可分解性）。
最近，Yin 與 Zhao（2024）展示了通過深度縮減方法，可以將可分解和平滑的 PC 轉換為樹形結構的 PC，并給出了一個準多項式的上界。

我們的重構方法主要關注結構化可分解電路 ，并通過圖形模型的視角分析，得出了更緊的復雜度上界。

7 討論

我們提出了概率電路重構 的問題，并開發了一種通用算法，用于將一個結構化可分解電路 重構為任意目標 vtree 結構 。

我們的方法利用了這樣一個觀點：將結構化可分解電路解釋為潛在變量樹結構的貝葉斯網絡 。基于這一解釋，我們可以利用貝葉斯網絡的概率語義，遞歸地構造出符合目標 vtree 的新電路。

作為重構的具體應用，我們展示了如何對兩個不一定具有相同結構 、但滿足某種連續性性質 （contiguity）的電路進行可高效計算的乘法操作 ；我們也展示了如何將一個電路重構為對數深度 的形式，且其大小僅增加次二次方級別 。

我們的工作邁出了理解“何時以及如何通過可高效變換來連接結構化電路空間”的重要一步——這個空間也被稱為層次化張量分解 （hierarchical tensor factorizations）（Loconte 等，2024a）。

許多有趣的理論問題仍有待解決，例如：我們算法的最優性 問題，以及某些特定結構下的電路復雜度下界 問題。

我們也預見，我們的重構算法不僅將在概率電路研究社區內催生新的方法論，也將在高維張量和概率分布的結構化表示領域中帶來廣泛影響。

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