動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)中條件獨(dú)立性的時(shí)序特性

Temporal Properties of Conditional Independence in Dynamic Bayesian Networks

https://arxiv.org/pdf/2511.10266

摘要
動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)（DBNs）是一種緊湊的圖模型，用于刻畫(huà)概率性系統(tǒng)——其中相互依賴的隨機(jī)變量及其概率分布隨時(shí)間演化。本文研究如何針對(duì)時(shí)序邏輯規(guī)范，驗(yàn)證條件獨(dú)立性（CI）命題的演化過(guò)程。為此，我們考慮兩種在CI命題之上的形式化規(guī)范：線性時(shí)序邏輯（LTL）和非確定性布奇自動(dòng)機(jī)（NBA）。該問(wèn)題存在兩個(gè)變體：隨機(jī)性CI性質(zhì)，需考慮給定的具體概率分布；結(jié)構(gòu)性CI性質(zhì)，則僅依賴DBN的圖結(jié)構(gòu)本身。我們證明：判定一個(gè)隨機(jī)性CI命題是否“最終成立”，其難度至少等同于數(shù)論中長(zhǎng)期懸而未決的線性遞推序列Skolem問(wèn)題；而針對(duì)LTL與NBA規(guī)范驗(yàn)證結(jié)構(gòu)性CI命題的演化，則屬于PSPACE復(fù)雜度類，且均為NP-難與coNP-難。此外，我們還識(shí)別出DBN圖結(jié)構(gòu)中若干自然的限制條件，可使結(jié)構(gòu)性CI性質(zhì)的驗(yàn)證變得可行（tractable）。

1 引言
貝葉斯網(wǎng)絡(luò)（BNs）（Pearl 1985, 1988；Neapolitan 1990）是數(shù)據(jù)科學(xué)與人工智能領(lǐng)域的核心工具，支持在不確定性條件下的建模與推理。BN通過(guò)有向無(wú)環(huán)圖（DAG）這一模板，簡(jiǎn)潔地表示完整的聯(lián)合概率分布：圖中的節(jié)點(diǎn)對(duì)應(yīng)隨機(jī)變量，邊刻畫(huà)變量間的依賴關(guān)系，并為每個(gè)變量指定其在父節(jié)點(diǎn)條件下的概率分布。BN已成功應(yīng)用于醫(yī)療AI（Lucas等，2004）、自然語(yǔ)言處理（Manning & Schütze，1999）、機(jī)器人學(xué)（Thrun等，2005）、生物信息學(xué)（Friedman，2000）以及風(fēng)險(xiǎn)評(píng)估（Fenton & Neil，2012）等領(lǐng)域。

動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)（DBNs）將BN擴(kuò)展至變量結(jié)果隨時(shí)間演化的系統(tǒng)建模（Murphy，2002；Koller & Friedman，2009）。DBNs通過(guò)對(duì)一組隨機(jī)變量的聯(lián)合概率分布序列進(jìn)行緊湊表示：即首先用一個(gè)初始BN定義時(shí)間點(diǎn)0（記為 V0）的初始聯(lián)合分布；再通過(guò)一個(gè)步進(jìn)BN（step BN）定義下一時(shí)刻 Vt+1的聯(lián)合分布（以當(dāng)前時(shí)刻變量 Vt為條件）。這兩個(gè)BN對(duì)應(yīng)的DAG共同構(gòu)成所謂的DBN模板；將該模板實(shí)例化為具體的條件概率分布（CPDs），即可得到一個(gè)具體的DBN。

DBN所具備的時(shí)序維度推動(dòng)其在機(jī)器人學(xué)（Thrun等，2005）與系統(tǒng)生物學(xué)（Palaniappan & Thiagarajan，2012）中的應(yīng)用。如今，DBN廣泛應(yīng)用于諸多領(lǐng)域；以下實(shí)例說(shuō)明其在現(xiàn)代AI中的持續(xù)重要性：

• 將DBN融入計(jì)算機(jī)視覺(jué)算法可提升其適應(yīng)性與效率（Piedade & Miraldo，2023）；

• DBN與大語(yǔ)言模型（LLMs）相結(jié)合，已被用于構(gòu)建能依據(jù)上下文、與用戶進(jìn)行多模態(tài)交互的智能系統(tǒng)（Han等，2025）；

• 在醫(yī)療領(lǐng)域，DBN可在保持可解釋性、并對(duì)缺失數(shù)據(jù)魯棒的前提下，支持重癥監(jiān)護(hù)室（ICU）中膿毒癥的早期預(yù)測(cè)（Agard等，2025）；

• 近期神經(jīng)科學(xué)研究采用多時(shí)間尺度DBN推斷腦區(qū)之間具有行為依賴性的有向交互作用，在高質(zhì)量數(shù)據(jù)集上展現(xiàn)出良好性能（Das等，2024）；

• 醫(yī)學(xué)之外，DBN還被用于太陽(yáng)能發(fā)電預(yù)測(cè)（Zhang等，2024）及交通網(wǎng)絡(luò)等動(dòng)態(tài)工程系統(tǒng)的韌性分析（Kammouh等，2020）。

鑒于其重要性，從數(shù)據(jù)中學(xué)習(xí)DBN結(jié)構(gòu)的算法仍是當(dāng)前活躍的研究方向（參見(jiàn)，例如Meng等，2024）。

為了表達(dá)系統(tǒng)的時(shí)序?qū)傩?，線性時(shí)序邏輯（LTL）和非確定性布希自動(dòng)機(jī)（NBAs），捕獲所有 ω -正則語(yǔ)言的使用，在過(guò)去幾十年中已成為一個(gè)成功的故事（參見(jiàn)，例如，（Baier和Katoen 2008））。我們旨在利用這些形式化方法來(lái)討論CI的時(shí)序方面。

1.1 貢獻(xiàn)

1. 在第3節(jié)中，我們介紹了用于DBN模板和DBN中結(jié)構(gòu)或隨機(jī)CI命題演變的時(shí)間規(guī)范機(jī)制，分別使用LTL和NBAs。我們制定了由此產(chǎn)生的結(jié)構(gòu)和隨機(jī)CI模型檢查問(wèn)題。

2. 在第4節(jié)中，我們展示了DBN模板對(duì)LTL公式和NBAs的結(jié)構(gòu)CI模型檢查問(wèn)題在PSPACE中是NP難的，并且也是coNP難的。在DBN模板的初始模板僅包含在步驟模板中也作為時(shí)間片內(nèi)邊出現(xiàn)的邊的自然限制下，我們證明了這些問(wèn)題是P類問(wèn)題。

3. 給定具有CPDs的完整DBNs，我們?cè)诘?節(jié)中展示了檢查最終隨機(jī)CI與檢查線性遞歸序列的Skolem問(wèn)題一樣難，這是一個(gè)著名的數(shù)論問(wèn)題，其可判定性狀態(tài)已經(jīng)開(kāi)放了幾十年。這意味著如果沒(méi)有在解析數(shù)論中的突破，隨機(jī)CI模型檢查問(wèn)題的可判定性結(jié)果是遙不可及的。

1.2 相關(guān)工作

如何在BNs中檢測(cè)結(jié)構(gòu)CI的問(wèn)題在1980年代和1990年代得到了回答，表明d-分離表征了所有遵循BN結(jié)構(gòu)的結(jié)構(gòu)CI，這在幾乎所有CPDs選擇下等同于隨機(jī)CI，并且通過(guò)顯示d-分離可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算這些結(jié)構(gòu)CI（參見(jiàn)（Pearl 1988；Geiger, Verma和Pearl 1990；Meek 1995））。確切地確定隨機(jī)CI是否成立需要精確計(jì)算必要的條件概率分布。然而，離散隨機(jī)變量條件獨(dú)立的近似測(cè)試方法是一個(gè)活躍的研究領(lǐng)域（參見(jiàn)，例如，（Canonne等，2018；Teymur和Filippi 2020））。通常，Boutilier等人（1996）研究了所謂的上下文敏感獨(dú)立性，表示變量可能僅在對(duì)其他變量的特定值分配下獨(dú)立。像隨機(jī)CI一樣，這種獨(dú)立性取決于具體的CPDs。

我們不知道對(duì)DBNs中CI的d-分離和檢測(cè)的徹底研究，更不用說(shuō)DBNs中CI的時(shí)序?qū)傩缘男问津?yàn)證了。關(guān)于BNs的其他擴(kuò)展，Shen等人（2019）研究了測(cè)試BNs，這是BNs的擴(kuò)展，表示一組概率分布而不是單一分布，并表明d-分離仍然可以用來(lái)檢測(cè)結(jié)構(gòu)CI。

2 預(yù)備知識(shí)

貝葉斯網(wǎng)絡(luò) 貝葉斯網(wǎng)絡(luò)（BN）是一種概率圖模型，它使用有向無(wú)環(huán)圖（DAG）表達(dá)一組變量及其條件依賴關(guān)系，其中每個(gè)節(jié)點(diǎn)代表一個(gè)變量，邊表示變量之間的直接概率依賴。

3 時(shí)間條件獨(dú)立性屬性的規(guī)范形式化

相反的方向，即d-分離對(duì)DBNs的完備性，結(jié)果證明是復(fù)雜的。我們?cè)诘?節(jié)中討論這個(gè)問(wèn)題。

4 結(jié)構(gòu)條件獨(dú)立性

為了傳達(dá)這些困難結(jié)果的感覺(jué)，我們首先提供一個(gè) DBN 模板家族的例子，其軌跡的周期是所用變量數(shù)量的指數(shù)級(jí)：

我們建立了判斷是否成立的NP難度：我們從一元DFA的NP完全交集問(wèn)題（Blondin, Krebs, 和 McKenzie 2016）進(jìn)行歸約。由于我們還可以訪問(wèn)否定公式，我們也可以從互補(bǔ)問(wèn)題進(jìn)行歸約。此外，這兩種屬性都可以用固定的NBAs表示，我們得到了以下結(jié)果，其證明是對(duì)上述例子的改編。

4.1 DBN通過(guò)轉(zhuǎn)換系統(tǒng)追蹤

4.2 限制性DBN的特殊情況

5 隨機(jī)條件獨(dú)立性

在本節(jié)中，我們建立了在給定具體條件概率分布時(shí)，關(guān)于隨機(jī)條件獨(dú)立性（CIs）推理的數(shù)論難度。具體來(lái)說(shuō)，我們將展示判斷形式為的公式是否成立至少和有理線性遞歸序列（LRS）的Skolem問(wèn)題一樣難。

這種歸約使用（Aghamohamadi et al. 2025, Cor. 1）將給定的LRS“嵌入”到馬爾可夫鏈中，然后使用引理 2.4 將馬爾可夫鏈轉(zhuǎn)換為DBN。我們注意到，作為推論，我們的構(gòu)造也可以用來(lái)將LRS的密切相關(guān)的正性問(wèn)題（參見(jiàn)，例如，(Quaknine and Worrell 2014)）用于數(shù)論難度的論證）歸約為判斷 Y 是否總是“正向影響” X 的問(wèn)題。

6 討論：DBN中的忠實(shí)性

命題3.1展示了DBNs中定理2.3的一個(gè)類似結(jié)果，盡管是單向的。然而，在未來(lái)的工作中，我們旨在正式證明結(jié)構(gòu)獨(dú)立性的概念在DBNs中對(duì)隨機(jī)獨(dú)立性是忠實(shí)的，從而為DBNs建立定理2.3的完整類似結(jié)果。與已知結(jié)果的區(qū)別在于，當(dāng)過(guò)渡到DBNs時(shí)，我們通過(guò)在不同時(shí)間切片中識(shí)別相同變量的分布來(lái)對(duì)參數(shù)施加約束。這減少了參數(shù)空間的維度，導(dǎo)致在任何給定時(shí)間 t 可接受的貝葉斯網(wǎng)絡(luò)家族嚴(yán)格更小。

我們注意到，定理2.3的證明（Meek 1995，第6.4節(jié)）依賴于一個(gè)局部依賴條件：如果是一條邊，那么 X 和 Y 必須是相關(guān)的。在貝葉斯網(wǎng)絡(luò)中，條件概率分布（CPDs）可以被選擇為使得沿著d-路徑的變量是局部依賴的，而所有其他變量仍然與其他任何變量獨(dú)立。這在動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)中是不可能的，因?yàn)闀r(shí)間和結(jié)構(gòu)約束阻止了這種隔離。這種限制是將論證擴(kuò)展到DBN設(shè)置的一個(gè)關(guān)鍵障礙。一個(gè)潛在的方法是考慮一個(gè)CPD，其中當(dāng)一個(gè)變量的大多數(shù)父節(jié)點(diǎn)為1時(shí)，該變量以更高的概率取值為1。雖然我們?cè)谶@里專注于二元變量，但在這個(gè)設(shè)置中建立結(jié)果將直接產(chǎn)生一般情況作為直接推論。另一個(gè)有希望的方向來(lái)自代數(shù)統(tǒng)計(jì)（Sullivant 2018），它應(yīng)用代數(shù)幾何和組合學(xué)的工具來(lái)研究統(tǒng)計(jì)模型，特別是那些涉及離散數(shù)據(jù)的模型。在貝葉斯網(wǎng)絡(luò)中，它將條件獨(dú)立性編碼為多項(xiàng)式方程，并分析由此產(chǎn)生的代數(shù)簇以理解結(jié)構(gòu)和概率屬性。另一種可能的方法可能涉及觀察在時(shí)間 t 描述條件（不）依賴的多項(xiàng)式序列在多變量有理函數(shù)域上形成一個(gè)線性遞歸，并且可以合理地訴諸于Skolem-Mahler-Lech定理（特征為0的域上線性遞歸的零點(diǎn)集是有限集和有限多個(gè)有效算術(shù)級(jí)數(shù)的并集）。

7 結(jié)論

我們引入了基于LTL和NBA的規(guī)范形式來(lái)表達(dá)DBN中CIs的時(shí)間屬性。這些形式化方法可以表達(dá)理想的系統(tǒng)屬性，例如在安全應(yīng)用中的非干擾性，并開(kāi)放了驗(yàn)證系統(tǒng)以滿足各種關(guān)于CIs時(shí)間演變的期望規(guī)范的可能性。

關(guān)于DBN中的隨機(jī)CI，我們的Skolem難度結(jié)果對(duì)于驗(yàn)證系統(tǒng)相對(duì)于隨機(jī)CI陳述的時(shí)間規(guī)范的潛力是令人清醒的——這可能會(huì)令人驚訝。獲得這一難度結(jié)果的關(guān)鍵是建立LRS和DBN之間復(fù)雜的聯(lián)系。

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