On the Power and Limits of Distance-Based Learning

Periklis Papakonstantinou, Jia Xu, Guang Yang
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2263-2271, 2016.

Abstract

We initiate the study of low-distortion finite metric embeddings in multi-class (and multi-label) classification where (i) both the space of input instances and the space of output classes have combinatorial metric structure and (ii) the concepts we wish to learn are low-distortion embeddings. We develop new geometric techniques and prove strong learning lower bounds. These provable limits hold even when we allow learners and classifiers to get advice by one or more experts. Our study overwhelmingly indicates that post-geometry assumptions are necessary in multi-class classification, as in natural language processing (NLP). Technically, the mathematical tools we developed in this work could be of independent interest to NLP. To the best of our knowledge, this is the first work which formally studies classification problems in combinatorial spaces. and where the concepts are low-distortion embeddings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-papakonstantinou16, title = {On the Power and Limits of Distance-Based Learning}, author = {Papakonstantinou, Periklis and Xu, Jia and Yang, Guang}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2263--2271}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/papakonstantinou16.pdf}, url = {https://proceedings.mlr.press/v48/papakonstantinou16.html}, abstract = {We initiate the study of low-distortion finite metric embeddings in multi-class (and multi-label) classification where (i) both the space of input instances and the space of output classes have combinatorial metric structure and (ii) the concepts we wish to learn are low-distortion embeddings. We develop new geometric techniques and prove strong learning lower bounds. These provable limits hold even when we allow learners and classifiers to get advice by one or more experts. Our study overwhelmingly indicates that post-geometry assumptions are necessary in multi-class classification, as in natural language processing (NLP). Technically, the mathematical tools we developed in this work could be of independent interest to NLP. To the best of our knowledge, this is the first work which formally studies classification problems in combinatorial spaces. and where the concepts are low-distortion embeddings.} }
Endnote
%0 Conference Paper %T On the Power and Limits of Distance-Based Learning %A Periklis Papakonstantinou %A Jia Xu %A Guang Yang %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-papakonstantinou16 %I PMLR %P 2263--2271 %U https://proceedings.mlr.press/v48/papakonstantinou16.html %V 48 %X We initiate the study of low-distortion finite metric embeddings in multi-class (and multi-label) classification where (i) both the space of input instances and the space of output classes have combinatorial metric structure and (ii) the concepts we wish to learn are low-distortion embeddings. We develop new geometric techniques and prove strong learning lower bounds. These provable limits hold even when we allow learners and classifiers to get advice by one or more experts. Our study overwhelmingly indicates that post-geometry assumptions are necessary in multi-class classification, as in natural language processing (NLP). Technically, the mathematical tools we developed in this work could be of independent interest to NLP. To the best of our knowledge, this is the first work which formally studies classification problems in combinatorial spaces. and where the concepts are low-distortion embeddings.
RIS
TY - CPAPER TI - On the Power and Limits of Distance-Based Learning AU - Periklis Papakonstantinou AU - Jia Xu AU - Guang Yang BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-papakonstantinou16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2263 EP - 2271 L1 - http://proceedings.mlr.press/v48/papakonstantinou16.pdf UR - https://proceedings.mlr.press/v48/papakonstantinou16.html AB - We initiate the study of low-distortion finite metric embeddings in multi-class (and multi-label) classification where (i) both the space of input instances and the space of output classes have combinatorial metric structure and (ii) the concepts we wish to learn are low-distortion embeddings. We develop new geometric techniques and prove strong learning lower bounds. These provable limits hold even when we allow learners and classifiers to get advice by one or more experts. Our study overwhelmingly indicates that post-geometry assumptions are necessary in multi-class classification, as in natural language processing (NLP). Technically, the mathematical tools we developed in this work could be of independent interest to NLP. To the best of our knowledge, this is the first work which formally studies classification problems in combinatorial spaces. and where the concepts are low-distortion embeddings. ER -
APA
Papakonstantinou, P., Xu, J. & Yang, G.. (2016). On the Power and Limits of Distance-Based Learning. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2263-2271 Available from https://proceedings.mlr.press/v48/papakonstantinou16.html.

Related Material