## 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

*O*((

*tn/*(1-

*p*))

^{2})

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).