On Debugging Rule Sets When Reasoning Under Uncertainty

From Tetherless World Wiki

Jump to: navigation, search

Citation: David C. Wilkins and Bruce G. Buchanan. (1986) On Debugging Rule Sets When Reasoning Under Uncertainty. In KSL-86-30, 1986.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author David C. Wilkins and Bruce G. Buchanan
title On Debugging Rule Sets When Reasoning Under Uncertainty
number KSL-86-30
institution Knowledge Systems, AI Laboratory
year 1986
Bibtex more
note STAN-CS-87-1181.
Access Paper
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.

KSL Technical Report ID: KSL-86-30
Facts about On Debugging Rule Sets When Reasoning Under UncertaintyRDF feed
Abstract Heuristic inference rules with a measure o … 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. set generated from 104 training instances.
Author David C. Wilkins and Bruce G. Buchanan  +
Bibtype techreport  +
Has author David C. Wilkins and Bruce G. Buchanan  +
Has identifier KSL-86-30  +
Has publishing details 1986  +
Has title On Debugging Rule Sets When Reasoning Under Uncertainty  +
Has where published KSL-86-30  +
Has year 1986  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-86-30  +
Note STAN-CS-87-1181.
Number KSL-86-30  +
Process note YES  +
Title On Debugging Rule Sets When Reasoning Under Uncertainty  +
Year 1986  +
Retrieved from "http://tw.rpi.edu/wiki/On_Debugging_Rule_Sets_When_Reasoning_Under_Uncertainty"
Personal tools