Name
Abstract | ||
|---|---|---|
We introduce a new combinatorial dimension that gives a good approximation of the number of queries needed to learn in the exact learning model, no matter what set of queries is used. This new dimension generalizes previous dimensions providing upper and lower bounds for all sorts of queries, and not for just example-based queries as in previous works. Our new approach gives also simpler proofs for previous results. We present specific applications of our general dimension for the case of unspecified attribute value queries, and show that unspecified attribute value membership and equivalence queries are not more powerful than standard membership and equivalence queries for the problem of learning DNF formulas. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-44581-1_23 | COLT/EuroCOLT |
Keywords | Field | DocType |
standard membership,new dimension,exact learning,previous dimension,previous work,general dimension,new approach,previous result,new combinatorial dimension,equivalence query,exact learning model,lower bound | Boolean function,Upper and lower bounds,Computer science,Mathematical proof,Equivalence (measure theory),Artificial intelligence,Machine learning,Sample exclusion dimension | Conference |
Volume | ISSN | ISBN |
2111 | 0302-9743 | 3-540-42343-5 |
Citations | PageRank | References |
6 | 0.60 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Jorge Castro | 2 | 34 | 3.27 |
| David Guijarro | 3 | 6 | 0.60 |