More Web Proxy on the site http://driver.im/

research-article

Public Access

Safe Triplet Screening for Distance Metric Learning

Authors:

Tomoki Yoshida,

Ichiro Takeuchi,

Masayuki KarasuyamaAuthors Info & Claims

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 2653 - 2662

https://doi.org/10.1145/3219819.3220037

Published: 19 July 2018 Publication History

Abstract

We study safe screening for metric learning. Distance metric learning can optimize a metric over a set of triplets, each one of which is defined by a pair of same class instances and an instance in a different class. However, the number of possible triplets is quite huge even for a small dataset. Our safe triplet screening identifies triplets which can be safely removed from the optimization problem without losing the optimality. Compared with existing safe screening studies, triplet screening is particularly significant because of (1) the huge number of possible triplets, and (2) the semi-definite constraint in the optimization. We derive several variants of screening rules, and analyze their relationships. Numerical experiments on benchmark datasets demonstrate the effectiveness of safe triplet screening.

References

[1]

J. Barzilai and J. M. Borwein . 1988. Two-point step size gradient methods. IMA journal of numerical analysis Vol. 8, 1 (1988), 141--148.

[2]

D. P. Bertsekas . 1999. Nonlinear programming. Athena scientific Belmont.

[3]

S. Boyd and L. Vandenberghe . 2004. Convex optimization. Cambridge university press.

Digital Library

[4]

S. Boyd and L. Xiao . 2005. Least-squares covariance matrix adjustment. SIAM J. Matrix Anal. Appl. Vol. 27, 2 (2005), 532--546.

Digital Library

[5]

H. L. Capitaine . 2016. Constraint selection in metric learning. arXiv preprint arXiv:1612.04853 (2016).

[6]

C.-C. Chang and C.-J. Lin . 2011. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST) Vol. 2, 3 (2011), 27.

Digital Library

[7]

F. Chollet et almbox. . 2015. Keras. https://github.com/keras-team/keras. (2015).

[8]

J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon . 2007. Information-theoretic metric learning. In Proceedings of the 24th international conference on Machine learning. ACM, 209--216.

Digital Library

[9]

O. Fercoq, A. Gramfort, and J. Salmon . 2015. Mind the duality gap: safer rules for the lasso. arXiv preprint arXiv:1505.03410 (2015).

Digital Library

[10]

L. E. Ghaoui, V. Viallon, and T. Rabbani . 2010. Safe feature elimination for the lasso and sparse supervised learning problems. arXiv preprint arXiv:1009.4219 (2010).

[11]

H. Hanada, A. Shibagaki, J. Sakuma, and I. Takeuchi . 2018. Efficiently Monitoring Small Data Modification Effect for Large-Scale Learning in Changing Environment. In Proceedings of The 32nd AAAI Conference on Artificial Intelligence. 1314--1321.

[12]

E. Hoffer and N. Ailon . 2015. Deep metric learning using triplet network. In International Workshop on Similarity-Based Pattern Recognition. Springer, 84--92.

[13]

P. Jain, B. Kulis, I. S. Dhillon, and K. Grauman . 2009. Online metric learning and fast similarity search. In Advances in neural information processing systems. 761--768.

Digital Library

[14]

B. Kulis et almbox. . 2013. Metric learning: A survey. Foundations and Trends® in Machine Learning Vol. 5, 4 (2013), 287--364.

[15]

S. Lee and E. P. Xing . 2014. Screening rules for overlapping group lasso. arXiv preprint arXiv:1410.6880 (2014).

[16]

R. B. Lehoucq and D. C. Sorensen . 1996. Deflation techniques for an implicitly restarted Arnoldi iteration. SIAM J. Matrix Anal. Appl. Vol. 17, 4 (1996), 789--821.

Digital Library

[17]

J. Liu, Z. Zhao, J. Wang, and J. Ye . 2014. Safe Screening with Variational Inequalities and Its Application to Lasso International Conference on Machine Learning. 289--297.

Digital Library

[18]

J. Malick . 2004. A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. Vol. 26, 1 (2004), 272--284.

