{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T01:31:06Z","timestamp":1775266266631,"version":"3.50.1"},"reference-count":48,"publisher":"MIT Press","issue":"5","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,4,13]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Pairwise similarities and dissimilarities between data points are often obtained more easily than full labels of data in real-world classification problems. To make use of such pairwise information, an empirical risk minimization approach has been proposed, where an unbiased estimator of the classification risk is computed from only pairwise similarities and unlabeled data. However, this approach has not yet been able to handle pairwise dissimilarities. Semisupervised clustering methods can incorporate both similarities and dissimilarities into their framework; however, they typically require strong geometrical assumptions on the data distribution such as the manifold assumption, which may cause severe performance deterioration. In this letter, we derive an unbiased estimator of the classification risk based on all of similarities and dissimilarities and unlabeled data. We theoretically establish an estimation error bound and experimentally demonstrate the practical usefulness of our empirical risk minimization method.<\/jats:p>","DOI":"10.1162\/neco_a_01373","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:17:58Z","timestamp":1614039478000},"page":"1234-1268","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":21,"title":["Classification From Pairwise Similarities\/Dissimilarities and Unlabeled Data via Empirical Risk Minimization"],"prefix":"10.1162","volume":"33","author":[{"given":"Takuya","family":"Shimada","sequence":"first","affiliation":[{"name":"University of Tokyo, Bunkyo-ku, Tokyo, 113-0333, Japan, and RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo 103-0027, Japan shima@ms.k.u-tokyo.ac.jp"}]},{"given":"Han","family":"Bao","sequence":"additional","affiliation":[{"name":"University of Tokyo, Bunkyo-ku, Tokyo, 113-0333, Japan, and RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo 103-0027, Japan tsutsumi@ms.k.u-tokyo.ac.jp"}]},{"given":"Issei","family":"Sato","sequence":"additional","affiliation":[{"name":"University of Tokyo, Bunkyo-ku, Tokyo, 113-0333, Japan, and RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo 103-0027, Japan issei.sato@is.s.u-tokyo.ac.jp"}]},{"given":"Masashi","family":"Sugiyama","sequence":"additional","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Project, Chuo-ku, Tokyo 103-0027, Japan, and University of Tokyo, Bunkyo-ku, Tokyo, 113-0333, Japan sugi@k.u-tokyo.ac.jp"}]}],"member":"281","published-online":{"date-parts":[[2021,4,13]]},"reference":[{"key":"2021041321534607500_B1","article-title":"A theoretical analysis of contrastive unsupervised representation learning.","author":"Arora","year":"2019","journal-title":"Proceedings of the 36th International Conference on Machine Learning"},{"key":"2021041321534607500_B2","first-page":"452","article-title":"Classification from pairwise similarity and unlabeled data","author":"Bao","year":"2018","journal-title":"Proceedings of the 35th International Conference on Machine Learning"},{"key":"2021041321534607500_B3","author":"Bao","year":"2020","journal-title":"Similarity-based classification: Connecting similarity learning to binary classification"},{"key":"2021041321534607500_B4","first-page":"27","article-title":"Semi-supervised clustering by seeding","author":"Basu","year":"2002","journal-title":"Proceedings of 19th International Conference on Machine Learning"},{"key":"2021041321534607500_B5","doi-asserted-by":"crossref","DOI":"10.1201\/9781584889977","author":"Basu","year":"2008","journal-title":"Constrained clustering: Advances in algorithms, theory, and applications"},{"key":"2021041321534607500_B6","first-page":"839","article-title":"Integrating constraints and metric learning in semi-supervised clustering","author":"Bilenko","year":"2004","journal-title":"Proceedings of the 21st International Conference on Machine Learning"},{"key":"2021041321534607500_B7","doi-asserted-by":"crossref","DOI":"10.1145\/1961189.1961199","article-title":"LIBSVM: A library for support vector machines.","author":"Chang","year":"2011,","journal-title":"ACM Transactions on Intelligent Systems and Technology"},{"key":"2021041321534607500_B8","author":"Chapelle","year":"2010","journal-title":"Semi-supervised learning"},{"key":"2021041321534607500_B9","first-page":"961","article-title":"On symmetric losses for learning from corrupted labels","author":"Charoenphakdee","year":"2019","journal-title":"Proceedings of the 36th International Conference on Machine Learning"},{"key":"2021041321534607500_B10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.neucom.2011.09.002","article-title":"Spectral clustering: A semi-supervised approach","volume":"77","author":"Chen","year":"2012","journal-title":"Neurocomputing"},{"key":"2021041321534607500_B11","first-page":"3447","volume-title":"Advances in neural information processing systems","author":"Chiang","year":"2015"},{"key":"2021041321534607500_B12","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1109\/CVPR.2005.202","article-title":"Learning a similarity metric discriminatively, with application to face verification","author":"Chopra","year":"2005","journal-title":"Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition"},{"issue":"3","key":"2021041321534607500_B13","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1162\/neco_a_01262","article-title":"Classification from triplet comparison data","volume":"32","author":"Cui","year":"2020","journal-title":"Neural Computation"},{"key":"2021041321534607500_B14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/1273496.1273523","article-title":"Information-theoretic metric learning.","author":"Davis","year":"2007","journal-title":"Proceedings of the 24th International Conference on Machine Learning"},{"key":"2021041321534607500_B15","first-page":"703","volume-title":"Advances in neural information processing systems","author":"Plessis","year":"2014"},{"key":"2021041321534607500_B16","first-page":"1386","article-title":"Convex formulation for learning from positive and unlabeled data","author":"du Plessis","year":"2015","journal-title":"Proceedings of the 32nd International Conference on Machine Learning"},{"key":"2021041321534607500_B17","author":"Dua","year":"2017","journal-title":"UCI machine learning repository"},{"key":"2021041321534607500_B18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.neucom.2014.09.081","article-title":"Making risk minimization tolerant to label noise","volume":"160","author":"Ghosh","year":"2015","journal-title":"Neurocomputing"},{"key":"2021041321534607500_B19","doi-asserted-by":"crossref","first-page":"1735","DOI":"10.1109\/CVPR.2006.100","article-title":"Dimensionality reduction by learning an invariant mapping","author":"Hadsell","year":"2006","journal-title":"Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition"},{"key":"2021041321534607500_B20","article-title":"Learning deep representations by mutual information estimation and maximization","author":"Hjelm","year":"2019","journal-title":"Proceedings of the International Conference on Learning Representations"},{"key":"2021041321534607500_B21","article-title":"Multi-class classification without multi-class labels","author":"Hsu","year":"2019","journal-title":"Proceedings of the International Conference on Learning Representations"},{"key":"2021041321534607500_B22","first-page":"253","article-title":"Maximum margin clustering with pairwise constraints","author":"Hu","year":"2008","journal-title":"Proceedings of the Eighth IEEE International Conference on Data Mining"},{"key":"2021041321534607500_B23","first-page":"5917","volume-title":"Advances in neural information processing systems","author":"Ishida","year":"2018"},{"key":"2021041321534607500_B24","first-page":"3294","volume-title":"Advances in neural information processing systems","author":"Kiros","year":"2015"},{"key":"2021041321534607500_B25","first-page":"307","article-title":"From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering","author":"Klein","year":"2002","journal-title":"Proceedings of the 19th International Conference on Machine Learning"},{"key":"2021041321534607500_B26","first-page":"421","article-title":"Constrained clustering by spectral kernel learning","author":"Li","year":"2009","journal-title":"Proceedings of the IEEE 12th International Conference on Computer Vision"},{"key":"2021041321534607500_B27","article-title":"An efficient framework for learning sentence representations","author":"Logeswaran","year":"2018","journal-title":"Proceedings of the International Conference on Learning Representations"},{"key":"2021041321534607500_B28","article-title":"On the minimal supervision for training any binary classifier from only unlabeled data","author":"Lu","year":"2019","journal-title":"International Conference on Learning Representations"},{"key":"2021041321534607500_B29","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","author":"MacQueen","year":"1967","journal-title":"Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability"},{"key":"2021041321534607500_B30","first-page":"3111","volume-title":"Advances in neural information processing systems","author":"Mikolov","year":"2013"},{"key":"2021041321534607500_B31","author":"Mohri","year":"2012","journal-title":"Foundations of machine learning"},{"issue":"3","key":"2021041321534607500_B32","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1002\/ejsp.2420150303","article-title":"Methods of coping with social desirability bias: A review","volume":"15","author":"Nederhof","year":"1985","journal-title":"European Journal of Social Psychology"},{"key":"2021041321534607500_B33","first-page":"89","article-title":"Information-theoretic semisupervised metric learning via entropy regularization","author":"Niu","year":"2012"},{"issue":"1","key":"2021041321534607500_B34","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02883985","article-title":"Some inequalities relating to the partial sum of binomial probabilities","volume":"10","author":"Okamoto","year":"1959","journal-title":"Annals of the Institute of Statistical Mathematics"},{"key":"2021041321534607500_B35","author":"Oord","year":"2018","journal-title":"Representation learning with contrastive predictive coding"},{"key":"2021041321534607500_B36","first-page":"708","article-title":"Loss factorization, weakly supervised learning and label noise robustness","author":"Patrini","year":"2016","journal-title":"Proceedings of the 33rd International Conference on Machine Learning"},{"key":"2021041321534607500_B37","first-page":"2227","article-title":"Deep contextualized word representations","author":"Peters","year":"2018","journal-title":"Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies"},{"key":"2021041321534607500_B38","first-page":"2998","article-title":"Semi-supervised classification based on classification from positive and unlabeled data","author":"Sakai","year":"2017"},{"key":"2021041321534607500_B39","first-page":"815","article-title":"Facenet: A unified embedding for face recognition and clustering","author":"Schroff","year":"2015","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"2021041321534607500_B40","first-page":"1857","volume-title":"Advances in neural information processing systems","author":"Sohn","year":"2016"},{"key":"2021041321534607500_B41","first-page":"577","article-title":"Constrained K-means clustering with background knowledge","author":"Wagstaff","year":"2001","journal-title":"Proceedings of the 18th International Conference on Machine Learning"},{"key":"2021041321534607500_B42","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/01621459.1965.10480775","article-title":"Randomized response: A survey technique for eliminating evasive answer bias","volume":"60","author":"Warner","year":"1965","journal-title":"Journal of the American Statistical Association"},{"key":"2021041321534607500_B43","first-page":"207","article-title":"Distance metric learning for large margin nearest neighbor classification","volume":"10","author":"Weinberger","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"2021041321534607500_B44","author":"Wu","year":"2020","journal-title":"Class2Simi: A new perspective on learning with label noise"},{"key":"2021041321534607500_B45","first-page":"521","volume-title":"Advances in neural information processing systems","author":"Xing","year":"2003"},{"issue":"4","key":"2021041321534607500_B46","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1109\/TPAMI.2006.65","article-title":"A discriminative learning framework with pairwise constraints for video object classification","volume":"28","author":"Yan","year":"2006","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2021041321534607500_B47","first-page":"1400","article-title":"Semi-supervised clustering by input pattern assisted pairwise similarity matrix completion","author":"Yi","year":"2013","journal-title":"Proceedings of the 30th International Conference on Machine Learning"},{"key":"2021041321534607500_B48","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1145\/1273496.1273636","article-title":"On the value of pairwise constraints in classification and consistency","author":"Zhang","year":"2007","journal-title":"Proceedings of the 24th International Conference on Machine Learning"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/direct.mit.edu\/neco\/article-pdf\/33\/5\/1234\/1908985\/neco_a_01373.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/direct.mit.edu\/neco\/article-pdf\/33\/5\/1234\/1908985\/neco_a_01373.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T19:13:01Z","timestamp":1697915581000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/33\/5\/1234\/97483\/Classification-From-Pairwise-Similarities"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,13]]},"references-count":48,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,4,13]]},"published-print":{"date-parts":[[2021,4,13]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01373","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,5]]},"published":{"date-parts":[[2021,4,13]]}}}