Learning Mahalanobis Distance Metric: Considering Instance Disturbance Helps

1 Introduction

Similarity and dissimilarity are widely used in machine learning area, such as classification [Bian and Tao, 2011, Luo et al., 2016], clustering [Xing et al., 2003, Xiang et al., 2008, Law et al., 2016b] and retrieval [McFee and Lanckriet, 2010]. The goal of Distance Metric Learning (DML) is to find a better distance computation which can perform better than the Euclidean one. Given a positive semi-definite matrix M, the (squared) Mahalanobis distance between two instances xi and xj can be defined as:

Since it considers the relationship between different types of features [Lim et al., 2013, Ye et al., 2016b], its advantages have been discovered and validated from various perspectives [Kulis, 2012, Bellet et al., 2015].

To train a Mahalanobis distance metric, various types of side information [Law et al., 2016a] should be collected to provide a direction for distance relative comparisons. After searching a metric decreasing the violation of these constraints, similar instances become close to each other while dissimilar ones are far away. Although ground-truth side information leads to a well-learned Mahalanobis metric [Verma and Branson, 2015, Cao et al., 2016], it is in fact unknown during the training process. Therefore, side information is often generated based on reliable raw features from various sources. For example, random choice [Davis et al., 2007], Euclidean nearest neighbor selection [Weinberger et al., 2006], and all-pair enumeration [Xing et al., 2003, Mao et al., 2016].

∗This work was supported by NSFC (61632004, 61673201).

To reduce the uncertainty in side information, [Huang et al., 2010] and [Wang et al., 2012] try a selection strategy among all target neighbors. While it is more reasonable to assume that there are inaccuracies in feature value collection, since the feature inaccuracies or noises will damage the structure of neighbors, and consequently affect the reliableness of side information. From the aspect of this generative process, we tackle the unreliability in metric learning and propose the Distance metRIc Facilitated by disTurbances (DRIFT) approach, using which a robust distance metric is achieved based on the explicit consideration of instance disturbances.

In DRIFT, all possible variations of disturbances on instances are involved in the expected distance, so as to form different side information constraints as well as assign reasonable weights on them. Specifically, when a pair of noisy instances meets the requirement of the provided side information, the DRIFT's learned metric should tolerate perturbations by enlarging the similarity region. As such the robustness of metric will increase and the generalization ability can be improved. On the contrary, if the side information was hard to satisfy for the concerned pair, assigning obvious perturbations can be risky. Hence, the tolerance level of disturbances on instance pairs reflects the reliableness of side information to some extent. Moreover, perturbation distribution modeled noises make DRIFT have the ability to represent instances distribution quantitatively [Van Der Maaten et al., 2013], and help reduce the effects of incorrect guidance in training. Therefore, it is expected that DRIFT can provide a robust distance metric with better discriminative ability.

DRIFT learns metric and disturbance of instances jointly. Benefited from metric decomposition, we get a simplified objective and acceleration variants with sub-problems further reducing to scalar group optimization. Our empirical investigations provide visualization effects demonstrating the interpretability of DRIFT. Real-world tasks validate DRIFT's superiorities on generalization and robustness, especially in the case of unreliable instances/side information.

The rest of this paper starts with discussions about related methods. Then the DRIFT approach is presented in detail. The last are experiments and conclusion.

2 RelatedWork

Mahalanobis distance is widely researched in distance metric learning. It is originally used in the clustering task [Xing et al., 2003] considering all pair comparisons. ITML [Davis et al., 2007] utilizes the randomly chosen pairwise side information and information based regularizer. While triplets constraints are considered in LMNN [Weinberger et al., 2006] to form a large margin objective. To find a better description of side information, a multi-stage strategy is proposed in [Weinberger and Saul, 2009, Zhan et al., 2009], where the metric learned in the previous stage is used to find nearest neighbors in the current one. [Huang et al., 2010] and [Wang et al., 2012] traverse all target neighbors to find best candidates. In DRIFT, we propose a new perspective on the refinement of side information by considering the disturbances over instances. Different metric learning methods and the ways they use side information can be found in [Bellet et al., 2015].

Perturbations modeling can be regarded as a type of regularization [Wager et al., 2013] to train a robust model [Chen et al., 2014, Wangni and Chen, 2016] or get better feature representations [Van Der Maaten et al., 2013, Chen et al., 2015, Li et al., 2016]. Qian et al. [2014] first consider noises in metric learning, but only fixed covariance perturbation is used to get a low rank solution. In DRIFT, we learn the perturbation distribution to directly model the noises for a robust metric.

The disturbance distribution is also closely related to the instance distributions, and consequently correlated with the instance generation mechanism. Different from [Ye et al., 2016a], where distributions are considered to model the multiple metrics and indirectly infer the metric for unseen instance, DRIFT explicitly models the distribution related to instances and side information. Mao et al. [2016] study robust manifold learning. Nevertheless, they focus on the instance distribution towards preserving their Euclidean distances. On the contrary, DRIFT approach considers the disturbance distribution directly for better discriminative ability.

3 Learning Distance Metric Considering Instance Disturbance

The Distance metRIc learning Facilitated by disTurbances (DRIFT) approach learns instance disturbances and distance metric jointly. In this section, we introduce notations first, then give a description of the distribution perturbed distance computation. After that, detailed DRIFT formulation and its optimization strategy are presented. Acceleration strategies are described at last.

3.1 Notations

Given a training set D = {xi, yi}Ni=1 , each instance xi ∈ Rd has a label yi ∈ 1, 2, . . . ,C. We focus on the input side information in the form of T triplets. 1 In the t-th triplet

1 Learning with perturbed distance in the pairwise form can also be formulated in a similar way.

{xti , xtj , xtk }, xtj is the target neighbor of instance xti and they should be close to each other using learned distance. While xtk is the imposter, i.e., a different class instance that needed to be pushed away. The learned Mahalanobis distance metric M lies in the set of positive semi-definite matrix S + d . ∥M∥2F = ⟨M,M⟩ = Tr(M ⊤M) is the Frobenius norm of a matrix. I is the identity matrix. [·]+ is a scalar input function which only preserves the non-negative part of input value.

We use P to denote the set of valid probability distributions (nonnegative and sum to one over random variable space). Denote pi(ϵ) ∈ P as the perturbation distribution for instance xi and p = {pi(ϵ)}Ni=1 is the set of all these distributions. For random variable ϵ ∈ Rd , the KL-divergence can produce a non-negative inconsistency measurement between two distributions p(ϵ) and p0(ϵ), which is defined as KL(p∥p0) = ∫ p(ϵ) log p(ϵ) p0(ϵ) dϵ.

3.2 Instance Disturbances inMetric Learning

Instance disturbance affects its neighborhood structures, inducing unreliability in training, which can be used for facilitating the utilization of side information. Taking perturbations into account in the distance computation, variants of instances should be used to explain the guidance of side information. In DRIFT, We focus on the expected Mahalanobis distance with metric M between two instances xi and xj , which is equivalent to covering all the instances ˆxi and ˆxj sampled from instance distribution p(xi) and p(xj), respectively [Li et al., 2016, Mao et al., 2016]:

Last step in Eq. 1 comes from the independent assumption between instances xi and xj. Since it is a general assumption that the disturbances on instances are centralized, i.e., Eˆxi [ˆxi] = xi, the above expected distance can be further transformed into:

Cov[xi] ∈ S + d is the covariance matrix of distribution p(xi). Hence, the expected Mahalanobis distance between two instances is appended with a term of covariances. Moreover, we can model the disturbance of instance based on Eq. 2 by introducing an unbiased random perturbation ϵ ∈ Rd , sampled from a distribution p(ϵ), to the expected distance computation. Therefore, the difference of two perturbed instances sampled from p(xi) and p(xj ) can be denoted as ˆxi-ˆxj = xi-xj +ϵ. Thus disturbance over distance also considers the variations over instances, as revealed by the distance transformation:

For the PSD property of metric M, the last term in Eq. 3 is a quadratic form which is positive no matter what value of ϵ takes. So the expected distance in Eq. 3 has the expansion property that enlarges original Mahalanobis distance value. In our DRIFT method, we consider the expected distance and learn the distribution over ϵ.

Given a triplet {xti , xtj , xtk }, the metric M should make the distance between xti and imposter xtk larger than the distance between xti and target neighbor xtj beyond a margin. Due to the expansion property, there is no additional effect in considering expected distance for imposter comparisons. Together with the fact that target neighbor relationship possesses more uncertainty [Wang et al., 2012], it's better to invoke the expected distance only in measuring the target neighbor pair. Therefore, we can formulate our Distance metRIc Facilitated by disTribution (DRIFT) approach as follows:

where the first part in the objective is a Frobenius norm regularizer on metric M. The second term is a distribution regularizer, i.e., KL-divergence is used to make the learned perturbation distribution pi(ϵ) close to a specified prior p0(ϵ). As in the general setting [Mao et al., 2016], we choose prior as a zero-mean multivariate normal distribution: p0 ∼ N(0, Σ0) for all instances, which satisfies the unbiased requirement. It is notable that in the Eq. 4, we do not constrain the form of pi(ϵ) but only require it as a valid distribution. Instances' different perturbations give rise to various impacts when computing distance with others, which considers local properties of instances. The third term minimizes the large margin violation. For each instance, the distance between imposters should be larger than (beyond a margin value) the expected distance between its target neighbors.

In our solution, we optimize over target neighbor instance xtj around its neighborhood to find the best disturbance, i.e., only the target neighbor ˆxtj = xtj + ϵ, ϵ ∼ pj(ϵ) is perturbed. This simplification gets the same results as considering the distribution on the perturbation of instance differences. Since most existing distance metric learning methods use Euclidean nearest neighbors as target neighbors [Weinberger and Saul, 2009], the perturbation of target neighbors relieves the problem of initial target selection and sets the target neighbor having the right distance with others as well. In addition, it is obvious that learning the parameters of the noise distribution can be regarded as measuring the tolerance of perturbation on target neighbors. Pairs satisfying constraint easily can tolerate perturbations more to some extent, and expand the similar range w.r.t. a center instance, which is shown in Fig. 1. On the other hand, these pairs attract more weights in the training, thus a robust metric is expected to be obtained.

3.3 Optimization for DRIFT

The objective formulation of DRIFT can be transformed to:

where ℓ(x) = [1 - x]+ is the hinge loss. Mahalanobis metric and instance disturbances are learned in an alternative manner.

When M is fixed, the third part of the optimization problem is a linear optimization over distribution pi, which tunes the perturbations under the guide of the current metric. When perturbation distributions p is fixed, the objective considers the influence of target neighbor by expected distance, and finds a global distance metric to push imposters farther away than target neighbors.

Fix metric M and solve distribution p: We can write the sub-problem in the constraints form:

With the convex property of KL-divergence, we can optimize Eq. 5 from dual. With non-negative multipliers α = {αt}Tt=1 and β = {βt}Tt=1 , the dual problem can be written as:

ct = dist2M (xti , xtk ) - dist2M (xti , xtj ) = ⟨M,At⟩ is the difference of Mahalanobis distance with metric M between imposters and target neighbors, where At = (xti , xtk )(xti , xtk )⊤ - (xti , xtj )(xti , xtj )⊤. The expectation Eptj [·] in Eq. 6 is taken over the distribution of the disturbance on xtj . After applying stationarity property of KKT condition [Boyd and Vandenberghe, 2004] in Eq. 6, we can get λ2 - αt - βt = 0, thus 0 ≤ αt ≤ λ2. When taking derivative w.r.t. pi(ϵ), we have

I t j = I t j (xi) is the indicator whether perturbation distribution of target neighbor j in t-th triplet belongs to xi. Since pi is a valid distribution, we can get the normalization constant from its exponential form, which achieves a multivariate normal distribution. By defining Σ-1 i = Σ-1 0 + 2 λ1 ∑Tt=1 I t j αtM, we have pi(ϵ) ∼ N(0, Σi). Because M is PSD, the updated covariance matrix is also PSD, meeting the requirement of a normal distribution. It is notable that distributions for perturbations on different instances differ in their ways combining dual variables. Due to complementary slackness, the value of αt should be zero if a large margin is preserved with the expected distance, then the disturbance will be close to the prior. Otherwise, the distribution will adapt to the current measurement so as to change the weights on different constraints.

Substituting the distribution, we can simplify the dual problem to an optimization of f1 on variable α:

where det(·) is the determinant of a matrix. From the smooth concave property of the log det(·) term, we can optimize the sub-problem for disturbance using accelerated projected gradient descent method [Nesterov, 2004, Li et al., 2014]. The gradient w.r.t. αt can be calculated as follows:

Although there is a matrix inverse operation in Eq. 9, it can be further simplified as shown in the next sub-section.

Fix distribution p and solve metric M: The sub-problem for distance metric M can be formulated as:

Since hinge loss is non-smooth, directly optimizing with subgradient descent will have slow convergence rate [Beck and Teboulle, 2009]. So we use a smooth approximation of hinge loss to accelerate the training of M:

The larger the parameter L in Eq. 11, the more ℓs(x) close to the hinge loss [Zhang et al., 2003, Qian et al., 2015a]. With this smoothed loss, the above sub-problem over metric M is a convex smooth one, which can also be optimized with accelerated projected gradient descent method.

