貝葉斯網(wǎng)絡的分解:局部和并行推理

貝葉斯網(wǎng)絡的分解：局部與并行推理

Decomposition for Bayesian Networks: Local andParallel Inference

https://arxiv.org/pdf/2607.04650

摘要

高維貝葉斯網(wǎng)絡中的概率推斷十分困難，因為對聯(lián)合分布進行精確處理的復雜度隨網(wǎng)絡規(guī)模呈指數(shù)級增長。我們提出了一種基于有向凸子圖的分解框架，并引入了一個最小d-分解樹。它們共同為經(jīng)典的連接樹構(gòu)造提供了一種有理論依據(jù)的替代方案。所提出的框架通過可以單獨學習和存儲的低維子模型來表示聯(lián)合分布。這種分解降低了計算成本，并自然地實現(xiàn)了并行計算。基于最小d-分解樹，我們進一步開發(fā)了兩種用于參數(shù)估計和概率推斷的并行算法。實驗表明，與連接樹方法相比，所提出的方法在保持推斷精度的同時大幅提高了計算效率，特別是對于低維查詢。

索引詞——貝葉斯網(wǎng)絡，有向無環(huán)圖，分解，有向凸子圖。

I. 引言

貝葉斯網(wǎng)絡（BNs）是概率圖模型，通過有向無環(huán)圖（DAGs）表示隨機變量間的條件依賴結(jié)構(gòu)[1]。該建模框架為表示高維數(shù)據(jù)中的復雜依賴關(guān)系提供了有原則且可解釋的理論基礎(chǔ)[2]。它還為不確定性下的概率表示和推理提供了數(shù)學上透明的框架。因此，它們已被廣泛應用于數(shù)據(jù)分析及相關(guān)工程領(lǐng)域，包括機器學習[3],[4]、生物醫(yī)學工程[5],[6]、決策支持系統(tǒng)[7],[8]和可靠性分析[9],[10]。

盡管有這些優(yōu)勢，在高維BNs中的學習和推理仍然具有挑戰(zhàn)性[1]。高維設(shè)置的特征通常是數(shù)據(jù)稀疏性、變量間復雜的非線性依賴關(guān)系以及巨大的計算成本。這些因素使得對聯(lián)合分布的直接估計變得困難，并需要更易處理的方法。

相關(guān)工作。由于分解對于高維BNs的可擴展學習和推理至關(guān)重要，許多研究已開發(fā)出基于分解的方法。早期的一條工作線是Pearl的[2]信念傳播算法[15]，它構(gòu)建一個聯(lián)結(jié)樹并通過消息傳遞對其進行校準。這種結(jié)構(gòu)為緩存中間計算結(jié)果提供了一種有效機制。隨后，Wu [15]提出了一種基于分治策略的無損BN分解方法。該方法首先執(zhí)行全局參數(shù)學習，然后將聯(lián)結(jié)樹分離器上的勢因子分解，并將其分發(fā)到相鄰的樹節(jié)點上。進一步表明，原始BN中編碼的條件獨立性在分解后的子網(wǎng)絡中得以完全保留。盡管有效，但這兩種方法仍然遵循全局范式。分解后，子網(wǎng)絡分布仍然依賴于全局學習的量進行初始化。因此，這些方法并沒有實現(xiàn)嚴格的局部建模或完全獨立的推理。

其他研究則側(cè)重于子模型本身的結(jié)構(gòu)和統(tǒng)計特性。Kim和Kim [16]提出了分裂器分解方法，該方法在分解后的子模型內(nèi)添加額外邊以確保邊際分布的一致性，使得子模型可以直接從局部數(shù)據(jù)中進行參數(shù)化。然而，這種策略不可避免地增加了子模型的結(jié)構(gòu)復雜性，導致更高的數(shù)據(jù)存儲和計算成本。這種“添邊”操作的根本原因在于有向無環(huán)圖在邊際化下不封閉[17],[18]，這突顯了BNs中分解的內(nèi)在困難。

為了解決這些局限性，Li和Guo [19]提出使用完全的d-分離器來分解BN，并表明所得子模型自然滿足條件獨立性約束。他們的工作識別了BNs中一種類似于無向圖模型[11]中原子分解的結(jié)構(gòu)機制，允許子模型僅基于局部數(shù)據(jù)執(zhí)行獨立的參數(shù)學習和存儲，同時還能用于后續(xù)推理。然而，他們的方法要求d-分解器滿足完全性條件，而這對于可分解性來說并非必需，因此限制了其實際適用性。

