Distance Metric Facilitated Transportation between Heterogeneous Domains

1 Introduction

A large amount of training examples leads to the effectiveness of a learning algorithm [Mohri et al., 2012]. In real applications, however, this is not always the case due to the high instance/label collection cost [Li et al., 2014; Li and Zhou, 2015]. The insufficiency of the training examples could be compensated by related tasks/data which are easier to obtain, so the knowledge from the source tasks can be extracted and adapted to help the learning on the target domain. Various methods and applications show that it is possible and necessary to deal with the divergence and do such kind of information transformation [Pan and Yang, 2010; Si et al., 2010; Long et al., 2014; Tommasi et al., 2014].

∗This research was supported by the National Key R&D Program of China (2018YFB1004300), the NSFC (61773198, 61632004), and the Tencent fund. Part of the work is implemented when the first author served as an intern in Tencent, China.

One common shift between tasks lies in the change of the statistics [Ben-David and Urner, 2012], including both conditional and marginal distributions. Thus, the consistency persistence followed by the distribution estimation lies the basis of the adaptation process. For example, instance weight keeps the statistical consistency between domains [Gretton et al., 2012]; the Optimal Transport (OT) also show effectiveness to transfer source domain instances to the target space in an unsupervised way based on the least effort principle [Courty et al., 2017a; 2017b]. Without restricting to this homogeneous case, the knowledge transfer could also be extended between heterogeneous feature sets. As in [Jiang and Li, 2017], paired inputs help learn better representation for a certain modality.

We consider a general supervised case on not-aligned heterogeneous domains with labeled examples, where source domain has relative more instances. There exist two apparent obstacles: the gap between two different feature sets, i.e., the two heterogeneous domains; and the change of distribution during the learning of the target task. In this paper, we solve the above two problems of heterogeneous transfer learning with the help of distance metric in a joint manner and propose the Metric Transporation on HEterogeneous RErepresentations (MAPHERE) approach. Specifically, we treat all target domain instances as anchors, and an asymmetric transformation is learned to map instance from the source to the target domain, whose advantage is two-side. On the one hand, the projection implements a bridge to reduce the discrepancy between domains; besides, it finds a metric in the target domain for measuring a better distance between objects. Based on the metric facilitated pairwise cost, optimal transport depicts the distribution shift between tasks well. Since the similar and dissimilar relationship between both source domain and cross-domain examples direct the whole transfer, the label information is fully utilized to leverage and preserve the domain structure. Leveraging the distance metric and transportation, the nearest neighbor classifier can determine labels on the target task. Experiments on synthetic datasets show that by adjusting original distance measure between instances effectively, the utilization of metric with side information assists the target classification a lot. In addition, on real applications over images and texts, our MAPHERE approach appears better performance w.r.t. the state-of-the-art methods.

The rest of the paper starts with the related work. Then the MAPHERE approach is described in detail after a brief introduction to the homogeneous optimal transport domain adaptation method. Last are experiments and conclusion.

2 RelatedWork

Owing to the ability to take advantage of related task knowledge to relieve the limited data burden of the current problem, transfer learning methods attract a lot of attention in the machine learning fields. Assuming there are only limited usable labeled examples in the target domain, how to extract as much information as possible from both current examples and from related domains in other tasks are stressed. Based on the type of source domain, methods of transfer learning could be partitioned to the homogeneous and heterogeneous cases [Pan and Yang, 2010]. For the former scenario, empirical estimation of distributions, for the marginal distribution [BenDavid et al., 2010; Courty et al., 2017b] or the joint distribution [Courty et al., 2017a], are optimized to keep the consistency between two tasks. While in the heterogeneous case, the paired relationship between objects [Kulis et al., 2011; Jiang and Li, 2017; Shi and Knoblock, 2017], the joint training over transformation and classifier [Hoffman et al., 2013], or a shared subspace [Aljundi et al., 2015] are learned to link two different domains together. Learned metric transformation in MAPHERE approach gives rise to the advantage transferring knowledge from source to the target domain without the feature set limit, and the leverage of side information persists the consistency between two distributions.

Optimal Transport (OT) finds a coupling between two distributions based on the ground cost, which can be used as a map across two sets [Kolouri et al., 2017]. Facilitated by the accelerated solver recently [Cuturi, 2013], the optimal transport has been successfully applied in various applications, such as multi-label cost computation [Frogner et al., 2015], and domain adaptation [Courty et al., 2017b; 2017a]. In the homogeneous case, the leaned transport plan is able to map all source domain instances together with labels to the target domain based on the Euclidean distance ground matrix. Supervision information can be incorporated into the group lasso regularizer on the transportation map. In MAPHERE, the advantage of OT is extended to the heterogeneous case. Better cost measurement with the learned transformation also assists the cross-task transportation estimation.

