Exception Dags as Knowledge Structures

Foundational Issues and Core Problems

The problem of transforming the knowledge bases of performance systems using induced rules or decision trees into comprehensible knowledge structures is addressed. A knowledge structure is developed that generalizes and subsumes production rules, decision trees, and rules with exceptions. It gives rise to a natural complexity measure that allows them to be understood, analyzed and compared on a uniform basis. This structure is a rooted directed acyclic graph with the semantics that nodes are concepts, some of which have attached conclusions, and the arcs are 'isa' inheritance links With disjunctive multiple inheritance. A detailed example is given of the generation of a range of such structures of equivalent performance for a simple problem, and the complexity measure of a particular structure is shown to relate to its perceived complexity. The simplest structures are generated by an algorithm that factors common concepts from the premises of rules. A more complex example of a chess dataset is used to show the value of this technique in generating comprehensible knowledge structures.