|
Author: Nader H. Bshouty
Affiliation:
Computer Science Department
Technion - Israel Institute of Technology
Haifa, Israel
Abstract.
Given a black box that contains a function ƒ: D → R 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 g ∈ C.
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
|