Loading...
Please wait, while we are loading the content...
Similar Documents
Malicious Membership Queries and Exceptions Malicious Membership Queries and Exceptions
| Content Provider | Semantic Scholar |
|---|---|
| Author | Angluin, Dana Krikis, Martinch |
| Copyright Year | 1994 |
| Abstract | We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) errors in the answers to membership queries and (2) learning nite variants of concepts drawn from a learnable class. To study (1), we introduce a malicious membership query, in which errors are permitted on a set of strings in the domain, such that the number of strings plus the sum of their lengths is bounded by L. Equivalence queries are answered correctly, and algorithms are allowed time polynomial in the usual parameters and L. We present a new polynomial-time learning algorithm in this model for monotone DNF formulas. To study (2), we consider classes of concepts that are polynomially closed under nite 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 nite exceptions. We give a new polynomial-time algorithm to learn the class of monotone DNF formulas with nite exceptions using equivalence and membership queries. Relating (1) and (2), we give a general transformation showing that any class of concepts that is polynomially closed under nite exceptions and is learnable in polynomial time using membership and equivalence queries is also polynomial-time learnable using malicious membership and equivalence queries. Corollaries include the polynomial-time learnability of the following classes using malicious membership and equivalence queries: deterministic nite accep-tors, boolean decision trees, and monotone DNF formulas with nite exceptions. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
