TL;DR
This paper bridges the gap between symbolic non-monotonic reasoning (like Shoham's preference logic) and numerical uncertainty handling (possibilistic logic). It shows that conditional possibility measures, derived from possibility distributions, naturally capture non-monotonic inference and belief revision, offering a unified framework for handling uncertain and inconsistent knowledge.
What Problem Does This Paper Address?
Artificial Intelligence (AI) systems often need to reason with incomplete, uncertain, or even contradictory information. Traditionally, this has been tackled with purely symbolic methods (like non-monotonic logics) or numerical approaches (like probability theory). While these have been successful, there's a persistent challenge in unifying them and understanding their deep connections. This paper specifically addresses how to reconcile preference-based semantics for non-monotonic reasoning with the numerical framework of possibilistic logic, which uses possibility measures to quantify uncertainty. The authors aim to show that possibilistic logic isn't just another way to handle uncertainty, but a powerful tool that inherently supports non-monotonic inference and belief revision, mirroring symbolic approaches.
Methods
The core of the paper lies in establishing equivalences between different formalisms:
- Possibility Distributions and Preference Relations: The authors start by defining a possibility distribution $\pi$ over interpretations (possible worlds). This distribution assigns a degree of possibility to each interpretation. A strict partial order is then induced on these interpretations based on their possibility values, directly mirroring Shoham's preference relation.
- Conditional Possibility Measures: They introduce a definition for conditional possibility measures, denoted $\Pi(q|p)$, which quantifies the possibility of $q$ given $p$. This definition is derived from the possibility distribution and is shown to satisfy properties analogous to conditional probability, particularly in how it handles conditioning.
- Non-Monotonic Entailment: The paper demonstrates that this conditional possibility measure naturally captures the notion of preferential entailment. Specifically, $p$ preferentially entails $q$ if the conditional possibility $\Pi(q|p)$ is greater than the conditional possibility of its negation, $\Pi(\neg q|p)$. This is equivalent to saying that the most plausible interpretations of $p$ are also interpretations of $q$.
- Possibilistic Logic and Belief Revision: They connect this to possibilistic logic, where formulas are assigned necessity measures (a dual of possibility measures). A knowledge base in possibilistic logic is a set of weighted formulas. The paper shows that semantic entailment in this setting, especially when dealing with partial inconsistency, aligns with non-monotonic inference. Furthermore, they establish a direct link between this non-monotonic inference and belief revision mechanisms, particularly Gärdenfors' epistemic entrenchment.
Datasets
Not discussed in the paper. The paper focuses on theoretical formalisms and uses illustrative examples rather than empirical evaluation on datasets.
Key Insights and Ideas
- Unified Semantics: The paper provides a powerful semantic link between symbolic preference-based non-monotonic logics and numerical possibilistic logic. It shows that the "preference" in non-monotonic reasoning can be directly modeled by the "possibility" assigned to interpretations.
- Conditional Possibility as Non-Monotonic Inference: The definition of conditional possibility measures is shown to satisfy the key axioms of non-monotonic consequence relations (like cut and restricted monotonicity). This means that reasoning with conditional possibilities inherently behaves in a non-monotonic way.
- Belief Revision is Implicit in Possibilistic Logic: A crucial insight is that the way possibilistic logic handles partial inconsistency and performs inference is equivalent to belief revision processes. This is demonstrated by showing that the axioms of epistemic entrenchment (central to belief revision) are mirrored by the axioms of qualitative necessity relations, which are the basis of possibilistic logic.
- Ordinal Nature of Weights: The paper emphasizes that the numerical weights used in possibilistic logic (and other uncertainty formalisms) often have an ordinal meaning, representing relative degrees of certainty or possibility rather than precise probabilities.
Key Results
- Equivalence of Preferential Entailment and Conditional Possibility: The paper formally proves that Shoham's preferential entailment $p \leadsto q$ is equivalent to $\Pi(q|p) > \Pi(\neg q|p)$ under a possibility distribution.
- Conditional Possibility Satisfies Non-Monotonic Axioms: Propositions 2, 3, and 4 demonstrate that conditional possibility measures satisfy the "cut," "restricted monotonicity," and "OR rule" axioms, which are fundamental to well-behaved non-monotonic consequence relations.
- Link to Belief Revision: Proposition 5 establishes a direct equivalence between non-monotonic entailment in possibilistic logic and belief revision operations, specifically showing that $N(q|p) > 0$ (meaning $p$ non-monotonically entails $q$) corresponds to $q$ being in the belief set resulting from revising with $p$.
- Illustrative Example: A detailed example demonstrates how a possibilistic knowledge base can be used to derive conclusions, and how adding new information can lead to a non-monotonic change in conclusions, mirroring belief revision.
Limitations and Future Work
- Focus on Propositional Logic: While the paper uses propositional logic for simplicity, the authors suggest that the framework can be extended to first-order logic.
- Ordinal Interpretation of Weights: The paper highlights that the numerical values are often ordinal. Future work could explore how to better leverage this ordinal nature.
- Connection to Constraint Programming: The authors note a proximity between possibilistic logic and constraint-directed programming, suggesting future research into interpreting necessity-valued clauses as soft constraints.
- Extension to Belief Functions: The paper hints that the close relationships observed might extend to belief functions (Shafer's theory of evidence), which would be a significant generalization.
- Bridging with Conditional Logic: The authors suggest further exploration of the links between their work and conditional logic, particularly Delgrande's logic of typicality.
Summary updated