Introduction
Non-monotonic reasoning systems allow for new information to invalidate previous conclusions, but they frequently encounter the "multiple extensions" problem. This occurs when a set of rules leads to conflicting but logically valid conclusions. While prioritized logics resolve these conflicts by ranking rules, these rankings are often criticized as arbitrary or hand-tuned. This paper proposes a data-driven approach to automatically generate these preference orderings from domain data using statistical inference.
Methodology
The authors employ SF logic, a prioritized logic framework where rules are assigned two-dimensional labels representing priority. The process involves three main steps:
- Rule Induction: Rules are learned from training data using the Golem Inductive Logic Programming (ILP) algorithm.
- Statistical Labeling: Each rule is assigned a label $(\hat{p}, c)$, where $\hat{p}$ is an estimate of the rule's probability of being correct (derived via relative frequency or Bayesian estimation) and $c$ represents reliability (based on the rule's coverage in the dataset).
- Conflict Resolution: Two comparison methods are defined:
- Definition 1: A total ordering where probability takes precedence, and reliability acts as a tie-breaker.
- Definition 2: A skeptical partial ordering where one rule is preferred only if it outperforms another on both dimensions.
Experimental Setup
The approach was evaluated on two scientific datasets:
- Protein Domain: Predicting alpha-helix structures in protein residues (1,778 training, 723 test examples).
- Drugs Domain: Predicting relative drug activity based on chemical structure (1,762 training, 1,026 test examples).
Results
The SF logic approach was compared against standard Prolog using negation-as-failure.
Protein Domain Results
In the Protein domain, SF logic improved accuracy to approximately 64%, compared to Prolog's 58-59%. Notably, the introduction of an "undecided" category allowed the system to avoid incorrect guesses when evidence was insufficient.
Drugs Domain Results
The performance gains were even more pronounced in the Drugs domain. SF logic achieved 93% accuracy, significantly higher than Prolog's 79-80%. Furthermore, the error rate dropped from ~20% in Prolog to just 5% in SF logic.
Discussion
A key insight is the value of "skepticism." Unlike standard Prolog, which forces a binary "yes/no" decision, SF logic can remain "undecided." While this results in an undecided rate of up to 30% in some cases, it drastically reduces the rate of incorrect conclusions. This trade-off is particularly beneficial in high-stakes scientific or medical applications where a wrong guess is more costly than an admission of uncertainty. Additionally, the inclusion of a "reliability" dimension ensures that rules with high accuracy but low coverage do not unfairly dominate more robust, well-supported rules.
Conclusion
This research demonstrates a generic mapping from raw data to logical priority, moving non-monotonic reasoning toward evidence-based engineering. Future work will focus on integrating statistical preferences with structural preferences like "specificity" and investigating the scalability of these prioritized logics for larger knowledge bases.
Summary updated