Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:452-465, 2017.
Abstract
Learning a target concept from a finite $n \times m$ concept space requires $\Omega{(n)}$ proper equivalence queries in the worst case. We propose a variation of the usual equivalence query in which the teacher is constrained to choose counterexamples randomly from a known probability distribution on examples. We present and analyze the Max-Min learning algorithm, which identifies an arbitrary target concept in an arbitrary finite $n \times m$ concept space using at most an expected $\log_2{n}$ proper equivalence queries with random counterexamples.
@InProceedings{pmlr-v76-angluin17a,
title = {The Power of Random Counterexamples},
author = {Dana Angluin and Tyler Dohrn},
booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory},
pages = {452--465},
year = {2017},
editor = {Steve Hanneke and Lev Reyzin},
volume = {76},
series = {Proceedings of Machine Learning Research},
address = {Kyoto University, Kyoto, Japan},
month = {15--17 Oct},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v76/angluin17a/angluin17a.pdf},
url = {http://proceedings.mlr.press/v76/angluin17a.html},
abstract = {Learning a target concept from a finite $n \times m$ concept space requires $\Omega{(n)}$ proper equivalence queries in the worst case. We propose a variation of the usual equivalence query in which the teacher is constrained to choose counterexamples randomly from a known probability distribution on examples. We present and analyze the Max-Min learning algorithm, which identifies an arbitrary target concept in an arbitrary finite $n \times m$ concept space using at most an expected $\log_2{n}$ proper equivalence queries with random counterexamples.}
}
%0 Conference Paper
%T The Power of Random Counterexamples
%A Dana Angluin
%A Tyler Dohrn
%B Proceedings of the 28th International Conference on Algorithmic Learning Theory
%C Proceedings of Machine Learning Research
%D 2017
%E Steve Hanneke
%E Lev Reyzin
%F pmlr-v76-angluin17a
%I PMLR
%J Proceedings of Machine Learning Research
%P 452--465
%U http://proceedings.mlr.press
%V 76
%W PMLR
%X Learning a target concept from a finite $n \times m$ concept space requires $\Omega{(n)}$ proper equivalence queries in the worst case. We propose a variation of the usual equivalence query in which the teacher is constrained to choose counterexamples randomly from a known probability distribution on examples. We present and analyze the Max-Min learning algorithm, which identifies an arbitrary target concept in an arbitrary finite $n \times m$ concept space using at most an expected $\log_2{n}$ proper equivalence queries with random counterexamples.
Angluin, D. & Dohrn, T.. (2017). The Power of Random Counterexamples. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in PMLR 76:452-465
This site last compiled Mon, 09 Apr 2018 09:37:13 +0000