On Debugging Rule Sets When Reasoning Under Uncertainty

Reference: Wilkins, D. C. & Buchanan, B. G. On Debugging Rule Sets When Reasoning Under Uncertainty. 1986.

Abstract: Heuristic inference rules with a measure of strenth less than certainty have an unusual property: better individual rules do not necessarily lead to a better overall rule set. All less-than-certain rules contribute evidence towards erroneous conclusions for some problem instances, and the distribution of these erroneous conclusions over the instances is not necessarily related to individual rule quality. This has important consequences for automatic machine learning of rules, since rule selection is usually based on measures of quality of indiviual rules. In this paper, we explain why the most obvious and intuitively reasonable solution to this problem, incremental modification and deletion of rules responsible for worng conclusions a la Teiresias, is not always appropriate. In our experience, it usually fails to converge to an optimal set of rules. Given a set of heuristic rules, we explain why the best rule set should be considered to be the element of the power set of rules that yields a global minimum error with respect to generating erroneous positive and negative conclusions. This selection process is modeled as a bipartite graph minimization problem and shown to be NP-complete. A solution method is described, the Antidote Algorithm, that performs a model-directed search of the rule space. On an example from medical diagnosis, the Antidote Algorithm significantly reduced the number of misdiagnoses when applied to a rule set generated from 104 training instances.

Notes: STAN-CS-87-1181.

Jump to... [KSL] [SMI] [Reports by Author] [Reports by KSL Number] [Reports by Year]
Send mail to: ksl-info@ksl.stanford.edu to send a message to the maintainer of the KSL Reports.