The Power of Random Counterexamples
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.
Cite
Text
Angluin and Dohrn. "The Power of Random Counterexamples." Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017.Markdown
[Angluin and Dohrn. "The Power of Random Counterexamples." Proceedings of the 28th International Conference on Algorithmic Learning Theory, 2017.](https://mlanthology.org/alt/2017/angluin2017alt-power/)BibTeX
@inproceedings{angluin2017alt-power,
title = {{The Power of Random Counterexamples}},
author = {Angluin, Dana and Dohrn, Tyler},
booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory},
year = {2017},
pages = {452-465},
volume = {76},
url = {https://mlanthology.org/alt/2017/angluin2017alt-power/}
}