動態貝葉斯網絡中條件獨立性的時序特性

動態貝葉斯網絡中條件獨立性的時序特性

Temporal Properties of Conditional Independence in Dynamic Bayesian Networks

https://arxiv.org/pdf/2511.10266

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

1 引言
貝葉斯網絡（BNs）（Pearl 1985, 1988；Neapolitan 1990）是數據科學與人工智能領域的核心工具，支持在不確定性條件下的建模與推理。BN通過有向無環圖（DAG）這一模板，簡潔地表示完整的聯合概率分布：圖中的節點對應隨機變量，邊刻畫變量間的依賴關系，并為每個變量指定其在父節點條件下的概率分布。BN已成功應用于醫療AI（Lucas等，2004）、自然語言處理（Manning & Schütze，1999）、機器人學（Thrun等，2005）、生物信息學（Friedman，2000）以及風險評估（Fenton & Neil，2012）等領域。

動態貝葉斯網絡（DBNs）將BN擴展至變量結果隨時間演化的系統建模（Murphy，2002；Koller & Friedman，2009）。DBNs通過對一組隨機變量的聯合概率分布序列進行緊湊表示：即首先用一個初始BN定義時間點0（記為 V0）的初始聯合分布；再通過一個步進BN（step BN）定義下一時刻 Vt+1的聯合分布（以當前時刻變量 Vt為條件）。這兩個BN對應的DAG共同構成所謂的DBN模板；將該模板實例化為具體的條件概率分布（CPDs），即可得到一個具體的DBN。

DBN所具備的時序維度推動其在機器人學（Thrun等，2005）與系統生物學（Palaniappan & Thiagarajan，2012）中的應用。如今，DBN廣泛應用于諸多領域；以下實例說明其在現代AI中的持續重要性：

• 將DBN融入計算機視覺算法可提升其適應性與效率（Piedade & Miraldo，2023）；

• DBN與大語言模型（LLMs）相結合，已被用于構建能依據上下文、與用戶進行多模態交互的智能系統（Han等，2025）；

• 在醫療領域，DBN可在保持可解釋性、并對缺失數據魯棒的前提下，支持重癥監護室（ICU）中膿毒癥的早期預測（Agard等，2025）；

• 近期神經科學研究采用多時間尺度DBN推斷腦區之間具有行為依賴性的有向交互作用，在高質量數據集上展現出良好性能（Das等，2024）；

• 醫學之外，DBN還被用于太陽能發電預測（Zhang等，2024）及交通網絡等動態工程系統的韌性分析（Kammouh等，2020）。

鑒于其重要性，從數據中學習DBN結構的算法仍是當前活躍的研究方向（參見，例如Meng等，2024）。

為了表達系統的時序屬性，線性時序邏輯（LTL）和非確定性布希自動機（NBAs），捕獲所有 ω -正則語言的使用，在過去幾十年中已成為一個成功的故事（參見，例如，（Baier和Katoen 2008））。我們旨在利用這些形式化方法來討論CI的時序方面。

1.1 貢獻

1. 在第3節中，我們介紹了用于DBN模板和DBN中結構或隨機CI命題演變的時間規范機制，分別使用LTL和NBAs。我們制定了由此產生的結構和隨機CI模型檢查問題。

2. 在第4節中，我們展示了DBN模板對LTL公式和NBAs的結構CI模型檢查問題在PSPACE中是NP難的，并且也是coNP難的。在DBN模板的初始模板僅包含在步驟模板中也作為時間片內邊出現的邊的自然限制下，我們證明了這些問題是P類問題。

3. 給定具有CPDs的完整DBNs，我們在第5節中展示了檢查最終隨機CI與檢查線性遞歸序列的Skolem問題一樣難，這是一個著名的數論問題，其可判定性狀態已經開放了幾十年。這意味著如果沒有在解析數論中的突破，隨機CI模型檢查問題的可判定性結果是遙不可及的。

1.2 相關工作

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

我們不知道對DBNs中CI的d-分離和檢測的徹底研究，更不用說DBNs中CI的時序屬性的形式驗證了。關于BNs的其他擴展，Shen等人（2019）研究了測試BNs，這是BNs的擴展，表示一組概率分布而不是單一分布，并表明d-分離仍然可以用來檢測結構CI。

2 預備知識

貝葉斯網絡 貝葉斯網絡（BN）是一種概率圖模型，它使用有向無環圖（DAG）表達一組變量及其條件依賴關系，其中每個節點代表一個變量，邊表示變量之間的直接概率依賴。

3 時間條件獨立性屬性的規范形式化

相反的方向，即d-分離對DBNs的完備性，結果證明是復雜的。我們在第6節中討論這個問題。

4 結構條件獨立性

為了傳達這些困難結果的感覺，我們首先提供一個 DBN 模板家族的例子，其軌跡的周期是所用變量數量的指數級：

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

4.1 DBN通過轉換系統追蹤

4.2 限制性DBN的特殊情況

5 隨機條件獨立性

在本節中，我們建立了在給定具體條件概率分布時，關于隨機條件獨立性（CIs）推理的數論難度。具體來說，我們將展示判斷形式為的公式是否成立至少和有理線性遞歸序列（LRS）的Skolem問題一樣難。

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

6 討論：DBN中的忠實性

命題3.1展示了DBNs中定理2.3的一個類似結果，盡管是單向的。然而，在未來的工作中，我們旨在正式證明結構獨立性的概念在DBNs中對隨機獨立性是忠實的，從而為DBNs建立定理2.3的完整類似結果。與已知結果的區別在于，當過渡到DBNs時，我們通過在不同時間切片中識別相同變量的分布來對參數施加約束。這減少了參數空間的維度，導致在任何給定時間 t 可接受的貝葉斯網絡家族嚴格更小。

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

7 結論

我們引入了基于LTL和NBA的規范形式來表達DBN中CIs的時間屬性。這些形式化方法可以表達理想的系統屬性，例如在安全應用中的非干擾性，并開放了驗證系統以滿足各種關于CIs時間演變的期望規范的可能性。

關于DBN中的隨機CI，我們的Skolem難度結果對于驗證系統相對于隨機CI陳述的時間規范的潛力是令人清醒的——這可能會令人驚訝。獲得這一難度結果的關鍵是建立LRS和DBN之間復雜的聯系。

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