Probabilistic Circuits:A Unifying Framework for Tractable Probabilistic Models?

概率電路：可處理概率模型的統(tǒng)一框架

https://starai.cs.ucla.edu/papers/ProbCirc20.pdf

1. 引言

概率模型是現(xiàn)代機(jī)器學(xué)習(xí)（ML）和人工智能（AI）的核心。事實上，概率論為在不確定性存在的情況下進(jìn)行決策提供了一種有原則且?guī)缀醣黄毡椴捎玫臋C(jī)制。例如，在機(jī)器學(xué)習(xí)中，我們假設(shè)數(shù)據(jù)是從一個未知的概率分布中抽取的。能夠以任何形式獲取這個分布，是統(tǒng)計機(jī)器學(xué)習(xí)的“圣杯”。它將許多機(jī)器學(xué)習(xí)任務(wù)簡化為簡單的概率推理問題。同樣，許多形式的基于模型的人工智能直接試圖將世界運行機(jī)制表示為某種形式的概率分布。

因此，人們在機(jī)器學(xué)習(xí)中投入了大量精力來從數(shù)據(jù)中學(xué)習(xí)這一分布。我們擬合越來越具有表達(dá)能力的概率模型作為密度估計器，使它們盡可能接近真實的數(shù)據(jù)生成分布。這種方法最近因深度生成模型的發(fā)展而流行起來，如生成對抗網(wǎng)絡(luò)（Goodfellow 等，2014）、變分自編碼器（Rezende 等，2014；Kingma 和 Welling，2013）以及歸一化流（Papamakarios 等，2019）。同時，通過統(tǒng)計學(xué)（Carpenter 等，2017）、編程語言（Holtzen 等，2020）、認(rèn)知科學(xué)（Griffiths 等，2010）和人工智能（Milch 等，2005；Domingos 和 Lowd，2009；Fierens 等，2015）領(lǐng)域的努力，也開發(fā)出了越來越豐富、能夠簡潔表達(dá)復(fù)雜分布的建模語言。

然而，這些概率模型日益增強的表達(dá)能力，以及現(xiàn)代神經(jīng)密度估計器在大規(guī)模數(shù)據(jù)上的可擴(kuò)展性，也帶來了巨大的代價：除了最簡單的情況外，幾乎無法在任何復(fù)雜的概率推理場景中實現(xiàn)可靠而高效的概率推理。具體來說，上述模型只能依賴各種近似技術(shù)來回答關(guān)于其表示的概率分布的基本問題。計算邊緣概率、條件概率、期望值或分布的眾數(shù)（mode），都只能通過幾乎沒有理論保證的近似方法完成。諷刺的是，隨著我們的模型越來越精確地擬合真實分布，我們在某種程度上卻離通過概率推理解決問題的目標(biāo)越來越遠(yuǎn)，這在一定程度上削弱了概率建模與學(xué)習(xí)的根本目的。

這種概率生成模型的狀態(tài)與該領(lǐng)域誕生之初的狀態(tài)形成了鮮明對比。在開創(chuàng)性的1960年代，隱馬爾可夫模型（HMM）（Stratonovich, 1960；Baum 和 Petrie, 1966）、卡爾曼濾波器（Kalman, 1960）、樸素貝葉斯分類器的早期應(yīng)用（Bailey, 1965；Boyle 等，1966）以及 Chow-Liu 樹學(xué)習(xí)算法（Chow 和 Liu, 1968）相繼問世。這些經(jīng)典概率模型具有明顯的局限性：它們的表達(dá)能力遠(yuǎn)不如當(dāng)今可用的模型。但它們有一個顯著而重要的優(yōu)點：具備高效的概率推理算法。這些可處理的概率模型后來支持了數(shù)十年來的科學(xué)和工程突破。

當(dāng)前在概率 AI 和 ML 中的一個趨勢是設(shè)計并利用那些理論上可以保證可靠且高效概率推理的模型。這些模型通常統(tǒng)稱為可處理概率模型（Tractable Probabilistic Models，TPMs），允許復(fù)雜推理過程在多項式時間內(nèi)被精確計算。一些“經(jīng)典”的 TPM 示例包括卡爾曼濾波器（Musoff 和 Zarchan，2009）、隱馬爾可夫模型（Koller 和 Friedman，2009）、樹分布（Chow 和 Liu，1968）以及有界樹寬的概率圖模型（PGMs）（Bach 和 Jordan，2002）。盡管這些模型不僅廣泛用于 AI 和 ML，還應(yīng)用于控制理論、系統(tǒng)工程和統(tǒng)計學(xué)，但它們被認(rèn)為在表達(dá)能力上有所限制。近年來，一種新興的 TPM 模型浪潮出現(xiàn)，承諾在不犧牲可處理性的前提下提升表達(dá)能力和效率。這些模型包括算術(shù)電路（Darwiche，2003）、概率決策圖（Jaeger，2004）、與或搜索空間（Marinescu 和 Dechter，2005）、多值決策圖（Dechter 和 Mateescu，2007）、和積網(wǎng)絡(luò)（Poon 和 Domingos，2011）、割集網(wǎng)絡(luò)（Rahman 等，2014）以及概率句子決策圖（Kisa 等，2014）。

在本文中，我們奠定了一個統(tǒng)一的框架來描述、學(xué)習(xí)和推理這些 TPM 形式體系，我們將這個框架命名為概率電路（Probabilistic Circuits，PCs）。PC 是定義聯(lián)合概率分布的計算圖，通過遞歸混合（求和單元）和因子分解（乘積單元）更簡單的分布（例如高斯分布或伯努利分布）來構(gòu)建整個分布。它們是具有表達(dá)能力的深度生成模型，因為它們確實將多個層次的潛變量編碼進(jìn)擁有數(shù)百萬連接和參數(shù)的大規(guī)模圖中。然而，與前述不可處理的神經(jīng)估計器不同，PC 允許在電路大小線性的時間內(nèi)進(jìn)行精確的概率推理，并且當(dāng)電路具有某些結(jié)構(gòu)屬性時，推理的成本是可以被理論認(rèn)證的。

具體而言，我們做出了以下貢獻(xiàn)。首先，我們將 PC 框架介紹為一個統(tǒng)一的理論和實踐工具，它可以推廣許多之前引入的 TPM 模型，同時抽象掉它們的語法差異。其次，我們將許多可處理的概率推理任務(wù)形式化并系統(tǒng)化為一類函數(shù)，稱為概率查詢類（probabilistic queries），這為我們討論現(xiàn)實世界中的概率推理需求以及比較不同模型類的推理能力提供了有用的抽象。第三，我們精確刻畫了在何種條件下可以在 PC 上高效計算這些查詢類，即當(dāng)其計算圖中存在某些結(jié)構(gòu)性質(zhì)時。最后，我們整理了已有的聯(lián)系，并繪制了 PC 與其他表示之間的新聯(lián)系，如多項式、分層混合模型、張量分解和邏輯電路，最終提出一個開放性問題：是否所有可處理的表示都可以表示為 PC，以及在什么條件下可以做到這一點。

本文其余部分組織如下：第 2 節(jié)介紹了必要的概率論背景知識，并形式化了概率查詢類和可處理表示的概念。第 3 節(jié)從零開始構(gòu)建 PC 框架，并討論如何使用 PC 計算完整證據(jù)查詢。第 4 節(jié)形式化了邊際推理及相關(guān)查詢類，并引入了平滑且可分解的 PC作為這些任務(wù)的可處理表示。在討論其他感興趣的查詢類之前，第 5 節(jié)建立了 PC 與其他表示之間的聯(lián)系，如（分層）混合模型和（多線性）多項式。第 6 節(jié)和第 8 節(jié)討論了計算由 PC 編碼的分布的眾數(shù)的任務(wù)。第 7 節(jié)討論了表達(dá)效率的概念，并在此概念下比較了不同的可處理 PC。隨后，第 9 節(jié)介紹了涉及兩個 PC 的高級查詢類，包括計算兩個 PC 之間的期望以及量化兩個 PC 分布之間距離的度量（如 Kullback-Leibler 散度）。第 10 節(jié)介紹了作為 PC 編碼的概率分布的變換，并進(jìn)行了討論。第 11 節(jié)為讀者提供了一個翻譯指南，將最受歡迎的 TPM 形式體系轉(zhuǎn)換為 PC，并討論了哪些結(jié)構(gòu)性質(zhì)——進(jìn)而對應(yīng)的可處理查詢類——被保留了下來。最后，在第 13 節(jié)結(jié)論之前，第 12 節(jié)追溯了 AI 和 ML 文獻(xiàn)中的可處理表示，從邏輯電路到其他半環(huán)的推廣。

