Polynomial-sample learnability about distance-0 and 1 DNF formulas
S. Yanagi, Mineichi Kudo, Masaru Shimbo · 2002
We show a positive result for learnability of all arbitrary disjunctive normal form (DNF) formula. We propose a learning algorithm that requires a polynomial number of examples in the size of an unknown formula under probably approximately correct (PAC) learning with a subset query, while it is not polynomial time. Our algorithm is based on Valiant's (1984) approach with respect to monotone-DNF.