Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries
Nader H. Bshouty, Nadav Eiron; 3(Jul):49-57, 2002.
Abstract
We present results concerning the learning of Monotone DNF (MDNF) from Incomplete Membership Queries and Equivalence Queries. Our main result is a new algorithm that allows efficient learning of MDNF using Equivalence Queries and Incomplete Membership Queries with probability of p=1-1/poly(n,t) of failing. Our algorithm is expected to make
queries, when learning a MDNF formula with t terms over n variables. Note that this is polynomial for any failure probability p=1-1/poly(n,t). The algorithm's running time is also polynomial in t,n, and 1/(1-p). In a sense this is the best possible, as learning with p=1-1/w(poly(n,t)) would imply learning MDNF, and thus also DNF, from equivalence queries alone.
An early version of this paper appeared as Bshouty and Eiron (2001).