A Caltech Library Service

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

Chen, Yuxin and Singla, Adish and Mac Aodha, Oisin and Perona, Pietro and Yue, Yisong (2018) Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners. In: Advances in Neural Information Processing Systems 31 (NIPS 2018). Advances in Neural Information Processing Systems. No.31. Curran Associates , Red Hook, NY, pp. 1-11.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 up the teaching process when considering existing models of version space learners, such as "worst-case" (the learner picks the next hypothesis randomly from the version space) and "preference-based" (the learner picks hypothesis according to some global preference). Inspired by human teaching, we propose a new model where the learner picks hypotheses according to some local preference defined by the current hypothesis. We show that our model exhibits several desirable properties, e.g., adaptivity plays a key role, and the learner's transitions over hypotheses are smooth/interpretable. We develop efficient teaching algorithms and demonstrate our results via simulation and user studies.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Mac Aodha, Oisin0000-0002-5787-5073
Perona, Pietro0000-0002-7583-5809
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2018 Neural Information Processing Systems Foundation, Inc. This work was supported in part by Northrop Grumman, Bloomberg, AWS Research Credits, Google as part of the Visipedia project, and a Swiss NSF Early Mobility Postdoctoral Fellowship.
Funding AgencyGrant Number
Northrop Grumman CorporationUNSPECIFIED
Amazon Web ServicesUNSPECIFIED
Swiss National Science Foundation (SNSF)UNSPECIFIED
Series Name:Advances in Neural Information Processing Systems
Issue or Number:31
Record Number:CaltechAUTHORS:20180613-144817832
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87081
Deposited By: Caroline Murphy
Deposited On:13 Jun 2018 22:21
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page