Timezone: »

 
Poster
Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
Farnam Mansouri · Yuxin Chen · Ara Vartanian · Jerry Zhu · Adish Singla

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #229
in Theory -- Learning Theory »
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, preference-based, 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 \in \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.
Keywords: Learning Theory · Theory
[ Paper]  [ Poster] 

Author Information

Farnam Mansouri (MPI-SWS)
Yuxin Chen (UChicago)
Ara Vartanian (University of Wisconsin -- Madison)
Jerry Zhu (University of Wisconsin-Madison)
Adish Singla (MPI-SWS)

More from the Same Authors