Exact Learning from an Honest Teacher That Answers Membership Queries
It provides a comprehensive overview for researchers in computational learning theory, but is incremental as it surveys existing literature.
This survey compiles known results, techniques, and open problems in exact learning from a teacher that answers membership queries, focusing on minimizing queries, time complexity, and resources to identify a function.
Given a teacher that holds a function $f:X\to R$ from some class of functions $C$. The teacher can receive from the learner an element~$d$ in the domain $X$ (a query) and returns the value of the function in $d$, $f(d)\in R$. The learner goal is to find $f$ with a minimum number of queries, optimal time complexity, and optimal resources. In this survey, we present some of the results known from the literature, different techniques used, some new problems, and open problems.