Name
Abstract | ||
|---|---|---|
The general dimension is a combinatorial measure that characterizes the number of queries needed to learn a concept class. We use this notion to show that any p-evaluatable concept class with polynomial query complexity can be learned in polynomial time with the help of an oracle in the polynomial hierarchy, where the complexity of the required oracle depends on the query-types used by the learning algorithm. In particular, we show that for subset and superset queries an oracle in Σ3P suffices. Since the concept class of DNF formulas has polynomial query complexity with respect to subset and superset queries with DNF formulas as hypotheses, it follows that DNF formulas are properly learnable in polynomial time with subset and superset queries and the help of an oracle in Σ3P. We also show that the required oracle in our main theorem cannot be replaced by an oracle in a lower level of the polynomial-time hierarchy, unless the hierarchy collapses. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.tcs.2005.10.016 | Theoretical Computer Science - Algorithmic learning theory(ALT 2002) |
Keywords | Field | DocType |
concept class,DNF formula,polynomial hierarchy,p-evaluatable concept class,Learning DNF formulas,superset query,Learning complexity,polynomial-time hierarchy,polynomial query complexity,polynomial general dimension,Polynomial-time hierarchy,Query learning,polynomial time,required oracle,hierarchy collapse | Polynomial hierarchy,Discrete mathematics,Structural complexity theory,Combinatorics,Concept class,Polynomial,Computer science,Oracle,NP-easy,Low,Time complexity | Journal |
Volume | Issue | ISSN |
350 | 1 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-00170-0 | 2 | 0.41 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Wolfgang Lindner | 2 | 23 | 3.38 |