Bounds in query learning

Hunter Chase, James Freitag
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1142-1160, 2020.

Abstract

We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of learning in terms of various combinatorial quantities. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. Our approach is flexible and powerful enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular $\omega$-languages), in some cases also producing new bounds on the number of queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-chase20a, title = {Bounds in query learning}, author = {Chase, Hunter and Freitag, James}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1142--1160}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/chase20a/chase20a.pdf}, url = {https://proceedings.mlr.press/v125/chase20a.html}, abstract = { We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of learning in terms of various combinatorial quantities. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. Our approach is flexible and powerful enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular $\omega$-languages), in some cases also producing new bounds on the number of queries.} }
Endnote
%0 Conference Paper %T Bounds in query learning %A Hunter Chase %A James Freitag %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-chase20a %I PMLR %P 1142--1160 %U https://proceedings.mlr.press/v125/chase20a.html %V 125 %X We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of learning in terms of various combinatorial quantities. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. Our approach is flexible and powerful enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular $\omega$-languages), in some cases also producing new bounds on the number of queries.
APA
Chase, H. & Freitag, J.. (2020). Bounds in query learning. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1142-1160 Available from https://proceedings.mlr.press/v125/chase20a.html.

Related Material