A System of Programs for Computer-Aided Induction: A Summary

Introduction

Inductive inference processes are not only fundamental for scientific research and discovery, but also are crucial for our everyday activities, in which we constantly have to determine relevant information in the enormous flow of information coming to us, or to make decisions based on insuf· ficient or partial information. Despite many attempts to formalize induction, not much has yet been achieved in this direction, and the research on induction is often treated with skepticism.

One way to break a stalemate is to work on induction tailored toward solving specific prob­ lems with a hope that it will bring an insight t o induction in general (e.g., work by Simon and Lea 73, Winston 70, Buchanan, Feigenbaum and Sridharan 72). Another way is to identify cer­ tain conceptually simple but basic inductive tasks, common to many inductive processes, and to ·find the most efficient and general solution for them (a t the final stage implemented as a comput­ er program). Having easily available programs for solving such well defined inductive tasks, a skillful user could use them as tools for attack­ ing complex induc tive problems in differ ent prac­ tical areas.

For example, such programs could aid special­ ists in various applied sciences in formulating hypotheses explaining experimentaldata, suggest. ing alternative hypotheses, detecting regularities in data, discovering the simplest conditions for certain actions. They could be useful for know­ ledge acquisition from examples in rule-based expert systems, in research on speech and image understanding systems. Also, they could serve as building blocks for solving more complex induc­ tive tasks. An example of the latter possibility is the fact (which was unexpectedly discovered) that inducing concepts in VL21 logic system (a form of the first order predicate logic with ad­ ditional operators; Larson and Michalski 77a)re­ quires at some stage a· solution of a simpler problem of inducing concepts in variable-valued propositional calculus (VL1 system; Michalski 75a) and, consequently, an already existing program was found directly applicable.

This tool building approach to induction has been followed by the author and his collaboratorc at the University of Illinois for the last few years. We have developed a theoretical basis, algorithms and computer programs for solving a class of inductive tasks, which we found often occuring in various practical inductive problems. The algorithms employ a number of novel ideas to combat the combinatorial complexity of the tasks. They are described in references to each program. This report gives only a brief review of the tasks we worked on and the developed programs, so that a potential user or an interested reader can be aware of their existance and availability. Some of the programs achieved a high level of ma­ turity (e.g., AQ7, AQll); some of them represent just an initial state. All programs are document­ ed and can be obtained on request.

Tasks and Programs

Below is given a summary of tasks considered with a reference to programs providing a solution for them. (A more detailed review is given in Michalski 77).

1. Determination of a relevant descriptor set. In solving inductive problems, the first step is often a determination of a relevant set of descrip tors (variables, predicates, functions, relations) which are ·used in the original problem descripticr. . The descriptors should be simple to measure or recognize, easy to interpret and as relevant as possible. A special case of this problem is when there is a large number of potentially useful variables (unary descriptors), and the problem is to select a small but sufficient subset consisting of the most relevant ones. Standard feature se­ lection techniques developed in pattern recogni­ tion are often not satisfactory, because they select variables based on a measure of usefulness of each variable taken separately. We have de­ veloped an algorithm for an interactive determina­ tion of a 'best' subset of variables, taken as a group rather than separately. The developed al­ gorithm was implemented in program AQPLUS (Forsburg 75).
2. ·Determination of an optimal ('simplest') dis­ criminant description of a collection of object classes, where objects are described by property lists (VL 1 level) or by an expression equivalent to a formula in the first order predicate logic (VLz level). A discriminant description is a description which contains only necessary descrip­ tors, in a proper relation, which distinquish a given class from all other classes. Programs AQll (Larson 76, Larson and Michalski 77), AQ7 (Larson and Michalski 75. Michalski 75b),AQ9 (Cuneo 75) solve various forms of this problem within the framework of the VL system (Michalski 75a) and program INDUCE-1 wifhin the framework of the VL 21 system (Larson and Michalski 77, Larson 77).
3. _Determination of a characteristic description of ~class of objects (with or without negative ex­ amples), where objects are described similarly as in 2. The difference between this task and the previous one is that here the goal is to determine a complete description of a given class of objects, which includes all common characteristics of ob­ jects in each class. A specific subtask here is to determine the least general conjunctive descrip tion of the class, whose objects are described by a property list or by a product ·of predicates (or some equivalent form). Winston (Winston 70) con­ sidered this task from the viewpoint of building a class description in a form of a labeled graph, Hayes-Roth (Hayes-Roth 76) within a formalism equivalent to a quantifier-free first order predi­ cate logic.

Program AQ7UNI (Stepp 76) provides a solution to this task within a framework of VL 1 system (involv­ ing both conjunctive and disjunctive descriptions), and program INDUCE-! within the framework of VL 21 (Larson and Michalski 77a). Among novel ideas im­ plemented in INDUCE-! is an ability to develop new descriptors built as functions of the original ones, to involve different schemas of generalization de­ pendent on the type of descriptors (nominal, inter­ val or structured), to provide either descriptive or descriminant descriptions by changing a descrip­ tion optimality criterion, and an ability to ac­ cept user's knowledge about restrictions and rela­ tions characterizing descriptors.

4. Determination of the most representative learn­ ing examples. This task occurs when one has ac­ cess to a large number of examples of each deci­ sion class, and the problem is how to select from the set the examples which are 'most instructive' to a description learning program. Program ESEL ('event selection') provides a solution to this problem (Larson and Mi chalski 77b).

Concluding Remarks

We have done experiments on applying programs to determine discriminant descriptions of liver diseases (Michalski 73, Larson 76) ., to determining · filt ers for non-uniform texture discrimination (Michalski 73), to formulate rules for win and draw in King-Pawn versus King chess end games (Michalski, Negri 76), to determine discriminant rules describing soybean diseases. The results from testing the derived soybean disease diagnostic rules gave more than 99% of correct diagnosis on 365 test cases of soybean diseases (Chilausky, Jacobsen, Michalski 76, 77). It may be interesting to remark that expert-derived rules applied to the same data gave only 83% correct decisions. This may be due to an inadequate representation of the expert's knowledge (in the form of decision rules) or the way it was applied (an evaluation schema for the rules), or some other factors. This sur­ prising result is a question to be explored in the future.

The above experiments have convinced us that the inductive programs of the kind we have been working on can find many useful applications.

The reported work is still at an early stage, and there is much room for further advancement in this direction.

Acknowledgments

The research described in this paper was sup­ ported in part by the National Science Foundation, Grant NSF MCS 74-03514. Author thanks Gary Kampen and James Larson for proofreading and the comments.