Digital Library

[19]

B. McFee and G. R. Lanckriet . 2010. Metric learning to rank. In Proceedings of the 27th International Conference on Machine Learning (ICML-10). 775--782.

Digital Library

[20]

K. Nakagawa, S. Suzumura, M. Karasuyama, K. Tsuda, and I. Takeuchi . 2016. Safe pattern pruning: An efficient approach for predictive pattern mining Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1785--1794.

Digital Library

[21]

E. Ndiaye, O. Fercoq, A. Gramfort, and J. Salmon . 2016. Gap safe screening rules for sparse-group lasso. In Advances in Neural Information Processing Systems. 388--396.

Digital Library

[22]

K. Ogawa, Y. Suzuki, and I. Takeuchi . 2013. Safe screening of non-support vectors in pathwise SVM computation Proceedings of the 30th International Conference on Machine Learning. 1382--1390.

Digital Library

[23]

S. Okumura, Y. Suzuki, and I. Takeuchi . 2015. Quick sensitivity analysis for incremental data modification and its application to leave-one-out cv in linear classification problems Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 885--894.

Digital Library

[24]

F. Schroff, D. Kalenichenko, and J. Philbin . 2015. Facenet: A unified embedding for face recognition and clustering Proceedings of the IEEE conference on computer vision and pattern recognition. 815--823.

[25]

M. Schultz and T. Joachims . 2004. Learning a distance metric from relative comparisons Advances in neural information processing systems. 41--48.

Digital Library

[26]

C. Shen, J. Kim, F. Liu, L. Wang, and A. Van Den Hengel . 2014. Efficient dual approach to distance metric learning. IEEE transactions on neural networks and learning systems Vol. 25, 2 (2014), 394--406.

[27]

A. Shibagaki, M. Karasuyama, K. Hatano, and I. Takeuchi . 2016. Simultaneous safe screening of features and samples in doubly sparse modeling Proceedings of the 33rd International Conference on Machine Learning. 1577--1586.

Digital Library

[28]

A. Shibagaki, Y. Suzuki, M. Karasuyama, and I. Takeuchi . 2015. Regularization path of cross-validation error lower bounds Advances in Neural Information Processing Systems 2015. 1675--1683.

Digital Library

[29]

T. Takada, H. Hanada, Y. Yamada, J. Sakuma, and I. Takeuchi . 2016. Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization. In Proceedings of The 8th Asian Conference on Machine Learning. 126--141.

[30]

J. Wang, P. Wonka, and J. Ye . 2014. Scaling SVM and least absolute deviations via exact data reduction International Conference on Machine Learning. 523--531.

Digital Library

[31]

J. Wang, J. Zhou, P. Wonka, and J. Ye . 2013. Lasso screening rules via dual polytope projection Advances in Neural Information Processing Systems. 1070--1078.

Digital Library

[32]

K. Q. Weinberger and L. K. Saul . 2009. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research Vol. 10, Feb (2009), 207--244.

Digital Library

[33]

Z. J. Xiang, Y. Wang, and P. J. Ramadge . 2017. Screening tests for lasso problems. IEEE transactions on pattern analysis and machine intelligence Vol. 39, 5 (2017), 1008--1027.

Digital Library

[34]

E. P. Xing, M. I. Jordan, S. J. Russell, and A. Y. Ng . 2003. Distance metric learning with application to clustering with side-information Advances in neural information processing systems. 521--528.

Digital Library

[35]

H. Yang . 1993. Conjugate gradient methods for the Rayleigh quotient minimization of generalized eigenvalue problems. Computing Vol. 51, 1 (1993), 79--94.

[36]

T. Yoshida, I. Takeuchi, and M. Karasuyama . 2018. Safe Triplet Screening for Distance Metric Learning. arXiv preprint arXiv:1802.03923 (2018).

[37]

W. Zhang, B. Hong, W. Liu, J. Ye, D. Cai, X. He, and J. Wang . 2016. Scaling Up Sparse Support Vector Machines by Simultaneous Feature and Sample Reduction. arXiv preprint arXiv:1607.06996 (2016).

