On Debugging Rule Sets When Reasoning Under Uncertainty

David C. Wilkins, Bruce G. BuchananAAAI 1986

Abstract

In probabilistic expert systems, high-quality individual rules can interact to produce a low-quality system. This paper proves that finding the optimal subset of rules to minimize errors is an NP-complete problem and introduces the Antidote Algorithm, a global heuristic search that cleans up rule sets by identifying and removing "deleterious interactions."

Introduction

During the "Golden Age" of expert systems in the 1980s, researchers relied heavily on heuristic rules to reason under uncertainty, using frameworks like MYCIN. The standard approach to improvement was incremental debugging: if the system failed a case, a knowledge engineer would modify or add a rule. However, this paper identifies a counter-intuitive phenomenon: better individual rules do not necessarily lead to a better overall rule set.

Because rules carry "Certainty Factors" (CF) rather than absolute truths, they can contribute false evidence in specific contexts. When multiple "good" rules are combined, they can interact in unexpected ways—termed deleterious interactions. Traditional debugging often fails here because fixing an error in one case frequently breaks the logic in another, leading to a "whack-a-mole" cycle that never converges to an optimal solution.

Problem Formalization and Complexity

The authors shift the perspective from local debugging to global optimization. They model the problem as a bipartite graph where one set of nodes represents training instances and the other represents the rules. Arcs connect rules to the instances they influence.

Bipartite graph representation of the relationship between instances (I) and rules (R).

By reducing the problem from the Satisfiability (SAT) problem, the authors prove that selecting the optimal subset of rules to minimize misdiagnoses is NP-complete. This complexity necessitates a heuristic approach rather than an exhaustive search.

The Antidote Algorithm

The proposed Antidote Algorithm is a heuristic search that iteratively deletes rules that do more harm than good across the entire training set. Instead of tweaking rule parameters, which might violate their probabilistic interpretations, the algorithm ranks rules based on a penalty function. This function considers:

  • Poison Rules: Strong rules causing uncounteractable misdiagnoses.
  • False Positives/Negatives: Frequency of a rule contributing to wrong vs. right conclusions.
  • Rule Strength: The absolute value of its Certainty Factor.

The algorithm removes the highest-ranking "offending" rules and re-evaluates the system until errors are minimized.

Empirical Evaluation

The researchers evaluated the Antidote Algorithm using the MYCIN case library, a classic benchmark in medical AI. The training set consisted of 104 medical cases, while a validation set of 10 cases was used to test generalization.

A detailed example of a rule set interacting with classified instances, showing how weights (+.5, -.5) contribute to instance labels (+1, -1).

The algorithm proved highly effective, typically converging in 5 to 15 iterations. On the training set, misdiagnoses were reduced from 15% to 5%. More importantly, the improvements generalized to unseen data, with the validation error rate dropping from 30% to 20%.

Discussion and Insights

A key insight is the Power Set Perspective: the "best" rule set is a specific subset of all generated rules. We must select the subset that "plays well together" rather than keeping every statistically valid rule. Furthermore, a rule with a high Certainty Factor is more "dangerous" because it is harder for other rules to counteract if it is wrong. This highlights the danger of global vs. local debugging; one must look at the distribution of errors across the entire instance space.

Limitations

The current Antidote Algorithm is limited to rule deletion and does not suggest modifications or new rule creation. Additionally, the penalty constants are domain-dependent and require manual tuning. While the primary focus is on "evidence-gathering" systems, more complex multi-step reasoning chains might require a more sophisticated graph model to handle rule chaining interactions.

Summary updated

BibTeX
@inproceedings{wilkins1986debugging,
  author = {David C. Wilkins and Bruce G. Buchanan},
  title = {{On Debugging Rule Sets When Reasoning Under Uncertainty}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure