Theorem Proving Under Uncertainty - A Possibility Theory-based Approach

TL;DR

This paper extends classical theorem proving (specifically, the resolution principle) to handle uncertain propositions using possibility and necessity measures. It introduces a refutation method that finds the most certain proof for a given proposition, offering a more nuanced way to reason with incomplete knowledge than traditional binary logic.

What Problem Does This Paper Address?

Automated reasoning systems, like those used in logic programming, typically operate on crisp, certain facts. However, real-world knowledge is often uncertain. This paper addresses the challenge of extending these powerful reasoning mechanisms to handle propositions whose truth value isn't definitively known, but rather has a degree of possibility or necessity. Unlike fuzzy logic, which deals with vague predicates (e.g., "John is young"), this work focuses on uncertain propositions that are either true or false in reality, but our knowledge about them is incomplete. The authors aim to quantify this uncertainty using possibility and necessity measures, which are shown to be more expressive than probability measures for distinguishing between lack of certainty and certainty of falsehood.

Methods

The core of the paper is an extension of the resolution principle to clauses weighted by necessity measures.

  • Possibility and Necessity Measures: The authors adopt Zadeh's possibility theory, defining possibility ($\Pi$) and necessity ($N$) measures. $N(p)$ quantifies the degree to which a proposition $p$ can be considered necessarily true, while $\Pi(p)$ quantifies the degree to which it is possible for $p$ to be true. Crucially, $N(p) = 1 - \Pi(\neg p)$. These measures satisfy specific axioms, including $N(p \wedge q) = \min(N(p), N(q))$ and $\Pi(p \vee q) = \max(\Pi(p), \Pi(q))$.
  • Extended Resolution Principle: The standard resolution rule, which combines clauses like $p \vee q$ and $\neg p \vee r$ to derive $q \vee r$, is extended. For uncertain clauses, if $N(p \vee q) \ge \alpha$ and $N(\neg p \vee r) \ge \beta$, then the resolvent $q \vee r$ has a necessity measure of at least $\min(\alpha, \beta)$. This "min" combination is a key difference from probabilistic approaches, which use a "max(0, $\alpha + \beta - 1$)" rule and can lead to less informative lower bounds.
  • Refutation Method: The paper adapts the refutation method, where a proposition to be proven is assumed false (negated with necessity 1), and the goal is to derive the empty clause (contradiction). The necessity measure of the empty clause derived through this process provides a lower bound for the necessity measure of the original proposition.
  • Linear Strategy with Ordered Search: To find the optimal refutation (one that yields the greatest possible lower bound for the necessity measure), the authors propose a linear resolution strategy combined with an ordered search method. This is analogous to a heuristic search algorithm (like A*) but adapted for possibility theory, using the "min" operation for combining costs. The goal is to find a path to the empty clause with the maximum possible necessity measure.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and uses a small, illustrative example.

Key Insights and Ideas

  • Necessity vs. Possibility: The framework elegantly distinguishes between a proposition being possibly true but not necessarily so ($N(p)=0, \Pi(p)>0$) and a proposition being certainly false ($N(p)=0, \Pi(p)=0$). This is a significant advantage over probability theory where $P(p)=0$ implies $P(\neg p)=1$.
  • "Min" Combination Rule: The use of the "min" operator for combining necessity measures in resolution is crucial. It ensures that the certainty of a derived conclusion is bounded by the least certain premise, preserving information more effectively than probabilistic approaches in certain scenarios.
  • Optimal Refutation: The paper demonstrates that finding the "best" proof (the one with the highest certainty) is achievable through a structured search strategy, rather than just finding any proof. This is vital for practical applications where the confidence in a conclusion matters.
  • Consistency in Uncertainty: The paper touches upon how to define and handle inconsistency in uncertain knowledge bases, suggesting that a subset of clauses with sufficiently high necessity measures can still form a consistent knowledge base.

Key Results

  • The paper formally extends the resolution principle to handle clauses weighted by necessity measures, establishing the rule: if $N(p \vee q) \ge \alpha$ and $N(\neg p \vee r) \ge \beta$, then $N(q \vee r) \ge \min(\alpha, \beta)$.
  • It proves that the necessity measure of the empty clause derived via refutation provides a lower bound for the necessity measure of the proposition being evaluated.
  • A linear resolution strategy with an ordered search method is proposed to find an optimal refutation, guaranteeing the greatest possible lower bound for the necessity measure.
  • An illustrative example is provided, demonstrating how the method can be applied to a small knowledge base and yielding a specific necessity degree for a conclusion.

Limitations and Future Work

  • Inconsistent Knowledge Bases: The paper acknowledges that real-world knowledge bases can be inconsistent. While it proposes a way to define the degree of inconsistency, further research is needed to effectively handle and reason with such bases.
  • Completeness: The completeness of the extended resolution principle for possibility theory is mentioned as a topic for further research.
  • Vague Predicates: The current framework focuses on uncertain propositions. Extending it to accommodate vague predicates (fuzzy logic) is identified as a significant area for future work, potentially by approximating fuzzy statements with collections of weighted, non-vague statements.
  • Elicitation of Weights: While the paper notes that weights have an "ordinal value" and are combined by the "min" operation, the practical aspect of eliciting these necessity measures from human experts remains a challenge.

Summary updated

BibTeX
@inproceedings{1987theorem,
  title = {{Theorem Proving Under Uncertainty - A Possibility Theory-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure