Paper Info
Title
Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
Abstract
Algorithmic machine teaching studies the interaction between a teacher and a learner where the teacher selects labeled examples aiming at teaching a target hypothesis. In a quest to lower teaching complexity and to achieve more natural teacher-learner interactions, several teaching models and complexity measures have been proposed for both the batch settings (e.g., worst-case, recursive, preferencebased, and non-clashing models) as well as the sequential settings (e.g., local preference-based model). To better understand the connections between these different batch and sequential models, we develop a novel framework which captures the teaching process via preference functions Sigma. In our framework, each function sigma is an element of Sigma induces a teacher-learner pair with teaching complexity as TD(sigma). We show that the above-mentioned teaching models are equivalent to specific types/families of preference functions in our framework. This equivalence, in turn, allows us to study the differences between two important teaching models, namely sigma functions inducing the strongest batch (i.e., non-clashing) model and sigma functions inducing a weak sequential (i.e., local preference-based) model. Finally, we identify preference functions inducing a novel family of sequential models with teaching complexity linear in the VC dimension of the hypothesis class: this is in contrast to the best known complexity result for the batch models which is quadratic in the VC dimension.
Year
Venue
Keywords
2019
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019)
vc-dimension
Field
DocType
Volume
Computer science,Artificial intelligence,Machine learning
Conference
32
ISSN
Citations 
PageRank 
1049-5258
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Mansouri, Farnam101.01
Yuxin Chen28510.59
Ara Vartanian300.68
Xiaojin Zhu43586222.74
Adish Singla539733.45