Introduction
In classical logic, knowledge is monotonic: adding new information never invalidates existing conclusions. However, real-world reasoning is inherently nonmonotonic. For instance, one might believe that birds fly until learning that penguins are flightless birds. System P provides a formal framework for this "default" reasoning, but its computational cost is a significant barrier for large-scale knowledge bases (KBs).
This paper introduces focused inference, a method that allows AI systems to draw sound conclusions by examining only a small, relevant subset of a large KB. This approach mimics human "snap decisions," where we ignore irrelevant data to reach quick conclusions without sacrificing logical integrity.
Methodology: The Focused Inference Framework
The core idea is to define "relevance" syntactically based on variable sharing between the query and the KB rules.
1. Iterated Focus
The authors define a hierarchy of focus levels. The "Direct Focus" ($F_0$) contains only variables present in the query. Subsequent levels ($F_i$) expand to include variables in rules that share variables with the current focus. This creates a notion of "syntactic distance" from the query.
2. Focused Inference Relations and Algorithms
Instead of reasoning over the entire KB ($\Delta$), the system operates on a subset ($\Delta_i$) corresponding to the $i$-th level of focus. The authors propose an Anytime Algorithm that starts with the smallest focus and incrementally expands it. Due to the "semi-monotony" property of System P, if a query is found to be true at a lower focus level, it is guaranteed to be true in the full KB, allowing for early termination.
To maintain efficiency during expansion, an Incremental Consistency algorithm updates the "Z-partition"—a data structure for managing default rules—without recalculating it from scratch.
Illustrative Examples
The theoretical framework is demonstrated using classic nonmonotonic reasoning scenarios, such as the relationship between birds, penguins, and flight.
As shown in the figure above, the Oviparous Example illustrates how "irrelevant" information (e.g., salamanders in $\Delta_{amphibian}$) can be syntactically isolated from queries regarding bird flight. This separation is what enables the focused inference mechanism to ignore large portions of the KB.
Key Insights
- Soundness without Completeness: While focused inference at a low level might not find every truth (it is incomplete), it is sound: it never produces a conclusion that would be false in the full System P.
- Convergence: As the focus expands, the inference relation eventually converges to full System P, justifying the anytime nature of the algorithm.
- Focused Rules: Standard logical rules like Cut and Right Weakening do not hold at a fixed focus level. The authors introduce "Focused" variants of these rules to maintain logical consistency within a specific focus.
Results and Performance
Complexity analysis indicates that focused inference offers significant speedups when queries can be resolved within a small focus. By reusing calculations across iterations, the system avoids the $O(|\Delta|^2)$ cost typically associated with re-evaluating consistency in large KBs. Proposition 7 formally proves that increasing the focus level only adds valid conclusions, ensuring that "snap decisions" are never contradicted by further reasoning.
Limitations and Future Work
The current framework relies on the semi-monotony of System P and a "clean" propositional language to avoid issues with redundant variables. Future research may explore "semantic focus"—defining relevance based on the meaning or influence of variables rather than just their names—and extending the approach to other formalisms like System Z or c-representations.
Summary updated