Sequential Thresholds: Context Sensitive Default Extensions

Choh Man TengUAI 1997

TL;DR

This paper proposes "sequential thresholding," a novel probabilistic framework that addresses the limitations of traditional default logic in handling context-dependent reasoning. By making the evolving context explicit, it offers a more intuitive and robust way to manage non-monotonic inferences, bridging the gap between logical and probabilistic approaches.

What Problem Does This Paper Address?

Common sense reasoning often involves making inferences based on incomplete information, where conclusions can be retracted if new evidence emerges. Default logic, a prominent formalism for this, struggles with scenarios where simple, intuitive default rules lead to unintended or multiple possible conclusions. This "qualification problem" arises because default rules are often treated as modular, failing to account for the dynamic and context-dependent nature of reasoning. For instance, the rule "birds typically fly" might be intuitively applied to Tweety, but this intuition changes if we also know Tweety is a penguin. Traditional default logic, without explicit context management, struggles to differentiate these cases. While semi-normal defaults and priority hierarchies offer partial solutions, they can become cumbersome or rely on external mechanisms. This paper aims to provide a more integrated and principled approach to context-sensitive default reasoning.

Methods

The core contribution is the introduction of sequential thresholding, a probabilistic framework that mimics the non-monotonic nature of default logic. Instead of absolute certainty, it uses a probabilistic acceptance criterion: a statement is accepted as true if its probability exceeds a certain threshold (1 - ε). The novelty lies in the sequential application of this threshold. Each accepted statement is then incorporated into the context for evaluating subsequent statements. This means the probability of a statement is re-evaluated based on the newly accepted information, creating an evolving context.

The paper also presents a generic semantic characterization of non-monotonic reasoning using "partition sequences." This abstract framework describes how reasoning progresses by progressively restricting the set of possible worlds. Both default logic and sequential thresholding are shown to be instantiations of this generic model. For default logic, this involves mapping default rules to conditions on possible worlds, and for sequential thresholding, it involves filtering worlds based on probabilistic thresholds.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Context is King: The paper strongly emphasizes that reasoning rules are not modular. Their applicability and intuitive use depend heavily on the surrounding context, which itself evolves as conclusions are drawn.
  • Bridging Logic and Probability: Sequential thresholding offers a compelling way to integrate probabilistic reasoning with the non-monotonic spirit of default logic. It allows for probabilistic "acceptance" of conclusions, which then become part of the reasoning context, much like facts in default logic.
  • Evolving Context as a Solution: By making the context explicit and dynamic, sequential thresholding provides a mechanism to resolve ambiguities that plague traditional default logic. The probability of a statement is evaluated within the current, updated context.
  • A Unified Semantic Framework: The generic "partition sequence" model provides a powerful abstraction for understanding various non-monotonic reasoning systems, highlighting their shared underlying structure of progressively refining possibilities.
  • Evaluating Extensions: Sequential thresholding can be used to assign a "goodness" score to multiple default logic extensions by finding the minimum threshold parameter required for each. This offers a principled way to rank extensions based on their probabilistic robustness within evolving contexts.

Key Results

The paper demonstrates that both normal default logic and sequential thresholding can be characterized by the same generic non-monotonic reasoning process (partition sequences). This similarity allows for a symbiotic relationship:

  • Default Logic Benefits: Sequential thresholding can be used to evaluate the "goodness" of default logic extensions by determining the minimum threshold parameter (ε) required to derive each extension. A smaller ε indicates a more robust or "better" extension.
  • Sequential Thresholding Benefits: Default logic can provide a mechanism for directing the sequential thresholding process by expressing preferences for which formulas to consider next, helping to focus the probabilistic evaluation.

The paper uses a canonical example (Example 3) involving birds, penguins, and flying to illustrate how default logic can lead to multiple extensions, while sequential thresholding, by considering the evolving context (e.g., knowing something is a penguin), can naturally favor one conclusion over another based on probabilistic thresholds.

Limitations and Future Work

  • Generating Threshold Sets: The paper acknowledges that sequential thresholding doesn't specify how the initial set of formulas to be thresholded (T) is generated. It suggests that formalisms like default logic could help direct this process.
  • "Messy Numbers": While sequential thresholding offers a probabilistic approach, the authors note that people are often uncomfortable assigning precise numerical probabilities. However, they argue that the framework's sensitivity to the threshold parameter (ε) makes it more useful for ranking extensions than for precise probabilistic inference.
  • Further Formalization: The authors mention that a more rigorous formalization of the generic non-monotonic partition sequences and their instantiations can be found in Teng (1997).

The future work suggested is the symbiotic integration of these formalisms to leverage the strengths of both default logic (for preference and structure) and sequential thresholding (for context-sensitive probabilistic evaluation).

Summary updated

BibTeX
@inproceedings{teng1997sequential,
  author = {Choh Man Teng},
  title = {{Sequential Thresholds: Context Sensitive Default Extensions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1997},
}
Figure