Introduction
In classical logic, the addition of new information never invalidates previously held conclusions—a property known as monotonicity. However, human "common sense" is fundamentally nonmonotonic. We routinely make assumptions (e.g., "birds fly") and retract them when presented with specific exceptions (e.g., "this bird is a penguin"). While early probabilistic frameworks like $\epsilon$-semantics provided a sound basis for such reasoning, they were often criticized for being "too conservative," failing to make the intuitive leaps required for true common-sense inference. This paper introduces a framework that combines infinitesimal probabilities with the Principle of Maximum Entropy (ME) to bridge this gap, creating a system that naturally handles irrelevant information and property inheritance.
The Problem: Conservatism in $\epsilon$-Semantics
$\epsilon$-semantics interprets default rules as conditional probabilities arbitrarily close to 1 ($P(B|A) \ge 1 - \epsilon$). While mathematically robust, this approach lacks the ability to ignore irrelevant details. For instance, if a system is told that "birds fly," an $\epsilon$-semantics model might refuse to conclude that a green bird flies, simply because it cannot be certain that color is independent of flight. This lack of "adventurous" reasoning prevents systems from performing property inheritance, where subclasses (like penguins) should still inherit general traits (like having wings) unless explicitly contradicted.
Methodology: The Maximum Entropy Framework
The authors propose treating default rules as constraints on a probability distribution and selecting the unique distribution that satisfies these constraints while maximizing entropy. This approach assumes the least amount of additional information beyond what is explicitly stated.
1. $\epsilon$-Constraints and Asymptotic Analysis
A rule $A \to B$ is modeled as $P(B|A) \ge 1 - \epsilon$, where $\epsilon$ is an infinitesimal positive number. To solve the resulting optimization problem, the authors use Lagrange multipliers and analyze the behavior of the distribution as $\epsilon$ approaches zero.
2. The Ranking Function ($\kappa$)
This analysis leads to a ranking function, $\kappa$, which assigns an integer weight to each possible world. The "abnormality" of a world is defined as the sum of the weights of the rules it violates. This provides a refined, weighted metric for evaluating the plausibility of different scenarios.
3. Minimal Core (MC) Sets
For a specific class of knowledge bases known as "Minimal Core Sets," the authors demonstrate that a greedy algorithm can efficiently calculate the weights of violating specific rules, bypassing the need for complex continuous optimization.
Key Insights: Independence and Inheritance
The Maximum Entropy approach provides two critical improvements over previous logical systems:
- Automatic Independence: By maximizing entropy, the system naturally encodes the intuition that if a property (like being green) is not stated to affect an outcome (like flying), it should be assumed irrelevant. This allows the system to correctly conclude that green birds fly without requiring explicit rules for every possible color.
- Inheritance Across Exceptions: ME allows exceptions to inherit properties from their parent classes. In the classic "Penguin Triangle" problem, the system recognizes that while penguins are exceptional birds because they do not fly, they should still be expected to have wings. Because violating the "birds have wings" rule adds an unnecessary "cost" to the world's abnormality score, the ME distribution prefers worlds where penguins retain wings.
Results and Theoretical Contributions
The paper provides the first precise formalization of the interaction between Maximum Entropy and infinitesimal probabilities. Key results include:
- Rational Monotony: The authors prove that their ME-based entailment satisfies the "Rational Monotony" requirement, a vital benchmark for nonmonotonic systems that standard $\epsilon$-semantics fails to meet.
- Behavioral Superiority: Qualitatively, the ME approach is shown to be more powerful than Lehmann’s (1989) "Rational Closure" method, particularly in its nuanced handling of property inheritance.
- Computational Machinery: The framework provides the necessary mathematical tools to decide if a conclusion is "ME-plausible" (i.e., its probability tends toward 1 as $\epsilon \to 0$) without performing exhaustive optimization.
Limitations and Future Work
Despite its strengths, the authors identify several areas for improvement:
- Causal Blindness: The ME approach currently struggles with causal reasoning. It cannot distinguish between causes and effects, leading to failures in benchmarks like the "Yale Shooting Problem," where the temporal direction of rules is essential.
- Computational Complexity: While greedy algorithms work for Minimal Core sets, finding the minimal world for general Horn expressions remains NP-complete.
- Syntax Sensitivity: The system can be sensitive to how rules are grouped (e.g., treating "Birds fly and have wings" as one rule vs. two), which can lead to counter-intuitive ranking changes.
Conclusion
By integrating Maximum Entropy with probabilistic logic, the authors have developed a framework that more closely mirrors human common-sense reasoning. The system successfully navigates the balance between logical rigor and the "adventurous" assumptions necessary to function in a world of incomplete information.
Summary updated