Bayesian Logic Programs

Kristian Kersting, Luc De Raedt

TL;DR

Bayesian Logic Programs (BLPs) unify the strengths of Bayesian networks and first-order logic by mapping logical ground atoms directly to random variables. This framework allows researchers to model complex, relational domains with uncertainty—such as genetics or dynamic computer networks—while maintaining a strict, elegant separation between qualitative structure and quantitative probability.

What Problem Does This Paper Address?

Traditional Bayesian networks (BNs) are "propositional" in nature. They work brilliantly for a fixed set of variables, but they struggle to represent domains with a variable number of objects or complex relationships. For example, modeling a computer network where nodes are constantly added or deleted, or a family tree with varying generations, requires a different BN for every specific instance.

On the other hand, logic programming (like Prolog) is designed for relations and objects but lacks a native way to handle probabilistic uncertainty. Previous attempts to combine these two worlds often resulted in complex formalisms that were either computationally inefficient, restricted to discrete variables, or lacked a clear separation between the "logic" and the "math."

Methods

The authors introduce Bayesian Logic Programs (BLPs), which consist of a set of Bayesian clauses. A Bayesian clause looks like A | A1, ..., An, which can be read as "the random variable $A$ is conditionally dependent on $A_1$ through $A_n$."

Key components of the method include:

  • One-to-One Mapping: Every ground atom in the logic program (e.g., height(john)) is treated as a unique random variable.
  • Separation of Concerns: The logic defines the qualitative structure (the dependency graph), while associated Conditional Probability Distributions (CPDs) define the quantitative relationships.
  • Combining Rules: Since multiple clauses might have the same head (e.g., a child inherits traits from both a mother and a father), BLPs use "combining rules" (like noisy-or or max) to merge these influences into a single conditional distribution.
  • Knowledge-Based Model Construction (KBMC): To answer a query, the system doesn't build a global network. Instead, it uses a backward-chaining procedure (similar to Prolog's SLD-resolution) to construct a "support network"—a minimal Bayesian network containing only the variables relevant to that specific query.

Datasets

As a foundational theoretical paper, it does not evaluate against large-scale public benchmarks. Instead, it uses several illustrative domains to prove representational power:

  • Quantitative Genetics: A running example modeling the inheritance of height (a continuous variable) across generations using Gaussian distributions.
  • Burglary Alarm: A translation of Judea Pearl’s classic BN example into the BLP framework.
  • Recursive Logic: Examples involving structured terms (like even(s(X))) to demonstrate how BLPs handle infinite domains and recursion.

Key Insights and Ideas

  • The "Secret Sauce" is the Atom: By viewing ground atoms as random variables rather than just boolean states, BLPs can naturally handle continuous domains and complex data structures (functors) that earlier probabilistic logics could not.
  • Generalization Power: The authors show that BLPs are a true superset of both Bayesian networks and "pure" Prolog. If you have only facts, it's a BN; if your probabilities are deterministic (1.0 or 0.0), it's a standard logic program.
  • Handling the Infinite: Even if a logic program implies an infinite number of possible random variables (due to recursion), the query-answering procedure remains finite and computable as long as the "support network" for the specific query is finite.
  • Efficiency through Logic: By using logical proofs to find dependencies, BLPs can be exponentially more efficient than previous frameworks that tried to build proof trees for every possible state of a variable.

Key Results

  • Declarative Semantics: The paper provides a formal proof that any "well-defined" BLP specifies a unique probability measure over its least Herbrand model.
  • Representational Flexibility: The authors demonstrate that BLPs can elegantly represent Hidden Markov Models (HMMs) and Dynamic Bayesian Networks (DBNs) by using logical variables to represent time steps.
  • Implementation: The authors provide a rudimentary interpreter (BLoP) written in Prolog that generates Hugin-compatible network files, proving the practical feasibility of the approach.

Limitations and Future Work

  • Learning: The current paper focuses on representation and inference. The authors acknowledge that learning both the structure (via Inductive Logic Programming) and the parameters (CPDs) of BLPs is the next major hurdle.
  • Negation: The framework currently focuses on definite clauses. Handling "negation as failure" (a staple of modern Prolog) in a probabilistic context remains a complex open challenge.
  • Scaling Inference: While the support network approach is efficient, performing exact inference on very large, highly connected relational models still faces the standard NP-hard challenges of Bayesian networks. Future work is needed on approximate inference techniques (like MCMC) tailored for BLPs.

Summary updated

Abstract

Bayesian networks provide an elegant formalism for representing and reasoning about uncertainty using probability theory. Theyare a probabilistic extension of propositional logic and, hence, inherit some of the limitations of propositional logic, such as the difficulties to represent objects and relations. We introduce a generalization of Bayesian networks, called Bayesian logic programs, to overcome these limitations. In order to represent objects and relations it combines Bayesian networks with definite clause logic by establishing a one-to-one mapping between ground atoms and random variables. We show that Bayesian logic programs combine the advantages of both definite clause logic and Bayesian networks. This includes the separation of quantitative and qualitative aspects of the model. Furthermore, Bayesian logic programs generalize both Bayesian networks as well as logic programs. So, many ideas developed
BibTeX
@inproceedings{kersting2001bayesian,
  author = {Kristian Kersting and Luc De Raedt},
  title = {{Bayesian Logic Programs}},
  booktitle = {Lirias},
  year = {2001},
  doi = {10.48550/arxiv.cs/0111058},
}

Loading related content...

Figure