Robust Distance Metric Learning via Simultaneous L1-Norm Minimization and Maximization
Hua Wang, Feiping Nie, Heng Huang · International Conference on Machine Learning · 2014
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, we propose a new objective for distance metric learning using the l1-norm distances. The resulted objective is challenging to solve, because it simultaneously minimizes and maximizes (minmax) a number of nonsmooth 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. We performed extensive empirical evaluations, where our new distance metric learning method outperforms related state-of-the-art methods in a variety of experimental settings.