Generating Alternative Hypotheses in AQ Learning




Michalski, Ryszard S.

Journal Title

Journal ISSN

Volume Title



In many areas of application of machine learning and data mining, it is desirable to generate alternative inductive hypotheses from the given data. The Aq-ALT or, briefly, ALT method, presented in this paper, generates alternative hypotheses in two phases. The first phase proceeds according to the standard Aq algorithm, but each star generation process produces not just one best complex, but rather a collection of complexes, called the elite. This phase ends when the union of best complexes constitutes a complete and consistent cover of the target set, called the primary hypothesis. The second phase derives alternative hypotheses by multiplying out the disjunctions of symbols representing complexes in each elite, and creating an irredundant DNF expression. Individual terms in this expression determine alternative hypotheses. These hypotheses are ranked according to a given hypothesis evaluation criterion, LEFh, and the alt best hypotheses are selected, where alt is a parameter provided to the program. The method is extended to inconsistent covering problem by introducing an event membership probability function. The selected hypotheses can be used as alternative generalizations of data, or arranged into an ensemble of classifiers to perform a form of boosting. The ALT method is general, and can thus be employed not only in concept learning, but also for generating alternative solutions to any general covering problem.



Covering problem, Alternative hypotheses, AQ learning, Machine learning, Natural induction, Knowledge mining, Data mining


Michalski, R. S., "Generating Alternative Hypotheses in AQ Learning," Reports of the Machine Learning and Inference Laboratory, MLI 04-6, George Mason University, Fairfax, VA, December, 2004.