Generating Explicit Orderings for Non-monotonic Logics

James Cussens, Anthony Hunter, Ashwin SrinivasanAAAI 1993

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:

  1. Rule Induction: Rules are learned from training data using the Golem Inductive Logic Programming (ILP) algorithm.
  2. 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).
  3. Conflict Resolution: Two comparison methods are defined:
  4. Definition 1: A total ordering where probability takes precedence, and reliability acts as a tie-breaker.
  5. 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.

Table 1: Performance comparison in the Protein domain.

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.

Table 2: Performance comparison in the Drugs domain.

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

BibTeX
@inproceedings{cussens1993generating,
  author = {James Cussens and Anthony Hunter and Ashwin Srinivasan},
  title = {{Generating Explicit Orderings for Non-monotonic Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure