Exceptional Subclasses in Qualitative Probability

Sek-Wah TanUAI 1994

TL;DR

This paper extends the System Z+ default reasoning framework to handle "exceptional subclasses" by introducing "cp-conditions." This allows for more nuanced inheritance of properties, ensuring that, for example, penguins can still be considered to have wings even though they are an exception to the rule that birds fly. The authors demonstrate that this extension doesn't compromise the tractability or consistency of the original system.

What Problem Does This Paper Address?

Default reasoning systems aim to capture common-sense reasoning, where we make assumptions about the world that can be overridden by specific exceptions. System Z+ is a qualitative probability framework for default reasoning that uses "normality defaults" of the form "typically if then $\psi$ (with strength $\delta$)." A key limitation of System Z+ is its inability to handle situations where an entity is an exception to one default but should still inherit other properties associated with the general rule.

Consider the classic example: "Typically, birds fly" and "Penguins are birds." System Z+ can infer that penguins fly. However, if we add "Penguins typically do not fly," System Z+ struggles. While it correctly concludes penguins don't fly, it also treats penguins as "exceptional birds" in a way that prevents them from inheriting other typical bird properties, such as having wings. This is problematic because we intuitively believe penguins do have wings. The paper addresses this gap by proposing a way to allow such inheritance of properties even in the presence of exceptions.

Methods

The paper introduces "cp-conditions" (ceteris paribus conditions) to refine System Z+. These conditions are binary relations between worlds (models of the defaults) that capture preferences when worlds agree on all but a specific set of defaults. Specifically, if two worlds agree on all defaults except for a set $\Delta'$, where one world verifies all defaults in $\Delta'$ and the other falsifies them, a cp-condition is established.

The authors then define "cp-admissibility" for belief rankings, which requires a ranking to be admissible in the Z+ sense and satisfy these new cp-conditions. A key theoretical contribution is proving that "cp-consistency" (the existence of a cp-admissible ranking) is equivalent to the original "consistency" of System Z+. This is crucial because it means the existing, semi-tractable algorithm for checking Z+ consistency can also be used to check cp-consistency. They also introduce a "minimal ranking" that embodies maximal ignorance under these new constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and uses illustrative examples rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Handling Exceptional Subclasses: The core insight is that exceptions to one default shouldn't necessarily invalidate inheritance of other properties. Cp-conditions provide a mechanism to enforce this nuanced reasoning.
  • Ceteris Paribus Preference: The cp-conditions formalize a "all else being equal" preference between worlds, which is fundamental to common-sense reasoning.
  • Tractability Preserved: A significant finding is that the proposed extension, while more expressive, does not increase the computational complexity of consistency checking. This is a major practical advantage.
  • Global vs. Local View: The paper contrasts its "global" view of placing constraints between worlds (when they agree on most defaults) with more "local" approaches that might focus on individual defaults.

Key Results

  • Cp-conditions: A formal definition of cp-conditions is provided, capturing preferences between worlds that agree on all but a specific set of defaults.
  • Cp-Admissibility and Cp-Consistency: These new notions are defined, and it's shown that cp-admissibility is closed under minimization.
  • Consistency Equivalence: The paper proves that a set of defaults is cp-consistent if and only if it is consistent in the original System Z+. This is a critical theoretical result.
  • Illustrative Examples: The paper demonstrates with the "penguin" example how the new framework allows penguins to inherit properties like having wings, despite being an exception to the rule that birds fly.

Limitations and Future Work

  • Computational Complexity of Ranking: While consistency checking remains tractable, the paper notes that it is "unclear at this point in time" if computing the specific "kappa ranking" (the minimal cp-admissible ranking) is computationally more complex than computing the K+ ranking. They do not provide a procedure for computing this ranking.
  • Comparison with Other Systems: The paper briefly compares its approach to Boutilier's system and Geffner's conditional entailment, highlighting differences in how specificity and exceptions are handled. However, a more comprehensive evaluation of the advantages and disadvantages of their "global" view compared to other systems remains to be fully explored.
  • Further Evaluation: The authors suggest that the advantages and disadvantages of their global view need to be fully evaluated.

Summary updated

BibTeX
@inproceedings{tan1994exceptional,
  author = {Sek-Wah Tan},
  title = {{Exceptional Subclasses in Qualitative Probability}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure