Robust Metric Learning by Smooth OptimizationKaizhu HuangNLPR,Institute of AutomationChinese Academy of SciencesBeijing, 100190 ChinaRong JinDept. of CSEMichigan State UniversityEast Lansing, MI 48824Zenglin XuSaarland University& MPI for InformaticsCampus E14, 66123Saarbrucken, GermanyCheng-Lin LiuNLPRInstitute of AutomationChinese Academy of SciencesBeijing, 100190 ChinaAbstractMost existing distance metric learningmethods assume perfect side informationthat is usually given in pairwise or tripletconstraints. Instead, in many real-worldapplications, the constraints are derivedfrom side information, such as users’ im-plicit feedbacks and citations among arti-cles. As a result, these constraints are usu-ally noisy and contain many mistakes. Inthis work, we aim to learn a distance met-ric from noisy constraints by robust opti-mization in a worst-case scenario, to whichwe refer as robust metric learning.We formulate the learning task initiallyas a combinatorial optimization problem,and show that it can be elegantly trans-formed to a convex programming problem.We present an efficient learning algorithmbased on smooth optimization [7]. It hasa worst-case convergence rate of O(1/√ε)for smooth optimization problems, where εis the desired error of the approximate so-lution. Finally, our empirical study withUCI data sets demonstrate the effective-ness of the proposed method in comparisonto state-of-the-art methods.1 IntroductionDistance metric learning is an important fundamen-tal research topic in machine learning. A numberof studies [1, 9, 8, 15, 12, 13, 6] have shown thatwith appropriately learned distance metrics, we willbe able to improve significantly both the classifica-tion accuracy and the clustering p erformance. De-pending on the nature of the side information, wecan learn a distance metric either from pairwise con-straints or from triplet constraints. In this work, wefocus on distance metric learning from triplet con-straints because of its empirical success. It aimsto learn a distance function f with a metric ma-trix A for a data set that is consistent with a setof triplet constraints D = {(xi, yi, zi)|f(xi, yi) ≤f(xi, zi), i = 1, . . . N} [6]. In the simplest form,the distance function f associated with A betweena pair of data points (xi, xj) is computed as (xi−xj)⊤A(xi− xj). For each triplet (xi, yi, zi) in D,we assume instance xiis more similar to yithan tozi, leading to a smaller distance between xiand yithan that between xiand zi.Most metric learning algorithms assume perfect sideinformation (i.e., perfect triplet constraints in ourcase). This however is not always the case in practicebecause in many real-world applications, the con-straints are derived from the side information suchas users’ implicit feedbacks and citations among arti-cles. As a result, these constraints are usually noisyand consist of many mistakes. We refer to the prob-lem of learning distance metric from noisy side in-formation as robust distance metric learning.Feeding the noisy constraints directly into a metriclearning algorithm will inevitably degrade its per-formance, and more seriously, it may even resultin worse performance than the straightforward Eu-clidean distance metric, as demonstrated in our em-pirical study.To address this problem, we propose a general frame-work of robust distance metric learning from noisyor uncertain side information in this paper. Weformulate the learning task initially as a combina-torial integer optimization problem, each {0, 1} in-teger variable indicating whether the triplet con-straint is a noisy or not. We then prove that thisproblem can be transformed to a semi-infinite pro-gramming problem [4] and further to a convex op-timization problem. We show that the final prob-lem can be solved by Nesterov’s smooth optimizationmethod [7], which has a worst-case convergence rateof O(1/√ε) for smooth objective functions, whereε is required level of errors. This is significantlyfaster than the sub-gradient method whose conver-gence rate is usually O(1/ε2). The proposed methodmay also b e adapted to the other distance metriclearning algorithms, e.g., the Large Margin NearestNeighbor (LMNN) method [12], when the side infor-mation is noisy.The rest of this paper is organized as follows. Inthe next section, we will briefly discuss the relatedwork. In Section 3, we review distance metric learn-ing with perfect side information. We then introducethe robust metric learning framework in Section 4.In Section 5, we evaluate our proposed frameworkon five real world data sets. Finally, we set out theconclusion in Section 6 with some remarks.2 Related WorkMany algorithms have been proposed for dis-tance metric learning in the literature. Exem-plar algorithms include Information-Theoretic Met-ric Learning [3] (ITML), Relevant Component Anal-ysis (RCA) [1], Dissimilarity-ranking Vector Ma-chine (D-ranking VM) [8], Generalized Sparse Met-ric Learning (GSML) [5], the method proposed byXing et al. [15], and Large Margin Nearest Neigh-bor (LMNN) [12, 13]. In particular, the last twomethods are regarded as state-of-the-art approachesin this field. Specifically, ITML maps the metricspace to a Gaussian distribution space and searchesthe best metric by learning the optimal Gaussianthat is consistent with the given constraints. [11]extends this work by the idea of information ge-ometry. In [15], a distance metric is then learnedto shrink the averaged distance within must-linkswhile enlarging the average distance within cannot-links simultaneously. In [1], RCA seeks a distancemetric which minimizes the covariance matrix im-posed by the equivalence constraints. In [12, 13],LMNN is proposed to learn a large margin nearestneighbor classifier. Huang et al. proposed a uni-fied sparse distance metric learning method [5] thatprovides an interesting viewpoint for understandingmany sparse metric learning methods. Besides theempirical results, the generalized performance of reg-ularized distance metric learning was analyzed in therecent study [6]. More discussion of distance metriclearning can be found in the survey [17].All the above methods assume perfect side informa-tion. In case of noisy constraints, direct applicationof the above methods may significantly degrade theirperformance, which is verified in our experiments.In order to alleviate the noisy side information, Wuet al. proposed a probabilistic framework for met-ric learning which is however specially