Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners

Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, Yisong Yue

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In real-world applications of education, an effective teacher adaptively chooses the next example to teach based on the learner’s current state. However, most existing work in algorithmic machine teaching focuses on the batch setting, where adaptivity plays no role. In this paper, we study the case of teaching consistent, version space learners in an interactive setting. At any time step, the teacher provides an example, the learner performs an update, and the teacher observes the learner’s new state. We highlight that adaptivity does not speed upthe teaching process when considering existing models of version space learners,such as the “worst-case” model (the learner picks the next hypothesis randomlyfrom the version space) and the “preference-based” model (the learner pickshypothesis according to some global preference). Inspired by human teaching, wepropose a new model where the learner picks hypotheses according to some localpreference defined by the current hypothesis. We show that our model exhibitsseveral desirable properties, e.g., adaptivity plays a key role, and the learner’stransitions over hypotheses are smooth/interpretable. We develop adaptive teachingalgorithms, and demonstrate our results via simulation and user studies.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 31
EditorsS. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett
PublisherNeural Information Processing Systems
Number of pages11
Publication statusPublished - 8 Dec 2018
EventThirty-second Conference on Neural Information Processing Systems (NeurIPS): NeurIPS -
Duration: 2 Dec 20188 Dec 2018


ConferenceThirty-second Conference on Neural Information Processing Systems (NeurIPS)
Internet address


Dive into the research topics of 'Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners'. Together they form a unique fingerprint.

Cite this