Structured and unstructured induction with EDAGs
Brian R. Gaines · 1995
Exception directed acyclic graphs (EDAGs) are knowledge structures that subsume trees and rules but can be substantially more compact. Manually constructed and induced EDAGs are compared by reconstructing Shapiro's "structured induction" of a chess end game. It is shown that the induced EDAG is very similar to that produced through consultation with experts, and that both are small, comprehensible solutions to a problem that is complex for people. Introduction A problem for knowledge discovery is that the trees or rules induced are not meaningful as "knowledge" (Quinlan 1991). Variant structures have been proposed that offer the possibility of more comprehensible models. Gaines' (1989) Induct induces rule graphs that cover common cases by default rules and infrequent cases through exception rules. Compton and Jansen's (1990) ripple-down rules generalize binary decision trees by allowing a node to contain a compound premise, and interior nodes to contain conclusions. Gaines (1991) sho...