Name
Abstract | ||
|---|---|---|
Most theories of learning consider inferring a functionf from either (1) observations aboutf or, (2) questions aboutf. We consider a scenario whereby thelearner observes f and asks queriesto some set A.EX[A] is the set of concept classesEX-learnable by an inductiveinference machine with oracle A.A andF areEX-equivalent ifEX[A] = EX[B]. The equivalenceclasses induced are the degrees ofinferability. We prove several results about thesedegrees: (1) There are an uncountable number of degrees. (2) ForA r.e., REC &egr; BC[A] iff &0slash;&huml; ≤TA´, and there is evidence thisholds for all sets A. (3) ForA, B r.e.,A ≡T BiffEX[A] = EX[B]. (4) There existsA, B low2 r.e.,A|RB,EX[A] = EX[B]. (hence (3) isoptimal). |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1145/130385.130406 | COLT |
Keywords | DocType | ISBN |
concept classesex-learnable,degrees ofinferability,b low2,observations aboutf,oracle a,uncountable number,evidence thisholds,andf areex-equivalent ifex,questions aboutf,inductiveinference machine,theories of learning | Conference | 0-89791-497-X |
Citations | PageRank | References |
7 | 0.64 | 5 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Cholak | 1 | 150 | 21.26 |
| Efim Kinber | 2 | 421 | 44.95 |
| Rodney G. Downey | 3 | 2082 | 207.92 |
| Martin Kummer | 4 | 115 | 7.55 |
| Lance Fortnow | 5 | 2788 | 352.32 |
| Stuart Kurtz | 6 | 37 | 1.82 |
| William Gasarch | 7 | 204 | 24.83 |
| Theodore A. Slaman | 8 | 265 | 45.05 |