A Framework for Integration of Logical and Probabilistic Knowledge

Jingsong Wang, Marco ValtortaAAAI 2011 · DOI

Abstract

This paper presents a novel framework for integrating First-Order Logic (FOL) and Bayesian Networks (BNs). By utilizing a "relation search" algorithm, logical knowledge bases are automatically converted into Logical Bayesian Networks (LBNs) and composed with existing Probabilistic Bayesian Networks (PBNs). This approach enables unified reasoning across deterministic and uncertain domains without requiring the adoption of new hybrid modeling languages.

Introduction

For decades, artificial intelligence research has grappled with the challenge of combining the expressive power of logic—which excels at defining rigid rules and relationships—with the ability of Bayesian networks to handle uncertainty. While hybrid formalisms like Markov Logic Networks (MLNs) or Bayesian Logic Programs (BLPs) have been developed, they often impose a steep learning curve, requiring researchers to rewrite existing knowledge into entirely new languages.

Presented at AAAI 2011, this paper addresses the gap for a simple, automated method to fuse "legacy" logical knowledge bases with standard Bayesian networks into a single, functional reasoning engine. The proposed framework treats logic and BNs as modular components linked via an automated translation layer.

Methodology: The Composite Bayesian Network

The core of the framework is a three-step process to create a Composite Bayesian Network (CBN), which serves as the unified reasoning structure.

The workflow for generating a Composite Bayesian Network (CBN) from logical and probabilistic inputs.
  1. Relation Search: An algorithm scans a logical Knowledge Base (KB) to identify formulas related to the variables in a user's probabilistic model. It accounts for both direct and indirect relationships (e.g., if $A$ and $B$ appear in one rule, and $B$ and $C$ in another, $A$ and $C$ are considered related).
  2. Logical Bayesian Network (LBN) Generation: The identified logical rules are translated into a BN structure. In propositional logic, operators are converted into Conditional Probability Tables (CPTs) acting as deterministic gates. For First-Order Logic (FOL), the system performs "grounding" and introduces special nodes to represent quantified formulas.
  3. Composition: The generated LBN is merged with the user’s original Probabilistic Bayesian Network (PBN). This step utilizes ontologies to ensure semantic alignment between logical terms and probabilistic variables.

Key Insights and Ideas

A central philosophy of this work is the "No New Language" approach. By treating logic and BNs as black boxes, the framework avoids the friction of new syntax. A critical technical insight is the use of Deterministic CPTs, where logical truth is represented as a probability of 1.0. By constructing CPTs that mirror truth tables, the Bayesian network can perform exact logical deduction within its probabilistic framework.

Furthermore, the authors provide a formal proof (Theorem 1) demonstrating the framework's correctness: if a logical statement is entailed by the knowledge base, the resulting Bayesian network will correctly assign it a probability of 1 given the evidence.

Results

The paper contributes a concrete, iterative pseudocode for the "Relation Search" algorithm, which efficiently identifies the relevant subset of a knowledge base for a specific query. The resulting unified reasoning engine successfully produces a single CBN capable of handling queries, observations, and assumptions from both logical and probabilistic sources simultaneously. Additionally, the authors demonstrate how to handle FOL complexities, such as Skolemization and grounding, within standard BN constraints.

Limitations and Future Work

While the framework is conceptually robust, it faces challenges in computational scalability. Grounding complex FOL formulas can lead to a "state-space explosion," making the resulting networks difficult to compute efficiently. Currently, the FOL implementation is restricted to function-free domains and requires formulas in Skolem form. As this is a theoretical and algorithmic paper, empirical benchmarks against systems like MLNs remain a primary focus for ongoing research.

Summary updated

BibTeX
@inproceedings{wang2011framework,
  author = {Jingsong Wang and Marco Valtorta},
  title = {{A Framework for Integration of Logical and Probabilistic Knowledge}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.1609/aaai.v25i1.8048},
}
Figure