2. 概率推理：模型、查詢與可處理性

概率電路是一種在大量查詢類別上具有可處理性的概率模型。本節(jié)提供了理解這些關(guān)鍵概念所需的背景知識。首先，我們討論概率模型是如何作為概率分布的緊湊表示，并介紹本文中將使用的概率符號。其次，我們將概率推理形式化為通過查詢概率模型來計算感興趣的量的問題。隨后，我們將這些查詢劃分為若干類別，這有助于我們刻畫它們在計算上的差異。第三，我們正式定義了對于某一類查詢而言“可處理”的含義。本節(jié)最后提出了一些在此背景下出現(xiàn)的科學(xué)問題，并將在本文后續(xù)部分予以回答：例如，什么使得一個概率模型對某一類查詢是可處理的？為此種可處理性我們需要付出怎樣的代價？

2.1 概率模型

概率論提供了一種有原則的方式來建模和推理我們所觀察到的世界中的不確定性。接下來，我們簡要回顧概率計算及其符號表示。1

世界是通過其屬性（或特征）來描述的。由于我們對其取值存在不確定性，因此我們將這些屬性視為隨機(jī)變量（Random Variables, RVs）。我們用大寫字母（如 X, Y）表示隨機(jī)變量，用粗體大寫字母（如X,Y）表示隨機(jī)變量集合。隨機(jī)變量X的定義域（domain）是指它可以取的所有可能值的集合，記作 val(X)。

隨機(jī)變量的取值用小寫字母（如 x, y）表示。當(dāng)上下文已明確是哪個隨機(jī)變量時，我們會將形如 X = x 的賦值簡寫為 x。

一個世界的狀態(tài)（也稱為配置、可能世界、完整狀態(tài)）是對每個隨機(jī)變量都賦予一個取值的情況。一個部分狀態(tài)則是僅對某些隨機(jī)變量賦值的情況。我們用粗體小寫字母（如y）來表示部分狀態(tài)或聯(lián)合狀態(tài)（如 Y = y，也可簡寫為 y）。

我們假設(shè)所有狀態(tài)x和隨機(jī)變量集合X都帶有下標(biāo)索引，即 xi 和 Xi。對于一組 n 個隨機(jī)變量X，其狀態(tài)空間 val(X) 是 val(X?) × … × val(X?) 的笛卡爾積。

定義在隨機(jī)變量集合X上的聯(lián)合概率分布，記作 p(X)，用于量化X的各種狀態(tài)下的不確定性。當(dāng)變量集合X可以被劃分為子集Y,Z時，我們也可以等價地寫作 p(Y,Z)。

從形式上講，我們的隨機(jī)變量的狀態(tài)空間構(gòu)成了一個樣本空間（sample space）。當(dāng)我們在這個樣本空間上定義一個事件的 σ-代數(shù)（σ-algebra），我們就得到了一個可測空間（measurable space）。我們的聯(lián)合概率分布則對應(yīng)于這個可測空間上的一個概率測度（probability measure），從而形成了一個概率空間（probability space）。

離散隨機(jī)變量上的分布由概率質(zhì)量函數(shù)（PMF, Probability Mass Function）描述，而連續(xù)隨機(jī)變量上的分布則由概率密度函數(shù)（PDF, Probability Density Function）描述。當(dāng)同時處理離散和連續(xù)隨機(jī)變量時，會使用混合離散-連續(xù)分布（mixed discrete-continuous distributions）。為了簡化記號，我們讓函數(shù) p(X = x) 根據(jù)上下文返回一個概率值或概率密度值。由于本文中的大多數(shù)陳述在這兩種情形下都成立，我們只在必要時才明確區(qū)分。

一個概率模型是一個概率分布的具體表示形式。對于一個具有參數(shù) θ 的概率模型 m，我們將使用 pm(X) 或 pθ(X) 來表示該概率模型所表示的概率分布。

事件是指被賦予了概率的一組狀態(tài)。在離散分布中，每個（部分）狀態(tài)都描述了一個基本事件。而對于連續(xù)隨機(jī)變量則需要更謹(jǐn)慎對待：它們的部分賦值通常并不直接對應(yīng)一個概率，而是對應(yīng)一個概率密度。因此，為了指定一個關(guān)于一般隨機(jī)變量 X 的事件，我們會說它的取值來自于某個區(qū)間 I，記作 X ∈ I。我們寫 X ∈ I 表示X中的每一個 Xi 都來自對應(yīng)的區(qū)間 Ii。涉及多個隨機(jī)變量的更復(fù)雜的事件類型——那些需要用形式邏輯語言來描述的事件——將在第 9 節(jié)中詳細(xì)討論。

我們假設(shè)讀者已經(jīng)熟悉標(biāo)準(zhǔn)的概率變換與規(guī)則，這些變換可以將一種分布轉(zhuǎn)換為另一種分布。例如，邊緣化（marginalization），也稱為求和消元（summing out）或積分消元（integrating out），可以從分布的作用域中移除一個變量。條件化（conditioning）則會從不符合觀測事件（通常稱為證據(jù)）的狀態(tài)中移除所有概率，并相應(yīng)地對其他概率進(jìn)行重新歸一化。

2.2 概率查詢

直觀上，一個概率模型可以被看作是一個“黑盒子”，我們可以就聯(lián)合概率分布中某些狀態(tài)和事件的不確定性提出問題。這些問題涉及計算聯(lián)合概率分布的一些感興趣的量，例如某個觀測狀態(tài)所對應(yīng)的概率質(zhì)量或概率密度、分布的眾數(shù)（mode）、某一階矩（moment）、熵（entropy）等。

在計算機(jī)科學(xué)文獻(xiàn)中，這類問題被稱為查詢（queries）。這個術(shù)語在數(shù)據(jù)庫領(lǐng)域（Vardi, 1982；Suciu 等，2011；Van den Broeck 等，2017）、概率圖模型（Koller 和 Friedman，2009；Dechter，2019）以及知識表示（Cali 等，2010；Juba，2019）中廣泛使用。查詢通常要求在對分布進(jìn)行某種變換之后計算感興趣的量。例如，人們可能會問：在給定證據(jù)并邊緣化掉一些變量之后，該分布的眾數(shù)是什么？

下面我們考慮一個關(guān)于不確定性下決策的簡單例子。

正如人們可能直覺到的那樣，計算查詢 q2 至少和計算查詢 q1 一樣困難：這兩個查詢都對分布進(jìn)行了邊緣化，但 q2 在處理更為復(fù)雜的邏輯約束（而不僅僅是部分狀態(tài)）的同時還進(jìn)行了最大化操作。通過觀察一個查詢所執(zhí)行的變換類型以及所計算的分布量，我們就可以將具有相似特征的查詢歸為一類，稱為查詢類（query classes）。這使我們能夠識別出具有類似計算挑戰(zhàn)的查詢，并形式化定義有用的可處理概率模型類別。

下面這個示例查詢代表了一個簡單但重要的查詢類，稱為完整證據(jù)查詢（Complete Evidence Queries，EVI）。

關(guān)鍵在于，EVI 查詢中的狀態(tài)x是完整的——它為分布中的每一個隨機(jī)變量（RV）都分配了一個取值。對于給定的模型m，回答一個 EVI 查詢相當(dāng)于計算該模型m在給定樣本x下的完整似然（complete likelihood）。因此，EVI 查詢是概率模型的最大似然學(xué)習(xí)（maximum-likelihood learning）的核心（Koller 和 Friedman，2009）。

本文將介紹一個遠(yuǎn)超 EVI 查詢類的豐富查詢類圖景。例如，例1中的查詢 q1 就屬于一個更難的查詢類，稱為邊際查詢（Marginal Queries，MAR），其目標(biāo)是計算在分布 p 中某個部分狀態(tài)的概率（或概率密度）。我們將在第4節(jié)中正式定義 MAR，并討論其性質(zhì)。此外，我們將展示它的計算挑戰(zhàn)與其他一些有趣的查詢類相同，如條件查詢（Conditional Queries，CON）和分布矩（Moments of a Distribution，MOM）的計算（例如均值或方差）。

除了分布的矩之外，我們可能還對它的眾數(shù)（mode）感興趣，即：在給定部分狀態(tài)作為證據(jù)的條件下，分布中最有可能的完整狀態(tài)。這類查詢被稱為最大后驗估計查詢（Maximum A Posteriori Queries，MAP），它們所需的計算工具與 MAR 不同，我們將在第6節(jié)中進(jìn)行討論。

