Oracles and Queries That Are Sufficient for Exact Learning (Extended Abstract)
Abstract
We show that the class of all circuits is exactly learnable in randomized expected polynomial-time using subset and superset queries. This is a consequence of the following result which we consider to be of independent interest: circuits are exactly learnable in randomized expected polynomial-time with equivalence queries and the aid of an NP-oracle. We also show that circuits are exactly learnable in deterministic polynomial-time with equivalence queries and a Σ3p-oracle. The hypothesis class for the above learning algorithms is the class of circuits of larger—but polynomially related—size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 Λ-V-Λ formulas (by the work of Angluin, this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas.
Cite
Text
Bshouty et al. "Oracles and Queries That Are Sufficient for Exact Learning (Extended Abstract)." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181067Markdown
[Bshouty et al. "Oracles and Queries That Are Sufficient for Exact Learning (Extended Abstract)." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/bshouty1994colt-oracles/) doi:10.1145/180139.181067BibTeX
@inproceedings{bshouty1994colt-oracles,
title = {{Oracles and Queries That Are Sufficient for Exact Learning (Extended Abstract)}},
author = {Bshouty, Nader H. and Cleve, Richard and Kannan, Sampath and Tamon, Christino},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {130-139},
doi = {10.1145/180139.181067},
url = {https://mlanthology.org/colt/1994/bshouty1994colt-oracles/}
}