Oracles in Sigmap2 Are Sufficient for Exact Learning
Abstract
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 Σ _2 ^p . As an application, it follows that boolean circuits are polynomial-time learnable with equivalence queries and the help of an oracle in Σ _2 ^p . Our results are based on known combinatorial properties characterizing polynomial query complexity and a careful application of hashing-techniques.
Cite
Text
Köbler and Lindner. "Oracles in Sigmap2 Are Sufficient for Exact Learning." International Conference on Algorithmic Learning Theory, 1997. doi:10.1007/3-540-63577-7_49Markdown
[Köbler and Lindner. "Oracles in Sigmap2 Are Sufficient for Exact Learning." International Conference on Algorithmic Learning Theory, 1997.](https://mlanthology.org/alt/1997/kobler1997alt-oracles/) doi:10.1007/3-540-63577-7_49BibTeX
@inproceedings{kobler1997alt-oracles,
title = {{Oracles in Sigmap2 Are Sufficient for Exact Learning}},
author = {Köbler, Johannes and Lindner, Wolfgang},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1997},
pages = {277-290},
doi = {10.1007/3-540-63577-7_49},
url = {https://mlanthology.org/alt/1997/kobler1997alt-oracles/}
}