Preferencebased Teaching of Unions of Geometric Objects
[edit]
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:185207, 2017.
Abstract
This paper studies exact learning of unions of nondiscretized geometric concepts in the model of preferencebased teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preferencebased teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types  for instance balls, axisaligned cubes, or axisaligned boxes  in arbitrary dimensions. It is shown that the PBTD of disjoint unions of some such types of concepts grows linearly with the number of concepts in the union, independent of the dimensionality. Teaching the union of potentially overlapping objects turns out to be more involved and is hence considered here only for unions of up to two objects.
Related Material


