The Magic of Logical Inference in Probabilistic Programming

Bernd Gutmann, Ingo Thon, Angelika Kimmig, Maurice Bruynooghe, Luc De Raedt

Abstract

Today, many different probabilistic programming languages exist and even more inference mechanisms for these languages. Still, most logic programming based languages use backward reasoning based on SLD resolution for inference. While these methods are typically computationally efficient, they often can neither handle infinite and/or continuous distributions, nor evidence. To overcome these limitations, we introduce distributional clauses, a variation and extension of Sato's distribution semantics. We also contribute a novel approximate inference method that integrates forward reasoning with importance sampling, a well-known technique for probabilistic inference. To achieve efficiency, we integrate two logic programming techniques to direct forward sampling. Magic sets are used to focus on relevant parts of the program, while the integration of backward reasoning allows one to identify and avoid regions of the sample space that are inconsistent with the evidence.

Introduction

Probabilistic Logic Programming (PLP) represents a powerful synthesis of relational logic—capable of structured reasoning—and probability theory, which manages uncertainty. Despite the promise of frameworks like ProbLog or PRISM, traditional PLP has historically faced two significant hurdles: the integration of continuous distributions and the "evidence bottleneck."

Most existing systems are optimized for discrete, Boolean facts. When faced with continuous variables (such as sensor data) or complex generative models with an unknown number of objects, these systems often falter. Furthermore, when evidence is introduced, standard generative sampling becomes highly inefficient; if only a tiny fraction of sampled worlds match the known evidence, the computational waste is immense. This paper introduces distributional clauses and a hybrid inference engine designed to bridge the gap between forward-driven generation and backward-driven logical focus.

Distributional Clauses

The authors extend Sato’s distribution semantics through the introduction of distributional clauses. A clause defined as h ~ D :- b1, ..., bn signifies that if the logical conditions b are satisfied, the random variable h is drawn from the distribution D. This formalism allows the program to represent both continuous values and an open-world assumption where the number of objects is not fixed a priori. By defining distributions conditional on logical predicates, the system can reason about potentially infinite Herbrand models while remaining computationally tractable through sampling.

A Hybrid Inference Methodology

To solve the efficiency issues inherent in sampling, the paper proposes a "best of both worlds" approach that combines forward and backward reasoning:

  1. Probabilistic Magic Sets: Borrowed from the field of deductive databases, this transformation rewrites the program so that forward reasoning only "activates" rules relevant to the specific query or evidence. This ensures that the sampler does not waste resources on irrelevant parts of the state space.
  2. Heuristic Lookahead (Backward Reasoning): The system employs a depth-bounded meta-interpreter to look ahead during the sampling process. If a partial sample is found to be logically inconsistent with the evidence, the system prunes that branch immediately. This "logic as a filter" approach prevents the engine from completing samples that are destined for rejection.
  3. Likelihood Weighting: Rather than relying on simple rejection sampling, the framework utilizes importance sampling. Each sample is assigned a weight based on its consistency with the evidence, allowing for more accurate probability estimates with fewer total samples.

Experimental Evaluation

The system was evaluated using synthetic benchmarks, including an Urn Model (involving a Poisson-distributed number of balls and noisy observations) and standard BLOG (Bayesian Logic) benchmarks.

Key results from these experiments include:

  • Acceptance Rates: The lookahead heuristic proved highly effective. As the depth of the logical check increased, the acceptance rate of samples reached 100% for specific queries, effectively eliminating wasted computation.
  • Variance Reduction: Likelihood weighting significantly outperformed simple rejection sampling, providing lower standard deviation in estimates.
  • Scalability: The system successfully handled scenarios involving Poisson distributions and large object counts where exact inference engines like PRISM typically encounter memory exhaustion.

Limitations and Future Directions

While the current framework excels at handling discrete evidence, it faces challenges with evidence on continuous variables (e.g., "the temperature is exactly 22.5 degrees"), where the probability of a sample matching the evidence is zero. Additionally, the performance of the system is sensitive to the Depth parameter of the lookahead heuristic; a depth that is too low misses pruning opportunities, while a depth that is too high introduces excessive overhead. Future work will focus on optimizing sampling speed through advanced program analysis and the memoization of logical proofs to further reduce redundant computation.

Summary updated

Abstract

Today, many different probabilistic programming languages exist and even more inference mechanisms for these languages. Still, most logic programming based languages use backward reasoning based on SLD resolution for inference. While these methods are typically computationally efficient, they often can neither handle infinite and/or continuous distributions, nor evidence. To overcome these limitations, we introduce distributional clauses, a variation and extension of Sato's distribution semantics. We also contribute a novel approximate inference method that integrates forward reasoning with importance sampling, a well-known technique for probabilistic inference. To achieve efficiency, we integrate two logic programming techniques to direct forward sampling. Magic sets are used to focus on relevant parts of the program, while the integration of backward reasoning allows one to identify and avoid regions of the sample space that are inconsistent with the evidence.
BibTeX
@inproceedings{gutmann2011magic,
  author = {Bernd Gutmann and Ingo Thon and Angelika Kimmig and Maurice Bruynooghe and Luc De Raedt},
  title = {{The Magic of Logical Inference in Probabilistic Programming}},
  booktitle = {Theory Pract. Log. Program},
  year = {2011},
  url = {https://openreview.net/forum?id=EfbCTklUCOR},
}
Figure