主要貢獻。我們的第一個貢獻是對d-分解器的圖論刻畫：一個子集是d-分解器當且僅當它是一個有向凸的d-分離器。基于此觀察，我們提出了一種BNs的分解框架，其中所得子圖自然滿足可壓縮性。定理1給出了聯(lián)合分布的誘導分解，并闡明了所得子模型的統(tǒng)計作用。

我們進一步開發(fā)了一種高效的分解算法，并將所得子圖組織成一棵極小d-分解樹，其中每個d-分解器對應一個d-凸的極小d-分離器。基于此結(jié)構(gòu)，我們開發(fā)了兩種算法，利用極小d-分解樹在高維網(wǎng)絡中進行并行參數(shù)估計和概率推理。在實驗部分，我們對離散型和高斯貝葉斯網(wǎng)絡進行了大規(guī)模模擬。結(jié)果表明，我們的方法在參數(shù)估計和推理方面都顯著優(yōu)于現(xiàn)有的基于聯(lián)結(jié)樹的方法，特別是在低維查詢方面。

本文的其余部分組織如下。第二節(jié)介紹了本文使用的必要符號和背景。第三節(jié)介紹貝葉斯網(wǎng)絡的有向分解并建立其基本性質(zhì)。該節(jié)還構(gòu)建了一棵極小d-分解樹，并提出了一個用于推理的剪枝規(guī)則。第四節(jié)描述了使用極小d-分解樹進行并行參數(shù)學習和概率推理的兩種算法。第五節(jié)通過實證實驗，將基于極小d-分解樹的方法在參數(shù)估計和推理方面的性能與標準方法進行了評估。最后，第六節(jié)對本文進行了總結(jié)并給出簡要討論。

II、預備知識

我們首先介紹貫穿本文使用的符號和定義。

C. 貝葉斯網(wǎng)絡與邊緣分布模型

III. 貝葉斯網(wǎng)絡的分解

A. 有向凸子圖

B. 基于d-凸子圖的分解

我們現(xiàn)在正式定義貝葉斯網(wǎng)絡的分解。

命題3表明，每個分解后的子模型與原始網(wǎng)絡對應的邊緣模型一致。這使得參數(shù)學習可以直接在每個子網(wǎng)絡上使用局部數(shù)據(jù)進行，并將結(jié)果存儲以備后續(xù)使用。因此，推理效率得到顯著提高，計算成本得以降低。基于這一性質(zhì)，定理1形式化了網(wǎng)絡聯(lián)合分布在分解上的因式分解。

根據(jù)定理1，本研究所提出的分解方法具有若干關(guān)鍵優(yōu)勢。首先，局部子模型的邊緣分布可以直接從子圖數(shù)據(jù)中計算并存儲，可坍縮性保證了其正確性。其次，分解不會引入額外的有向邊，保留了原始子圖拓撲結(jié)構(gòu)，進一步提升了推理效率和準確性。

在實際應用中，準確識別合適的 d-分解器并高效分解貝葉斯網(wǎng)絡仍然具有挑戰(zhàn)性。這一困難源于有向無環(huán)圖中可能存在大量 d-分離器，這使得順序進行 d-凸性驗證和分解在計算上代價高昂。在下一小節(jié)中，我們通過使用基于樹的結(jié)構(gòu)來有效構(gòu)建最小 d-分解樹，從而應對這一挑戰(zhàn)，實現(xiàn)可擴展的參數(shù)學習和概率推理。

C. 一種高效的分解算法

該定義同時規(guī)定了邊上的分離器條件和節(jié)點上的不可約條件。一般而言，滿足這些條件的最小 d-分解樹并不唯一。

條件（i）要求，對于樹的每條邊，相應節(jié)點的交集是 G G中的一個最小 d-分解器。該條件確保貝葉斯網(wǎng)絡沿該邊被正確分解為兩個子模型。

條件（ii）進一步要求，沒有任何最小 d-分解器能夠分解與樹中任一節(jié)點相關(guān)聯(lián)的子模型。這保證了每個子模型在結(jié)構(gòu)上是不可約的。

在實踐中，有向無環(huán)圖的最小 d-分解樹可以從最小 d-分離樹構(gòu)建，后者是 Liu 等人 [23] 為結(jié)構(gòu)學習引入的一個概念。在構(gòu)建過程中，交集形成非凸 d-分離器的相鄰節(jié)點會被迭代合并，直到無法進一步合并為止。該過程生成該有向無環(huán)圖的最小 d-分解樹。基于這一方法，我們提出了一種構(gòu)建有向無環(huán)圖 G G的最小 d-分解樹的算法，如算法2所述，隨后對其正確性和計算復雜度進行簡要討論。

IV. 基于分解的并行學習與局部推理

本節(jié)介紹兩個過程。我們首先在分解后的子網(wǎng)絡上進行并行參數(shù)學習。然后，基于最小 d-分解樹的剪枝，開發(fā)一種局部推理算法。

A. 并行參數(shù)學習

并行參數(shù)學習通過將全局任務拆分為更小的子問題，提升了高維貝葉斯網(wǎng)絡的可擴展性。利用最小 d-分解樹，全局估計任務被劃分為對應于每個簇及其兩兩交集的獨立子問題。對于每個子問題，我們提取相應的數(shù)據(jù)，并通過最大似然或貝葉斯方法估計局部參數(shù)。然后，利用推論1重構(gòu)全局聯(lián)合分布。詳細過程如算法3所述。

由推論1可知，若一個貝葉斯網(wǎng)絡可以分解為 k k個 d-凸子圖的并集，則其聯(lián)合分布完全由這 k k個子圖上的邊緣分布以及它們兩兩交集中的 k ? 1 k?1個邊緣分布所決定。這種分解既降低了計算和存儲成本，也為使用最小 d-分解樹進行高效參數(shù)學習和概率推理奠定了基礎(chǔ)。

IV. 基于分解的并行學習與局部推理

本節(jié)介紹兩個過程。我們首先在分解后的子網(wǎng)絡上進行并行參數(shù)學習。然后，基于最小 d-分解樹的剪枝，開發(fā)一種局部推理算法。

A. 并行參數(shù)學習

并行參數(shù)學習通過將全局任務拆分為更小的子問題，提升了高維貝葉斯網(wǎng)絡的可擴展性。利用最小 d-分解樹，全局估計任務被劃分為對應于每個簇及其兩兩交集的獨立子問題。對于每個子問題，我們提取相應的數(shù)據(jù)，并通過最大似然或貝葉斯方法估計局部參數(shù)。然后，利用推論1重構(gòu)全局聯(lián)合分布。詳細過程如算法3所述。

B. 局部統(tǒng)計推理

大規(guī)模貝葉斯網(wǎng)絡中概率推理的目標是高效計算指定目標子集上的分布。最小 d-分解樹通常包含大量與查詢變量無關(guān)的節(jié)點，直接使用整棵樹會帶來不必要的計算開銷。為解決這一問題，我們引入遞歸約簡規(guī)則，從最小 d-分解樹中剪除無關(guān)的葉子節(jié)點，從而提高推理的效率和可擴展性。

命題4提供了從最小 d-分解樹中剪除葉子節(jié)點而不影響查詢變量推理準確性的判據(jù)。其核心思想在于，這些葉子節(jié)點中與查詢或證據(jù)變量相關(guān)的任何信息已包含在剩余節(jié)點中，且模型可坍縮到該剩余集合上。通過迭代移除此類葉子節(jié)點，最小 d-分解樹在實現(xiàn)結(jié)構(gòu)約簡的同時，保留了推理所需的所有依賴關(guān)系。這一性質(zhì)確保了局部后驗概率可以高效計算，而無需處理整個網(wǎng)絡，如下列算法所形式化描述。

算法4利用最小 d-分解樹對貝葉斯網(wǎng)絡執(zhí)行局部推理。該過程移除那些查詢或證據(jù)變量已包含在剩余簇中的葉子節(jié)點。此剪枝過程持續(xù)進行，直到所有剩余葉子節(jié)點都與查詢或證據(jù)相關(guān)。若僅剩一個簇，則應用變量消除法。

否則，在剪枝后的最小 d-分解樹上應用置信傳播，以計算給定證據(jù)下查詢變量的后驗概率。由此實現(xiàn)了精確推理，同時避免了在網(wǎng)絡中與目標后驗無關(guān)的部分上進行計算。

V. 實證研究

在本節(jié)中，我們報告了在所提出的最小 d-分解樹框架下，評估參數(shù)學習、模型精度和推理效率的數(shù)值實驗。實驗在配備 Intel(R) Xeon(R) Silver 4215R CPU（2 個處理器）和 128 GiB 內(nèi)存的系統(tǒng)上進行。本研究所用所有代碼可在 https://github.com/Balance-H/Decomposition-for-BNs獲取。

