Semi-Supervised Optimal Transport for Heterogeneous Domain Adaptation

1 Introduction

Domain adaptation (DA) aims to leverage data from an auxiliary source domain to assist the learning task in a domain of interest, a.k.a., target domain. Most existing works of DA consider the homogeneous DA problem, in which source and target samples share the same feature space [Long et al., 2014]. Compared with the homogeneous setting, heterogeneous domain adaptation (HDA) addresses a more challenging situation where the source and target samples are represented in different feature spaces [Li et al., 2014]. For instance, source and target samples could be images embedded in different kinds of features [Yan et al., 2017b], or documents in different languages [Zhou et al., 2016].

∗The co-first author.

†The corresponding author.

Most of the previous studies of HDA are devoted to learning a feature mapping function to transform the source and target samples into a common feature space. Nevertheless, these mapping functions are usually restricted in a predefined assumption space, e.g., linear projections used in [Tsai et al., 2016; Yan et al., 2017b], hence their capacities of transformation between two heterogeneous feature spaces would be rather limited.

In this paper, we propose a novel HDA algorithm by exploiting the theory of optimal transport (OT). Instead of learning a feature transformation, OT aims to match two distributions by transporting samples from one distribution to another. Very recently, a few works have been reported to apply OT for homogeneous domain adaptation [Perrot et al., 2016; Courty et al., 2017]. However, these methods rely on a transport distance metric for two sets of homogeneous samples, which is not applicable to HDA problems.

To address this issue, we treat the two heterogeneous feature spaces as two individual metric spaces and employ the entropic Gromov-Wasserstein (EGW) discrepancy [Peyr´e et al., 2016] to learn a transport plan, which transports samples from one metric space into another metric space. The EGW discrepancy is a powerful metric in OT for learning an optimal transport matrix, such that the distance between two metric spaces is minimized. EGW has been shown to be effective for many tasks such as 3D object matching [Peyr´e et al., 2016]. Since no common distance metric between two metric spaces is required, EGW can be naturally applied to the HDA problem.

A potential issue when applying EGW for HDA is that EGW is an unsupervised approach without considering label information. Therefore, even though the marginal distributions of two domains are matched, the semantic concepts may not be well aligned after the transportation. As illustrated in the simulated results in Figure 1, the transported source samples obtained by EGW (Figure 1(d)) follow a similar distribution with the target samples (Figure 1(b)). However, the target and transported source samples with different labels are mixed up, which leads to a significant performance drop in classification.

To alleviate the above issue, we propose to incorporate label information into EGW to learn an optimal transport plan satisfying label consistency for classification. We leverage both labeled and unlabeled target samples to constrain the transport matrix, such that the transported source samples and target samples with the same label follow similar distributions, as illustrated in Figure 1(f). The principal contributions of our work are summarized as follows.

• We propose a semi-supervised entropic GromovWasserstein discrepancy approach named SGW to incorporate the supervision information when learning the optimal transport. A conditional distribution matching regularization and a group entropic regularization are introduced to effectively exploit the label information to constrain the transportation.
• We apply a projected gradient algorithm with the Kullback-Leibler divergence to efficiently solve the derived optimization problem.
• We conduct comprehensive experiments on both synthetic and real-world datasets to demonstrate the effectiveness of our proposed method.

2 Related Studies

By leveraging knowledge extracted from data in an auxiliary source domain, domain adaptation addresses the problem where the labeled samples in a target domain are insufficient to train an effective classifier [Pan and Yang, 2010; Patel et al., 2015; Shao et al., 2015]. Homogeneous domain adaptation considers the situation where the source and target domains share the same feature space but have different data distributions [Pan et al., 2011; Long et al., 2015; Yan et al., 2017a; Liu et al., 2017]. Recent years, heterogeneous domain adaptation (HDA) has attracted a lot of attention [Zhou et al., 2014; 2016; Moon and Carbonell, 2017; Luo et al., 2017]. Compared with the homogeneous setting, HDA is more challenging due to the heterogeneity between the source and target feature spaces, making it difficult to directly leverage source samples to assist the target learning task.

In general, existing HDA algorithms can be categorized into two groups. The first group uses extra auxiliary data to connect the source and target feature spaces. In [Wu et al., 2014], co-occurrence data are employed to build relationships between the source and target samples, and graphbased algorithms are conducted for classification. TTL [Tan et al., 2015] applies a collective matrix factorization method to learn semantic new representations for target data. Yan et al. exploited co-occurrence data to address HDA in online learning settings [Yan et al., 2017c]. These methods require extra co-occurrence data, which are not always available in real-world applications.

Rather than relying on co-occurrence data to connect feature spaces, the second group of HDA algorithms aims to find effective feature transformations to map source and target samples into the same feature space. HFA [Duan et al., 2012] and SHFA [Li et al., 2014] augment source and target samples based on two projection matrices, and simultaneously train an SVM classifier on the augmented data. CDLS [Tsai et al., 2016] finds representative landmarks to learn a domain-invariant feature subspace, and then a classifier for target data is trained in the learned subspace. DCA [Yan et al., 2017b] jointly seeks for a discriminative correlation subspace defined by Canonical Correlation Analysis and learns a classifier in the found subspace.

Different from the above works, we address HDA by exploiting optimal transport [Peyr´e and Cuturi, 2017], which does not learn explicit feature transformations. Although there are a few works addressing homogeneous domain adaptation problems using optimal transport [Courty et al., 2017; Perrot et al., 2016; Redko et al., 2017], optimal transport for HDA is challenging and barely studied in the literature. It is not applicable to directly use the existing transport cost for homogeneous samples to the HDA problem. In this paper, we propose to learn optimal transport for HDA by leveraging the entropic Gromov-Wasserstein discrepancy [Peyr´e et al., 2016] to minimize the difference between the metric matrices of two heterogeneous domains.

3 LearningModel

3.1 Problem Statement and Notations

In heterogeneous domain adaptation (HDA), we are given a source domain and a target domain, which have different feature representations. The source domain contains a large number of labeled samples, and the target domain only contains a limited number of labeled samples (and a number of unlabeled samples in certain scenarios). The task is to take the advantage of the source labeled samples to improve the classification performance in the target domain.

For convenience of presentation, we denote the source samples as Xs = [xs1 , . . . , xsns ]⊤ ∈ Rns×ds with ns being the number of source samples and ds being the source feature dimension, and xsi ∈ Rds is the i-th source sample with label ys i ∈ Ys. The target samples are represented as Xt = [xt1 , . . . , xtnt ]⊤ ∈ Rnt×dt , where nt is the number of target samples, xti ∈ Rdt is the i-th target sample with dt being the feature dimension, Among the target samples, Xl = [xl1 , . . . , xlnl ]⊤ ∈ Rnl×dt are labeled target samples with labels {yl i }nl i=1 ∈ Yt , and Xu = [xu1 , . . . , xunu ]⊤ ∈ Rnu×dt are unlabeled target samples, where nl and nu are the number of labeled and unlabeled target samples, respectively, and nt = nl + nu. In our HDA problems, We have nl ≪ nu, ds ̸= dt and Ys = Yt = {1, . . . ,K}.

For the matrix A, log(A) and exp(A) are element-wise operations. The entropy of A is defined by

where Ai,j is the (i, j)-th element of A. For the matrices A and B, the inner product is defined as

3.2 Entropic Gromov-Wasserstein Discrepancy

The major challenge in HDA is that the feature representations in two domains are different. Thus, it is important to build the correspondence between heterogeneous feature spaces for reducing the domain discrepancy. To achieve this, we employ the entropic Gromov-Wasserstein (EGW) discrepancy [Peyr´e et al., 2016], which has shown superior performance in 3D object matching.

The EGW discrepancy is based on the optimal transport theory, which seeks for an optimal solution to transport a set of samples (or a distribution) to another set of samples (or another distribution). The advantage of the EGW discrepancy is that it does not rely on the distance between two sets of samples, which is usually required in classical optimal transport problems. Instead, EGW is defined on two individual metricmeasure spaces, thus is appropriate for the HDA problem, where the feature spaces of two domains are heterogeneous.

In particular, given a set of samples in one domain, the corresponding empirical distribution can be represented by a simplex of histograms p ∈ ∆n def. = {p ∈ Rn+|p⊤1n = 1}, where n is the number of samples, and the vector 1n = [1, . . . , 1]⊤ ∈ Rn . We use ps = [ 1 ns , . . . , 1 ns ]⊤ and pt = [ 1 nt , . . . , 1 nt ]⊤ to represent the empirical distributions of source and target samples, respectively. The joint distribution of ps and pt is defined by T ∈ T def. = {T ∈ Rns×nt |T1nt = ps, T⊤1ns = pt}.

Let Ms (resp. Mt) be a matrix representing a certain metric on source (resp. target) samples, the entropic GromovWasserstein problem seeks for an optimal transport matrix T, which gives the best match of two metric matrices. The EGW problem reads

where M s i,j (resp., M t i′ ,j ′ ) is the (i, j)-th (resp., (i′ , j ′ )-th) element of Ms (resp., Mt). The loss function ℓ(M s i,j , M t i′ ,j ′ ) measures the difference between M s i,j and M t i′ ,j ′ and is defined by ℓ(M s i,j , M t i′ ,j ′) = (M s i,j -M t i′ ,j ′)2 . The entropic regularization term is used to induce a smoother solution. Here we adopt the linear kernel matrix to construct the metric matrices, i.e., Ms =XsX⊤s andMt =XtX⊤t .

Let the transported source samples in the target domain be ˜Xs, and the transported metric matrix be ˜Ms = ˜Xs ˜X⊤s . After obtaining the transport matrix T, ˜Xs can be obtained by the GW barycenter [Peyr´e et al., 2016], which is given as follows

Note that the size of the transport matrix T is ns × nt. As a result, ˜Xs have the same numbers of features to that of target samples. Although the transportation is linear, the feature transformation induced by T is usually highly nonlinear [Courty et al., 2017]. As a result, the EGW potentially possesses a higher capacity compared with conventional HDA methods such as [Li et al., 2014; Yan et al., 2017b]. After learning the transportation, a classifier can be trained using the labeled target samples and transported labeled source samples, and then be applied to the unlabeled target samples for classification.

3.3 Semi-supervised Entropic Gromov-Wasserstein Discrepancy

A potential drawback when exploiting the entropic GW discrepancy for the HDA problem is that it does not exploit the label information in source and target domains. While it has shown superior performance in 3D object matching, the training samples in real-world tasks are more noisy and diverse. Thus, it is more desirable to further incorporate the label information to guide the learning of the transport matrix T.

To this end, we propose a semi-supervised entropic Gromov-Wasserstein discrepancy (SGW) to seek for the optimal transport satisfying label consistency constraints in the target domain. Motivated by this, we propose the following learning problem to achieve the objective of label consistency based on both labeled and unlabeled training data,

where E(T) is the abbreviation of EMs,Mt (T), Ωl(T) is designed for labeled target samples, and Ωu(T) is for unlabeled target samples. Next, we present the technical details regarding these two terms.

3.4 Conditional DistributionMatching

The solution to the EGW problem is able to adapt the marginal distributions of the target and transported source samples. To further match the conditional distributions of them, we enforce the centroids of target and transported source samples with the same label to approach each other. To this end, we minimize Ωl(T) to make the data with the same label distribute close. Let ˜Xs = nsTXt = [˜xs1 , . . . , ˜xsns ]⊤ be the transported source instrances, Ωl(T) is defined as follows:

where nsk and nlk are the number of labeled source and target samples with label k, ˜xsik and xlik are samples with label k. P ∈ RK×ns and Q ∈ RK×nl are label indicator matrices and are constructed by the following equations,

Ωl(T) is identical to the conditional maximum mean discrepancy when using the linear kernel, which measures the conditional distribution discrepancy between two sets of samples [Long et al., 2014; Tsai et al., 2016].

3.5 Group Entropic Regularization

Recall that the transport matrix T models how likely each source sample will be transported to each target sample, which is also referred to as mass. Intuitively, given a target sample, most of the mass of it should be transported from the source samples with the same label. Therefore, we divide the source samples into different groups according to their labels, and for the j-th column of the joint distribution T·,j, we design a group entropic regularization term to make the probability distribute on one group. Specifically, let Ik be the indices of the source samples with label k, the probability TIk,j is the sum of the probabilities from the source samples with label k to j-th target sample, i.e., TIk,j = ∑i∈Ik Ti,j, the regularization term is defined as

By minimizing the above group entropic regularization term, the probability for one target sample is concentrated on one group of source samples with the same label.

4 Optimization

Problem (5) is non-convex with the equality constraints, thus is difficult to solve. To efficiently solve it, we apply a projected gradient descent algorithm according to the KullbackLeibler divergence [Benamou et al., 2015; Peyr´e et al., 2016]. Specifically, at the τ-th iteration, Tτ is firstly updated by the exponentiated gradient method as follows:

where α > 0 is a step size. And then ˆTτ is projected into the definition domain T with the Kullback-Leibler metric

From [Benamou et al., 2015], the projection operation in Eq. (11) can be rewritten as the following regularized optimal transport problem

which can be solved by the Sinkhorn's fixed point algorithm [Cuturi, 2013]. Specifically, the transport cost matrix -ϵ log( ˆTτ ) can be simplified as

where we set ϵα = 1, and Ω(Tτ ) = λΩl(Tτ ) + γΩu(Tτ ). The solution to Problem (12) is

where the matrix Θ is constructed by

and the vectors (u, v) are computed using Sinkhorn's fixed point iterations as follows.

where the division operations are performed element-wisely. Algorithm 1 summarizes the main steps of the proposed SGW algorithm.

5 Experiment

5.1 Synthetic Data

To better illustrate our proposed approach, we use synthetic data to visualize the transport matrices and the transported source data obtained by EGW and SGW. The synthetic data are generated fromWine dataset 1 , which includes 178 samples with three classes. To generate heterogeneous source and target samples, we randomly pick up three and two features as the source and target features, respectively.

Figures 1(a) and 1(b) show the source and target data, where three colors correspond to three classes. The transport matrices obtained by EGW and SGW are visualized in Figures 1(c) and 1(e), respectively, in which a lighter point is a larger value indicating the corresponding joint distribution of the source and target samples is higher. For better observability, we order samples according to their labels to make the samples with the same label gather together. Therefore, in a label consistency preserving transport matrix, the larger values must be in the colored square frames. The transported source data in the target feature space are shown in Figures 1(d) and 1(f), respectively.

1 https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/

Algorithm 1 Semi-supervised Entropic Gromov-Wasserstein.

Initialize: T1 = psp⊤t , τ = 1.

• 1: repeat
• 2: Compute ˜Xs by Eq. (4).
• 3: Construct Θ based on Tτ and Eq. (15).
• 4: Obtain (u, v) by the fixed point iterations in Eq. (16).
• 5: Update Tτ+1 by Eq. (14)
• 6: τ := τ +1.
• 7: until Convergence.
• 8: Train a classifier on ( ˜Xs,Ys) and (Xl,Yl).
• 9: Predict for the unlabeled target data Xu.

From the results of EGW in Figures 1(c) and 1(d), we observe that although the transported source samples follow a similar distribution to the target samples, some source samples are transported to the mismatching regions with different labels in the target domain. For SGW, three labeled target samples are used for training, and the results are shown in Figures 1(e) and 1(f). We observe that most source samples are transported to the regions with the same labels in the target domain, which verifies the effect of Ωl(T) in Eq. (6). In addition, in Figure 1(e), one target sample is usually transported from a group of source samples with the same label, which demonstrates the effect of our proposed group entropic regularization in Eq. (9).

5.2 Real-World Datasets

To further validate the effectiveness of our proposed approach, we conduct experiments on two benchmark realworld datasets for object recognition and text classification, respectively.

Object Recognition: We use Office and Caltech-256 datasets for the object recognition task. Office [Saenko et al., 2010] includes images with 31 classes from three domains: amazon (A), dslr (D) and webcam (W). We use the publicly available SURF [Bay et al., 2006] and DeCAF6 [Donahue et al., 2014] features, and the dimensions of SURF and DeCAF6 features are 800 and 4096, respectively. Caltech-256 (C) [Griffin et al., 2007] includes images with 256 classes, and the same 800-d SURF features are publicly available. Following [Tsai et al., 2016; Yan et al., 2017b], we use the 10 overlapping classes between two datasets to construct classification tasks.

Text Classification: The text classification task is conducted on the Reuters multilingual dataset [Amini et al., 2009], which includes six classes and five languages, i.e., English, French, German, Italian and Spanish. Each language is taken as a domain. Similar to the experimental setup in [Li et al., 2014; Tsai et al., 2016], The documents are represented by TF-IDF features and are preprocessed by PCA with 60% energy preserved.

5.3 Baseline Methods

We compare with SVM [Chang and Lin, 2011], CCA+OT, EGW, SHFA [Li et al., 2014], CDLS [Tsai et al., 2016] and DCA [Yan et al., 2017b]. Among these methods, SVM is a simple baseline without considering source domain data. CCA+OT firstly performs CCA on source and target data, and then transports source data into the target domain based on a classical optimal transport method. EGW learns the optimal transport matrix by solving the EGW problem, and an SVM classifier is trained on the transported source samples. SHFA, CDLS and DCA are three state-of-the-art HDA methods, which are performed in a semi-supervised HDA fashion, where some unlabeled target samples are used for training.

For simplicity and fair comparison, we set the trade-off parameter of SVM to C = 1 for all the methods and tasks. The parameters of SGW are empirically set to ϵ = 0.01, λ = 1 and γ = 1, and the sensitivity study is provided in Section 5.6. For the baseline methods, we follow the previous work [Li et al., 2014] to search the parameters in the spaces recommended by the original papers and report their best results. We repeatedly conduct experiments 10 trials and report the average classification accuracies.

5.4 Results on Object Recognition Tasks

Office includes three domains (i.e., A, D and W), which are represented as two types of features (i.e., SURF and DeCAF6), and Caltech-256 dataset includes one domain (i.e., C) with SURF features. We take C as the source domain, and a domain in Office as the target domain, and vice versa.

We randomly choose 3 target samples per class as the labeled target data, and the rest target samples as the test data. 20 labeled source samples are used for training for the source domains A, W and C, and 5 labeled source samples are used for training for the source domain D, since the number of samples in D is much smaller.

Table 1 presents the results of the Office-Caltech dataset. SGW achieves the best results, which demonstrates the effectiveness of our proposed method. The domain adaptation methods CCA+OT, SHFA, CDLS and DCA outperform SVM, which verifies that leveraging knowledge from heterogeneous source domain is beneficial for the target task. Compared with SVM, EGW achieves improvements in most cases, which shows that the EGW discrepancy is helpful for matching the data structure between two heterogeneous domains. However, there are still a few cases that EGW is even worse than SVM. A possible reason is that the samples from different categories could be mixed up after transportation since the label information is not employed in EGW. Our proposed SGW obtains consistent better performance than the baseline methods. We attribute this to the effective use of label information for guiding the optimal transport.

5.5 Results on Text Classification Tasks

Similar to the settings in [Li et al., 2014; Tsai et al., 2016], we take Spanish as the target domain, and the other four languages as the source domain, respectively. We randomly choose 100 source samples per class as the labeled source data. For the target domain, {5, 10, 15, 20} samples are used as labeled training samples, and the remaining samples are used as test data, among which 3,000 samples are unlabeled training data for semi-supervised learning.

Figure 2 shows the results on the text classification tasks w.r.t. different numbers of labeled target samples. We observe that the performance of all the methods increases when using more labeled target samples for training, which validates the effect of adding more labeled target data. Our SGW approach consistently outperforms all the baselines, which demonstrates the effectiveness of our proposed method for heterogeneous domain adaptation.

5.6 Sensitivity Study

We take the task C(SURF) → W(DeCAF6) as an example to study the parameter sensitivity of SGW. We vary the trade-off parameters ϵ, λ and γ in the search space {0.001, 0.01, 0.1, 1, 10, 100}, and plot the results in Figure 3. DCA achieves the second best result on this task, thus is taken as the reference. In most cases, SGW outperforms DCA, which demonstrates that the performance of SGW is stable to the trade-off parameters in the certain range. We have similar observations on other tasks.

5.7 Running Time Results

We take C(SURF) →W(DeCAF6) as a representative task to evaluate the efficiencies of all the methods. The experiments are performed on a workstation with Xeon 3.40 GHz CPU and 16 GB of RAM. Table 2 presents the running time results. SVMonly involves target data, thus achieves the shortest running time. SHFA, CDLS and DCA learn feature transformations and classifiers, and have to solve quadratic programming problems with heavy matrix computations. As a result, the running times of them are much longer than SVM. EGW and SGW usually converge to a good solution within a few iterations. Therefore, the running times of EGW and SGW are less than those of SHFA, CDLS and DCA.

6 Conclusion

In this paper, we propose a new algorithm using optimal transport for heterogeneous domain adaptation. We learn an optimal transport matrix to transport labeled source samples into the target domain. To incorporate label information to guide the learning of optimal transport, we propose a semisupervised entropic Gromov-Wasserstein discrepancy, which remains the metric matrices on source data before and after transportation, and makes the labeled target and transported source samples follow similar conditional distributions. We conduct extensive experiments on both synthetic and realworld datasets, and the results demonstrate the effectiveness and efficiency of our proposed method.

Acknowledgments

This work was supported by National Natural Science Foundation of China (NSFC) 61502177 and 61602185, and Recruitment Program for Young Professionals, and Guangdong Provincial Scientific and Technological funds 2017B090901008, 2017A010101011, 2017B090910005, and Fundamental Research Funds for the Central Universities D2172500, D2172480, and Pearl River S&T Nova Program of Guangzhou 201806010081 and CCF-Tencent Open Research Fund RAGR20170105.