TL;DR
This paper introduces a novel approach to default reasoning using belief functions, a framework for handling uncertainty. By defining "epsilon-belief functions" with extreme values (close to 0 or 1), the authors develop a system that addresses long-standing issues in default reasoning, such as specificity, inheritance blocking, and ambiguity, offering a more robust way to draw plausible conclusions from incomplete information.
What Problem Does This Paper Address?
In artificial intelligence, "default reasoning" is about making plausible conclusions from incomplete knowledge. Imagine knowing that "birds fly" but also that "penguins don't fly." If you also know "penguins are birds," you'd want to conclude that penguins don't fly, not that they do. This requires a system that can handle exceptions and prioritize more specific information over general rules.
The field has grappled with several desirable properties for such reasoning systems:
- Rationality: Conclusions should follow logical rules.
- Specificity: Specific rules (like "penguins don't fly") should override general ones ("birds fly").
- Property Inheritance: Objects should inherit properties from their superclasses unless there's a conflict (e.g., if birds have legs, penguins should too, unless explicitly stated otherwise).
- Ambiguity Preservation: If there are conflicting arguments for and against a conclusion, the system should remain undecided (like the "Nixon diamond" problem: Nixon is a Quaker and a Republican, but we shouldn't definitively say he is or isn't a pacifist).
- Syntax Independence: The reasoning shouldn't change based on how the rules are written (e.g., avoiding redundancy issues).
While various approaches exist (probabilistic, possibilistic), none have perfectly captured all these desiderata. This paper aims to bridge this gap by leveraging belief functions.
Methods
The core of the paper's contribution lies in its novel use of belief functions to model default reasoning. Instead of standard probability or possibility distributions, they introduce epsilon-belief functions. These are special belief functions where the "mass" assigned to different possibilities is either very close to 0 or very close to 1 (represented by infinitesimals).
They define three consequence relations based on these epsilon-belief functions:
- bf-consequence: This is a direct adaptation of the definition of logical entailment using epsilon-belief functions. It turns out to be equivalent to existing systems like System P and Adams' epsilon-semantics, which, while rational, struggle with issues like irrelevance and inheritance blocking.
- lc-consequence (Least Commitment): This relation is derived by focusing on a specific subset of epsilon-belief functions that are "least committed" – meaning they spread belief as little as possible while still satisfying the defaults. This approach is shown to be equivalent to Pearl's System Z, which handles specificity better but can still have issues.
- lcd-consequence (Least Commitment plus Dempster's Rule): This is the most sophisticated relation. It combines the least commitment principle with Dempster's rule of combination, a standard way to merge information from multiple independent sources. Each default rule is treated as an independent piece of evidence, and their combined effect is modeled. This approach is designed to be more "bold" and to address the remaining problems.
Datasets
Not discussed in the paper. The paper focuses on theoretical formalisms and uses example knowledge bases to illustrate its points, rather than relying on empirical datasets.
Key Insights and Ideas
- Extreme Beliefs for Defaults: Using belief assignments that are either near 0 or near 1 for default rules is a clever way to encode "generally" or "almost always" without resorting to precise probabilities. This captures the essence of exceptions.
- Dempster's Rule as Source Combination: Treating each default rule as an independent source of information and combining them with Dempster's rule provides a principled way to aggregate evidence, especially when dealing with multiple, potentially conflicting, defaults.
- LCD Solves Key Problems: The LCD consequence relation is shown to effectively tackle issues like irrelevance (e.g., a red bird flying) and inheritance blocking (e.g., penguins having legs) where other systems falter.
- Unified Framework: The paper suggests that belief functions can provide a unifying framework for understanding various existing default reasoning systems (System P, System Z, penalty logic, lexicographic approaches, preferred sub-theories).
Key Results
- The
bf-consequence relation is equivalent to System P and Adams' epsilon-semantics. - The
lc-consequence relation is equivalent to Pearl's System Z. - The
lcd-consequence relation is shown to be strictly stronger than System P and to correctly address problems of irrelevance, inheritance blocking, ambiguity, and redundancy, as demonstrated through several examples. - The paper presents theorems showing the relationships between these new relations and existing ones, highlighting that
lcdis incomparable with System Z but strictly stronger than System P.
Limitations and Future Work
- Rational Monotonicity: The authors acknowledge that LCD does not satisfy "rational monotonicity," a property related to how conclusions should behave when new information is added. They are actively researching different rules to characterize LCD-consequence more precisely.
- Independence Assumption: LCD relies on the assumption that default rules (treated as sources) are independent. The authors plan to explore variants of LCD that relax this assumption, which could lead to different reasoning behaviors.
- Intuitive Acceptability: While LCD addresses many desiderata, one example (Example 8) suggests that in certain ambiguity cases, LCD might still produce results whose intuitive acceptability is questionable, possibly due to the strong assumption of independence.
- Computational Complexity: While not explicitly detailed, the complexity of computing these relations, especially with Dempster's rule, would be a practical consideration for future work.
Summary updated