TL;DR
This paper reframes syntax-based default reasoning as a model-based diagnosis problem, treating each piece of information as a component that can "fail" with a small probability. This probabilistic perspective allows for a principled way to define various nonmonotonic consequence relations, unifying existing approaches and introducing new ones.
What Problem Does This Paper Address?
Traditional syntax-based approaches to default reasoning and inconsistency handling often select "preferred" subsets of a knowledge base (KB) when it becomes inconsistent. These subsets are then used to derive conclusions. However, these methods can be sensitive to the exact syntactic representation of the KB, leading to different conclusions for semantically equivalent KBs. This paper aims to bridge this gap by providing a probabilistic foundation for these syntax-based approaches, drawing parallels with model-based diagnosis. The core problem is to find a robust and principled way to define nonmonotonic consequence relations that are less susceptible to syntactic variations and can be interpreted probabilistically.
Methods
The authors propose viewing each piece of information (a formula) in a knowledge base as a component in a diagnosis system. These components are assumed to be independent and have a very small, equal probability of "failing" (i.e., being rejected). This is formalized using the ATMS (Assumption-based Truth Maintenance System) framework, where each assumption corresponds to a piece of information.
Key methodological steps include:
- Probabilistic Model: Assigning an infinitesimal probability of fault ($\epsilon$) to each assumption, assuming independence. This induces a probability distribution over "environments" (sets of assumptions that are true).
- Dempster-Shafer Belief Function: Using this probability distribution to define a Dempster-Shafer belief function. This function quantifies the probability that a given formula can be deduced from the KB, effectively measuring its "provability."
- Consequence Relations: Deriving various nonmonotonic consequence relations from this belief function. These relations are defined based on thresholds of belief, existential provability, and majority voting over scenarios.
The novelty lies in the probabilistic interpretation of syntax-based reasoning and the systematic derivation of consequence relations from this probabilistic framework, connecting it to established concepts in diagnosis and belief functions.
Datasets
Not discussed in the paper. The paper uses a theoretical framework and an illustrative example, not empirical datasets.
Key Insights and Ideas
- Diagnosis as Default Reasoning: The core insight is that syntax-based default reasoning can be elegantly modeled as a model-based diagnosis problem. Each piece of information is a component, and inconsistency arises from "faulty" components (rejected information).
- Probabilistic Foundation for Syntax-Based Reasoning: By assigning infinitesimal probabilities of fault to information sources, the paper provides a principled probabilistic interpretation for syntax-based approaches, addressing their sensitivity to syntax.
- Belief Function as Provability: The Dempster-Shafer belief function derived from the probabilistic model serves as a measure of "provability" from the KB, offering a quantitative way to assess the strength of conclusions.
- Unified Framework for Consequence Relations: The paper demonstrates how a variety of existing syntax-based consequence relations can be recovered and reinterpreted within this probabilistic framework, and also introduces new ones. This suggests a spectrum of nonmonotonic reasoning behaviors, from very cautious to more adventurous.
- Parsimony Principle: The probabilistic approach naturally favors "maximal cardinality" consistent environments (analogous to minimal fault sets in diagnosis), aligning with the principle of parsimony.
Key Results
- Proposition 1: Shows that only environments of maximal cardinality have a non-zero probability as $\epsilon \to 0$.
- Proposition 3 & 14: Establishes that the belief function Bel$_K(\psi) = 1$ if and only if $\psi$ is a logical consequence of the hard facts ($F \models \psi$). This defines a very strong, monotonic consequence relation.
- Proposition 6: Defines a "strong" consequence relation ($\models_1$) where $K \models_1 \psi$ if and only if $\psi$ is entailed by all maximal scenarios.
- Proposition 8: Defines a "weak" consequence relation ($\models_4$) where $K \models_4 \psi$ if and only if $\psi$ is entailed by at least one scenario. This corresponds to provability in at least one extension of a normal default theory.
- Proposition 10: Defines a "majority" consequence relation ($\models_6$) where $K \models_6 \psi$ if $\psi$ is provable in the majority of maximal scenarios.
- Figure 1: Illustrates the hierarchical relationship between the various defined consequence relations, showing how some are strictly stronger than others.
Limitations and Future Work
- Prioritized Knowledge Bases: The paper briefly touches upon the extension to prioritized knowledge bases, suggesting that lexicographically preferred subtheories correspond to environments with non-zero probability in the prioritized probabilistic model. This is a promising avenue for future work.
- Computational Complexity: While the paper provides theoretical definitions and characterizations, the algorithmic and implementation aspects of these consequence relations are not deeply explored, though the authors hope that existing work on tractable subclasses and ATMS/diagnosis can be leveraged.
- Non-infinitesimal Probabilities: The definitions of consequence relations still hold for non-infinitesimal probabilities, but the theoretical results and characterizations become less interesting. The focus on infinitesimal probabilities is key to the clean theoretical results.
- "Unsafe" Consequence Relations: The paper notes that some defined consequence relations (like $\models_2$ and $\models_4$) are "unsafe" in the sense of Pinkas and Loui, meaning they might not always satisfy desirable properties. The authors suggest that more cautious relations are generally preferred in practice.
Summary updated