Distance metric learning aims to find better representations than the Euclidean one, considering the correlation between features and task property. Both pairwise and triplet side-information provide the direction for distance optimization [Davis et al., 2007; Weinberger and Saul, 2009]. Transformations could be learned to fuse domain information together [Geng et al., 2011; Wang et al., 2014; Luo et al., 2016]. Emphasizing domain linkages, MAPHERE transfers label and structure information across domain effectively.

3 Homogeneous Domain Adaptation with Optimal Transport

Consider two heterogeneous feature spaces, i.e., source domain with Ns examples {(xsi , ys i )}Ns i=1 , where instance xsi ∈ Rds forms Xs ∈ RNs×ds and ys i ∈ {1, . . . ,C} with totally C classes. While there are Nt examples {(xtj , yt j )}Nt j=1 in the target domain. xtj ∈ Rdt forms Xt ∈ RNt×dt and yt j ∈ {1, . . . ,C}. The number of available instances in the target domain is much smaller than the one of the source domain, i.e., Nt ≪ Ns. Denote xsi ∼ Xs with marginal distribution µs, and xtj ∼ Xt with marginal distribution µt, respectively. 1 is an all one-value vector, whose length could be determined by the context. In this supervised learning task, the goal is to utilize all examples from the source domain to help the classifier training of the target task.

First consider the homogeneous case when ds = dt, it is reasonable to assume that the change between source and target domains comes from an unknown, possibly non-linear transformation T (·) on the input space. In addition, the label information can be preserved after this transformation, i.e., ps(y | xsi ) = pt(y | T (xsi )), with ps and pt correspond to source and target conditional distributions. This transformation between domains could be discovered by the Kantorovitch relaxation of Optimal Transport (OT) [Courty et al., 2017b], via optimizing a coupling Π over µs and µt:

The coupling Π satisfies the constraint that the two marginals of Π are exactly equal to µs and µt, and c(xs , xt ) is the ground matrix measuring cost when moving from xs to xt . Π provides a way to push-forward one distribution to another, and the value of Eq. 1 can be regarded as the divergence between two distributions, even there is no overlap between them. With limited instances, both source and target marginal distributions could be estimated in the empirical form, i.e., the uniform distribution over all examples. In this discrete case, Eq. 1 is transformed to:

C ∈ RNs×Nt with Cij = c(xsi , xtj ) is the pairwise cost matrix, and squared Euclidean distance is used in the following discussion. T ∈ RNs×Nt is the transportation map from Xs to Xt, which shows the proportion to move a unit mass of each source domain instance to the target. Two constraints over T require the transportation should be consistent with the marginal distributions. OT interpolates source and target distributions, and the transported source domain instance ˆxti = T (xsi ) could be represented as [Perrot et al., 2016]:

After taking derivatives w.r.t. x and set it to zero, we can get ˆxti = NsX⊤ t T ⊤ i , where Ti is the i-th row of T. Since the transformation is represented by the interpolation with all target domain instances, it is able to reflect a non-linear T .

Therefore, based on OT, domain adaptation could be progressed in two stages: first the optimal transportation map T is evaluated based on the cross-domain pairwise Euclidean distance cost; then all source domain instances, together with their label information, are transferred to the target domain, which augments the target task training set a lot. Last, a standard classifier is applied over this augmented set. The effectiveness of this strategy has been validated in [Perrot et al., 2016; Courty et al., 2017a; 2017b].

4 The MAPHERE Approach

There are two main drawbacks of the previous OT transfer strategy. First, it is hard to estimate the right instance relationship with the Euclidean distance, since it neglects the differences between domains [Bellet et al., 2015]. The provided label information, although limited, can help improve the distance estimation. Besides, since Euclidean distance computation requires features with the same form of representation, the OT based approaches are hard to be applied over heterogeneous feature sets. In this paper, we propose the Metric Transportation on heterogeneous representations (MAPHERE) approach, taking advantage of distance metric learning to solve above two considerations simultaneously.

In MAPHERE, an asymmetric transformation acts as a distance metric to fill the gap between diverse features, and facilitates the distance computation cross tasks. Based on the new distance measure, optimal transport furthermore reduces the differences between two domain distributions, and finds correspondences between the mapped source domain instances and the target set. Weakly supervised side information, i.e., the pairwise similar and dissimilar relationship between objects, is also incorporated in to direct the whole transfer process. Thus, same class instances will have small distances, while different class instances have larger ones. The main flow of MAPHERE is illustrated in Fig. 1.

