FAST LEARNING OF K-TERM DNF FORMULAS WITH QUERIES

This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time n . 2(O(k)), where n is the number of input variables. This improves upon previous O(n(k)) bounds and allows one to learn DNF formulas of O(log n) terms in polynomial time. We present the algorithm in its most natural form as a randomized algorithm and then show how recent derandomization te chniques can be used to make it deterministic. The algorithm is an exa ct learning algorithm, but one where the equivalence query hypotheses and the final output are general (not necessarily k-term) DNF formulas . For the special case of two-term DNF formulas, we give a simpler ver sion of our algorithm that uses at most 4n + 2 total membership and eq uivalence queries. (C) 1995 Academic Press, Inc.