Exact Learning from Membership Queries: Some Techniques, Results and New Directions
Abstract
Given a black box that contains a function f : D → R from some class of functions C . The black box can receive an element d (query) of the domain D and in time T returns the value f ( d ) ∈ R . Our goal is to exactly find (exactly learn) f with minimum number of queries and optimal time complexity. Or at least decide whether f ≡ 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 survey 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.
Cite
Text
Bshouty. "Exact Learning from Membership Queries: Some Techniques, Results and New Directions." International Conference on Algorithmic Learning Theory, 2013. doi:10.1007/978-3-642-40935-6_4Markdown
[Bshouty. "Exact Learning from Membership Queries: Some Techniques, Results and New Directions." International Conference on Algorithmic Learning Theory, 2013.](https://mlanthology.org/alt/2013/bshouty2013alt-exact/) doi:10.1007/978-3-642-40935-6_4BibTeX
@inproceedings{bshouty2013alt-exact,
title = {{Exact Learning from Membership Queries: Some Techniques, Results and New Directions}},
author = {Bshouty, Nader H.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2013},
pages = {33-52},
doi = {10.1007/978-3-642-40935-6_4},
url = {https://mlanthology.org/alt/2013/bshouty2013alt-exact/}
}