Deriving a Stationary Dynamic Bayesian Network from a Logic Program with Recursive Loops

Yi-Dong Shen, Qiang Yang, Jia-Huai You, Li-Yan YuanarXiv 2005 · DOI · arXiv

Abstract

Recursive loops in a logic program present a challenging problem to the PLP framework. On the one hand, they loop forever so that the PLP backward-chaining inferences would never stop. On the other hand, they generate cyclic influences, which are disallowed in Bayesian networks. Therefore, in existing PLP approaches logic programs with recursive loops are considered to be problematic and thus are excluded. In this paper, we propose an approach that makes use of recursive loops to build a stationary dynamic Bayesian network. Our work stems from an observation that recursive loops in a logic program imply a time sequence and thus can be used to model a stationary dynamic Bayesian network without using explicit time parameters. We introduce a Bayesian knowledge base with logic clauses of the form $A \leftarrow A_1,...,A_l, true, Context, Types$, which naturally represents the knowledge that the $A_i$s have direct influences on $A$ in the context $Context$ under the type constraints $Types$. We then use the well-founded model of a logic program to define the direct influence relation and apply SLG-resolution to compute the space of random variables together with their parental connections. We introduce a novel notion of influence clauses, based on which a declarative semantics for a Bayesian knowledge base is established and algorithms for building a two-slice dynamic Bayesian network from a logic program are developed.

Introduction

Probabilistic Logic Programming (PLP) aims to unify formal logical reasoning with the uncertainty management of Bayesian Networks (BNs). A significant hurdle in this integration is the presence of recursive loops. In standard logic programming, loops like aids(X) :- aids(X) can cause infinite recursion. In the context of BNs, such loops create cycles, violating the requirement that BNs be Directed Acyclic Graphs (DAGs).

Historically, PLP frameworks have either prohibited recursive loops or required users to manually insert time parameters (e.g., $p(X, T) :- p(X, T-1)$). However, time-parameter-based approaches are often "leaky"; an insufficient time bound $T$ may result in false negative answers. This paper presents a method to transform these recursive loops into a feature by interpreting them as temporal feedback mechanisms, enabling the automatic derivation of stationary Dynamic Bayesian Networks (DBNs).

Methodology

The proposed approach utilizes a Bayesian Knowledge Base (BKB), which employs a specific structure for influence clauses: $A \leftarrow A_1, \dots, A_l, true, Context, Types$. This structure distinguishes between variables exerting influence ($A_i$) and the logical context required for that influence to manifest.

To ensure computational termination, the framework uses SLG-resolution (tabling). This technique allows the inference engine to recognize previously encountered goals, effectively "cutting" infinite loops. When the system detects a cycle, it applies a Two-Slice DBN Algorithm to transform the logical loop into a temporal sequence by introducing state input nodes (representing variables at time $t-1$).

Unrolling a recursive logic program into a temporal sequence of influences.

This unrolling process, as illustrated in Figure 1, demonstrates how recursive dependencies are mapped across time slices. The resulting model is a stationary DBN, where transition probabilities remain constant across all time steps.

A two-slice Dynamic Bayesian Network (DBN) derived from recursive logic.

As shown in Figure 2, the algorithm compactly represents these temporal dependencies within a two-slice structure, where the state at $t-1$ informs the state at $t$.

Results and Discussion

The effectiveness of this approach was evaluated using benchmark logic programs, including the AIDS Program for disease transmission feedback and synthetic Path Relations.

Key results include:

  • Guaranteed Termination: SLG-resolution ensures the system terminates even with complex recursive structures.
  • Robustness: Unlike time-parameter-based frameworks, this method finds all valid answers by treating loops as fixed-points in the well-founded model, avoiding the "leaky" behavior of manual time bounds.
  • Computational Efficiency: For Datalog programs, the complexity of deriving the network structure remains polynomial.

The "aha moment" of this research is the realization that cycles in logic are not mere redundancies but compact representations of feedback loops. By treating recursion as implicit time, the framework allows for cleaner, less error-prone code.

Conclusion and Future Work

This paper demonstrates that recursive loops can be a powerful tool for modeling dynamic systems without explicit time parameters. While currently focused on stationary DBNs and Datalog, future research will explore learning BKB clauses directly from data and applying these methods to large-scale domains such as Traditional Chinese Medicine (TCM), where diagnostic rules are inherently recursive and contextual.

Summary updated

Abstract

Recursive loops in a logic program present a challenging problem to the PLP framework. On the one hand, they loop forever so that the PLP backward-chaining inferences would never stop. On the other hand, they generate cyclic influences, which are disallowed in Bayesian networks. Therefore, in existing PLP approaches logic programs with recursive loops are considered to be problematic and thus are excluded. In this paper, we propose an approach that makes use of recursive loops to build a stationary dynamic Bayesian network. Our work stems from an observation that recursive loops in a logic program imply a time sequence and thus can be used to model a stationary dynamic Bayesian network without using explicit time parameters. We introduce a Bayesian knowledge base with logic clauses of the form $A \leftarrow A_1,...,A_l, true, Context, Types$, which naturally represents the knowledge that the $A_i$s have direct influences on $A$ in the context $Context$ under the type constraints $Types$. We then use the well-founded model of a logic program to define the direct influence relation and apply SLG-resolution to compute the space of random variables together with their parental connections. We introduce a novel notion of influence clauses, based on which a declarative semantics for a Bayesian knowledge base is established and algorithms for building a two-slice dynamic Bayesian network from a logic program are developed.
BibTeX
@misc{shen2005deriving,
  author = {Yi-Dong Shen and Qiang Yang and Jia-Huai You and Li-Yan Yuan},
  title = {{Deriving a Stationary Dynamic Bayesian Network from a Logic Program with Recursive Loops}},
  year = {2005},
  eprint = {cs/0506095},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0506095},
}
Figure