Probabilistic Disjunctive Logic Programming

Liem NgoUAI 1996

TL;DR

This paper introduces a novel framework for Probabilistic Disjunctive Logic Programming (PDLP) that combines the expressive power of disjunctive logic programming with probabilistic reasoning. It addresses the challenge of quantifying uncertainty in logic programs by extending Poole's probabilistic abduction and using the principle of indifference to derive default probabilities from minimal models, offering a way to handle partial probabilistic information.

What Problem Does This Paper Address?

Traditional disjunctive logic programming (DLP) allows for representing uncertainty through disjunctions (e.g., "A or B is true"). However, it doesn't provide a mechanism to assign likelihoods or preferences to these disjunctive possibilities or to the resulting possible states of the world (represented by minimal models). On the other hand, quantitative logic programming approaches exist, but they often require complete probability distributions, which are difficult to obtain in practice. This paper bridges this gap by proposing a framework that integrates probabilistic information into DLP, allowing for reasoning with partial probabilities and deriving default probabilities when information is incomplete. This is particularly useful for tasks like abductive reasoning in diagnosis, where understanding the likelihood of different explanations is crucial.

Methods

The core of the proposed framework lies in extending Poole's Probabilistic Horn Abduction. Key methodological contributions include:

  • Hypothesis-based Probability Specification: Probabilistic information is encoded through "disjoint declarations" of hypotheses. These declarations specify probabilities for mutually exclusive and exhaustive ground atoms (hypotheses). For example, disjoint(hasDoc: 0.2, noDoc: 0.8) means there's a 20% chance of hasDoc being true and 80% chance of noDoc being true.
  • Principle of Indifference for Default Probabilities: When probabilistic information is not fully specified, the paper leverages the principle of indifference. This principle is applied to the set of minimal models of a program. If a set of minimal models is associated with a specific hypothesis base, and that set is finite, the principle of indifference is used to assign equal probability to each model within that set.
  • Full and Partial Explanations: To handle uncertainty, the paper defines "f-explanations" (full explanations) and "p-explanations" (partial explanations). An f-explanation is a set of hypotheses that guarantees a formula is true in all minimal models derived from those hypotheses. A p-explanation is a set of hypotheses where a formula is true in some but not all minimal models. This distinction is crucial for calculating probabilities.
  • Probabilistic Semantics: A probabilistic semantics is defined that extends the minimal model semantics of DLP and the possible world semantics of probabilistic logics. This semantics assigns probabilities to ground formulas by considering both f-explanations (for fully determined probabilities) and p-explanations (for deriving default probabilities using the principle of indifference).
  • Bottom-Up Procedure: A procedure is presented to construct a "complete hypothetical model forest" for a probabilistic disjunctive deductive database (PDDB). This forest represents the semantics of the PDDB and is used to compute the default probability of ground formulas.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and illustrates its concepts with examples derived from hypothetical scenarios.

Key Insights and Ideas

  • Bridging Disjunction and Probability: The paper successfully integrates the "either/or" nature of disjunctive logic programming with the "how likely" aspect of probabilistic reasoning, creating a more expressive and practical logic programming paradigm.
  • Handling Incomplete Probabilistic Information: The use of the principle of indifference to derive default probabilities from minimal models is a key insight, allowing for reasoning even when precise probabilities are unknown. This is a significant advantage over methods requiring complete probability distributions.
  • Formalizing Explanations for Uncertainty: The distinction between full and partial explanations provides a structured way to analyze how hypotheses influence the truth of formulas and to quantify uncertainty based on these explanations.
  • Minimal Models as a Probabilistic Sample Space: The paper elegantly uses the set of minimal models, a standard concept in DLP, as the foundation for a probabilistic sample space, grounding the probabilistic semantics in established logic programming theory.

Key Results

The paper proposes a framework and defines semantics for Probabilistic Disjunctive Logic Programming. It introduces:

  • A formal definition of a probabilistic disjunctive logic program (PDLP).
  • A probabilistic semantics that extends minimal model semantics and possible world semantics.
  • Concepts of full and partial explanations for ground formulas.
  • A method for calculating default probabilities of ground formulas, particularly for "finitely defined" formulas.
  • A bottom-up procedure for constructing a complete hypothetical model forest for PDDBs, which can be used to compute probabilities.

While the paper doesn't present extensive empirical results with quantitative metrics on large datasets, it demonstrates the framework's applicability through illustrative examples (e.g., Example 3 and Example 7).

Limitations and Future Work

The authors acknowledge several limitations and outline promising avenues for future research:

  • Focus on Positive DLP: The initial attempt is confined to positive disjunctive logic programs. Extending the framework to handle negation and other complex logical constructs is a natural next step.
  • Efficiency of Bottom-Up Procedure: The presented bottom-up procedure for constructing the hypothetical model forest can be inefficient as it might require generating all minimal models. The authors suggest developing more efficient, top-down procedures that determine relevant hypothesis sets and only generate necessary portions of the model forest.
  • Interval Probabilities: The current framework primarily deals with point-valued probabilities. Extending it to handle interval probabilities would further enhance its expressiveness and ability to represent uncertainty.
  • Non-finite P-Explanations: The current approach is limited to scenarios where p-explanations lead to a finite number of minimal models for applying the principle of indifference. Relaxing this constraint to handle non-finite p-explanations, as long as bounds on probabilities can be determined, is a significant area for future work.
  • Syntactic Criteria for Query Answering: The authors conjecture that syntactic criteria might exist to answer queries using only local portions of the program, which could lead to more efficient inference.

Summary updated

BibTeX
@inproceedings{ngo1996probabilistic,
  author = {Liem Ngo},
  title = {{Probabilistic Disjunctive Logic Programming}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1996},
}
Figure