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 · 2O(k), where n is the number of input variables. This improves upon previous O(nk) 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 techniques can be used to make it deterministic. The algorithm is an exact 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 version of our algorithm that uses at most 4n + 2 total membership and equivalence queries.