Given the learned perturbation distribution pi in Eq. 7, we can compute the expectation over the quadratic form in Eq. 10 analytically. For a triplet {xti , xtj , xtk }, the expected term Eptj [ϵ⊤Mϵ] = ⟨Eptj [ϵϵ⊤],M⟩ = ⟨Σtj ,M⟩. The covariance matrix Σtj corresponds to the target neighbor j in triplet t, which can be estimated with learned α. If we denote the objective over M with smoothed loss as f2, we can get the gradient w.r.t. metric M as:

where at = dist2M (xti , xtk ) - dist2M (xti , xtj ) - Eptj [ϵ⊤Mϵ] is the input distance value. ℓ′s (at) = 1 1+exp(-L(at-1)) -1 is the derivative value of the smoothed hinge loss.

3.4 Acceleration for DRIFT

Since M should be projected to the PSD cone to preserve a valid metric, we can use its eigen-decomposition M = UDU ⊤ to further accelerate the optimization process over α. For M's symmetric property, its eigen vector U is an orthogonal matrix, and D = diag{D1,D2, . . . ,Dd} is a diagonal matrix containing its eigenvalues. In the following discussion, we set prior covariance Σ0 = λI.

To get the objective of the dual problem in Eq. 8 when solving the perturbation distribution, we need to compute

Since the determinant of a matrix equals to the product of its eigen-values, we can get O1 = ∑Dd=1 log( 1λ + qtDd) with qt = 2 λ1 ∑Tt=1 I t j αt as the accumulated coefficient for each instance. Therefore, the computation of the matrix in Eq. 8 degrades to a scalar group computation problem.

To compute the gradients w.r.t. αt, we need to get O2 = Tr((Σ-1 0 + qtM)-1M). Directly computing the trace term needs the inverse and multiplication of a d × d matrix. However, we can transform O2 as:

The last equation comes from the fact that the trace of a matrix equals to the sum of its eigen-values. In summary, we transform the distribution optimization over α to a problem only consisting of group of scalars computation with little computational cost.

After the distribution p is known, we need to find Σi = (Σ-1 0 + qtM)-1 to complete the gradient computation when optimizing the metric M. We can rewrite the covariance matrix computation as:

which avoids the inverse computation. Operator diag(Dd) forms the variables over index d to a diagonal matrix.

The number of triplets increases when we meet largescale datasets, and it is difficult to enumerate all triplets in a single gradient computation of M. Stochastic gradient descent can be a rescue [Qian et al., 2015a], which can be used to reduce the computational burden in the metric subproblem. In this case, we can consider an upper bound of the loss over the expected distance, where the disturbance of instances can be seamlessly imbedded in the stochastic gradient of metric. For the t-th triplet, using Jensen's inequality, we have ℓ(dist2M (xti , xtk ) - E[dist2M (xti , ˆxtj )]) = [1 - dist2M (xti , xtk ) + E[dist2M (xti , ˆxtj )]]+ ≤ E([1 - dist2M (xti , xtk ) + dist2M (xti , ˆxtj )]+). Therefore, we can optimize following objective upper bound for metric M:

(c) Selected Skeletons

(d) Visual Effects of Distribution

Figure 2: Visualization of DRIFT's property on synthetic data. Plots (a)-(d) show the original instances, projected instances, selected skeleton and the learned distribution (for left bottom instances), respectively.

where unbiased gradient can be computed by randomly choosing a triplet and disturbing the target neighbor with its known perturbation distribution.

4 Experiments

In this section, empirical investigations are conducted to validate the effectiveness of DRIFT. In detail, we first show the interpretability of the process of DRIFT on synthetic data, then DRIFT is compared with state-of-the-art methods on the real datasets. At last, we demonstrate the robustness of DRIFT given perturbed side information and instances.

4.1 Visualization on Synthetic Set

We first demonstrate the property of DRIFT on a 2D synthetic dataset. There are totally 600 instances with 2 classes. Class 1 is distributed in two different areas as in plot (a) of Fig. 2. We set the prior of DRIFT to 0.01I. Using only a single metric, DRIFT clusters the same cluster instances together (plot (b)).

Plot (c) shows the instances in the original space who have zero dual variable sums. As in Eq. 7, when the sum of dual variables related to a particular instance is larger than zero, a difficult constraint is identified and the instance perturbation covariance will be compressed. Therefore, we can use the dual variable αt to reflect the reliableness of side information to some extent and select the skeleton of data. We also give a visualization of learned distribution. Sizes of ellipsoids in the plot (d) are proportional to their covariances. The larger an ellipsoid, the wider the range of position the corresponding instance can drift. Instances in area "B" and "C" have large neighborhood range, which can satisfy the side information and enlarge the class boundary simultaneously. While instances near the class boundary (area "A") are hard to deal with. So compared with previous instances, they have smaller expected distance with others when they are selected as target neighbors, and therefore impose smaller weights on their related constraints.