The location of the target task examples are anchored during the whole training process, and the source domain instances are mapped to the target feature space with a transformation L ∈ Rdt×ds . This asymmetric movement avoids the inter-domain collapse and helps the final discriminative process [Kulis et al., 2011]. The mapped source domain instance xsi can be represented as ˆxsi = Lxsi ∈ Rdt . With the help of L, the mapped source domain instance ˆxsi has the same type of representation with xtj in the target domain.

Considering types of differences between two domains, there may still exist a discrepancy between two sets even in the same feature space. Therefore, the transfer process is continued by aligning the remaining distribution differences by the optimal transport over the target domain. The ground cost matrix between mapped source domain instances ˆxsi and target domain instances xti can be computed in the squared form, Cij = ‖ˆxsi -xtj ‖22 . The better the metric L revealing the relationship between instances, the more exact the cost estimation between two sets. Based on the new distance measurement, MAPHERE seeks a transportation plan T ∈ RNs×Nt in the form of Eq. 2, and gets a nonlinear map between transformed source instances and target representations.

Up to now, the relationship between two tasks are linked with transformation L and transportation T in an unsupervised way. MAPHERE is also able to make use of the limited label information in both domains by considering the pairwise linkages between objects. It is the relative comparison between objects that reveals more useful information with limited instances. Formally, we construct P pairs, P = {(xpm, xpn , ypmn )}Pp=1 , and in each pair, ypmn ∈ {-1, 1} denotes whether two instances are similar or not. Following formulation reveals the satisfaction of similarity relationship:

ℓ(·) is a convex loss function, which is usually an upper bound of the 0-1 loss. γymn is the pre-defined threshold value for similar and dissimilar instances. For example, for square loss, ℓ(x) = (x- 1)2 , it requires the similar (resp. dissimilar) objects should have small distances near γ1 -1 (resp. γ-1 +1). Thus, similar instances are pulled together, while dissimilar ones are pushed far away. This relationship should be kept both in source and target domains, so in MAPHERE, two types of pairs are extracted. The first type focuses on the relationship of the source domain. With similar and dissimilar instances generated based on nearest neighbors for each example, pairs indicate the class information of the source task. It is notable that this type of constraint preserves the source domain structure in the target space, and the concrete form of the pair could be (NsX⊤ t T ⊤ m , NsX⊤ t T ⊤ n ), which are the last transferred representations of source domain examples for xm and xn. The second type of pairs includes one target instance and one source mapped instance, i.e., the cross-domain pairs. Since there are only limited target labeled examples, we can sample same class and different class instances from the mapped source set to generate pairs. Thus, for source domain instance xm and target domain instance xn, we use the pair (NsX⊤ t T ⊤ m , xtn ) in the objective. In summary, we utilize the pairwise linkage information from both source and cross domains, which directs the learning process of target transportation T, and indirectly influences the training of crossdomain projection L. The whole objective of MAPHERE is

The feature space transformation L and target domain transportation map T are learned in a joint manner. Ω(L) is the regularizer over L. λ1 and λ2 are two non-negative parameters. With learned transportation plan T, all source task instances {xsi }Ns i=1 could be transferred to the target domain, together with their labels. With which, the final classification is conducted with 1 Nearest Neighbor on the target domain.

(a) GroundTruth

(b) OT

(c) OTGL

(d) MMDT

(e) MAPHERE

(f) GroundTruth

(g) OT

(h) OTGL

(i) MMDT

(j) MAPHERE

Figure 2: The effectiveness of MAPHERE approach on the synthetic dataset. We use different colors to differentiate the 3 classes, and use crosses/circles to denote source and target instances, respectively. The first row of plots show the transportation maps output by different methods, the darker the color, the smaller the transportation plan value. Different columns correspond to different methods. The first column is the ground truth result, and (f) is the original scatter of source and target instances. Plots (g) - (j) show the transformed source domain instances in the target domain by different methods, and original target domain instances. Best viewed in color.

5 Optimization for MAPHERE

The optimization for MAPHERE in Eq. 4 could be solved in an alternative manner. When the cross domain mapping L is fixed, the OT problem uses the distance between mapped source instances and the target instances as the ground metric. With the adjusted cost matrix, the transportation plan is updated under the supervision of types of linkages. Given the transportation T, the source domain instances are mapped to align with target anchors using the transportation weights.

With fixed transportation map T revealing a type of crossdomain pairwise similarity, we tune the feature space map L:

Since Tij ≥ 0, the subproblem actually finds a map between source and target examples, weighted by the transportation plan between them. The pair with larger weights Tij shows more representation similarity considering the distribution change, thus it requires more strength to reduce their differences. We can get the closed form solution of L, i.e.,

(6)

when the biased regularizer Ω(L) = ‖L-L0‖2F is used. L0 is a prior for the transformation L.

With optimized L, the cost matrix C could be computed between transformed source and target instances. The optimization subproblem for T is difficult since there are equality constraints over T in the objective, and T also exists in the metric loss function, as shown in the following formulation:

Considering the possible nonlinear term over T, the objective can be solved with conditional gradient descent method [Courty et al., 2017b], a.k.a. Frank-Wolfe optimizer. It linearizes the objective by first order approximation, which could be solved in an easier and efficient way. The convergence property of the conditional gradient descent could be found in [Jaggi, 2013]. Square loss is used in the remaining part of the paper. Since there are two types of pairs, we consider their derivatives separately. When two instances in a pair both come from the source domain, we have the loss term oil = (yil(γyil - ‖NsX⊤ t T ⊤ i - NsX⊤ t T ⊤ l ‖22 ) - 1)2 , which has the derivative for Ti (similar for Tl)

While for a cross domain pair, i.e., oij = (yij(γyij - ‖NsX⊤ t T ⊤ i -xtj ‖22 ) -1)2 , we have

