Some results on the computational complexity of refining confidence factors

AbstractRule bases are commonly used in the implementation of knowledge bases for expert systems. Knowledge engineers, with the help of experts, are good at designing the structure of the rule base but poor at setting values for the strengths of the rules. This paper presents an algorithmic analysis of problems related to setting the strength of rules (synthesis) and to modifying them when good estimates are given (refinement). Models of knowledge base and learning protocols are discussed. We define several problems of rule strength synthesis and refinement and show them to be computationally intractable—even if we settle for approximate values or demand that cases be fitted only in a fixed percentage of cases. Perhaps the most striking result is that the refinement of rule strengths in MYCIN-like systems is intractable even when (1) the depth of rule chaining is bounded by two, (2) we are concerned only with the classification of outputs, rather than the exact values of the certainty factors of possible diagnoses, and (3) good estimates of the strengths are given. The concept of gradualness in knowledge refinement, introduced by Rada, is characterized using algorithmic complexity. Some problems in neural network learning are related to the ones introduced here. The paper ends by indicating directions for further research