Name
Abstract | ||
|---|---|---|
This note studies the learnability of the class of k-term DNF with a bounded number of negations per term and using either membership queries only or equivalence queries only. We give tight upper and lower bounds for the number of tens and negations per term when learning with a polynomial number of membership queries. We prove that a polynomial number of equivalence queries will not suffice. Finally, we give an algorithm for the simple-PAC model. (C) 1998 Published by Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0020-0190(98)00090-8 | EuroCOLT |
Keywords | Field | DocType |
concept learning,upper and lower bounds,algorithms | Discrete mathematics,Combinatorics,Negation,Computer science,Upper and lower bounds,Equivalence (measure theory),Learnability,Monotone polygon,Bounded function | Journal |
Volume | Issue | ISSN |
67 | 2 | 0020-0190 |
ISBN | Citations | PageRank |
3-540-62685-9 | 4 | 0.50 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jorge Castro | 1 | 34 | 3.27 |
| David Guijarro | 2 | 4 | 0.50 |
| Víctor Lavín | 3 | 25 | 3.54 |