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 = {Gao, Ziyuan and Kirkpatrick, David and Ries, Christoph and Simon, Hans and Zilles, Sandra}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {185--207}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/gao17a/gao17a.pdf}, url = {https://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 %P 185--207 %U https://proceedings.mlr.press/v76/gao17a.html %V 76 %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 Proceedings of Machine Learning Research 76:185-207 Available from https://proceedings.mlr.press/v76/gao17a.html.

Related Material