Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization

Hua Wang, Feiping Nie, Heng Huang
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1836-1844, 2014.

Abstract

Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared L2-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, in this paper we propose a new objective for distance metric learning using the L1-norm distances. However, the resulted objective is very challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth L1-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general L1-norm minmax problem, which is rarely studied in literature. We have performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings to cluster both noiseless and noisy data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-wangj14, title = {Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization}, author = {Wang, Hua and Nie, Feiping and Huang, Heng}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1836--1844}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/wangj14.pdf}, url = {https://proceedings.mlr.press/v32/wangj14.html}, abstract = {Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared L2-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, in this paper we propose a new objective for distance metric learning using the L1-norm distances. However, the resulted objective is very challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth L1-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general L1-norm minmax problem, which is rarely studied in literature. We have performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings to cluster both noiseless and noisy data.} }
Endnote
%0 Conference Paper %T Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization %A Hua Wang %A Feiping Nie %A Heng Huang %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-wangj14 %I PMLR %P 1836--1844 %U https://proceedings.mlr.press/v32/wangj14.html %V 32 %N 2 %X Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared L2-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, in this paper we propose a new objective for distance metric learning using the L1-norm distances. However, the resulted objective is very challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth L1-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general L1-norm minmax problem, which is rarely studied in literature. We have performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings to cluster both noiseless and noisy data.
RIS
TY - CPAPER TI - Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization AU - Hua Wang AU - Feiping Nie AU - Heng Huang BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-wangj14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1836 EP - 1844 L1 - http://proceedings.mlr.press/v32/wangj14.pdf UR - https://proceedings.mlr.press/v32/wangj14.html AB - Traditional distance metric learning with side information usually formulates the objectives using the covariance matrices of the data point pairs in the two constraint sets of must-links and cannot-links. Because the covariance matrix computes the sum of the squared L2-norm distances, it is prone to both outlier samples and outlier features. To develop a robust distance metric learning method, in this paper we propose a new objective for distance metric learning using the L1-norm distances. However, the resulted objective is very challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of non-smooth L1-norm terms. As an important theoretical contribution of this paper, we systematically derive an efficient iterative algorithm to solve the general L1-norm minmax problem, which is rarely studied in literature. We have performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings to cluster both noiseless and noisy data. ER -
APA
Wang, H., Nie, F. & Huang, H.. (2014). Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1836-1844 Available from https://proceedings.mlr.press/v32/wangj14.html.

Related Material