multistrategy constructive induction: AQ17-MCI

(Michalski, Bloedorn, Wnek)

Conventional concept learning techniques generate hypotheses in the same representation space in which original training examples are presented. In many learning problems, however, the original representation space is inadequate for formulating the correct hypothesis. This inadequacy can be evidenced by a high degree of irregularity in the distribution of instances of the same class in the original representation space.

A functional diagram of the AQ17-MCI program.

We have been developing a methodology and a system, AQ17-MCI, for interpreting a range of strategies for an automated improvement of the knowledge representation spaces.

The system includes three basic mechanisms:

(1) for accepting expert advice about the rules and procedures for generating new attributes;

(2) for analyzing learning examples and generating new attributes as logical or mathematical functions of the original attributes (implemented in AQ17-DCI version, which stands for data-driven constructive induction)

(3) for detecting “strong patterns” in the rules generated in one iteration of the rule generation module, and then using these patterns for proposing candidate attributes for a new iteration (implemented in AQ17-HCI version, which stands for hypothesis-driven constructive induction).

The attributes generated by these mechanisms are evaluated for their relevance to the problem at hand. If they pass the relevance test, they are used to reformulate original learning examples, and the rule generation module (based on the AQ algorithm) generates new rules. The quality of the rules is determined, and those that pass the quality criterion are stored in the knowledge base.

AQ17-MCI significantly extends current machine learning capabilities, as it is capable for “multi-mechanism” improvement of the original description space. It is a powerful program that represents a new generation of symbolic learning systems, and thus has a potential for important new applications. (See its performance on MONKS’ problems, described in the project “A Comparative Study of Learning Methods.”)

Selected Reference

Bloedorn, E.E., “Multistrategy Constructive Induction,” Ph.D. Dissertation, School of Information Technology and Engineering, Reports of Machine Learning and Inference Laboratory, MLI 96-7, George Mason University, Fairfax, VA, 1996.

Bloedorn, E., Michalski, R.S., and Wnek, J., “Multistrategy Constructive Induction: AQ17-MCI,” Proceedings of the 2nd International Workshop on Multistrategy Learning, May 26-29, 1993.

For more references, see publications section.