Refinement of Uncertain Rule Bases via Reduction

Refining deep (multilayer) rule bases of an expert system with uncertainty to cover a set of new examples can be very difficult (NP-hard). We analyze refinement via reduction, an approach first proposed in [Ginsberg, 1988b], where it is claimed that this approach eases the complexity of refining rule bases without uncertainty. We outline a model of rule bases with uncertainty, and give necessary and sufficient conditions on uncertainty combination functions that permit reduction from deep to flat (non-chaining) rule bases. We prove that reduction cannot be performed with most commonly used uncertainty combination functions. However, we show that there is a class of reducible rule bases in which the strength refinement problem is NP-hard in the deep rule base, reduction is polynomial, and the flat rule base can be refined in polynomial time. This result also allows polynomial refinement of practical expert systems in the form of rule deletion. Thus, our results provide some theoretical..