Temporal Properties of Conditional Independence in Dynamic Bayesian Networks

• URL: http://arxiv.org/abs/2511.10266v1
• Date: Fri, 14 Nov 2025 01:42:23 GMT
• Title: Temporal Properties of Conditional Independence in Dynamic Bayesian Networks
• Authors: Rajab Aghamov, Christel Baier, Joel Ouaknine, Jakob Piribauer, Mihir Vahanwala, Isa Vialard,
• Abstract summary: We study the verification of conditional-independence propositions against temporal logic specifications.<n>We show that deciding if a CI proposition eventually holds is at least as hard as the Skolem problem for linear recurrence sequences.
• Score: 5.033660455789586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• On Multi-Step Theorem Prediction via Non-Parametric Structural Priors [50.16583672681106]
  In this work, we explore training-free theorem prediction through the lens of in-context learning (ICL)<n>We propose Theorem Precedence Graphs, which encode temporal dependencies from historical solution traces as directed graphs, and impose explicit topological constraints that effectively prune the search space during inference.<n>Experiments on the FormalGeo7k benchmark show that our method achieves 89.29% accuracy, substantially outperforming ICL baselines and matching state-of-the-art supervised models.
  arXiv  Detail & Related papers  (2026-03-05T06:08:50Z)
• Learning Identifiable Structures Helps Avoid Bias in DNN-based Supervised Causal Learning [56.22841701016295]
  Supervised Causal Learning (SCL) is an emerging paradigm in this field.<n>Existing Deep Neural Network (DNN)-based methods commonly adopt the "Node-Edge approach"
  arXiv  Detail & Related papers  (2025-02-15T19:10:35Z)
• Compositional Structures in Neural Embedding and Interaction Decompositions [101.40245125955306]
  We describe a basic correspondence between linear algebraic structures within vector embeddings in artificial neural networks. We introduce a characterization of compositional structures in terms of "interaction decompositions" We establish necessary and sufficient conditions for the presence of such structures within the representations of a model.
  arXiv  Detail & Related papers  (2024-07-12T02:39:50Z)
• Consistency of Neural Causal Partial Identification [17.503562318576414]
  Recent progress in Causal Models showcased how identification and partial identification of causal effects can be automatically carried out via neural generative models.<n>We prove consistency of partial identification via NCMs in a general setting with both continuous and categorical variables.<n>Results highlight the impact of the design of the underlying neural network architecture in terms of depth and connectivity.
  arXiv  Detail & Related papers  (2024-05-24T16:12:39Z)
• DynGFN: Towards Bayesian Inference of Gene Regulatory Networks with GFlowNets [81.75973217676986]
  Gene regulatory networks (GRN) describe interactions between genes and their products that control gene expression and cellular function. Existing methods either focus on challenge (1), identifying cyclic structure from dynamics, or on challenge (2) learning complex Bayesian posteriors over DAGs, but not both. In this paper we leverage the fact that it is possible to estimate the "velocity" of gene expression with RNA velocity techniques to develop an approach that addresses both challenges.
  arXiv  Detail & Related papers  (2023-02-08T16:36:40Z)
• On the Foundations of Cycles in Bayesian Networks [4.312746668772342]
  We present a foundational study regarding semantics for cyclic BNs that are generic and conservatively extend the cycle-free setting. First, we propose constraint-based semantics that specify requirements for full joint distributions over a BN to be consistent with the local conditional probabilities and independencies. Second, two kinds of limit semantics that formalize infinite unfolding approaches are introduced and shown to be computable by a Markov chain construction.
  arXiv  Detail & Related papers  (2023-01-20T14:40:17Z)
• Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks [0.0]
  Probabilistic context-free grammars (PCFGs) and dynamic Bayesian networks (DBNs) are widely used sequence models with complementary strengths and limitations. We present Recursive Bayesian Networks (RBNs), which generalise and unify PCFGs and DBNs, combining their strengths and containing both as special cases.
  arXiv  Detail & Related papers  (2021-11-02T19:21:15Z)
• Disentangling Identifiable Features from Noisy Data with Structured Nonlinear ICA [4.340954888479091]
  We introduce a new general identifiable framework for principled disentanglement referred to as Structured Independent Component Analysis (SNICA) Our contribution is to extend the identifiability theory of deep generative models for a very broad class of structured models. We establish the major result that identifiability for this framework holds even in the presence of noise of unknown distribution.
  arXiv  Detail & Related papers  (2021-06-17T15:56:57Z)
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures [132.74509389517203]
  We introduce a parametric variational family modelled by an autoregressive distribution over the space of discrete DAGs. In experiments, we demonstrate that the proposed variational posterior is able to provide a good approximation of the true posterior.
  arXiv  Detail & Related papers  (2021-06-14T17:52:49Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)
• Propagation for Dynamic Continuous Time Chain Event Graphs [0.0]
  We present a tractable exact inferential scheme analogous to the scheme in Kjaerulff (1992) for discrete Dynamic Bayesian Networks (DBNs) We show that the CT-DCEG is preferred to DBNs and continuous time BNs under contexts involving significant asymmetry and a natural total ordering of the process evolution.
  arXiv  Detail & Related papers  (2020-06-29T08:24:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.