Exact Learning of u-DNF Formulas with Malicious Membership Queries

We consider exact learning of concepts using two types of query: extended equivalence queries, and malicious membership queries, that is, membership queries that are permitted to make errors on some arbitrarily chosen set of examples of a bounded cardinality. We present a randomized algorithm to learn ¯-DNF formulas using these queries. The expected running time of the algorithm is polynomial in the number of variables and the maximum number of strings on which the membership oracle is allowed to make errors. 1 Introduction We continue the investigation begun by Angluin and Krikis [2] concerning the effects of errors in the answers to membership queries in the model of equivalence queries and malicious membership queries. We are interested in the question of whether polynomial-time learnability of a concept class using equivalence queries and (errorfree) membership queries implies polynomial-time learnability in the error model of equivalence queries and malicious membership queries, ..