Distance Metric Learning under Covariate Shift

1 Introduction

Distance Metric learning (DML) is an important problem in many machine learning problems, such as classification through nearest neighborhood methods [Sriperumbudur and Lanckriet, 2007], clustering [Davis et al., 2007] and semisupervised learning [Yeung and Chang, 2007], etc. DML aims at learning a distance metric for an input space from some additional information such as must-link/cannot-link constraints between data instances. In the case of classification, for example, the class label information can be converted to such constraints, where data instances with the same label can be used to construct must-link pairs and those from different classes can be used to form cannot-link pairs. The key intuition in DML is to find a distance metric that can pull must-link instance pairs close to each other while push the cannot-link pairs away from each other.

Although different DML algorithms have been proposed [Xing et al., 2003; Yeung and Chang, 2007; Davis et al., 2007], previous research works generally assumed that the training and test data are drawn from the same distribution. If this assumption holds, the metric learned from the training data will work well on the test data. However, in many real world applications, it may be inappropriate to make this assumption. For example, in some cases, the training data may be collected with a sampling bias [Zadrozny, 2004], and in other cases, the data distribution may change due to the changing environment [Pan et al., 2008]. In these situations, the distance metric learned on training data cannot be directly utilized on the test data. Figure 1 shows a synthetic data example: for the training data, the first dimension (x-axis) has more discriminative information. However, for the test data, the second dimension (y-axis) contains more discriminative information. Thus, the metric that keeps the must-link training instances close to each other does not necessarily keep them to be close after the distribution changes. We refer to such discrepancies as the inconsistency problem in metric learning.

The problem of learning when the training and test data have different distributions has been studied from different perspectives, e.g., as covariate shift [Bickel et al., 2007], sample selection bias [Zadrozny, 2004] or domain adaptation [Daume and Marcu, 2006]. Previous related research in transfer learning mainly focused on supervised learning, including classification and regression. To the best of our knowledge, there has been no work that addresses metric learning when the training and test data have different distributions. In fact, the concept of distances is closely related to data distribution. It is well known that the Euclidean distance is linked to Gaussian distribution and the Manhattan distance measure (1-norm distance) is associated with Laplace distribution. Therefore, any change of distribution will cause problems for metric learning, invalidating many previous results.

In this paper, we concentrate on the problem of consistent distance metric learning under covariate shift. The assumption made under covariate shift in classification problems is that although the data distributions can change, the conditional distributions of labels given features keep stable. For metric learning we make a similar assumption that the conditional distributions of the indicator variable of mustlink/cannot-link keep stable. We theoretically analyze the consistency property of distance metric learning when training and test data follow different distributions. Based on our analysis, we propose a convex optimization problem for consistent distance metric learning (CDML). We novelly adapt importance sampling methods used in supervised learning for metric learning. Two importance weighting strategies are investigated. The first strategy estimates the importance weights for data instances before using them to calculate importance weights for instance pairs. The second strategy directly estimates the importance weights for instance pairs. The two strategies are compared and analyzed from both theoretical and practical perspectives. We conduct empirical experimentation with both synthetic and real world datasets to demonstrate the effectiveness of the proposed algorithm.

2 Distance Metric Learning

Distance Metric learning (DML) aims to learn a distance metric from a given collection of must-link/cannot-link instance pairs while preserving the distance relation among the training data instances. In general, DML can be formulated as the following multi-objective optimization problem:

where xi and xj are instances drawn from distribution Pr(x) and dθ(xi, xj) is the distance function for xi and xj with the parameter θ. S is the set of must-link pairs and D is the set of cannot-link pairs. In most distance metric learning algorithms, the distance function type is restricted to the Malahanobis distance, which can be defined as

where A is a parameter in the distance function that is a positive semi-definite matrix. Since we can always factorize A into A = LTL, the Malahanobis distance in the original feature space can be regarded as the Euclidean distance in a new feature space after a linear transformation is applied to the original feature space, as shown below,

To be precise, this is a pseudo metric rather than a metric from a mathematical perspective. However, in this paper we still follow the terminologies of previous work.

The first objective in Equation 1 is to minimize the expected distance of must-link pairs. The second objective is to maximize the distance of cannot-link pairs. When Malahanobis distance is used, the square of the distance is usually considered instead of the distance function (Equation 2), in order to simplify the formulation.

In order to solve the multi-objective optimization problem, the objective functions can be converted to a single-objective optimization problem. One conversion strategy is to use one objective as the optimization goal and the other as constraints, as done in [Xing et al., 2003]. A second strategy is to regard both objectives as constraints and optimize a new objective function as in [Davis et al., 2007]. The constraints for mustlink relations can either be hard or soft. For hard constraints, we have

and for the soft constraints, we have

where u is the upper bound for the distance between mustlink pairs and ξ is a slack variable. Similarly, for cannot-link pair we can obtain the hard constraints.

and the soft ones

where l is a lower bound for the distance of cannot-link pairs.

A more general formulation of DML is to consider a loss function over the distance function. We can show that different strategies mentioned above can be regarded as using different loss functions. In fact, we can define the loss function L(sij, dA(xi, xj)) similar to hinge loss, where sij is a label set to 1 for must link pairs and -1 for cannot-link pairs. For must-link pairs,

and for cannot-link pairs,

Then we can formulate the DML problem as,

Problem 1.

Similar to supervised learning, it is infeasible to optimize the expected loss in Problem 1 in practical problems. We need to solve the following problem where the empirical loss is minimized.

Problem 2.

where N is the number of pairs considered.

This would introduce the problem of generalization ability, which will be discussed in the next section.

3 Consistency inMetric Learning

The above formulation of DML has an implicit assumption to guarantee generalization ability: the distributions of training and test data are identical. However, when the training and test data are drawn from different distributions, the metric that keeps the must-link pairs of training instances close to each other may not keep the ones in the test data close due to the changes in data distributions. In this section, we will first define consistency in distance metric learning problem. Then we will investigate how to handle this problem when covariate shift exists.

Definition 1. A metric learning algorithm is consistent if

where N is the number of training data.

A consistent metric-learning method will guarantee the ability of generalizing the metric learned on a finite set of training data to the test data. Different from the consistency problem defined for pattern recognition problems, metric learning is defined on instance pairs rather than instances. In other words, it considers the relations between instances. Therefore, the consistency of metric learning is about the generalization ability of relation between data instances.

In the case of covariate shift, the distributions of training and test data are different. Thus, we have

Accordingly, general DML algorithms will fail to satisfy the consistency property.

In a supervised learning setting, the covariate shift problem can be solved by importance sampling methods [Shimodaira, 2000]. Based on Theorem 1, presented as follows, we can also adapt importance sampling methods to the distance metric learning problem.

Theorem1. Suppose that xi and xj are drawn independently from Pr(x). If a metric learning algorithm for Problem 2 is consistent without covariate shift, then minimizing the following function (Equation 14) using this algorithm can produce consistent solutions under covariate shift.

where wij = Pr′ (xi)Pr′ (xj) Pr(xi)Pr(xj )

Proof. Since themetric learning algorithm is consistent without covariate shift, we have

Let us denote the right hand side of the above equation by ℓ′ (x; A).

This shows the conclusion holds.

In supervised learning with covariate shift, Pr′ (x)/Pr(x) is called the importance weight. The weight wij is the product of importance weights for xi and xj . Therefore, this approach needs to estimate the importance weight for x first. Since the loss function is defined over pairs of instances, it is possible to directly estimate the importance weight on instance pairs in some cases. For example, it is possible when the distance is induced by a norm, which indicates d(xi, xj) = f(xi - xj ). The Malahanobis distance also belongs to such a case. From this perspective, we can calculate the importance weight for instance pairs using

where Δx = xi - xj. We need to introduce the concept of cross-correlation in this case. If X and Y are two independent random variables with probability distributions g and h, respectively, then the probability distribution of the difference X - Y is given by the cross-correlation g ⋆ h,

where g∗ denotes the complex conjugate of g. Then, we can have another formulation of CDML solution directly defined using Δx.

Theorem 2. If the distance is introduced by a norm, then dθ(xi, xj) = f(Δx). Suppose that δx is a random variable drawn from Q(x) = Pr(x) ⋆ Pr(x), and that a metric learning algorithm for Problem 2 is consistent without covariate shift, minimizing the following problem (equation 18) using this algorithm can produce consistent solutions under covariate shift.

where wij = Pr′ (δx)/Pr(δx).

The proof is similar with the one in Theorem 1 except the two variable now changed to one variable δx and the details are omitted here. From this point of view, the problem is treated as a supervised learning problem where instances are pairs. Although both approaches can be used to solve the CDML problem, they are not equivalent, with each having its own advantages and drawbacks. We will discuss and compare the two weighting approaches later.

In our analysis, we have the prerequisite that the original distance metric learning itself is consistent without covariate shift. This condition, although nontrivial to address, is beyond the scope of this paper. We believe that this condition can be addressed similarly to what was done in pattern recognition [Vapnik, 1995].

4 Metric Learning Under Covariate Shift

As we analyzed in the above section, the corresponding consistent metric learning problem can be formulated as

It can also be regarded as a cost-sensitive distance metric learning problem, where violating different pair constraints could introduce different costs. In the following, we formulate it as a convex optimization problem.

4.1 Our Approach

We have so far proposed a general framework for consistent distance metric learning. In this section, we will propose a specific convex optimization problem to solve the CDML.

Given the loss function defined in previous section, the cost sensitive learning problem then becomes,

where tr(M) is the trace of the matrix M.

It is easy to show the above problem is a convex optimization problem. More specifically, the problem can be converted to the following semi-definite problem (SDP), where general SDP solvers can be applied to.

where

and W = diag(wij), Λ = diag(ξij), B = (xi - xj )(xi - xj)T. For (i, j) ∈ S, Eij has only one nonzero element with Eij(i, j) = -1; For (i, j) ∈ D, Eij has only one nonzero element with Eij (i, j) = 1.

In this paper we use a general SDP solver (SDPT3 1 ) to solve our problem. As shown in [Weinberger and Saul, 2008], it is possible to investigate the structure in the pairwise relationship to reduce the complexity. We plan to develop algorithms that are more efficient for this problem in the future.

If we have some prior knowledge over the distribution and metrics, we can include one regularization term into Equation 20. In [Kulis et al., 2006], Kulis has shown the connection between KL-divergence and Bregman Matrix Divergence. The Burg matrix divergence can be introduced as a regularization term

where DBurg(A, A0) = (tr(AA-1 0 ) - logdet(AA-1 0 )) -n. We let A0 = I if we do not have any specific prior information. The problem is still a convex optimization problem. We adopt the successive approximation method used in [Grant and Boyd., 2009] to solve this convex optimization problem.

1 http://www.math.nus.edu.sg/∼mattohkc/sdpt3.html

Our approach is related to information-theoretic metric learning (ITML) [Davis et al., 2007] if we do not consider the importance weights. However, the loss function used in ITML only minimized the divergence between the learned matrix and its prior. As such the loss function in ITML cannot be directly applied to cost sensitive learning. For this reason, hinge loss is introduced in our method.

4.2 Estimating ImportanceWeights

Accurately estimating the importance weights is crucial in covariate shift. In this paper, we use a state-of-the-art algorithm proposed by Tsuboi in [Tsuboi et al., 2008] for this estimation. We will briefly introduce the algorithm in this section.

Since estimating the distribution of x is not trivial when the data dimension is high, directly estimating the importance weight Pr′ (x) Pr(x) is a preferable approach [Tsuboi et al., 2008]. Let w(x) = ∑k αkϕk(x), where αk are parameters to be learned from data samples and {ϕk(x)} are the basis functions such that ϕk(x) ≥ 0 for all x. The importance weight is obtained by minimizing KL(Prtest(x)||Pr′test (x)), where Pr′test (x) = w(x)Prtrain(x). It can be further converted to a convex optimization problem.

where ntrain is the number of training data.

In this paper, our focus is to deal with the consistent metric learning problem. Readers are referred to [Tsuboi et al., 2008] for details on estimating importance weights. There are also other candidate methods for estimating importance weights [Huang et al., 2007]. An advantage of learning the weighting function is that it allows us to generalize importance weights to out-of-sample data. Another point from [Tsuboi et al., 2008] is that the error of importance weight is proportional to O(1/√n), where n is the number of instances. For the method of estimating weights on pairs, we consider Δx as variable themselves in the above equations and we can construct more data instances to estimate the weights. Theoretically, we will have more accurate importance weights. However, from the experiments we will see that these additions will not always give better performance in practice.

5 Experiments

In this section, we evaluate the performance of our proposed methods on both synthetic and real world datasets. Since we have two weighting methods, we refer to the first one, which looks at instances and is described in Theorem 1 as CDML1 and the other one, which looks at instance pairs and is in Theorem 2 as CDML2.

5.1 Experiment Setup

We construct Gaussian mixture models for generating the training and test data. Data in the positive and negative classes are generated from two 2-dimensional Gaussian mixture models respectively. The mixture weights for training and test data are different. Therefore covariate shift exists in the datasets. Figure 2 displays the two datasets. We also test our algorithm on real-world benchmark datasets. They include two datasets from UCI 2 and another two from IDA 3 . For the UCI datasets, we follow previous research work on sample selection bias: the covariate shift is simulated by artificially introducing bias [Huang et al., 2006]. For the IDA datasets, they are already split into training and test sets and covariate shift already exists in the original split [Sugiyama et al., 2008]. Therefore, we directly use the IDA datasets in the experiments.

We evaluated our method both on classification and clustering problems. For the classification task, the results are obtained by a K-Nearest-Neighbor (KNN) classifier based on the metric learned. The value is the average accuracy of KNN for K ranging from 1 to 5. We also perform clustering based on the metric learned. Normalized Mutual Information (NMI) is used to evaluate the clustering result, which is defined in [Xu et al., 2003].

In all experiments, we randomly sample 50 pairs of mustlink/cannot-link from the data and repeat 10 times to calculate the variance of results. The parameter u and l are chosen by the 5% and 95% percentiles of the distribution of Δx.

5.2 Experimental Results

In this section, we first use the synthetic datasets to illustrate the idea of CDML comprehensively. Then we compare our method with two baseline algorithms. The first one is using Euclidean distance directly. The second is information-theoretic metric learning (ITML), which is one state-of-the-art metric learning algorithm proposed by Davis et al. in [Davis et al., 2007]. We conduct evaluation with both classification and clustering tasks.

2 http://www.ics.uci.edu/∼mlearn/MLRepository.html

3 http://ida.first.fraunhofer.de/projects/bench/

As shown in Figure 2, both GMM datasets have covariate shifts if we consider the distribution Pr(x). The two datasets are different when we consider the relation between their instances. Take the cannot-link pairs as an example, GMM1 does not have significant covariate shift when considering the distribution of Q(δx) as illustrated in Figure 3. However, in GMM2, not only Pr(x) but also Q(δx) has covariate shift, as shown in Figure 4. This may cause the difference between the results of CDML1 and CDML2. We can observe from Table 1 that the classification accuracy with KNN classifier based on CDML1 has significant improvement while CDML2 does not. For GMM2, both CDML1 and CDML2

have significant improvement. Since δx is invariant with respect to translation, it cannot detect the shift in translation. This experiment shows that, although CDML2 has its advantage over CDML1 theoretically, in practice it may not outperform CDML1. It is interesting to see that CDML1 generally performs better. Table 2 shows the performance comparison using classification accuracy on IDA datasets. From this table, we can find that CDML outperforms Euclidean and is comparable to ITML. Table 3 shows the clustering results on two UCI datasets. We can see the improvement is even more significant than classification.

6 RelatedWork

The problem of covariate shift was introduced to machine learning community by [Zadrozny, 2004]. The problem of estimating importance weight is addressed by [Huang et al., 2006; Sugiyama et al., 2008]. Huang et al. proposed to use a non-parametric kernel methods which calculates the importance weights by minimizing the difference of means of training and test data in a universal kernel space [Huang et al., 2006]. Sugiyama et al. proposed another similar approach which minimizes the KL divergence between the distributions. In [Sugiyama et al., 2008], Bickel et al. proposed a method to unify the importance weight estimation step and supervised learning step together [Bickel et al., 2007]. However, these works only focus on supervised learning problems. To our best knowledge, there is no previous work on considering covariate shift in metric learning problems.

7 Conclusion and FutureWork

In this paper, we address the problem of consistent metric learning under covariate shift. A cost sensitive metric learning algorithm was proposed. Two importance weighting methods were proposed and analyzed. Experiments were carried out on both synthetic and real world datasets on both classification and clustering tasks. Currently we are using the general SDP solvers for our proposed problem. In the future, we plan to develop faster and more scalable algorithm for this problem.

Acknowledgments

Bin Cao and Qiang Yang would like to thank the support of Hong Kong RGC/NSFC Grant N HKUST624/09 and RGC Grant 621010.