Loading...
Please wait, while we are loading the content...
Similar Documents
Oracles in ... are Sufficient for Exact Learning (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Köbler, Johannes Lindner, Wolfgang |
| Description | . We consider representation classes of polynomial query complexity in Angluin's exact learning model with all three possible combinations of membership and (proper) equivalence queries allowed. We show that in all three cases, polynomial query complexity implies already polynomial-time learnability where the learner additionally has access to an oracle in \Sigma p 2 . As an application, it follows that boolean circuits are polynomial-time learnable with equivalence queries and the help of an oracle in \Sigma p 2 . Our results are based on known combinatorial properties characterizing polynomial query complexity and a careful application of hashing-techniques. 1 Introduction When considering efficient learning notions two questions arise immediately. First, one may ask for the combinatorial, or information-theoretic complexity of the concept classes learnable in the model when no resource bounds on the learner are involved. Second, one may consider the computational complexity of ... |
| File Format | |
| Language | English |
| Publisher | Springer |
| Publisher Date | 1997-01-01 |
| Publisher Institution | In Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence |
| Access Restriction | Open |
| Subject Keyword | Polynomial-time Learnability Exact Learning Information-theoretic Complexity Boolean Circuit Possible Combination Combinatorial Property Polynomial Query Complexity Implies Polynomial Query Complexity Equivalence Query Representation Class Careful Application Computational Complexity |
| Content Type | Text |
| Resource Type | Article |
