Timezone: »

 
Poster
On Batch Teaching with Sample Complexity Bounded by VCD
Farnam Mansouri · Hans Simon · Adish Singla · Sandra Zilles

@

In machine teaching, a concept is represented by (and inferred from) a small number of labeled examples. Various teaching models in the literature cast the interaction between teacher and learner in a way to obtain a small complexity (in terms of the number of examples required for teaching a concept) while obeying certain constraints that are meant to prevent unfair collusion between teacher and learner. In recent years, one major research goal has been to show interesting relationships between teaching complexity and the VC-dimension (VCD). So far, the only interesting relationship known from batch teaching settings is an upper bound quadratic in the VCD, on a parameter called recursive teaching dimension. The only known upper bound on teaching complexity that is linear in VCD was obtained in a model of teaching with sequences rather than batches.This paper is the first to provide an upper bound of VCD on a batch teaching complexity parameter. This parameter, called STDmin, is introduced here as a model of teaching that intuitively incorporates a notion of ``importance'' of an example for a concept. In designing the STDmin teaching model, we argue that the standard notion of collusion-freeness from the literature may be inadequate for certain applications; we hence propose three desirable properties of teaching complexity and demonstrate that they are satisfied by STDmin.

Keywords: Collusion-Freeness · Machine Teaching · VC Dimension
[ Paper]  [ Slides]  [ Poster]  [ OpenReview] 

Author Information

Farnam Mansouri (University of Toronto)
Hans Simon (Max-Planck Institute)
Hans Simon

1978: Diploma (roughly equivalent to Masters) in Mathematics (Univ. of Saarbrücken) 1981: Doctor's degree in Computer Science (Univ. of Saarbrücken) 1989: "Habilitation degree" (Univ. of Saarbrücken) 1979-1989: Research Assistant at the Computer Science Department of the University of Saarbrücken 87/88: Temporary Professor Position at the Univ. of Darmstadt 89: Temporary Professor Position at the Univ. of Dortmund 89: Temporary Professor Position at the Univ. of Saarbrücken 1990-1997: Professor (tenured) at the Univ. of Dortmund 1997-2020: Professor (tenured) at the Ruhr-University-Bochum since August: 2020 Professor im Ruhestand (Emeritus) For more detailed information see: https://www.ruhr-uni-bochum.de/lmi/simon/work/cv.html

Adish Singla (MPI-SWS)
Sandra Zilles (zilles@cs.uregina.ca)

More from the Same Authors