現(xiàn)實世界中復(fù)雜的決策可能需要比 EVI、MAR 或 MAP 查詢更為復(fù)雜的概率推理過程。邊際最大后驗估計查詢（Marginal MAP Queries，MMAP）結(jié)合了 MAR 和 MAP 的特點——它要求對一組隨機(jī)變量進(jìn)行邊緣化，并在另一組隨機(jī)變量上尋找最有可能的部分狀態(tài)。我們將在第8節(jié)中討論 MMAP 類，并將其與其他困難類聯(lián)系起來；特別是與計算分布（邊際）熵的信息論查詢類之間的關(guān)系。

本文涉及的最后一類概率查詢關(guān)注的是多個模型的性質(zhì)。這類查詢用于詢問一個分布與另一個復(fù)雜對象之間的關(guān)系，這個對象可以是第二個分布，也可以是一個復(fù)雜的事件或函數(shù)。我們將這些查詢歸入一個統(tǒng)稱類別——成對查詢（Pairwise Queries，PAIR），因為它們共享許多相同的計算特性。在第9節(jié)中討論的 PAIR 查詢示例包括：兩個分布之間的Kullback-Leibler 散度（KLD）、某個函數(shù)的期望值（EXP）以及某個復(fù)雜邏輯事件的概率（PR），比如例1中查詢 q2 所提到的“交通擁堵”事件。

2.3 可處理的概率推理

當(dāng)我們說一個概率模型是可處理的時，我們期望它能提供兩種類型的保證。第一種保證是該模型能夠進(jìn)行精確推理：即對查詢的回答忠實于模型所表示的概率分布，在獲取這些回答的過程中不涉及任何近似。3 第二種保證是查詢的計算可以高效地進(jìn)行，也就是說，其計算時間是該概率模型大小的多項式函數(shù)。

在定義2中，效率這一概念轉(zhuǎn)化為關(guān)于模型類中模型大小 |m| 的多項式時間復(fù)雜度。
模型大小對于不同的模型類可以有不同的定義方式，但在所有情況下，它都代表了在給定模型輸入規(guī)模下所需計算量的一個代理指標(biāo)。

對于經(jīng)典的概率圖模型（如貝葉斯網(wǎng)絡(luò) BNs 和馬爾可夫隨機(jī)場 MRFs），模型大小通常可以用其因子（factor）的大小來表示（Darwiche, 2009；Koller 和 Friedman, 2009）。
而對于以計算圖形式表示的模型，例如神經(jīng)密度估計器（Papamakarios 等，2019）以及我們所討論的概率電路，模型大小將直接對應(yīng)于圖中的邊數(shù)。

在上述定義中，回答查詢的復(fù)雜性僅依賴于一個模型的大小。然而，對于某些更高級的查詢類（如涉及多個模型的 PAIR 類），我們需要表達(dá)其相對于所有相關(guān)模型大小的依賴關(guān)系。
特別地，對于 PAIR 類中的一些查詢，比如計算包含簡單事件析?。╠isjunction）的復(fù)雜事件的概率，其中一個模型可能是該事件的緊湊表示（例如，編譯成一個邏輯電路，參見第12節(jié)）。
在這種情況下，我們將用于編碼查詢事件的模型的大小稱為查詢的大小，并記作 |q|。

2.4 可處理概率模型的性質(zhì)

需要注意的是，定義2并沒有將“可處理性”表述為一種絕對屬性。
可處理性只能是相對于某一類查詢而言的，也就是說，它是針對某一族模型和某一類查詢所定義的：可處理性是一個光譜性的概念（tractability is a spectrum）。

事實上，一種對于某個查詢類來說是可處理的表示形式，可能在另一個查詢類下無法在多項式時間內(nèi)進(jìn)行推理。
對于一個模型類，我們將其可處理帶（tractable band）定義為該模型類能夠有效處理的所有查詢類的集合，即在這個集合中的每一個查詢類，該模型類都是一種可處理的表示形式。

從這個角度來看，不同的模型類可以通過其可處理帶的廣度來進(jìn)行比較，并根據(jù)它們在特定應(yīng)用領(lǐng)域中的實用性進(jìn)行排序。此外，當(dāng)面對具有相同可處理帶的不同模型類時，自然會引發(fā)一個問題：這些表示形式中是否存在某些共同的結(jié)構(gòu)特征，這些特征對于支持那些查詢類的可處理推理來說是充分的或必要的。

在下一節(jié)中，通過引入概率電路（Probabilistic Circuits, PCs）這一框架，我們將為許多可處理表示提供一個肯定的答案。具體來說，PCs 清晰的操作語義將有助于：

1. 統(tǒng)一許多可處理表示的形式化表達(dá)與符號系統(tǒng)
2. 以一種清晰的方式追蹤模型類的可處理帶與其所具備的結(jié)構(gòu)性質(zhì)之間的關(guān)系

表1展示了不同類型的概率電路如何通過其所具備的結(jié)構(gòu)性質(zhì)來支持對每一類查詢的可處理推理。這將在后續(xù)章節(jié)中進(jìn)一步展開說明。

3. 概率電路：表示方法

我們將概率電路（Probabilistic Circuits, PCs）引入作為一個通用且統(tǒng)一的計算框架，用于可處理的概率建模。

這服務(wù)于兩個主要目的：

第一個目的是統(tǒng)一文獻(xiàn)中迄今提出的各種不同的形式化體系（formalisms）用于可處理模型。
概率電路將最近提出的各類模型的不同圖形化和語法形式進(jìn)行協(xié)調(diào)與抽象，這些模型包括：算術(shù)電路（Darwiche, 2003）、概率決策圖（Jaeger, 2004）、與或搜索空間（Marinescu 和 Dechter, 2005）、多值決策圖（Dechter 和 Mateescu, 2007）、和積網(wǎng)絡(luò)（Poon 和 Domingos, 2011）、割集網(wǎng)絡(luò)（Rahman 等，2014）以及概率句子決策圖（Kisa 等，2014）。此外，一些更經(jīng)典的可處理模型，例如有界樹寬的概率圖模型，也可以自然地被納入概率電路的框架中（Darwiche, 2009）。我們將在第11節(jié)中提供所有這些形式體系到概率電路的翻譯詞匯表。

第二個目的是使我們能夠僅基于一些明確定義的結(jié)構(gòu)性質(zhì)來推理一個模型類的可處理帶（tractable band）。
反過來，這有助于我們更深入地理解在廣泛的可處理概率表示中，哪些性質(zhì)是必要的或充分的。我們在第4至第9節(jié)中針對不同查詢類介紹并討論這些性質(zhì)，并在第11.7節(jié)中探討是否所有可處理的表示都可以轉(zhuǎn)化為概率電路。

在本節(jié)中，我們首先以一種由下而上且直觀的方式構(gòu)建概率電路框架，通過介紹概率電路為可處理概率建模所提供的“語法規(guī)則”中的基本組成單元。隨后，我們將以更正式、由上而下的方式對這些概念進(jìn)行整合和介紹。

3.1 可處理概率建模的基本組成要素

概率電路通過圖的形式化方法，以遞歸的方式編碼聯(lián)合概率分布。本質(zhì)上，概率電路是一種計算圖，它所編碼的函數(shù)可以刻畫一個分布，例如概率質(zhì)量函數(shù)（PMF）或概率密度函數(shù)（PDF）。通過對某些輸入進(jìn)行評估，PC 能夠編碼用于回答特定概率查詢的計算過程，即執(zhí)行推理（inference）。

現(xiàn)在我們介紹構(gòu)建此類圖所需的最基本計算單元：分布單元（distribution units）、乘積單元（product units）和求和單元（sum units）。

3.1.1 輸入單元：簡單的可處理分布

首先，考慮這種計算圖中最小的一種形式，即僅由一個計算單元構(gòu)成的圖。這個單一單元就可以表示一組隨機(jī)變量（RVs）上的完整概率分布。我們將其命名為分布單元（distribution unit），在后續(xù)內(nèi)容中也會稱其為輸入單元（input unit），因為它們將構(gòu)成整個概率電路（PC）的輸入部分。

此類單元所編碼的計算——即它在給定某些輸入時所產(chǎn)生的輸出——取決于所考慮的查詢類以及它所表示分布的具體參數(shù)形式（parametric form）。

由于以這種方式定義的計算節(jié)點實際上充當(dāng)了一個封裝了分布函數(shù)的“黑盒子”，這種形式化方法是非常靈活的。首先，我們不需要為了回答不同查詢類的問題而更換節(jié)點類型。只需根據(jù)相應(yīng)的查詢類對所編碼的分布進(jìn)行評估即可：例如，對于 EVI 查詢（如示例4所示），可以評估某一點的概率密度；對于 MAR 查詢，可以在某個區(qū)間上進(jìn)行邊緣化；而對于 MAP 查詢，則可以直接返回該分布的眾數(shù)（mode）。

其次，只要某個概率分布是當(dāng)前查詢類下的可處理表示形式，我們就可以將任何現(xiàn)成的（out-of-the-box）概率分布作為輸入單元插入其中。此外，請注意，我們并不局限于歸一化（normalized）的分布，只需要輸入單元中所編碼的函數(shù)是非負(fù)的，并且假設(shè)它對 MAR 查詢是可處理的，那么我們就可以輕松獲得其配分函數(shù)（partition function）。

許多具有較大可處理帶、并且可以通過單一分布單元直接表示的常見分布包括最常用的單變量分布（univariate distributions），例如伯努利分布（Bernoulli）、分類分布（Categorical）、高斯分布（Gaussian）、泊松分布（Poisson）、伽馬分布（Gamma）以及其他指數(shù)族分布。對于這些分布，EVI、MAR 和 MAP 查詢都可以通過解析方式設(shè)計實現(xiàn)。?

然而，分布單元并不僅限于單變量分布。事實上，上述許多分布族在擴(kuò)展到多變量情形時仍然保持可處理性。例如，考慮在隨機(jī)變量X上廣泛使用的多元高斯分布（multivariate Gaussian distribution）。它仍然可以在 |X| 的立方時間內(nèi)實現(xiàn)可處理的條件化和邊緣化，并且通過設(shè)計可以在常數(shù)時間內(nèi)完成最大化（因為均值就是眾數(shù)）。

由于我們可以始終以這種方式將簡單的分布編碼為單個單元，因此分布單元構(gòu)成了我們遞歸構(gòu)建概率電路（PCs）的基礎(chǔ)情況（base case）。接下來我們要介紹的另外兩種單元則提供了歸納步驟（inductive step），使我們能夠?qū)⒃絹碓綇?fù)雜的 PC 組合在一起。

3.1.2 乘積單元：獨立因子分解

將一個聯(lián)合分布分解為若干更小分布的最簡單方式之一是使其可因子化（factorize）；也就是說，將每一個較小的分布視為相互獨立的。

將一個聯(lián)合分布分解為更小的因子，是經(jīng)典概率圖模型（PGMs）所基于的核心假設(shè)，其中聯(lián)合分布的因子化方式由隨機(jī)變量之間的依賴結(jié)構(gòu)所決定，并通過圖的形式化方法進(jìn)行編碼（Koller 和 Friedman，2009）。
在這些模型中，最簡單的一類因子化模型是完全因子化分布（fully-factorized distributions），其中圖中的所有隨機(jī)變量都是不相連的；也就是說，聯(lián)合分布被分解為各個單變量的邊緣分布。

要將一個完全因子化模型表示為計算圖，我們只需要引入一個對若干輸入分布單元執(zhí)行乘積操作 的計算單元即可。

乘積單元所表示的因子化形式在接下來多個可處理推理場景中將起到關(guān)鍵作用，因為它們體現(xiàn)了一種“分而治之”（divide-et-impera）的推理策略：將復(fù)雜的推理問題“拆解”為一組更小的問題。然而，為了表示一個部分因子化但非完全因子化的模型——也就是一個可能更具表達(dá)能力的模型——我們需要讓乘積單元不僅接收來自分布單元的輸入，還要接收來自另一種類型單元的輸入：求和單元（sum units）。事實上，求和單元將有助于對不同因子之間的相關(guān)性進(jìn)行建模。

3.1.3 求和單元：混合模型

將多個簡單分布組合成一個具有更強表達(dá)能力的單一模型的思想，是混合模型（mixture models）的核心（McLachlan 和 Peel，2004）。在此我們重點關(guān)注具有正權(quán)重的有限混合模型?，其定義如下。?

即使一個混合模型的各個成分（component）本身編碼的是完全因子化的模型，它仍然能夠捕捉非完全因子化的分布，其原因在于：每一個混合模型都隱式地編碼了一個分類潛變量（latent variable, LV）。這個潛變量充當(dāng)了對混合成分的選擇器（selector），從而在各個成分分布之間引入了相關(guān)性。

事實上，混合密度中的權(quán)重可以被解釋為將該潛變量設(shè)為指示某個成分的取值的先驗概率；而各個成分分布則可以被視為在給定所選潛變量取值時的條件分布。

混合模型的分布可以通過引入一個求和單元（sum unit）來輕松表示為計算圖，該求和單元計算其接收到的輸入的加權(quán)平均值。由于權(quán)重代表了混合成分，我們在圖形中將其表示為連接求和單元與其輸入的邊上的標(biāo)注。

示例9（作為求和單元的混合模型）

考慮示例7中的兩個高斯分布的混合模型。下圖（左側(cè)）展示了一個計算圖：每個單變量高斯成分由一個輸入分布單元表示，并通過帶有混合權(quán)重的邊連接到一個求和單元，從而表示示例7中的混合密度。

3.2 概率電路：結(jié)構(gòu)與參數(shù)

現(xiàn)在我們已經(jīng)介紹了所有的基本組成單元，接下來我們可以嚴(yán)格地整體定義概率電路（PCs）的語法，并引入本文后續(xù)將使用的術(shù)語。
首先，與經(jīng)典的概率圖模型（PGMs）類似，我們有必要區(qū)分一個 PC 的結(jié)構(gòu)（structure）和它的參數(shù)化（parameterization）。

3.3 針對完整證據(jù)查詢的可處理電路

在進(jìn)入下一節(jié)討論更具挑戰(zhàn)性的查詢類之前，我們首先考慮一個基礎(chǔ)任務(wù)：評估由概率電路（PC）所編碼的聯(lián)合概率質(zhì)量函數(shù)（PMF）、概率密度函數(shù)（PDF）或混合的質(zhì)量-密度函數(shù)，在給定一個完整狀態(tài)（complete state）下的取值。這類查詢屬于完整證據(jù)查詢（Complete Evidence Queries），即定義1中介紹的 EVI 查詢類。

請注意，在 EVI 查詢類中，我們明確指的是歸一化（normalized）的概率分布。因此在此我們假設(shè) PC 所編碼的函數(shù)是歸一化的；如果它們不是歸一化的，我們將在下一節(jié)中進(jìn)一步討論何時以及如何對其進(jìn)行歸一化。

定義5至定義8為概率電路提供了一種遞歸語法式的語義結(jié)構(gòu)，用于組合可處理的概率模型。事實上，令 Cn 是概率電路 C 中以單元 n 為根節(jié)點的子電路，即該計算圖以 n 作為輸出，并包含所有遞歸地為 n 及其內(nèi)部單元提供輸入的單元。
Cn 本身也是一個 PC，即一個在變量集合 φ(n) 上編碼某個函數(shù)的計算圖，并由參數(shù) θn 進(jìn)行參數(shù)化。

這一特性可以通過以下遞歸定義來捕捉：

因此，定義10 提供了一種自然的方式來回答 EVI 查詢：通過遞歸地評估 PC 中所編碼的函數(shù)。
只要在每次遞歸調(diào)用時緩存中間計算結(jié)果，這種方法就能保證整個計算過程僅需多項式數(shù)量級的計算步驟。

回答一個概率電路C（定義在隨機(jī)變量X上）的EVI 查詢 p(x)的迭代版本總結(jié)在算法1中。

首先，以前饋方式對C的有向無環(huán)圖（DAG）進(jìn)行拓?fù)渑判颍摧斎雴卧旁谳敵鰡卧啊?br/>每個單元n將其計算結(jié)果存儲在一個局部寄存器r?中。
最終的輸出p(x)可以從排序中的最后一個單元（即電路的根節(jié)點）的寄存器中讀取。

第3.1節(jié)中的示例4、示例6和示例9分別展示了每種計算單元如何進(jìn)行這種前饋式評估。
以下示例則將它們整合到一個更大的電路中。

3.4 超越簡單的概率電路

我們在本節(jié)中對概率電路（PCs）所給出的基本定義，已經(jīng)足以構(gòu)建一個可以統(tǒng)一多種可處理概率表示的框架。正如我們在后續(xù)章節(jié)中將展示的那樣，這一框架具有廣泛的適用性。

在電路理論文獻(xiàn)中，這個基本框架已經(jīng)被以許多有趣的方式進(jìn)行了擴(kuò)展。對于希望深入了解并超越 PC 的讀者，我們在此提供一些相關(guān)擴(kuò)展的概述。11

非概率電路，仍然以包含求和與乘積操作的計算圖形式表示，在計算復(fù)雜性理論中被稱為算術(shù)電路（arithmetic circuits），它為研究模型類的表達(dá)效率和算法復(fù)雜性提供了最簡單且最優(yōu)雅的形式之一（Shpilka 和 Yehudayoff，2010）。

我們在后續(xù)章節(jié)中提供的許多理論結(jié)果，其根源都可以追溯到算術(shù)電路或更簡單的布爾電路（用于編碼邏輯公式的電路）中的類似結(jié)果。在第12.2節(jié)中，我們將深入探討 PC 與通過加權(quán)模型計數(shù)（Weighted Model Counting, WMC）進(jìn)行的邏輯公式上的概率推理之間的緊密（甚至是因果性的?。┞?lián)系（Darwiche 和 Marquis，2002）。受這種聯(lián)系的啟發(fā)，人們也研究了對一階邏輯表示的擴(kuò)展，包括針對 WMC 電路（參見 Van den Broeck（2013）的綜述）以及 PC（Webb 和 Domingos，2013），并且還開發(fā)了相應(yīng)的學(xué)習(xí)方法（Nath 和 Domingos，2014；Niepert 和 Domingos，2015）。

此外，第12.1節(jié)還將討論對其他半環(huán)上可處理電路的進(jìn)一步推廣，這些電路不局限于求和與乘積操作。

受復(fù)雜性電路研究結(jié)果的啟發(fā)，人們也探索了 PC 的替代計算圖結(jié)構(gòu)，以提高其表達(dá)效率。這些嘗試包括引入執(zhí)行除法操作的計算單元（Sharir 和 Shashua，2018），以及允許求和單元使用可能為負(fù)的權(quán)重（Dennis，2016），從而實現(xiàn)非單調(diào)但依然保持正值的混合模型（Valiant，1979b）。

我們對 PC 結(jié)構(gòu)和參數(shù)的定義也可以以多種方式進(jìn)行推廣：

1. 作用域函數(shù)（scope function）如定義7中所述，是與 PC 的計算圖分離的。因此，它可以被視為一個可以從數(shù)據(jù)中獨立學(xué)習(xí)的額外參數(shù)（Trapp 等，2019），而計算圖本身則成為一組 PC 的模板（template）。

2. 在 PC 中，參數(shù)本身也可以被建模為一級隨機(jī)變量（first-class random variables）。例如，如果我們?yōu)檫@些參數(shù)指定先驗分布（例如，為求和權(quán)重指定 Dirichlet 分布，或為高斯輸入單元的參數(shù)指定 NIG 分布），就可以得到一種貝葉斯解釋的電路。雖然從穩(wěn)健建模不確定性的角度來看這種方法很有吸引力，但在貝葉斯 PC 中的推理通常是不可處理的。不過，可以利用 PC 的可處理推理能力作為子程序，來進(jìn)行高效的近似推理，例如通過采樣（Vergari 等，2019b；Trapp 等，2019）或通過變分（Zhao 等，2016a）或矩匹配（Rashwan 等，2016；Jaini 等，2016）優(yōu)化進(jìn)行近似。這種貝葉斯處理方式使得我們可以將求和單元推廣到具有無限但可數(shù)個成分的混合模型（Trapp 等，2019）。

   類似的思路也可用于建模 PC 中的高階不確定性，從不精確概率（imprecise probabilities）的角度來看（Walley，1991）：PC 中的標(biāo)量求和權(quán)重可以推廣為區(qū)間表示，從而使電路不再表示單一分布，而是表示一個置信集（credal set）中的多個分布（Mauá 等，2017；Antonucci 等，2019）。

3. 輸入單元也可以超越簡單的、可處理的概率分布。盡管已有多種不同的參數(shù)化分布（Jaini 等，2016；Molina 等，2017；Dennis，2016；Vergari 等，2019b）和非參數(shù)分布（Molina 等，2018；Morettin 等，2020）被用作輸入單元，但最近的研究也開始采用不可處理的模型，如變分自編碼器（Tan 和 Peharz，2019），以及分類器和回歸器（Trapp 等，2020；Khosravi 等，2020）作為輸入單元。

4. 針對邊際查詢的可處理電路

在本節(jié)中，我們將擴(kuò)展概率電路（PC）框架，使其能夠有效地回答一類重要的查詢——邊際查詢（marginal queries）。

我們首先在第4.1節(jié)中形式化定義 MAR 查詢類，然后在第4.2節(jié)中，通過概率電路計算圖的一些結(jié)構(gòu)性質(zhì)（即平滑性（smoothness）和可分解性（decomposability）），精確刻畫哪些類型的 PC 是該查詢類的可處理表示。

此外，在第4.3節(jié)中，我們將展示這些結(jié)構(gòu)性質(zhì)如何使得與 MAR 類具有相同計算挑戰(zhàn)的其他查詢類（如條件查詢（CON）和分布矩的計算）也能實現(xiàn)可處理的推理。最后，在第4.4節(jié)中，我們提供一些延伸閱讀資料，介紹關(guān)于表示與學(xué)習(xí)平滑且可分解的 PC及相關(guān)可處理形式體系的研究進(jìn)展。

4.1 MAR 與 CON 查詢類

當(dāng)我們希望對那些并非所有隨機(jī)變量（RVs）都被完全觀測到的世界狀態(tài)進(jìn)行推理時，邊際查詢（MAR, Marginal Queries）就變得至關(guān)重要。

這種情況可能出現(xiàn)在以下場景中：

• 我們無法獲取某些變量的值，例如患者記錄中的缺失值；

• 或者我們并不關(guān)心某些變量的具體取值，如我們在交通擁堵場景中所討論的情形（參見第2.2節(jié)）。

  
  

正如這個例子所表明的那樣，邊際查詢（marginal queries）與完整證據(jù)查詢（complete evidence queries）之間的關(guān)鍵區(qū)別在于：邊際查詢允許部分狀態(tài)作為證據(jù)。

從本質(zhì)上講，這就相當(dāng)于對完整證據(jù)概率進(jìn)行積分和求和操作。因此，我們可以定義一個更一般的邊際查詢類，其中這些操作12 是在隨機(jī)變量定義域的子集上進(jìn)行的。

請注意，積分是在區(qū)間的笛卡爾積（即一個超立方體）上進(jìn)行的。因此，計算一個邊際查詢相當(dāng)于從完整證據(jù)計算中邊緣化掉 k 個變量，也就是求解一個形式如下的k 維積分：

當(dāng)隨機(jī)變量Z被在其整個定義域上邊緣化時，即 I? = val(Z?)，我們便得到了經(jīng)典定義的邊際查詢（Darwiche, 2009；Koller 和 Friedman, 2009），簡記為 p(E = e)。
此外，一般意義上的 MAR 查詢類也包括對分布 p 的聯(lián)合累積分布函數(shù)（CDF）進(jìn)行積分的查詢，當(dāng)這種積分是在所有隨機(jī)變量的開區(qū)間上進(jìn)行時就屬于此類。

最后，很自然地可以得出：EVI ? MAR。

與 MAR 具有相同計算挑戰(zhàn)的另一個查詢類是條件查詢類（Conditional Queries，CON），即計算一個部分狀態(tài)下某個事件的概率，其條件是另一個以部分狀態(tài)形式給出的事件。

4.2 平滑且可分解的概率電路（Smooth and Decomposable PCs）

求解像 MAR 或 CON 查詢中所需的多變量定積分問題，通常是一個#P-難問題（Baldoni 等，2011），因此許多常見的概率模型（如貝葉斯網(wǎng)絡(luò)（Darwiche, 2009）、馬爾可夫隨機(jī)場（Koller 和 Friedman, 2009）、變分自編碼器（Rezende 等，2014；Kingma 和 Welling, 2013）以及歸一化流（Papamakarios 等，2019））在執(zhí)行這一任務(wù)時表現(xiàn)困難也就不足為奇了。

然而，如果對概率電路（PC）的計算圖結(jié)構(gòu)施加某些結(jié)構(gòu)性限制，則可以保證對于 MAR 和 CON 查詢中的所有可能查詢，都能在線性時間內(nèi)完成計算。

通過觀察那些可以轉(zhuǎn)化為 PC 的最簡單概率模型，我們可以理解這些結(jié)構(gòu)性質(zhì)是什么，并了解這些計算如何被推廣到 PC 中的一般算法框架。

在最簡單的情況下,回答一個MAR查詢等價于提取那個編碼了整個分布的單一分布單元的輸出。

其中，證據(jù)變量（evidence RVs）和待邊緣化的變量被根據(jù)X的劃分方式分別劃分為集合E = E? ∪ … ∪ E? 和Z = Z? ∪ … ∪ Z?，這種劃分也誘導(dǎo)了在多元區(qū)間I? × … × I?上的劃分。也就是說，因子之間的獨立性使得這些較小積分可以獨立計算。從操作上看，我們可以對一個乘積單元（product unit）的各個輸入分別求解其對應(yīng)的子積分，然后以一種“分而治之”（divide-et-impera）的方式將它們組合成一個乘積。

同樣，這表明對一個表示混合模型的概率電路（PC）進(jìn)行積分的計算，可以推遲到對其輸入求和單元的子電路進(jìn)行積分計算，然后在求和輸出中對其結(jié)果進(jìn)行加權(quán)。

因此，通過在以通常的前饋方式評估概率電路（PC）的同時，遞歸地重復(fù)上述所有步驟，我們就可以找到一種用于計算 MAR 查詢的一般性方案，如下一定義所述。

請注意，一個不能計算某個分布 p 的邊際值的概率電路（PC），并不一定意味著對于某些邊際查詢是不可處理的——可能存在其他多項式時間的算法（如不同于算法2的方法）來處理這些部分狀態(tài)的計算。

相反，那些能夠計算邊際值的 PC，允許每一個邊際積分嚴(yán)格按照該 PC 的結(jié)構(gòu)進(jìn)行分解，這種自頂向下的分解方式在示例14至示例16中已有描述，并且通過前饋評估即可精確地獲取查詢結(jié)果。

直觀上，我們可以將這類 PC 看作在其計算圖中緊湊地存儲了所有用于計算任意隨機(jī)變量子集、任意部分狀態(tài)和任意區(qū)間上的邊際值的計算圖集合。

這里仍存在一個問題：在什么條件下，一個 PC 可以保證正確地計算邊際值？

答案在于對它的計算圖施加限制，強制滿足兩個結(jié)構(gòu)性質(zhì)：

1. 可分解性

   （Decomposability）

2. 平滑性

   （Smoothness）

接下來的定義和示例將形式化地引入并說明可分解且平滑的 PC這一類重要的概率電路。

所有作為簡單 PC 示例所使用的因子化模型，在設(shè)計上都是可分解的，因為為了保證概率獨立性，每個因子都不會與其他因子共享隨機(jī)變量（RVs）。

然而，請注意，即使一個 PC 中的所有乘積單元都是可分解的，一個可分解的 PC 也不一定在其作用域上表示一個完全因子化的分布。這是因為其中可能存在求和單元（sum units），它們會在其輸入子電路所表示的分布之間引入相關(guān)性。

通常，在處理有效的混合模型時，平滑性（smoothness）是被隱含假設(shè)的，這一點在我們目前為止所使用的所有高斯混合模型（GMM）示例中都成立。

事實上，概率電路（PC）可以被視為經(jīng)典混合模型的一種推廣，更準(zhǔn)確地說，是一種分層混合模型（hierarchical mixture model）。
我們將在第7節(jié)中進(jìn)一步看到，如果一個 PC 是可分解的但不是平滑的，我們可以在多項式時間內(nèi)對其進(jìn)行平滑化處理，即應(yīng)用一種變換，輸出一個保持原分布不變但具有平滑性的 PC。

可以看出，可分解性是因子化模型中進(jìn)行邊際計算的一個充分條件：當(dāng)具備該性質(zhì)時，總能將較大的積分分解為在更小且互不重疊的作用域上進(jìn)行（參見公式4）。

同樣地，對混合成分上的求和與積分操作的“安全交換”（參見公式5），其數(shù)學(xué)依據(jù)來自于Fubini 定理的適用性。

在一個 PC 中，只要滿足這些結(jié)構(gòu)性質(zhì)，并假設(shè)輸入分布本身允許進(jìn)行可處理的邊際計算，那么就足以保證任意邊際查詢都可以高效計算（Darwiche, 2003；Peharz 等, 2015）。

然而，這些結(jié)構(gòu)性質(zhì)是否也是實現(xiàn)高效計算所必需的條件，這一點并不那么明顯。

正如下一個定理所示，要想能夠高效地計算邊際值，一個概率電路（PC）必須是平滑且可分解的。

為了證明定理19，我們首先引入概率電路的淺層表示（shallow representation），這將更便于我們進(jìn)行操作。
任何定義在隨機(jī)變量X上的概率電路C都可以被“展開”為一個等價的概率電路S，其形式如下：

也就是說，它由一個單一的求和單元構(gòu)成，該求和單元連接了數(shù)量可能呈指數(shù)增長的乘積單元（記作 K），每個乘積單元都將其輸入為電路C中的M?個輸入分布單元，記作L??。

這種淺層表示有助于我們理解概率電路（PCs）、混合模型以及多項式表示之間的關(guān)系，我們將在第5節(jié)中深入探討這一點。

要將一個深層的概率電路C轉(zhuǎn)換為其淺層表示S，我們可以遞歸地應(yīng)用經(jīng)典代數(shù)半環(huán)中的乘法對加法的分配律，按照“先輸入后輸出”的順序進(jìn)行轉(zhuǎn)換。
該構(gòu)造遵循概率電路的遞歸定義（參見定義10），具體步驟如下：

• 如果C是一個單獨的輸入分布單元，那么其對應(yīng)的淺層表示S將包含一個僅有一個乘積單元的求和單元，該乘積單元的權(quán)重為 θ = 1，并由輸入分布 L := C 提供輸入。

• 如果C是一個具有 R 個子電路和權(quán)重 θ?, ..., θ? 的求和單元 n，則其淺層表示S將包含一個單一的求和單元 n′，它的輸入是所有出現(xiàn)在其子電路的淺層表示S?, ..., S?中的乘積單元，并且這些乘積單元的權(quán)重分別乘以對應(yīng)的 θ?, ..., θ?。

• 如果C是一個由 R 個子電路組成的乘積單元 n，則其淺層表示通過對其各個子電路的淺層表示S?, ..., S?進(jìn)行笛卡爾積運算得到。也就是說，S中的每一個乘積單元都是從每個S?中各取一個乘積單元相乘得到的，并且其權(quán)重是它們各自權(quán)重的乘積。

上述構(gòu)造表明，每一個子電路C?的淺層表示S?都與其作用域（scope）保持一致；并且對于電路C中的每一個乘積單元 n，在S中都會存在多個由 n 與其他單元相乘而形成的乘積單元。我們將參與這種“一到多”映射的S中的單元稱為對應(yīng)乘積單元（corresponding products）。

此外，請注意：淺層表示S是通過對C的有向無環(huán)圖（DAG）結(jié)構(gòu)進(jìn)行操作而獲得的，因此該構(gòu)造與輸入分布單元的具體評估方式無關(guān)。特別地，對于任意的部分狀態(tài)和區(qū)間，根據(jù)算法2對S和C進(jìn)行評估時，返回的結(jié)果是相同的。

我們首先證明：如果一個電路能夠在任意參數(shù)化下高效計算邊際值，則它必須是可分解的。該證明利用了以下關(guān)于 PC 及其淺層表示之間可分解性的關(guān)系。

假設(shè)C是不可分解的。根據(jù)命題20，我們知道它的淺層表示S也是不可分解的。此外，我們可以確定在S中必然存在一個乘積單元，它要么包含同一個輸入分布單元的兩個副本，要么包含作用域重疊的兩個輸入單元。

令Z為這樣一個不可分解的乘積單元中所共享的變量之一?，F(xiàn)在考慮一個形式為p(E = e, Z ∈ I)的任意邊際查詢（MAR），其中e是定義在E = X \ {Z}上的一個部分狀態(tài)，I是如定義11中所定義的一個積分區(qū)間。通過執(zhí)行算法2來計算此類查詢時，將導(dǎo)致以下計算過程

方程（6）和（7）在一般情況下對于所有參數(shù)選擇并不相等，因此算法2在面對不可分解的 PC時，并不一定會返回正確的邊際值。

接下來我們將證明：一個支持可處理邊際計算的概率電路（PC），不僅必須是可分解的，還必須是平滑的。
我們再次借助關(guān)于淺層表示的以下結(jié)論來展開證明。

接下來，假設(shè)C是可分解的，但不是平滑的。根據(jù)命題21，我們知道它的淺層表示S也不是平滑的，并且存在一個乘積單元，其作用域不包含變量Z ∈ X。

我們再次考慮一個邊際查詢（MAR）：p(E = e, Z ∈ I)，其中e是定義在E = X \ {Z}上的一個部分狀態(tài)，I是Z上的一個積分區(qū)間。

假設(shè)I涉及所有那些在作用域中不包含 Z的乘積單元集合。此外，由于C（以及對應(yīng)的S）是可分解的，因此S中的每一個乘積單元最多只包含一個依賴于Z的輸入分布單元；不失一般性，我們將這樣的單元記作j = M?。

一般情況下，方程（8）與方程（9）并不相等。因此，在缺乏平滑性的情況下，算法2無法保證正確計算 MAR 查詢。

例如，如果Z 是一個離散變量，且I = val(Z)，那么對于每一個i ∈ I，方程（9）中的每一項相比于方程（8）都缺少了一個因子 ∫? dZ = |val(Z)|，因此算法2的輸出會低估（lower bounds）真實的邊際值。

由此可見，可分解性和平滑性準(zhǔn)確地刻畫了所有在任意參數(shù)化下都能支持邊際計算的概率電路結(jié)構(gòu)。

4.3 分布矩的可處理計算

本質(zhì)上，平滑性與可分解性使得我們能夠?qū)⒁粋€大的積分問題拆解為更小、易于計算的積分子問題，從而實現(xiàn)對MAR 查詢類的可處理計算。

這一強大的思想還可以用于高效計算其他涉及多變量積分的概率查詢類。
例如，計算一個概率分布的均值和方差，或者更一般地，計算它的任意階矩（moments），都可以利用這一機(jī)制進(jìn)行可處理的推理。

因此，只要輸入分布單元能夠支持對給定矩查詢的可處理計算，一個平滑且可分解的概率電路（PC）就可以以可處理的方式計算矩查詢。

我們現(xiàn)在通過數(shù)學(xué)歸納法來證明上述命題。

作為基例（base case），如果C(X)僅包含一個輸入分布單元，那么算法3只需直接計算該分布的k 階矩（moment of degree k）。

4.4 MAR 及其擴(kuò)展

在本節(jié)中，我們?yōu)楦信d趣的讀者提供一些額外的文獻(xiàn)指引，涉及本節(jié)所討論主題的相關(guān)研究。

可分解性（decomposability）與平滑性（smoothness）是許多可以表示為概率電路（PC）的可處理概率模型（TPMs）所普遍假設(shè)的兩個“核心”結(jié)構(gòu)性質(zhì)（參見表2及第11節(jié)）。

在和積網(wǎng)絡(luò)（SPNs, Sum-Product Networks）的文獻(xiàn)中（Poon 和 Domingos，2011），平滑性被稱為完備性（completeness）。在 Poon 和 Domingos（2011）最初的定義中，SPN 是定義在二值隨機(jī)變量上的概率模型，能夠進(jìn)行可處理的 MAR 查詢的 SPN 被稱為是有效的（valid）。

對于二值隨機(jī)變量的情形，有效性的充分條件是平滑性與一致性（consistency），其中后者是可分解性的一個推廣。后來，Peharz 等人（2015）指出，對于具有可處理輸入節(jié)點（無論其類型如何）的概率電路來說，可分解性與平滑性實際上已經(jīng)足以保證其對 MAR 查詢的可處理計算。

然而，一致性仍在刻畫一類可處理 PC 的過程中扮演角色，只不過它適用于另一個查詢類——MAP 查詢，我們將在第6節(jié)中進(jìn)一步說明這一點。

最后，Martens 和 Medabalimi（2014）證明了，平滑性與可分解性是一個更嚴(yán)格的有效性定義（稱為強有效性 stronger validity）的充要條件。他們的結(jié)論基于 SPN 與（集合）多線性多項式之間的聯(lián)系（參見第5節(jié)）以及后者表示形式的性質(zhì)。

我們在本節(jié)中得出的理論結(jié)果與此類似，但結(jié)論略有推廣，因為我們將其擴(kuò)展到了任意參數(shù)化下的一般概率電路。

5. 概率電路的多重面貌

我們現(xiàn)在介紹幾種對概率電路（PCs）的解釋，它們直接源自 PC 的操作語義。
這些解釋將幫助我們把 PC 放在整個概率建模領(lǐng)域的更廣闊背景下進(jìn)行理解，并將在后續(xù)章節(jié)中發(fā)揮重要作用。13

5.1 概率電路不是概率圖模型（PGMs）

盡管概率電路是通過圖形化形式表達(dá)的概率模型，但它們并不是傳統(tǒng)意義上的概率圖模型（Probabilistic Graphical Models, PGMs）（Koller 和 Friedman, 2009）。

事實上，像貝葉斯網(wǎng)絡(luò)和馬爾可夫隨機(jī)場這樣的經(jīng)典 PGM 具有明確的表示語義，而 PC 的語義則是操作性的（operational）。也就是說：

• 在 PC 的計算圖中，每個單元直接表示如何評估它所編碼的概率分布，即如何回答概率查詢；

• 而在 PGM 的圖中，節(jié)點表示隨機(jī)變量（RVs），邊則表示變量之間的（條件）獨立性假設(shè)；

• PC 中連接單元的邊定義了在回答查詢時運算的執(zhí)行順序，而不是表示變量間的關(guān)系。

在 PGM 中，回答一個查詢的任務(wù)通常依賴于外部算法，如變量消元法、消息傳遞、遞歸條件等，其復(fù)雜度取決于圖結(jié)構(gòu)的特性。

第11.1節(jié)將討論如何將多個 PGM 直接轉(zhuǎn)換為 PC 框架下的計算圖。這種將一種圖形表示轉(zhuǎn)換為另一種、同時保持底層概率分布不變的過程被稱為編譯（compilation）。

5.2 概率電路就是神經(jīng)網(wǎng)絡(luò)

如果說 PC 不具備 PGM 的語義，那么它們確實與神經(jīng)網(wǎng)絡(luò)（Neural Networks, NNs）具有相似之處。

實際上，PC 中的計算圖是一種特殊的神經(jīng)網(wǎng)絡(luò)，其中神經(jīng)元被限制為以下三種類型：輸入分布單元、求和單元或乘積單元。

• 求和單元

  輸出的是其輸入的線性變換，類似于感知機(jī)中的前激活函數(shù)；

• 乘積單元

  實現(xiàn)了一種乘法交互機(jī)制（Jayakumar 等，2019），這在注意力機(jī)制和許多現(xiàn)代門控單元（如 LSTM）中都能找到（Ha 等，2016；Bahdanau 等，2014）。

因此，PC 是一種包含兩種非線性形式的神經(jīng)網(wǎng)絡(luò)：

1. 輸入分布單元通過對密度或質(zhì)量函數(shù)的非線性變換來“扭曲”輸入；

2. 乘積單元引入第二種非線性。

如果我們重新參數(shù)化 PC 中的計算，在處理求和單元和乘積單元時交替使用線性域和對數(shù)域，就可以得到一種更經(jīng)典的前饋感知機(jī)解釋——即在線性變換之后緊接著一個非線性變換（無偏置項）（Vergari 等，2019a）。

受限的 PC 的計算圖比普通神經(jīng)網(wǎng)絡(luò)更加稀疏，因此將其映射到張量化的高效 GPU 計算表示更具挑戰(zhàn)性。不過，近期的研究正在逐步縮小這一差距（Sharir 等，2016；Vergari 等，2019a；Peharz 等，2019，2020）。

5.3 概率電路是多項式

在 PC 中采用求和單元和乘積單元作為內(nèi)部神經(jīng)元，使得我們可以將 PC 解釋為多元多項式函數(shù)，其中變量是由輸入分布單元所編碼的密度函數(shù)。

我們在自底向上構(gòu)建 PC 的淺層表示以證明定理19時，已經(jīng)利用了這種解釋。

接下來我們將以一種自頂向下的方式提供更正式的刻畫，首先引入一個關(guān)鍵概念：誘導(dǎo)子電路（induced sub-circuit）。

請注意，誘導(dǎo)子電路的數(shù)量（從而多項式表示中的項數(shù)）可能隨著隨機(jī)變量（RVs）數(shù)量的增加而呈指數(shù)增長。雖然這種表示形式看起來在實際中可能難以應(yīng)用，但電路多項式在以下方面具有重要意義：

• 它有助于設(shè)計學(xué)習(xí)算法（Zhao 等，2016b；Vergari 等，2019b）；

• 有助于驗證概率電路的性質(zhì)并證明相關(guān)結(jié)論（參見第4.2節(jié)）；

• 并為理解概率電路的表達(dá)能力提供了直觀解釋，如下文所述。

當(dāng)所有可能的輸入單元對應(yīng)的dc值都為 1 時，一個電路多項式（circuit polynomial）就是一個多線性多項式（multilinear polynomial）。

此外，當(dāng)參與多項式項中的輸入分布的作用域集合是互不重疊的，即該電路是可分解的（Martens 和 Medabalimi，2014），該多項式進(jìn)一步成為集合多線性多項式（set-multilinear polynomial）（Shpilka 和 Yehudayoff，2010）。