We initialize the transformation L first, then the optimal transport plan T could be solved based on the refined cost matrix. Since each sub-problem decreases the total loss function of the objective in Eq. 4, the final algorithm will converge at last. In the implementation, L0 is an identity matrix in the homogeneous case; while in the heterogeneous scenario, L0 comes from a least square problem mapping the source domain instances to the center of corresponding target domain classes. Two types of pairs are sampled based on Euclidean distance nearest neighbors of instances (5NN and 3NN are used to construct source and target domain same class similar pairs, while 1NN are used to generate both domains' impostors). λ1 = 1 and λ2 = 10 are default parameters.

6 Experiments

We validate the effectiveness of our MAPHERE approach from various perspectives. Based on a synthetic example, the importance of the "metric facilitated" consideration is stressed; then MAPHERE is extensively compared with other methods in both homogeneous and heterogeneous case in both image and text classifications.

6.1 Synthetic Illustration

We first illustrate the necessity of "metric facilitated" consideration in the domain adaptation task on a synthetic dataset. A 2D three-class dataset is generated based on Gaussian distribution, where the source and target domains are with different centers but the same variances. There are 50 instances in each class. The corresponding classes in source and target domains are first generated in near locations, and then we exchange the label of the latter two classes in the target domain. Since the direct space location information is not correct for two of the three classes, the transfer learning methods should utilize the label information to do a good transfer.

We compare with unsupervised Optimal Transport based Domain Adaptation (OT), its supervised extension with Group Lasso (OTGL) [Courty et al., 2017b], and Maximum Margin Domain Adaptation (MMDT) [Hoffman et al., 2013]. OTGL considers the class information with the group lasso regularizer on transportation plan. MMDT learns a transformation over the source domain hypothesis, and trains classifier and cross-domain mapping jointly. All methods are investigated with default parameters. The learned transportation map and mapped source domain results are shown in Fig. 2.

The first row of plots in Fig. 2 are the plots of true and learned transportation maps, i.e., a type of similarity matrix between source and target domain instances. The darker the color, the smaller the value. Plot (a) shows the ground truth transportation, where the permutation between last two classes can be clearly found. The block diagonal structure exists in (b)-(d). OT finds the cross-domain mapping with the Euclidean distance, so source domain instances are uniformly mapped to the nearby target instances, neglecting their labels. OTGL and MMDT consider the class information.

For MMDT, we plot the scaled inner product similarity matrix between domains as its transportation plan. Since missing a good metric between instances, it is hard for them to find a good match between distance computation and class correspondence. In (c)-(d), the relationship between classes is disturbed. For MAPHERE, the class mapping is correctly learned, which is similar to the ground-truth. The second row in Fig. 2 demonstrates the mapped source domain instances in the target space. Similarly, (f) is the original source and target plot. From results in (g)-(j), only our MAPHERE approach maps source domain instances to corresponding target classes correctly. The performance of MAPHERE validates the importance to utilize the specific distance computation and the label information in transfer learning.

6.2 Homogeneous Image Classification

We first test the performance of MAPHERE approach on homogeneous domain adaptation task on the Office-Caltech dataset. There are totally four domains, namely Amazon (A), Caltech (C), DSLR (D) and Webcam (W), and 10 classes for each. Each domain is used as source and target alternatively, which generates 12 different tasks. We use the same protocol (including the splits) as [Perrot and Habrard, 2015]. For each task, we repeat the investigations 20 trials, and in each trial, there are 8 labeled source examples (20 if the source is Amazon) and 3 labeled target examples are selected. All instances are normalized thanks to the zscore and the dimensionality is reduced to 20 using a PCA.

We compare with optimal transport for domain adaptation with two different class regularizers OTIT and OTGL [Courty et al., 2017b], mapping estimation for optimal transport OTMT [Perrot et al., 2016], joint domain adaptation method JDOT [Courty et al., 2017a], Maximum Margin learning for domain invariant representation (MMDT) [Hoffman et al., 2013], Asymmetric Regularized Cross-domain transformation (ARC) [Kulis et al., 2011], Geodistic Flow Kernel (GFK) [Gong et al., 2012] and Hypothesis biased Large Margin Nearest Neighbor (LMNNH) [Perrot and Habrard, 2015]. All methods do classification with 1NN on the target domain, with the help of transformed instances or classifier.

The LMNN and 1NN results on the source and target domains are listed as baselines (LMNNT, 1NNS, and 1NNT). Test accuracy values (mean±std.) are listed in Table 1. From the results, OT methods can achieve good performance, which shows that joint consideration of source and target distributions is useful, and OT is able to learn the transportation map in some cases. Our MAPHERE approach can achieve the best performance in most tasks, which attributes to the feature space transformation and effective utilization pairwise linkage. Compared with ARC, which only learns a domains transformation, the superiority of MAPHERE validates the necessity of the further distribution consideration with OT.

The changes of performance given different amount of source labeled data are also investigated, as shown in Fig. 3. The number of labeled examples in each source task class increases from 4 to 20. MAPHERE is compared with ARC, MMDT, OTMT, JDOT, OTIT, and OTGL. Due to the page limit, 2 tasks, i.e., W→C and C→A, are listed. From the results, the performance of all methods increases when there are more source domain labels, which shows the helpfulness of enough source task labeled data. In addition, our MAPHERE approach achieves best performance with all the label ratios. Therefore, our MAPHERE approach is effective even there are only limited number of labels from the source domain.

6.3 Heterogeneous Image Classification

The extension to heterogeneous cases of MAPHERE is also considered on the Office-Caltech dataset, with the same experimental settings as before. But in this case, the source and target tasks have different dimensions, i.e., PCA to 30 for source domain, and 20 for target tasks. Results are shown in Table 2, where SVM on the target task is listed as a baseline. Besides, we compare with HFA [Li et al., 2014], which can learn with augmented features. MAPHERE also performs best in this heterogeneous case. Compared with MMDT, the superiority of MAPHERE validate the assistance of OT based distribution alignment after transformation, and the effectiveness of using pairwise information between objects.

7 Investigation onWeb Page Classification

In this section, we investigate MAPHERE over a web page classification problem. 1 Web pages are described by their web texts and linkage information with others. In this experiment, source domain is the web texts and the target domain is the linkage information. Dimensionality reduction is applied to each domain and keeps 50% energy. Source and target dimensionality are 40, 17 (Cornell), 41, 24 (Wisconsin); and 40, 27 (Washington), respectively. Each task has 5 classes. There are only 5 instances for each class in the target domain. Results are shown in Table 3. MMDT and HFA cannot perform well in this task. MAPHERE also gets good results, thanks to the learned transformation and the distribution change consideration.

8 Conclusion

How to utilize limited labeled examples from the related task is important in machine learning fields, and the main obstacles lie in the fact both feature space and distribution will change. We propose the Metric Transportation on HEterogeneous REpresentations (MAPHERE) approach in this paper, which learns the transformation between feature space and the transportation plan handling the non-stationary distribution jointly. Based on the learned transformation, a better distance metric is evaluated on the target task. The limited label information from source task is also organized as pairwise linkages between both source and cross-domain objects. Experiments on both homogeneous and heterogeneous cases show that the MAPHERE approach deals with the transfer learning task effectively. Future directions include the consideration of novel classes in both source and target tasks.

1 Data from http://www.cs.cmu.edu/ webkb/