Learnability of DNF with representation-specific queries
Lin Forrest Yang, Avrim L. Blum, Jaime Carbonell · 2013
We study the problem of PAC learning the class of DNF formulas with a type of natural pairwise query specific to the DNF representation. Specifically, given a pair of positive examples from a polynomial-sized sample, we consider boolean queries that ask whether the two examples satisfy at least one term in common in the target DNF, and numerical queries that ask how many terms in common the two examples satisfy. We provide both positive and negative results for learning with these queries under both uniform and general distributions.