Abstract
We present a novel approach to probabilistic logic programming that incorporates inheritance with overriding. This framework is based on new notions of entailment for reasoning with conditional constraints, derived from classical logical entailment by adding the principle of inheritance with overriding. By utilizing recent advancements in probabilistic default reasoning, specifically $z$-entailment and $lex$-entailment, we analyze the semantic properties of these new relations. We also provide algorithms for their implementation and demonstrate that the added expressive power does not increase the computational complexity compared to standard probabilistic logic.
Introduction
Integrating formal logic with probability is a fundamental challenge in artificial intelligence. While classical "logical entailment" (0-entailment) provides a rigorous foundation, it is often too weak to infer meaningful conclusions from a set of probabilistic rules. Common alternatives, such as the principle of maximum entropy or Bayesian networks, have their own drawbacks: maximum entropy can collapse uncertainty into a single distribution, while Bayesian networks require rigid acyclic structures and precise probabilities.
A significant hurdle in pure probabilistic logic is the inheritance problem. Standard entailment fails to allow a subclass to inherit traits from a superclass. Stronger versions, like 1-entailment, allow inheritance but fail when conflicts arise. For instance, if birds generally fly (90-95%) but penguins do not (0-5%), 1-entailment results in an inconsistent model for penguins because it attempts to satisfy both conflicting rules. This paper addresses this by formalizing inheritance with overriding, allowing more specific reference classes to take precedence.
Methodology
The proposed framework treats probabilistic logic programs as probabilistic default theories. Knowledge is partitioned into strict conditional constraints and defeasible constraints (defaults). To resolve conflicts, the paper adapts two semantics from nonmonotonic reasoning:
- $z$-entailment: Based on Pearl’s System Z, this method ranks default rules by specificity. When conflicts occur, the logic prefers the most specific applicable rules.
- $lex$-entailment: A lexicographic refinement of $z$-entailment that offers more robust reasoning by considering the number of rules satisfied at each level of specificity.
The author introduces algorithms such as z-partition, tight-z-consequence, and tight-lex-consequence to compute probability bounds by reducing the problem to standard probabilistic satisfiability checks.
Key Insights
A central theme of the work is the connection between Reichenbach’s "reference-class reasoning" (the principle of using the narrowest applicable class for statistics) and the concept of inheritance with overriding in Object-Oriented Programming.
Furthermore, the proposed entailment relations are mathematically grounded, satisfying formal postulates for nonmonotonic reasoning, including Cautious Monotonicity, Rational Monotonicity, and Irrelevance. This ensures that the logic behaves predictably and rationally in the face of new information.
Complexity and Results
A major contribution of this research is the proof that adding overriding mechanisms does not increase computational complexity. In the propositional case, determining the consistency of a probabilistic logic program remains NP-complete.
For query processing, computing the tightest possible probability interval (Tight S-Consequence) is $F\Delta_2^P$-complete for both $z$-entailment and $lex$-entailment. This complexity holds for both general and 1-conjunctive cases, matching the performance of older, less expressive systems.
Conclusion and Future Work
This work establishes a robust framework for probabilistic logic programming that handles inheritance and overriding gracefully. While the current complexity analysis is limited to the propositional case, extending these results to full first-order logic remains a challenge. Future work will also explore the relationship between this framework and the maximum entropy principle, which also exhibits forms of inheritance with overriding.
Summary updated