研究动态贝叶斯网络中条件独立性随时间的变化规律。
Temporal Properties of Conditional Independence in Dynamic Bayesian Networks
- 用线性时序逻辑和非确定性自动机形式化条件独立性的时序性质
- 随机型条件独立判定复杂度等价于数论中的施克伦问题
- 结构型条件独立验证在特定图结构下可高效求解
动态贝叶斯网络（DBNs）是建模随时间演化的相互依赖随机变量及其分布的紧凑图模型。本文研究条件独立（CI）命题在时间逻辑规范下的可验证性。考虑两种形式化：线性时序逻辑（LTL）与非确定性布赫自动机（NBAs）。该问题分为两类：随机型CI性质需考虑具体概率分布，而结构型CI性质仅基于网络图结构。我们证明，判断随机型CI命题是否最终成立，其复杂度至少等价于线性递推序列的施克伦问题——一个长期未解的数论难题。相比之下，结构型CI性质在LTL与NBA规范下的验证属于PSPACE，且为NP与coNP难。此外，我们识别出若干自然的图结构限制，使结构型条件独立验证变为易处理问题。
原文摘要 · Abstract (English)
Dynamic Bayesian networks (DBNs) are compact graphical representations used to model probabilistic systems where interdependent random variables and their distributions evolve over time. In this paper, we study the verification of the evolution of conditional-independence (CI) propositions against temporal logic specifications. To this end, we consider two specification formalisms over CI propositions: linear temporal logic (LTL), and non-deterministic Büchi automata (NBAs). This problem has two variants. Stochastic CI properties take the given concrete probability distributions into account, while structural CI properties are viewed purely in terms of the graphical structure of the DBN. We show that deciding if a stochastic CI proposition eventually holds is at least as hard as the Skolem problem for linear recurrence sequences, a long-standing open problem in number theory. On the other hand, we show that verifying the evolution of structural CI propositions against LTL and NBA specifications is in PSPACE, and is NP- and coNP-hard. We also identify natural restrictions on the graphical structure of DBNs that make the verification of structural CI properties tractable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。