How many queries are needed to learn?

Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any "honest" class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P ≠ NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Σ4p.

    Original languageEnglish (US)
    Pages (from-to)840-862
    Number of pages23
    JournalJournal of the ACM
    Volume43
    Issue number5
    DOIs
    StatePublished - Sep 1996

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Information Systems
    • Hardware and Architecture
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'How many queries are needed to learn?'. Together they form a unique fingerprint.

    Cite this