4.2 Comparisons on Real-World Benchmarks

To test the classification ability of the learned metric for DRIFT, we compare the proposed DRIFT with state-of-the-art metric learning methods on 15 real datasets over 30 random trials. In each trial, 70% of training data is randomly selected, and the rest is used for test. Parameters are tuned for each method ranging from {10-2 , 10-1 , . . . , 102 }.

We compare with three parts of methods. First is the stateof-the-art metric learning methods, namely LMNN [Weinberger et al., 2006], DNE [Zhang et al., 2007], ITML [Davis et al., 2007], GMML [Zadeh et al., 2016] and RVML [Perrot and Habrard, 2015]. Second group including the ones weighting the side information in the training process, i.e., MSLMNN [Weinberger and Saul, 2009], LNML [Wang et al., 2012] and MSML [Qian et al., 2015b]. The last two methods consider noise/distribution in the distance computation: SGDD [Qian et al., 2014] and MPME [Mao et al., 2016]. The learned metric is validated using 3NN. The results with Euclidean distance is denoted as EUCLID. For our DRIFT approach, we test both performance of the batch and stochastic solver, which are shown as DRIFTB and DRIFTS respectively. In the implementation, we initialize metric M = I and α as zero vector. Triplets are initialized the same way as LMNN.

Average test errors of all methods are listed in Table 1. From the results, it can be found that the classification results for kNN can be improved with learned metrics, which shows the necessity and effectiveness of the metric learning. In addition, the methods considering the reliability of provided side information can give better results. For example, triplet selection method LNML gets better results than the non-selection counterpart LMNN. Although MPME considers instance distribution in the training process, it only uses the Euclidean distance as a learning guidance, so cannot perform well when the Euclidean one is not suitable. Our DRIFT approach can perform best on 9 of 15 datasets. Since it considers the instance disturbance, it identifies and takes advantages of useful side information constraints during the training. Compared with LNML, it can give even better results. Effectiveness of DRIFT can also be validated by its t-test comparison with others.

4.3 Investigations on Robustness

To test the robustness of DRIFT approach when dealing with noisy side information, we test DRIFT on above datasets with perturbed triplets constraints. The same partition as last subsection is used and parameters of all methods are fixed before training. For a triplet set {xti , xtj , xtk }Tt=1 generated with 3 target neighbors and 10 imposters based on Euclidean nearest neighbor, we construct a noisy version by sampling 20% of them on which positions of xtj and xtk are exchanged. We compare our DRIFT method (batch solver) with LMNN, MSLMNN and LNML, since they obtain a metric from given fixed triplets. For the multi-stage method MSLMNN, we also corrupt its newly generated side information. The results of compared methods are listed in Fig. 3. Due to the page limit, only 4 of datasets are shown. Euclidean distance results are also compared. Due to the fact that the corrupted information does not influence kNN, it can often get better results than others. It can be found clearly in Fig. 3 that the corrupted side information has a huge impact on the metric learning process. Both LMNN and MSLMNN get worse results than the Euclidean one, i.e., they learn a poor metric with corrupted constraints. LNML can relieve the negative variation, but DRIFT is almost not affected by this side information and can even train a good metric. It maybe in DRIFT the perturbations of instances takes different types of side information into consideration hence improve its robustness on average.

Performances with the change of noise level are also investigated. The maximum absolute values of each feature construct the basic noise vector, and times of it are added to the original datasets. Averaged test errors of different noise levels are recorded in Fig. 4. From the results, it is notable that DRIFT performs better than others under various noisy environment. In summary, these two performance comparisons validate the robustness of DRIFT, which strengthens the advantage of DRIFT in an unknown scenario.

5 Conclusion

We claim one of the prominent side information noise comes from the inaccuracies of feature values, which will damage the neighbor structure and seriously degenerate the robustness of metric learning approaches. Aiming at the noisy instance issues, Distance metRIc learning Facilitated by disTurbances (DRIFT) approach is proposed in this paper, which considers the perturbations on instance target pairs, to learn a robust metric. It is notable that expected distance for noisy instances is not only used for modeling types of feature value perturbations but also takes account of the constraints weights. Acceleration of DRIFT is also provided. Experiments on real datasets validate the effectiveness of DRIFT on classification performance. Results under noisy environments also highlight the DRIFT's superiorities. DRIFT can also be used to reveal the instance relationship for graph construction, which can be an interesting future work.