University of Illinois Chicago
Browse

Bounds in query learning

Download (343.67 kB)
journal contribution
posted on 2021-04-17, 20:58 authored by James FreitagJames Freitag, Hunter Chase
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ω-languages), in some cases also producing new bounds on the number of queries.

Funding

CAREER: Applied Model Theory

Directorate for Mathematical & Physical Sciences

Find out more...

Model Theory and Differential Equations

Directorate for Mathematical & Physical Sciences

Find out more...

History

Citation

Freitag, J.Chase, H. (2020). Bounds in query learning. Proceedings of Thirty Third Conference on Learning Theory, PMLR, 125, 1142-1160.

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC