Metric Learning in Optimal Transport for Domain Adaptation

1 Introduction

Domain adaptation (DA) has been shown to be very effective in many real world applications, e.g., in computer vision, medical diagnosis, or recommender systems, to cite a few. The main idea is to use labeled data of a source domain to improve the performance of a classifier deployed on a related target domain which suffers from a lack of labeled examples. In this paper, we address a complex setting, called unsupervised DA, where there is only unlabeled data available from the target distribution.

Different approaches have been proposed to tackle this problem, some of them coming with theoretical guarantees (see, e.g. the survey [Redko et al., 2019b]). One classical way is to learn a common latent space where the distribution shift is smaller. For instance, the Subspace Alignment algorithm (SA) [Fernando et al., 2013] learns a classifier in a subspace obtained after a linear alignment of the source and target eigenvectors. In a similar manner, the Correlation Alignment (CORAL) [Sun et al., 2016] uses the covariance of the source and target distributions to reduce the shift, while Transfer Component Analysis (TCA) [Pan et al., 2011] looks for common features between the two domains. Some other works directly learn the target labels but do not gather the two distributions in a common feature space. This is the case of MEDA [Wang et al., 2018] which learns a domaininvariant classifier in Grassman manifold. On the other hand, DA with deep learning has received much attention during the past decade from the computer vision community leading to a substantial amount of research to address visual tasks for which a large amount of training data or a pre-trained model is available (see, e.g. the survey [Wang and Deng, 2018]).

More recently, Optimal Transport (OT) has been shown to be a very promising tool to perform DA tasks. OT consists in mapping two source and target probability measures with a minimal cost of transportation associated to the socalled Wasserstein distance. Beyond its use in deep learning to solve visual DA tasks (see, e.g., [Sun and Saenko, 2016; Bhushan Damodaran et al., 2018]), this idea of reducing the shift by OT has been exploited in a more generic DA setting by the algorithm OTDA [Courty et al., 2017b]. OTDA modifies the original Kantorovich optimization problem by resorting to a regularization preventing the transportation plan from moving two source points of different labels onto the same target example. Then, a classifier can be learned from the labeled source data and deployed over the target distribution. Based on this work, [Courty et al., 2017a] ensures that the final classifier is coherent with the transportation plan.

Inspired from both SA and OTDA, our contribution aims at using OT for domain adaptation by aligning the source and target subspaces. The main conjecture we formulate in this paper is that the Euclidean distance usually used as the cost matrix in OT may not be the best metric to perform the adaptation. While learning a better metric (especially a Mahalanobis distance) in OT has been recently studied [Deshpande et al., 2019; Genevay et al., 2018; Paty and Cuturi, 2019; Cuturi and Avis, 2014], optimizing such a ground metric to address DA tasks has not receive attention yet. We fill this gap from both a theoretical and an algorithmic perspective. First, we formally establish a relation between the target error and the magnitude of different Wasserstein distances. This prompts us to see the Wasserstein distance as a parameterized metric that might be minimized, leading to a better transportation plan for DA. We also formally make a link between a PCA and the minimization of the Wasserstein distance. Based on this theoretical analysis, we propose MLOT, an algorithm which optimizes a Mahalanobis distance that improves the Optimal Transport between the source and target subspaces generated by a PCA. Unlike OTDA which does not change the feature space, MLOT jointly optimizes (i) the dimensionality reduction of the source domain, (ii) the transportation plan between the source and the target and (iii) the underlying metric used in the transportation. The intuition behind MLOT is illustrated in Figure 1. The original source and target examples are represented on the left. The second figure shows the limitation of OTDA when the transportation is performed in the original feature space. The figure on the right gives evidence on the advantage of performing a PCA before learning jointly the ground metric and the transportation plan.

The rest of the paper is organized as follows: Section 2 reminds the main principles of OT, DA and Metric Learning. Section 3 is dedicated to the theoretical contribution of our paper which leads to the design of our MLOT algorithm in Section 4. An extensive experimental study is presented in Section 5 before our conclusion in Section 6.

2 Optimal Transport andMetric Learning

In this section, we briefly introduce Optimal Transport, its use in OTDA, and Metric Learning.

2.1 Optimal Transport and OTDA

Let X ⊆ Rn be a feature space. We consider here a source distribution µs and a target distribution µt both defined over X. OT [Villani, 2008] aims at moving µs on the top of µt with a transportation plan of minimal cost. We will use in this paper the formulation proposed by Kantorovich [1942] which gives the Wasserstein distance between µs and µt. Let Π(µs, µt) be the collection of all joint probability measures on X ×X with marginals µs and µt respectively. Let suppose that µs and µt have a finite p-order moment with p ≥ 1. One can define the p-Wasserstein distance at the power p as

where c : X × X → R is a cost function. The minimizer of the previous problem γ ∗ corresponds to the Optimal Transport plan. In practice, we deal with the empirical measures ˆµs and ˆµt supported on ms and mt examples respectively. In such a case, γ ∗ can be represented by a matrix of size ms × mt where γ ∗ i,j corresponds to the mass that should be sent from the point xis to the point xjt . Let ˆΠ(ˆµs, ˆµt) = {γ ∈ Rms×mt + |γ1mt = ˆµs, γ T 1ms = ˆµt}. Considering the Euclidean distance as the cost function, we denote by C p the ms × mt matrix composed of the costs C p ij = ‖xis - xjt ‖p2 . The p-Wasserstein distance can be reformulated as follows:

It is worth noting that (i) Problem (2) is a linear program, (ii) the solution is not stable and (iii) the algorithmic complexity is supercubic. To change it into a strongly convex problem with a unique solution, we usually add a regularization term in the form of the classic Shannon entropy [Cuturi, 2013]. Let λe ∈ R+ be a small regularization parameter, we get

with Ωe(γ) = - ∑ms i=1 ∑mt j=1 γij log(γij). Problem (3) can be efficiently solved by resorting to the Sinkhorn-Knopp algorithm [Cuturi, 2013]. The mass of a source point will now be spread across several target points preventing the algorithm from overfitting and leading to smoother solutions.

OTDA (Optimal Transport for Domain Adaptation) [Courty et al., 2017b] was the first attempt to use Optimal Transport for Domain Adaptation. While Problem (3) is totally unsupervised, OTDA takes into account the labels of the transported points. Let us suppose that a discrete label ys ∈ Y = J1, cK is associated to each source example, with c the number of classes. OTDA adds a penalty term to prevent two source points of different labels from being sent to the same target location. This takes the form of the following optimization problem:

where Ωc(γ) = ∑mt j=1 ∑ccl=1 ‖γ(Icl, j)‖2 and γ(Icl, j) is the column j of matrix γ with only the rows corresponding to samples of class cl.

2.2 Metric Learning

As said before, the cost matrix C used in OT is usually set to the Euclidean distance. Though this choice seems natural, it has a direct impact on the quality of the transportation. We suggest here to optimize this matrix by learning a metric that allows us to better match in a DA setting the source and target distributions, hopefully in a smaller feature space. Metric Learning (ML), and especially Mahalanobis distance learning, has been widely studied in the literature during the past decade (see, e.g., the survey [Bellet et al., 2015]). It typically boils down to optimizing the shape and the orientation of an ellipsoid rather than using the Euclidean ball. More formally, let L ∈ Rk×n with k ∈ J1, nK and M be a PSD matrix such as M = LT L. For all (i, j) ∈ J1,msK2 , the squared Mahalanobis distance D2M parameterized by M is defined as

Notice that L defines a unique M but there is more than one Cholesky decomposition of M. The goal of Metric Learning is to learn either the matrix L or M under semantic constraints, which typically aim to bring closer examples of the same class while pushing away data of different labels (see, e.g. LMNN [Weinberger and Saul, 2009] or ITML [Davis et al., 2007]). The problem is often convex in M but the PSD constraint makes the optimization more complicated. The minimization in L is not convex but is simpler and gives good results in practice. In the rest of this paper, we will denote by Ωl(L) the underlying objective function of the metric learning problem. Note that learning a Mahalanobis distance for OT has been recently studied [Deshpande et al., 2019; Genevay et al., 2018; Paty and Cuturi, 2019; Cuturi and Avis, 2014]. Our objective in the rest of this paper is to show how to optimize such a ground metric when OT is used to address domain adaptation tasks by the alignment of the source and target subspaces.

3 Theoretical Analysis of DAwith OT

In this section, we derive two theoretical results. First, we establish a strong relation between a PCA and the minimization of the Wasserstein distance. Then, we derive a generalization bound on the target error whose terms depend on several Wasserstein distances. By changing the Euclidean costs by a Mahalanobis distance, we can see Wp p (ˆµs, ˆµt) as a parameterized distance that might be optimized from training data. This leads to the design of a new Domain Adaptation algorithm, called MLOT (see Section 4), which learns the ground metric allowing us to optimize the transportation plan while performing the adaptation.

3.1 PCA andWasserstein Distance

As usually done in OT, let us use the push forward notation. For any measurable function g : X -→ X and distribution µ on X, we define g# µ(B) = µ(g-1 (B)) for all Borel B ∈ B(X). In practice, this means that we draw a point from µ and then apply the transformation g to that point. If g is a linear function, it can be assimilated to its associated matrix G. Let Dim(Im(g)) be the dimension of the affine subspace formed by the image of g. This notation allows us to define the dimension of a non-centered vector space.

The following theorem aims at showing that PCA is the best way to reduce the dimension of a distribution in the sense of the Wasserstein distance. By dimensionality reduction, we mean that the transformed distribution lays in a subspace (not necessarily centered) of X, but the points are still defined in X (see Figure 2). For the sake of clarity, we consider here the case of the 2-Wasserstein with the Euclidean distance as the underlying distance. We also focus on the case of a discrete centered distribution. The complete derivation for the more general case can be proved in a similar way.

Theorem 1. Given a set of m examples {xi }mi=1 lying in a n dimensional space and i.i.d. from a distribution µ. Let ˆµ the empirical counterpart of µ defined as ˆµ = 1m ∑mi=1 δxi with E(ˆµ) = 0. Let d ∈ J1, nK and V be the d × n matrix formed with the first d normalized eigenvectors of the covariance matrix of ˆµ. Let Gd = {g : Rn -→ Rn |Dim(Im(g)) ≤ d}. Then, we have

Proof. Suppose that the minimizer g∗ ∈ Gd of Problem (6) exists. In such a case, let γg∗ be the associated optimal coupling matrix. With these notations, we get:

To get rid of the last term of Eq. (7), let us reorder the function g∗ into ˜ g∗ (xi ) = g∗ (xj ) when (γg∗)i,j = 1m . In this case, the corresponding matrix γ˜ g∗ = 1m Im with Im the identity matrix, and we get:

The last line comes from the PCA. It shows that V T V associated with 1m Im upper bounds the optimal solution g∗ . But since V T V ∈ Gd, it is actually the optimal solution.

Theorem 1 tells us that PCA is the best way to reduce the dimension in the sense of the Wasserstein distance. The next result provides a generalization bound on the target error where Wasserstein distances are the main terms to minimize.

3.2 Upper Bound on the Target Risk

Let H = {h|h : X → Y} be the hypothesis space. We assume the existence of a deterministic ground-truth function f : X → Y which gives the label associated to each point of X. For all (h, h′ ) ∈ H2 , we define ϵt(h, h′ ) = Px∼µt (h(x) ̸= h′ (x)) and ϵs(h, h′ ) = Px∼µs (h(x) ̸= h′ (x)) which represent the disagreement between two classifiers. The goal of DA is to find the best h ∈ H which minimizes the target risk ϵt(h, f) = Px∼µt (h(x) ̸= f(x)). In the same way, ϵs(h, f) = Px∼µs (h(x) ̸= f(x)) is the source risk. To simplify the notations, let us use ϵt(h, f) = ϵt(h) and ϵs(h, f) = ϵs(h).

Lemma 1 (Generalization bound [Shen et al., 2017]). Let µs, µt be two probability measures on X. Assume the hypotheses h ∈ H are all K-Lipschitz continuous for some K ∈ R∗+. Then, ∀(h, h)′ ∈ H2 , the following holds:

Building on the proof of Redko et al. [2017] based on the seminal works of Ben-David et al. [2007] and Mansour et al. [2009], we derive the following bound.

Theorem 2. Let gs : X -→ X and gt : X -→ X. Under the assumption of Lemma 1, ∀h ∈ H, the following holds:

where λ is the combined error of the ideal hypothesis h∗ that minimizes the combined error ϵs(h∗ ) + ϵt(h∗ ).

Proof. We have :

Algorithm 1 MLOT

Input: η (gradient step) Xs Xt Ys

• 1: Vs = PCA(Xs), Vt = PCA(Xt)
• 2: Ls = V T s Vs, Lt = V T t Vt
• 3: for i = 1 to N do
• 4: γ = argmin γ∈ˆΠ(ˆµs,ˆµt)〈γ, C 2 (Ls, Lt)〉-λeΩe(γ)+λcΩcl(γ)
• 5: Ls = Ls - η∇Ls (〈γ,C 2 (Ls,Lt)〉+λlΩl(Ls))
• 6: end for
• 7: ˜Xs = γLtXt
• 8: classifier = classifier method( ˜Xs, Ys)
• 9: ˆ Yt = classifier(Xt)
• 10: return ˆ Yt

Note that if gs and gt are linear, gs#ˆµs and gt#ˆµt can be seen as linear projections of the source and target examples taking the form of two matrices that can be learned by any standard metric learning algorithm. Therefore, rather than discussing about its tightness, it is worth noticing that the previous bound is the first one which jointly relates (i) the target risk in domain adaptation, (ii) the minimization of the Wasserstein distance and (iii) the metrics that can be learned to get a better transportation plan. We can use Theorem 1 to minimize bothW2(ˆµs, gs#ˆµs) andW2(gt#ˆµt, ˆµt). Note that W2(µs, ˆµs) and W2(ˆµt, µt) can be bounded under some assumptions using Theorem 2.1 in [Bolley et al., 2007]. Moreover, λ is supposed to be small to allow the adaptation. A theoretical analysis about λ is available in [Redko et al., 2019a].

The last term of interest that has to be minimized in the bound of Theorem 2 is W2(gs#ˆµs, gt#ˆµt). We address this problem from an algorithmic perspective thanks to our algorithm MLOT presented in the next Section.

4 MLOT: Metric Learning in OT for DA

Inspired from OTDA [Courty et al., 2017b], our algorithm MLOT leverages our previous theoretical analysis and resorts to an additional term Ωl(Ls) dedicated to optimize a metric allowing us to get a better transportation plan. Let us consider the cost function C 2 (Ls,Lt)ij = ‖Lsxis - Ltxjt ‖22 . MLOT takes the form of the following joint optimization problem:

Note that MLOT only learns the matrix Ls associated to the source data. The reason is twofold. First, it prevents the algorithm from leading to a trivial minimal solution W2(Ls#ˆµs, Lt#ˆµt) where both matrices Ls and Lt are null. By this way, MLOT tends to provide two different matrices Ls (which is learned) and Lt (set to V T t Vt according to Theorem 1) which better capture the peculiarities of the two distributions. Second, labels - that are required to learn a metric - are available only in the source domain. To find the solution of Problem (10), we minimize the objective function w.r.t. γ and Ls alternately. From a practical point of view, we apply one step of gradient descent over Ls and then completely compute the optimal γ. Since the problem is not convex, the initialization of Ls is key. According to Theorem 1, we use a PCA to set Ls = V T s Vs. At the initialization, Ls is a n × n matrix of rank d. But note that along the iterations, this rank can increase if it allows a better adaptation. The pseudo-code of MLOT is described in Algo. 1, where Xs and Xt are the source and target datasets, and Ys is the set of source labels.

Note that any gradient descent-based metric learnign algorithm can be used to learn Ls via the term λlΩl(Ls). Note also that the computation of the barycenter of the transported points ˜Xs = γLtXt makes sense only if the 2-Wasserstein is used. Figure 3 summarizes the workflow of MLOT.

5 Experiments

In this section, we perform experiments and demonstrate the effectiveness of MLOT compared to OTDA and other baselines on various datasets and types of features.

5.1 Datasets

We use the Office-Caltech dataset [Gong et al., 2012] which is a classic benchmark on visual DA. We study the effect of using different features such as SURF features [Bay et al., 2006] and DeCAF Deep Learning features [Donahue et al., 2014]. The Office-Caltech dataset is composed of 4 different subsets (Amazon, Caltech, DSRL, Webcam) that are combined in a pairwise manner, to create 12 DA subproblems. The notation A → C means that Amazon is used as the source and Caltech as the target. There are the same 10 classes in each dataset containing from 157 to 1,123 images.

We also use the Office31 dataset [Saenko et al., 2010] with features extracted from the 7th layer of DeCAF Deep Learning network. The dataset is composed of 4,110 images in 3 subsets (Amazon, DSLR, Webcam) with 31 classes.

5.2 Setup and Cross-validation

We compare 10 different methods 1 that are able to handle arbirtary features. We exclude deep learning methods as they require having the original images and fine tuning a network. We compare: NA(No Adaptation). The classifier is learned on the source dataset and directly applied on the target. LMNN: Large Margin Nearest Neighbor [Weinberger and Saul, 2009]. SA: Subspace Alignment [Fernando et al., 2013]. CORAL: CORrelation ALignment [Sun et al., 2016]. TCA: Transfer Component Analysis [Pan et al., 2011]. OT:

1 We could not run MEDA [Wang et al., 2018] because the implementation requires the use of a proprietary software.

Optimal Transport with entropy [Cuturi, 2013]. OTDA: Optimal Transport with entropy and class regularization [Courty et al., 2017b]. OTDAp: OTDA after a PCA. JDOT: Joint Distribution Optimal Transportation [Courty et al., 2017a]. MLOT: our method. Following [Courty et al., 2017b] the final classification is done with a 1-Nearest Neighbor (1NN).

In unsupervised DA, there is no target label and it is impossible to use the classical cross-validation procedure to choose the best hyper-parameters. To fairly compare methods, we take inspiration from the work of [Zhong et al., 2010] and apply the following strategy for all methods. We first assign pseudo-labels to the target points (using the considered method) and then use these target labels to re-assign labels to the source data, using a basis DA algorithm. Here, we choose SA [Fernando et al., 2013] which has been shown to be one of the most robust DA method. We can then compare the actual source labels with the predicted source ones. We take the set of hyper-parameters that gives the best accuracy over 48 hours, limited to 1000 iterations. This back-and-forth adaptation is done independently for each pair of datasets. MLOT is parameterized by 5 hyper-parameters: the three regularization parameters (λe, λc, λl) which control the trade-off between each term in Eq. (10), the number of dimensions kept by the PCA (d) and the number of iterations (N). Note that in these experiments, we used arbitrarily LMNN [Weinberger and Saul, 2009] to learn Ls in the term Ωl(Ls). Therefore, an additional parameter has to be tuned corresponding to the margin used in this metric learning algorithm. Note that SA and MLOT resort to a PCA. To speed-up the process, we used a "randomized"-PCA [Halko et al., 2011] and run 10 iterations. This explains why the variance is indicated for these three methods in the reported results in Table 1.

The code of the 10 methods is available 2 , together with the datasets, the code for the cross-validation that recreates Table 1, and the code that produces automatically Figures 1 and 4.

5.3 Analysis of the Results

The results are reported in Table 1. For the SURF features, MLOT outperforms, on average, all the other methods. MLOT outperforms OTDA 8 times over the 12 DA subproblems and yields impressive improvements for some cases (e.g. W -→ A and C -→ D) and a clear gain on average (1.5 points). The results on Office-Caltech DeCAF6 features show the effectiveness of our method on deep learning features. MLOT outperforms by 1.8 the second best method (here OT). On the Office31 dataset, the best results are obtained by SA. MLOT is still very competitive and outperforms OTDA by 0.9 point on average.

As already mentioned, cross-validating the hyperparameters in unsupervised DA is key and is still an open problem, since we do not have access to labels from the target domain. We performed an experimental comparison to show how the cross-validation method used in this paper behaves when compared to a scenario where we would use the actual labels of the target examples. Table 2 reports the gap between the optimal hyperparameters and those obtained by our method inspired from [Zhong et al., 2010]. We can see that the ranking of the methods is preserved, even though this experiment shows that there is still room for improving the way we may tune the parameters in unsupervised DA. Note that the other datasets show similar behaviors. To show the specific gain brought by MLOT compared to OTDA, we performed a last experiment where we set the hyper-parameters of MLOT as follows: λl = 1, N = 10, marginLMNN = 10, d = 70; and we tune λe and λc. The results are reported in Figure 4. It is worth noticing that whatever the set of parameters, MLOT always yields better accuracy, which confirms the interest of learning a metric and using the PCA to initialize Ls and Lt. Note that when the entropy term has more importance (last column), the difference between the two methods is smaller because γ tends to be uniform. When the class regularization is set to 0 (first row), OTDA becomes similar to OT (Sinkhorn algorithm). This shows the effectiveness of MLOT even without the class regularization. However, the performances drop without this supervised information which tends to show that the metric learned and the class regularization are complementary. Notice that the results of MLOT are quite good for many values of the entropy and class regularizations (Figure 4 on the right). The best performance is 50.9 which is better than the result obtained by the cross-validation method. Once again, this is an evidence about the difficulty of tuning parameters in unsupervised DA.

2 https://github.com/Hv0nnus/MLOT

6 Conclusion

We proposed in this paper a new Domain Adaptation (DA) method, called MLOT, benefiting from both Metric Learning (ML) and Optimal Transport (OT). Dedicated to address problems in the complex unsupervised DA setting, MLOT jointly learns a good metric and the optimal transportation plan. A theoretical study has driven the design of MLOT. We derived a bound on the target error which prompts us to learn the ground metric involved in the Wasserstein distance. The experimental study has shown very competitive results and a significant improvement compared to OTDA, the first method coupling OT and DA. Although deep learning is not at the core of this paper, note that we designed a differentiable version of MLOT using the PyTorch framework. While the first results, with pre-extracted features, did not bring any performance boost, this implementations opens the door to a full end-to-end model for Wasserstein-based domain adaptation.

Acknowledgements

This paper is part of the TADALoT Project funded by the region Auvergne-Rhˆone-Alpes (France) with the Pack Ambition Recherche (2017, 17 011047 01).