MALICIOUS OMISSIONS AND ERRORS IN ANSWERS TO MEMBERSHIP QUERIES

We consider two issues in polynomial-time exact learning of concepts u sing membership and equivalence queries: (1) errors or omissions in an swers to membership queries, and (2) learning finite variants of conce pts drawn from a learnable class. To study (1), we introduce two new k inds of membership queries: limited membership queries and malicious m embership queries. Each is allowed to give incorrect responses on a ma liciously chosen set of strings in the domain. Instead of answering co rrectly about a string, a limited membership query may give a special ''I don't know'' answer, while a malicious membership query may give t he wrong answer. A new parameter L is used to bound the length of an e ncoding of the set of strings that receive such incorrect answers. Equ ivalence queries are answered correctly, and teaming algorithms are al lowed time polynomial in the usual parameters and L. Any class of conc epts learnable in polynomial time using equivalence and malicious memb ership queries is learnable in polynomial time using equivalence and l imited membership queries; the converse is an open problem. For the cl asses of monotone monomials and monotone k-term DNF formulas, we prese nt polynomial-time learning algorithms using limited membership querie s alone. We present polynomial-time learning algorithms for the class of monotone DNF formulas using equivalence and limited membership quer ies, and using equivalence and malicious membership queries. To study (2), we consider classes of concepts that are polynomially closed unde r finite exceptions and a natural operation to add exception tables to a class of concepts. Applying this operation, we obtain the class of monotone DNF formulas with finite exceptions. We give a polynomial-tim e algorithm to learn the class of monotone DNF formulas with finite ex ceptions using equivalence and membership queries. We also give a gene ral transformation showing that any class of concepts that is polynomi ally closed under finite exceptions and is learnable in polynomial tim e using standard membership and equivalence queries is also polynomial -time learnable using malicious membership and equivalence queries. Co rollaries include the polynomial-time learnability of the following cl asses using malicious membership and equivalence queries: deterministi c finite accepters, boolean decision trees, and monotone DNF formulas with finite exceptions.