Proper learning of \(k\)-term DNF formulas from satisfying assignments (Q2323349)

Learning the class of \(k\)-term Disjunctive Normal Form (DNF) formulas is difficult. Unless \(\mathrm{RP} = \mathrm{NP}\), it is not feasible to learn \(k\)-term DNF formulas properly in a distribution-free sense even if both positive and negative examples are available and even if false positives are allowed. In this paper, the authors construct an efficient algorithm that, for fixed but arbitrary \(k\) and \(q\), if examples are drawn from \(q\)-bounded distributions, it properly learns the class of \(k\)-term DNFs without false positives from positive examples alone with arbitrarily small relative error.