Exact Learning from Membership Queries
Some Techniques, Results and New Directions

(tutorial lecture for ALT 2013)

Author: Nader H. Bshouty

Affiliation: Computer Science Department
Technion - Israel Institute of Technology
Haifa, Israel

Abstract. Given a black box that contains a function ƒ: DR from some class of functions C. The black box can receive an element d of the domain D and in time T returns the value ƒ(d)∈R. Our goal is to exactly find (learn) ƒ with minimum number of queries and optimal time complexity. Or at least decide whether ƒ ≡ g for some function gC.

This problem has different names in different areas: Interpolation, Exactly Learning, Inferring, Identifying, Active Learning, Guessing Game, Testing, Functional Verification, Hitting Set and Black Box PIT from Substitution or Membership Queries.

In this tutorial we give some of the results known from the literature, different techniques used mainly for the problem of exact learning and new directions that we think are worth investigating.

©Copyright Author
Valid HTML 4.1