SIMPLE LEARNING ALGORITHMS USING DIVIDE-AND-CONQUER

This paper investigates what happens when a learning algorithm for a c lass C attempts to learn target formulas from a different class. In ma ny cases, the learning algorithm will find a ''bad attribute'' or a pr operty of the target formula which precludes its membership in the cla ss C. To continue the learning process, we proceed by building a decis ion tree according to the possible values of this attribute (divide) a nd recursively run the learning algorithm for each value (conquer). Th is paper shows how to recursively run the learning algorithm for each value using the oracles of the target. We demonstrate that the applica tion of this idea on some known learning algorithms can both simplify the algorithm and provide additional power to learn more classes. In p articular, we give a simple exact learning algorithm, using membership and equivalence queries, for the class of DNF that is ''almost'' unat e, that is, unate with the addition of O(log n) nonunate variables and a constant number of terms. We also find algorithms in different mode ls for boolean functions that depend on k terms.