Pairwise Supervision Can Provably Elicit a Decision Boundary

Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, Masashi Sugiyama
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:2618-2640, 2022.

Abstract

Similarity learning is a general problem to elicit useful representations by predicting the relationship between a pair of patterns. This problem is related to various important preprocessing tasks such as metric learning, kernel learning, and contrastive learning. A classifier built upon the representations is expected to perform well in downstream classification; however, little theory has been given in literature so far and thereby the relationship between similarity and classification has remained elusive. Therefore, we tackle a fundamental question: can similarity information provably leads a model to perform well in downstream classification? In this paper, we reveal that a product-type formulation of similarity learning is strongly related to an objective of binary classification. We further show that these two different problems are explicitly connected by an excess risk bound. Consequently, our results elucidate that similarity learning is capable of solving binary classification by directly eliciting a decision boundary.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-bao22a, title = { Pairwise Supervision Can Provably Elicit a Decision Boundary }, author = {Bao, Han and Shimada, Takuya and Xu, Liyuan and Sato, Issei and Sugiyama, Masashi}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2618--2640}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/bao22a/bao22a.pdf}, url = {https://proceedings.mlr.press/v151/bao22a.html}, abstract = { Similarity learning is a general problem to elicit useful representations by predicting the relationship between a pair of patterns. This problem is related to various important preprocessing tasks such as metric learning, kernel learning, and contrastive learning. A classifier built upon the representations is expected to perform well in downstream classification; however, little theory has been given in literature so far and thereby the relationship between similarity and classification has remained elusive. Therefore, we tackle a fundamental question: can similarity information provably leads a model to perform well in downstream classification? In this paper, we reveal that a product-type formulation of similarity learning is strongly related to an objective of binary classification. We further show that these two different problems are explicitly connected by an excess risk bound. Consequently, our results elucidate that similarity learning is capable of solving binary classification by directly eliciting a decision boundary. } }
Endnote
%0 Conference Paper %T Pairwise Supervision Can Provably Elicit a Decision Boundary %A Han Bao %A Takuya Shimada %A Liyuan Xu %A Issei Sato %A Masashi Sugiyama %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-bao22a %I PMLR %P 2618--2640 %U https://proceedings.mlr.press/v151/bao22a.html %V 151 %X Similarity learning is a general problem to elicit useful representations by predicting the relationship between a pair of patterns. This problem is related to various important preprocessing tasks such as metric learning, kernel learning, and contrastive learning. A classifier built upon the representations is expected to perform well in downstream classification; however, little theory has been given in literature so far and thereby the relationship between similarity and classification has remained elusive. Therefore, we tackle a fundamental question: can similarity information provably leads a model to perform well in downstream classification? In this paper, we reveal that a product-type formulation of similarity learning is strongly related to an objective of binary classification. We further show that these two different problems are explicitly connected by an excess risk bound. Consequently, our results elucidate that similarity learning is capable of solving binary classification by directly eliciting a decision boundary.
APA
Bao, H., Shimada, T., Xu, L., Sato, I. & Sugiyama, M.. (2022). Pairwise Supervision Can Provably Elicit a Decision Boundary . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:2618-2640 Available from https://proceedings.mlr.press/v151/bao22a.html.

Related Material