A. 參數(shù)學習

我們首先將分解后子網(wǎng)絡上的參數(shù)估計與直接全局估計進行比較。使用了 BNlearn 庫中的六個代表性貝葉斯網(wǎng)絡——Child、Alarm、Hailfinder、Hepar2、Win95pts 和 Pigs——其頂點數(shù)量從 20 到 441 不等。實驗按以下步驟進行：

備注1：在這些貝葉斯網(wǎng)絡中，所有變量均為二值變量。參數(shù)估計采用最大似然估計，固定樣本量為150,000。分解方法中的并行核心數(shù)根據(jù)子模型數(shù)量動態(tài)分配，最多使用9個核心。為確保公平比較，所報告的運行時間僅包含參數(shù)學習階段。

圖2展示了參數(shù)估計效率隨網(wǎng)絡規(guī)模的變化情況，網(wǎng)絡按從小到大的順序排列。對于較小的網(wǎng)絡，如Child和Alarm，由于并行計算的開銷，分解方法帶來的效率提升有限。隨著網(wǎng)絡規(guī)模增大，分解的優(yōu)勢變得更加明顯。對于大型網(wǎng)絡，在子模型上進行并行估計相比于全局估計實現(xiàn)了顯著的加速。在這六個基準網(wǎng)絡上，串行部分平均占總計算時間的不到20%。有關(guān)網(wǎng)絡樹寬以及分解后子圖維度分布的詳細信息，請參見補充材料S.2。

小的網(wǎng)絡，如Child和Alarm，由于并行計算的開銷，分解方法帶來的效率提升有限。隨著網(wǎng)絡規(guī)模增大，分解的優(yōu)勢變得更加明顯。對于大型網(wǎng)絡，在子模型上進行并行估計相比于全局估計實現(xiàn)了顯著的加速。在這六個基準網(wǎng)絡上，串行部分平均占總計算時間的不到20%。有關(guān)網(wǎng)絡樹寬以及分解后子圖維度分布的詳細信息，請參見補充材料S.2。

Remark 1. In these Bayesian networks, all variables are binary. Parameters are estimated by maximum likelihood with a fixed sample size of 150,000. The number of parallel cores in the decomposition method is assigned dynamically based on the number of sub-models, with a maximum of 9 cores. To ensure a fair comparison, the reported running times include only the parameter learning phase.直譯

備注1：在這些貝葉斯網(wǎng)絡中，所有變量均為二值變量。參數(shù)估計采用最大似然估計，固定樣本量為150,000。分解方法中的并行核心數(shù)根據(jù)子模型數(shù)量動態(tài)分配，最多使用9個核心。為確保公平比較，所報告的運行時間僅包含參數(shù)學習階段。

合并圖片內(nèi)容直譯

B. 并行學習的準確性

C. 最小 d-分解樹中的局部推理

前述實驗表明，學習得到的分解模型在分布上與原始模型非常匹配。因此，我們轉(zhuǎn)而關(guān)注推理效率，評估在最小 d-分解樹框架下聯(lián)合概率查詢的計算成本。同時，通過逐步增加查詢變量的維度來進行壓力測試，以評估剪枝機制在高維設(shè)置下的優(yōu)勢。

VI. 結(jié)論與討論

我們提出了一個貝葉斯網(wǎng)絡的分解框架，將原始網(wǎng)絡劃分為若干子圖，這些子圖所對應的子模型可以并行學習和存儲。我們還構(gòu)建了一個最小 d-分解樹，并配以用于局部推理的剪枝規(guī)則。基于該框架，我們開發(fā)了用于參數(shù)估計和概率推理的兩個算法。實驗表明，所提方法在參數(shù)估計和推理兩方面均提高了計算效率，尤其在查詢維度較小時更為顯著。

最小 d-分解樹并非唯一，如何為給定網(wǎng)絡找到使計算成本最小化的分解仍是一個開放性問題。對于分解后仍然高維的子圖，可以應用第二階段分解來構(gòu)建嵌套 d-分解樹，類似于文獻[24]中的嵌套聯(lián)結(jié)樹。此類擴展可能進一步提高推理效率，值得未來研究。

所提方法也存在局限性。該方法對稠密網(wǎng)絡和高維查詢的效果較差。然而，這一局限性也是精確推理方法普遍存在的。

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