Abstract
In classical logic, knowledge is monotonic: once a proposition is proven true, it remains true regardless of subsequent information. However, human reasoning is inherently non-monotonic, requiring the ability to retract conclusions in the face of new evidence or exceptions. This paper presents a framework for non-monotonic reasoning using probability intervals and Dempster’s Rule of Combination. By representing relationships as intervals of confirmation and disconfirmation, the proposed method provides a mathematically rigorous approach to resolving conflicts between general rules and specific exceptions, such as the classic "Tweety the bird" problem.
Introduction
A fundamental challenge in artificial intelligence is the representation of "default" knowledge. We often operate on the assumption that "birds fly," yet we must be prepared to retract this conclusion if we learn that a specific bird is an ostrich or a penguin. Early AI approaches to this problem, such as McCarthy’s circumscription, relied on complex logical predicates to account for "abnormal" cases. Alternatively, systems using single-valued "certainty factors" often failed to distinguish between a lack of evidence (ignorance) and the presence of conflicting evidence.
Ginsberg (1984) addresses these limitations by shifting from single probability values to probability ranges, utilizing the Dempster-Shafer theory of evidence. This approach allows for a more nuanced representation of uncertainty and provides a formal mechanism for evidence combination that naturally handles non-monotonicity.
The Probability Interval Framework
The core of the proposed system is the representation of relationships (or "arcs") in a semantic network as a pair $(c, d)$. Here, $c$ represents the degree to which evidence confirms a proposition, and $d$ represents the degree to which it disconfirms it. This pair defines a probability interval $[c, 1-d]$.
This representation offers several advantages:
- Ignorance vs. Certainty: Total ignorance is represented by $(0, 0)$, resulting in the widest possible interval $[0, 1]$. Absolute certainty is represented by $(1, 0)$, or $[1, 1]$.
- Conflict Representation: A narrow interval resulting from high values of both $c$ and $d$ indicates a state of conflict rather than a lack of information.
- Rules as Objects: By treating rules as arcs within the network, the system can apply "metarules"—rules that govern the validity or activation of other rules.
Dempster’s Rule of Combination
To integrate multiple independent sources of evidence, the paper employs Dempster’s Rule of Combination. This mathematical formula allows the system to merge two probability intervals into a single, updated interval.
A critical property of this rule is that it is both commutative and associative. In practical terms, this means the order in which the system encounters new facts does not influence the final conclusion. This stability is a significant improvement over earlier non-monotonic systems where the sequence of information could lead to different logical states.
Furthermore, the rule is shown to be "nearly invertible." Ginsberg provides a specific formula for the inverse of the combination rule, allowing the system to "subtract" evidence. If a previously held belief is found to be false, the system can mathematically retract its influence without needing to re-evaluate the entire chain of reasoning from scratch.
Resolving the Ostrich Paradox
The effectiveness of this approach is best demonstrated through the "Tweety" problem. In a standard monotonic system, the rules "birds fly" and "ostriches do not fly" would create a contradiction when applied to an ostrich named Tweety.
In Ginsberg’s framework, the "bird" rule is assigned a high but non-certain probability (e.g., $(0.9, 0)$), while the specific fact that Tweety is an ostrich—and therefore cannot fly—is assigned a logical certainty $(0, 1)$. Because of the mathematical properties of Dempster’s Rule, a logical certainty $(1, 0)$ or $(0, 1)$ always outweighs a non-monotonic default. Consequently, the system naturally concludes that Tweety cannot fly, effectively deactivating the general rule in favor of the specific exception without requiring a complex hierarchy of rule priorities.
Limitations and Considerations
While the framework provides a robust mathematical foundation for non-monotonicity, it relies on the independence assumption. Dempster’s Rule assumes that the pieces of evidence being combined are independent. If the same rule is applied repeatedly to the same data, it could lead to an artificial inflation of confidence. Implementations must therefore track "rule firing" to prevent redundant evidence combination.
Additionally, while the paper demonstrates success on classic AI thought experiments, the computational scaling of these calculations in massive, real-world knowledge bases remains a subject for further investigation.
Conclusion
Ginsberg’s application of Dempster’s Rule to semantic networks offers a compelling alternative to purely logical or single-valued probabilistic approaches to non-monotonic reasoning. By utilizing probability intervals, the system gains the ability to distinguish between ignorance and conflict, resolve exceptions through mathematical weight, and efficiently retract evidence through invertibility. This work remains a foundational contribution to the intersection of evidence theory and automated reasoning.
Summary updated