[edit]
The Power of Random Counterexamples
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:452-465, 2017.
Abstract
Learning a target concept from a finite n×m concept space requires Ω(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×m concept space using at most an expected log2n proper equivalence queries with random counterexamples.