[38]

Q. Zhou and Q. Zhao . 2015. Safe subspace screening for nuclear norm regularized least squares problems. In International Conference on Machine Learning. 1103--1112.

Digital Library

[39]

J. Zimmert, C. S. de Witt, G. Kerg, and M. Kloft . 2015. Safe screening for support vector machines. In NIPS 2015 Workshop on Optimization in Machine Learning (OPT).

Cited By

Wang HJiang KXu Y(2022) Sequential safe feature elimination rule for -regularized regression with Kullback–Leibler divergence Neural Networks10.1016/j.neunet.2022.09.008155(523-535)Online publication date: Nov-2022
https://doi.org/10.1016/j.neunet.2022.09.008
Sun PYang L(2022)Low-rank supervised and semi-supervised multi-metric learning for classificationKnowledge-Based Systems10.1016/j.knosys.2021.107787236:COnline publication date: 25-Jan-2022
https://dl.acm.org/doi/10.1016/j.knosys.2021.107787
Dantas CSoubies EFévotte C(2021)Expanding boundaries of gap safe screeningThe Journal of Machine Learning Research10.5555/3546258.354649422:1(10665-10721)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.5555/3546258.3546494
Show More Cited By

Index Terms

Safe Triplet Screening for Distance Metric Learning
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
2. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Convex optimization

Recommendations

Safe Triplet Screening for Distance Metric Learning
Distance metric learning has been widely used to obtain the optimal distance function based on the given training data. We focus on a triplet-based loss function, which imposes a penalty such that a pair of instances in the same class is closer than a ...
Distance metric learning revisited
ECMLPKDD'12: Proceedings of the 2012th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part I

The success of many machine learning algorithms (e.g. the nearest neighborhood classification and k-means clustering) depends on the representation of the data as elements in a metric space. Learning an appropriate distance metric from data is usually ...
Distance metric learning with eigenvalue optimization

The main theme of this paper is to develop a novel eigenvalue optimization framework for learning a Mahalanobis metric. Within this context, we introduce a novel metric learning approach called DML-eig which is shown to be equivalent to a well-known ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2018

2925 pages

ISBN:9781450355520

DOI:10.1145/3219819

General Chairs:
Yike Guo
Imperial College London
,
Faisal Farooq
IBM

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

PRESTO
MI2I project of the Support Program for Starting Up Innovation Hub
JST CREST
RIKEN Center for AIP
MEXT KAKENHI

Conference

KDD '18

Sponsor:

KDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 19 - 23, 2018

London, United Kingdom

Acceptance Rates

KDD '18 Paper Acceptance Rate 107 of 983 submissions, 11%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
558
Total Downloads

Downloads (Last 12 months)107
Downloads (Last 6 weeks)18

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang HJiang KXu Y(2022) Sequential safe feature elimination rule for -regularized regression with Kullback–Leibler divergence Neural Networks10.1016/j.neunet.2022.09.008155(523-535)Online publication date: Nov-2022
https://doi.org/10.1016/j.neunet.2022.09.008
Sun PYang L(2022)Low-rank supervised and semi-supervised multi-metric learning for classificationKnowledge-Based Systems10.1016/j.knosys.2021.107787236:COnline publication date: 25-Jan-2022
https://dl.acm.org/doi/10.1016/j.knosys.2021.107787
Dantas CSoubies EFévotte C(2021)Expanding boundaries of gap safe screeningThe Journal of Machine Learning Research10.5555/3546258.354649422:1(10665-10721)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.5555/3546258.3546494
Yoshida TTakeuchi IKarasuyama M(2021)Distance metric learning for graph structured dataMachine Learning10.1007/s10994-021-06009-3110:7(1765-1811)Online publication date: 16-Jun-2021
https://doi.org/10.1007/s10994-021-06009-3
Yoshida TTakeuchi IKarasuyama MTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Learning Interpretable Metric between GraphsProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330845(1026-1036)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330845

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents