On the Relationship between Probabilistic Logic

IJCAI 1999

TL;DR

This paper bridges the gap between probabilistic logic and $\pi$-CMS systems by reformulating $\pi$-CMS within a probabilistic logic framework. This allows for a more efficient solution to $\pi$-CMS problems, especially when independence assumptions are relaxed, and reveals that $\pi$-CMS with independence assumptions may not fully exploit available information.

What Problem Does This Paper Address?

Expert systems often need to reason under uncertainty. Two prominent approaches are probabilistic logic models and $\pi$-CMS (probabilistic Clause Maintenance Systems). While these families share similarities, $\pi$-CMS typically assumes independence among its assumptions, which can be a strong and sometimes unrealistic constraint. This paper aims to unify these approaches by showing how $\pi$-CMS can be expressed using the more general framework of probabilistic logic, thereby relaxing the independence assumption and potentially leading to more efficient and accurate reasoning. The authors investigate the relationship between these two formalisms and propose new methods for solving $\pi$-CMS problems.

Methods

The core of the paper lies in reformulating $\pi$-CMS problems as Generalized Linear Programming (GLP) problems, specifically using the framework of Probabilistic Satisfiability (PSAT).

  • Probabilistic Logic (PSAT): This approach models uncertainty by assigning probabilities to logical sentences. The goal is to find bounds on the probability of a new sentence given a set of known sentences and their probabilities. This is achieved through a linear programming formulation.
  • $\pi$-CMS: These systems typically compute "support" and "plausibility" for propositions based on assumptions. A key difference is their usual assumption of independence among these assumptions.
  • Reformulation of $\pi$-CMS: The authors propose two formulations for $\pi$-CMS within the PSAT framework:
  • Formulation F1: Directly translates $\pi$-CMS into a PSAT problem. This involves a master problem and a subproblem that is an unconstrained nonlinear program in 0-1 variables.
  • Formulation F2: Exploits the structure of $\pi$-CMS by moving the "justification" constraints (related to clauses) into the subproblem. This results in a master problem with fewer constraints and a subproblem that is a constrained linear program in 0-1 variables.
  • Solution Method: Both formulations are solved using a column generation technique, an iterative process that starts with a basic feasible solution and progressively adds columns (representing possible worlds or assumption combinations) to improve the objective function. Heuristic and exact algorithms are used to solve the subproblems, which involve finding columns with negative reduced costs.

Datasets

The paper does not introduce new datasets. Instead, it uses randomly generated problems for $\pi$-CMS/PSAT to evaluate the performance of their proposed algorithms. These generated problems vary in the number of assumptions, justifications, and variables, with clauses containing up to 4 literals. The probabilities for these problems are derived from feasible worlds.

Key Insights and Ideas

  • Unifying Framework: The paper successfully demonstrates that $\pi$-CMS can be elegantly reformulated as a probabilistic logic problem, providing a common ground for both formalisms.
  • Relaxing Independence: By removing the independence assumption on $\pi$-CMS assumptions, the system can potentially capture more nuanced relationships and provide more accurate probability bounds.
  • Efficient $\pi$-CMS Solution: Formulation F2, which leverages the structure of $\pi$-CMS, offers a significantly more efficient way to solve these problems compared to direct application of probabilistic logic methods.
  • Information Exploitation: When the independence condition is maintained in $\pi$-CMS, the resulting probability intervals can overlap with those from the corresponding probabilistic logic model. This suggests that $\pi$-CMS, under this condition, might not be fully exploiting all available information.

Key Results

  • Speedup: Formulation F2, using column generation, achieved speedups of up to 7000 times compared to applying probabilistic logic methods directly to Formulation F1 on larger instances.
  • Comparison with ABEL: Table 3 shows that $\pi$-CMS with independence conditions (using the ABEL program) can produce probability intervals that overlap with, rather than being strictly contained within, the intervals from the $\pi$-CMS/PSAT model. This highlights a potential limitation of the independence assumption.
  • Algorithm Performance: The paper presents detailed tables (Table 1 and Table 2) comparing the performance of Formulation 1 and Formulation 2 across various problem sizes, showing significant improvements in computation time and the number of columns generated for Formulation 2.

Limitations and Future Work

  • Independence Assumption: The paper notes that when the independence condition is imposed on $\pi$-CMS, solving even smaller instances becomes cumbersome, and the probability intervals may overlap with those from the probabilistic logic model, indicating incomplete information utilization.
  • Future Exploration: The authors suggest that further exploration is needed to understand why $\pi$-CMS with independence conditions doesn't fully exploit available information. They also mention that the efficiency gains of Formulation F2 are particularly pronounced on larger instances, implying that this approach is well-suited for complex real-world problems. The paper also hints at future work exploring the implications of conditioning and conditional independence in probabilistic satisfiability.

Summary updated

BibTeX
@inproceedings{1999relationship,
  title = {{On the Relationship between Probabilistic Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure