Optimal refinement of rule bases

Article type: Research Article

Authors: Kelbassa, Hans‐Werner

Affiliations: Department of Computer Science, University of Paderborn, D‐33102 Paderborn, Germany E‐mail: kelbassa@uni‐paderborn.de

Abstract: This article presents a formal analysis of the rule refinement selection problem. There is no satisfactory methodical standard for the optimal refinement of rule bases. Current refinement systems select the best overall rule base refinements out of a set of normal, conflicting, and alternative ones, not by exact optimization procedures but rather by using local greedy heuristics. Within the last decade different research prototypes have demonstrated scientific progress in the development of rule base validation systems. In particular, several rule refinement generators have been tested. However, the optimal refinement of rule bases is an unsolved problem. This paper describes a novel global Operations Research approach to the selection of optimal rule refinements. The problem analysis and the formal description of the optimization are carried out using a well‐defined example which is developed in three steps. First, conflicting rule refinements are analyzed. Next, simple alternatives are considered. Then also the optimization with regard to alternative refinement heuristics yielding combinatorial effects termed subsumption and synergy is formalized. The mathematical analysis of the rule refinement selection problem leads to the conclusion that the introduction of a special binary relation termed ONE‐OF DISJUNCTION and the use of so‐called EITHER‐OR CONSTRAINTS enables the formulation of a binary linear maximization problem to be solved by an appropriate Operations Research procedure. Finally, it will be explored how to come up with weighted objective functions and a suitable multi‐criteria validation gain calculation. This global optimization of rule base refinement GRSP holds for every refinement selection problem and will yield a more powerful generation of rule refinement systems so that the development time for large and complex rule bases will be shortened.

Keywords: Rule base validation, optimal refinement selection, subsumption and synergy, complex gain calculation, rule refinement classes, conflicting and alternative rule refinements, evaluation of safety‐critical knowledge bases

Journal: AI Communications, vol. 17, no. 3, pp. 123-154, 2004