Preference-based Teaching of Unions of Geometric Objects

Ziyuan Gao, David Kirkpatrick, Christoph Ries, Hans Simon, Sandra Zilles
; Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:185-207, 2017.

Abstract

This paper studies exact learning of unions of non-discretized geometric concepts in the model of preference-based teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preference-based teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types -- for instance balls, axis-aligned cubes, or axis-aligned 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v76-gao17a, title = {Preference-based Teaching of Unions of Geometric Objects}, author = {Ziyuan Gao and David Kirkpatrick and Christoph Ries and Hans Simon and Sandra Zilles}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {185--207}, year = {2017}, editor = {Steve Hanneke and Lev Reyzin}, volume = {76}, series = {Proceedings of Machine Learning Research}, address = {Kyoto University, Kyoto, Japan}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/gao17a/gao17a.pdf}, url = {http://proceedings.mlr.press/v76/gao17a.html}, abstract = {This paper studies exact learning of unions of non-discretized geometric concepts in the model of preference-based teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preference-based teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types -- for instance balls, axis-aligned cubes, or axis-aligned 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.} }
Endnote
%0 Conference Paper %T Preference-based Teaching of Unions of Geometric Objects %A Ziyuan Gao %A David Kirkpatrick %A Christoph Ries %A Hans Simon %A Sandra Zilles %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-gao17a %I PMLR %J Proceedings of Machine Learning Research %P 185--207 %U http://proceedings.mlr.press %V 76 %W PMLR %X This paper studies exact learning of unions of non-discretized geometric concepts in the model of preference-based teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preference-based teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types -- for instance balls, axis-aligned cubes, or axis-aligned 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.
APA
Gao, Z., Kirkpatrick, D., Ries, C., Simon, H. & Zilles, S.. (2017). Preference-based Teaching of Unions of Geometric Objects. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in PMLR 76:185-207

Related Material