請注意，在這種情況下，誘導(dǎo)子電路（induced sub-circuit）是一棵樹（有時也被稱為誘導(dǎo)樹（induced tree））（Zhao 等，2015）。

5.4 概率電路是分層混合模型

如第3.2節(jié)所述，概率電路（PC）中的一個平滑的求和單元（smooth sum unit）表示一個混合模型，其各個成分是由該求和單元的輸入子電路所代表的分布。

此外，正如示例8所示，我們可以將一個平滑的 PC解釋為對其每個求和單元所關(guān)聯(lián)的分類潛變量（categorical latent variable, LV）進(jìn)行邊緣化。

因此，PC 是一種分層潛變量模型，更確切地說，是一種深度混合模型。在下文中，我們將討論 PC 的潛變量語義及其含義。

首先，請注意，一個電路多項式表示（參見定義25）揭示了：PC 中離散潛變量的層次結(jié)構(gòu)可以被壓縮成一個單一的潛變量，它對應(yīng)于淺層表示中那個唯一的求和單元。

這個單一潛變量所能取的狀態(tài)數(shù)量，正好等于該 PC 所擁有的誘導(dǎo)子電路的數(shù)量。換句話說，一個深層電路以緊湊的方式編碼了一個具有指數(shù)級數(shù)量成分的混合模型。

這種“緊湊性”或稱“表達(dá)效率”將在第7節(jié)中被形式化地定義為模型規(guī)模的函數(shù)。

因此，每一個有限且淺層的混合模型都可以轉(zhuǎn)化為一個平滑且淺層的概率電路（只要每個成分表示的是一個可處理的分布）。

但目前仍是一個開放問題是：在什么條件下，一個淺層混合模型也可以在多項式時間內(nèi)轉(zhuǎn)化為一個緊湊、深層（即可分解的）概率電路？

上述淺層與深層 PC 的對偶性也反映在如何圖形化表示相關(guān)潛變量之間的依賴關(guān)系上，即構(gòu)建潛變量層次結(jié)構(gòu)的一個獨立映射結(jié)構(gòu)（i-map structure）（Koller 和 Friedman，2009）。

從 PC 的誘導(dǎo)樹表示出發(fā)，Zhao 等人（2015）將 PC 的依賴結(jié)構(gòu)轉(zhuǎn)換為一個貝葉斯網(wǎng)絡(luò)，該網(wǎng)絡(luò)是一個二分圖，其中潛變量和觀測隨機(jī)變量分別構(gòu)成兩個節(jié)點集合。

從這個角度看，潛變量之間沒有邊連接，并且在給定觀測變量的條件下，它們是相互條件獨立的。

相比之下，Peharz 等人（2016）則構(gòu)建了一個有向無環(huán)圖（DAG），其中葉子節(jié)點是觀測變量，而每一個潛變量節(jié)點都依賴于所有在拓?fù)淝梆來樞蛑形挥谒蟮钠渌麧撟兞浚ㄟ@些潛變量與后續(xù)的求和單元相關(guān)聯(lián)）。

Butz 等人（2020）進(jìn)一步探討了更精細(xì)的依賴結(jié)構(gòu)：在某些假設(shè)條件下（例如該 PC 是從一個 PGM 編譯而來（Darwiche 和 Marquis，2002）），可以通過一個稱為反編譯（decompilation）的過程，識別出原始 PGM 的結(jié)構(gòu)（包括顯式的潛變量）。

將概率電路（PC）解釋為一種深度潛變量模型（deep latent variable model）表明，PC 的模型似然函數(shù)是非凸的。因此，電路參數(shù)通常通過期望最大化（Expectation-Maximization, EM）算法進(jìn)行學(xué)習(xí)（Dempster 等，1977）。

此外，顯式地表示一個平滑且可分解的 PC 所邊緣化的潛變量，為利用這些電路作為表示學(xué)習(xí)中的特征提取器（representation learning）開辟了道路（Vergari 等，2018，2019a）。

在這些場景中，一個有用的理論工具是與平滑且可分解的 PCC相關(guān)聯(lián)的增強電路（augmented circuit）A（Peharz 等，2016）。
一個增強型 PC 將其基礎(chǔ) PC 中涉及潛變量Z的計算具體化為計算圖中的一些附加單元。換句話說，它編碼了聯(lián)合分布p(X, Z)，并允許使用標(biāo)準(zhǔn)的 PC 推理方法對其執(zhí)行概率推理。

簡而言之，將定義在隨機(jī)變量X上的 PCC增強為A是一個兩步過程：

1. 顯式表示潛變量 Z

   ：為 C 中每個與求和單元 n 相關(guān)聯(lián)的潛變量 Z?（其取值 val(Z?) = k），引入一組 k 個指示性輸入分布單元（indicator input distribution units）；

2. 正確連接這些單元

   ，以“開啟”或“關(guān)閉”n 的各個輸入；

3. 對增強后的電路進(jìn)行平滑化處理

   （Darwiche, 2001b；Shih 等，2019），即確保其中每一個求和節(jié)點相對于新引入的 Z 都是平滑的。

對于一個定義在X上的平滑且可分解的概率電路 C，其增強后的聯(lián)合分布 pA(X,Z) 的計算圖不僅保持了平滑性和可分解性，而且還滿足另一個稱為確定性（determinism）的性質(zhì)（我們將在第6節(jié)中討論該性質(zhì)）。

此外，如果C的輸入分布屬于指數(shù)族分布（exponential families），那么增強后的聯(lián)合分布 pA(X,Z) 也將屬于指數(shù)族。1?在這種情況下，通過 EM 算法對C的參數(shù)進(jìn)行優(yōu)化，等價于沿著由底層密度的Fisher信息度量（Fisher information metric）所誘導(dǎo)的自然梯度方向進(jìn)行優(yōu)化（Sato, 1999）。

5.5 句法變換

由于一個概率電路（PC）通過其計算圖編碼了一個刻畫概率分布的函數(shù)，因此對該分布執(zhí)行某種變換（例如設(shè)置證據(jù)或進(jìn)行邊緣化，如第2.1節(jié)所述），也會引起該 PC 計算圖的相應(yīng)變換。我們將在第5.6節(jié)中回顧這些對計算圖的操作。

反過來，也可以對 PC 的計算圖本身進(jìn)行變換，而不改變其所編碼的概率分布函數(shù)。我們將這類操作稱為句法變換（syntactic transformations），下面我們將回顧其中一些變換。

如果對以下任何一種句法變換的應(yīng)用都不會改變計算圖結(jié)構(gòu)，則稱該 PC 處于規(guī)范形式（canonical form）。

首先，我們可以輕松地使輸入分布具有唯一性：
如果一個 PC 中有兩個不同的輸入分布單元編碼了相同的函數(shù)，我們可以刪除其中一個，并將其輸出添加到保留單元的輸出集合中。

其次，我們可以將一個 PC 轉(zhuǎn)換為交替排列求和單元與乘積單元的形式，而不改變其表示的分布；
即，求和單元只接收來自乘積單元或輸入分布單元的輸入，反之亦然。
要實現(xiàn)這種排列方式，必須迭代地合并相鄰的同類單元，直到不再存在這樣的單元為止。

舉個例子，在一個 PCC中有兩個計算單元n和i，它們是同一種類型的（例如兩個求和單元），并且i同時向n以及其他類型（例如乘積單元）的單元c?, ..., c?提供輸入。

• 首先，我們可以復(fù)制i，并將這個副本從n上斷開（它仍然向c?, ..., c?提供輸入）；

• 然后，通過將i的所有輸入單元重新定向為n的輸入，可以將i合并進(jìn)n，從而保持C所表示的分布不變。

最后，在規(guī)范形式下，我們假設(shè) PC 的求和權(quán)重都是非零的，因為我們可以高效地剪枝掉零權(quán)重。

也就是說，我們可以直接移除所有權(quán)重為零的邊，并按照“先輸出后輸入”的順序迭代地移除那些沒有輸出連接的單元。

6. 針對 MAP 查詢的可處理電路

本節(jié)介紹另一類可處理的概率電路（PCs），即能夠高效回答 MAP 查詢的概率電路。

我們首先在第6.1節(jié)中形式化定義MAP 查詢類，然后在第6.2節(jié)中，通過其計算圖的結(jié)構(gòu)性質(zhì)——確定性（determinism）與一致性（consistency）——來刻畫哪些 PC 對于 MAP 查詢是可處理的。

6.1 MAP 查詢類

如前文簡要提及的那樣，MAP 查詢（最大后驗查詢）涉及一個分布的眾數(shù)（mode），如下例所示。