Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
Abstract
We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the learning-with-equivalence-queries (LwEQ) paradigm. More concretely, we consider a learner who asks equivalence queries (i.e., "is the queried hypothesis the target hypothesis?"), and a teacher responds either "yes" or "no" along with a counterexample to the queried hypothesis. This learning paradigm has been extensively studied when the learner receives worst-case or random counterexamples; in this paper, we consider the optimal teacher who picks best-case counterexamples to teach the target hypothesis within a hypothesis class. For this optimal teacher, we introduce LwEQ-TD, a notion of TD capturing the teaching complexity (i.e., the number of queries made) in this paradigm. We show that a significant reduction in queries can be achieved with best-case counterexamples, in contrast to worst-case or random counterexamples, for different hypothesis classes. Furthermore, we establish new connections of LwEQ-TD to the well-studied notions of TD in the learning-from-samples paradigm.
Cite
Text
Kumar et al. "Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm." Neural Information Processing Systems, 2021.Markdown
[Kumar et al. "Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/kumar2021neurips-teaching/)BibTeX
@inproceedings{kumar2021neurips-teaching,
title = {{Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm}},
author = {Kumar, Akash and Chen, Yuxin and Singla, Adish},
booktitle = {Neural Information Processing Systems},
year = {2021},
url = {https://mlanthology.org/neurips/2021/kumar2021neurips-teaching/}
}