CHR(PRISM)-based probabilistic logic learning

Jon Sneyers, Wannes Meert, Joost Vennekens, Yoshitaka Kameya, Taisuke Sato

Abstract

CHRiSM (CHance Rules induce Statistical Models) is a novel probabilistic logic programming language that merges the expressive, multi-headed rule system of Constraint Handling Rules (CHR) with the statistical inference capabilities of PRISM. By introducing "chance rules" that support localized probabilities, CHRiSM allows for the construction of complex statistical models that natively support parameter learning via the Expectation-Maximization (EM) algorithm. This paper explores the formal semantics of CHRiSM and demonstrates its utility through various applications, including game theory simulations and Bayesian networks.

Introduction

Integrating logical structure with probabilistic uncertainty has been a long-standing challenge in logic programming. While systems like PRISM successfully extend Prolog with probabilistic predicates, they are often constrained by Prolog's single-headed rule structure. Conversely, Constraint Handling Rules (CHR) offer a high-level language for multiset rewriting and complex constraint solving but are traditionally deterministic. Previous attempts to make CHR probabilistic often lacked "localized meaning," where the probability of a rule firing depended on the entire system state, complicating both reasoning and learning.

CHRiSM addresses these limitations by providing a formalism that is both highly expressive and statistically robust. In CHRiSM, each rule match is treated as an independent "experiment," ensuring that probabilities are localized and mathematically rigorous.

Methods and Operational Semantics

CHRiSM is implemented via a source-to-source transformation into CHR(PRISM). The core of the language is the chance rule, defined by the syntax: P ?? Hk \ Hr <=> G | B where P represents a probability expression. A rule fires with probability P if the constraints in the head (Hk and Hr) are present in the store and the guard G is satisfied.

The system's behavior is governed by a formal state-transition system ($ω_t^{??}$), which tracks the probability of various execution paths.

Operational semantics of CHRiSM showing state-transition rules for Fail, Solve, Introduce, Probabilistic-Choice, and Maybe-Apply.

Key components of this semantics include:

  • Localized Probabilities: Each rule match is treated as a unique experiment using PRISM’s multi-valued random switches.
  • Distribution Semantics: The language induces a probability distribution over final states, specifically addressing "ambiguous" programs where execution order might influence outcomes.
  • PRISM Integration: By compiling to PRISM, CHRiSM inherits support for sampling, probability computation, and EM-learning.

Evaluation and Applications

The authors evaluated CHRiSM through several illustrative models, focusing on the language's expressiveness and learning capabilities.

Rock-Paper-Scissors

A primary example is a Rock-Paper-Scissors simulation used to demonstrate EM-learning. The system observes game outcomes where only the winner is known (partial observation). Despite the hidden nature of the moves, CHRiSM successfully recovers the players' move distributions (e.g., estimating that a player chooses Scissors 71% of the time) using only the final scores of 100 games.

Probability tree for a Rock-Paper-Scissors game simulation, illustrating probabilistic choices and resulting winner states.

Other Applications

  • Random Graphs: CHRiSM can concisely generate Erdős–Rényi or sparse graphs in just a few lines of code.
  • Bayesian Networks: The language can represent standard probabilistic graphical models, such as the classic "Alarm" network, demonstrating its versatility in encoding traditional statistical structures.

Key Insights

A critical realization in the development of CHRiSM was the distinction between confluence (a logical property) and unambiguity (a probabilistic property). While a program may be logically confluent—always reaching the same result—it is considered "ambiguous" if the probability of reaching that result varies based on the execution strategy. CHRiSM's design prioritizes mathematical rigor in its distribution semantics to handle such cases.

Conclusion and Future Work

CHRiSM demonstrates significant expressiveness, capable of modularly encoding other probabilistic logics like CP-logic and LPADs. Its implementation is efficient, with the transformation to CHR(PRISM) occurring in linear time.

However, several areas for improvement remain. The current "explanation search" for complex models can be slow, and there is no general decidable test for program unambiguity. Future work will focus on extending the system to support non-ground terms and exploring structure learning to automatically derive rules from data.

Summary updated

BibTeX
@article{sneyers2010chr,
  author = {Jon Sneyers and Wannes Meert and Joost Vennekens and Yoshitaka Kameya and Taisuke Sato},
  title = {{CHR(PRISM)-based probabilistic logic learning}},
  journal = {Theory Pract. Log. Program.},
  year = {2010},
  doi = {10.1017/s1471068410000207},
}
Figure