Name
Abstract | ||
|---|---|---|
We introduce a combinatorial dimension that characterizes the number of queries needed to exactly (or approximately) learn concept classes in various models. Our general dimension provides tight upper and lower bounds on the query complexity for all sorts of queries, not only for example-based queries as in previous works. As an application we show that for learning DNF formulas, unspecified attribute value membership and equivalence queries are not more powerful than standard membership and equivalence queries. Further, in the approximate learning setting, we use the general dimension to characterize the query complexity in the statistical query as well as the learning by distances model. Moreover, we derive close bounds on the number of statistical queries needed to approximately learn DNF formulas. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jcss.2007.03.003 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
query learning,query complexity,example-based query,dnf formula,statistical queries,unspecified attribute value membership,learning dnf formulas,statistical query,equivalence query,learning by distances,combinatorial dimension,uav queries,standard membership,approximate learning setting,general dimension,upper and lower bounds | Query optimization,Discrete mathematics,Query learning,Query language,Combinatorics,Upper and lower bounds,Web query classification,Equivalence (measure theory),Spatial query,Mathematics | Journal |
Volume | Issue | ISSN |
73 | 6 | Journal of Computer and System Sciences |
Citations | PageRank | References |
9 | 0.64 | 26 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Jorge Castro | 2 | 34 | 3.27 |
| David Guijarro | 3 | 27 | 2.44 |
| Johannes Köbler | 4 | 580 | 46.51 |
| Wolfgang Lindner | 5 | 23 | 3.38 |