General Heterogeneous Transfer Distance Metric Learning via Knowledge Fragments Transfer

1 Introduction

We often encounter the label or side information (such as the similar/dissimilar constraints) deficiency problem in the machine learning and pattern recognition applications due to the high labeling cost (labor-intensive and expensive). Transfer learning [Pan and Yang, 2010; Luo et al., 2014; Hu et al., 2015; Isele et al., 2016] is able to mitigate this problem in the target learning task or domain by leveraging information from other related source tasks or domains [Liu et al., 2017]. A typical example is the unconstrained human gait recognition, which is to identify a person's manner of walking from a distance in the wild conditions [Tao et al., 2007b]. We can only label a few gait images (or image sequences) in a new scenario but we may have large amounts of labeled ones in some other scenarios. The data distributions of two different scenarios can be very different due to the varying lighting and background. Hence, the recognition model trained in a label-rich scenario may perform bad in the label-scarce one, and transfer learning is helpful in this case. Some other examples include the sentiment classification [Pan and Yang, 2010], and image super-resolution [Dai et al., 2015].

Recently, transfer distance metric learning (TDML) [Luo et al., 2014; Hu et al., 2015] has attracted an increasing attention, because it is crucial to learn a reliable distance metric [Tao et al., 2007a] to reveal the data relationships in diverse research areas, ranging from clustering and classification to kernel machines and ranking [Kulis, 2012; Lim and Lanckriet, 2014]. Traditional TDML algorithms usually assume the source and target domain share the same feature representation. This assumption may not be valid in practice. For example, the document representations of different languages vary in multilingual document categorization since the utilized vocabularies are different [Luo et al., 2016]. Some recent works on image annotation and retrieval suggest utilizing source features to guide learning a better representation for target features [Qi et al., 2012; Dai et al., 2015]. The feature spaces of source and target domains can be quite different and there is sometimes semantic gap between them (e.g. text and visual features) [Xu et al., 2014; 2015].

There exist some heterogeneous transfer learning (HTL) approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011; Qi et al., 2012] that are able to manage heterogeneous representations. These approaches often transform the heterogeneous features into a common subspace, so that the difference between heterogeneous domains is reduced. Most of the HTL methods are not specially designed for distance metric learning (DML), but we can derive a metric from the learned transformation for each domain. Although effective in some cases, the current HTL approaches exhibit two main defects: 1) the source and target transformations are learned together. Consequently, they are not feasible when original source domain data are not available, and only source metric is provided. Besides, learning both the source and target transformations may significantly increase the complexity of the algorithms when the number of samples in the source domain is large; 2) the transformations are restricted to be linear and thus the performance may be unsatisfactory in many visual analysis-based applications, since the structure of data distribution is nonlinear for most types of the visual features.

Inspired by the knowledge fragment transfer strategy [Vapnik and Izmailov, 2015], we develop a general heterogeneous TDML (HTDML) framework to overcome these defects. In particular, the proposed HTDML first learns the source distance metric by applying existing linear or nonlinear metric learning algorithms on the given labeled source data. Then we extract some knowledge fragments from the learned metric for transfer. In this paper, we assume there are abundant unlabeled samples that have feature representations in both of the source and target domains. By simultaneously minimizing the empirical losses w.r.t. the metric in the target domain, and enforcing the metric to agree with the knowledge fragments on the unlabeled samples, we learn an improved target metric by making use of the additional source information contained in the fragments.

The main advantages of the proposed HTDML are: 1) the source knowledge fragments can be learned offline, we do not have to reuse the original source domain data. Hence, the algorithm can be used in the applications where source domain data are invisible. Besides, any (linear or nonlinear) metric learning algorithms can be adopted to learn the source knowledge fragments. Thus, the method is general, flexible, and easy-to-use; 2) nonlinear metric can be learned for the target domain by incorporating some nonlinear learning technique, such as gradient boosting regression tree (GBRT) [Kedem et al., 2012]. Hence the proposed method can be widely adopted in many applications, especially the challenging visual-analytic based ones. We conduct experiments on two popular applications: scene classification and object recognition. In addition to the Euclidean (EU) and single domain DML baselines, we further compare with several representative heterogeneous transfer learning approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011; Qi et al., 2012; Dai et al., 2015]. The results validate the superiority of the proposed HTDML.

2 Heterogeneous Transfer Distance Metric Learning

Problem setting: we suppose the training set with (weakly supervised) side information for the target domain is given by DLM = {x1Mi , x2Mi , yMi}NM i=1 , where x1Mi , x2Mi ∈ RdM , and yMi = ±1 indicates x1Mi and x2Mi are similar/dissimilar to each other. In the target domain, we have only a few samples with side information, and thus DML may perform poorly. Therefore, we assume there exists a relevant source domain with the training set DL S = {x1Si , x2Si , ySi}NS i=1 , where x1Si , x2Si ∈ RdS belong to different feature space from the target domain samples. In the source domain, either the features are stronger than the target domain [Dai et al., 2015], or the samples (with side information) are abundant, i.e., NS ≫ NM. To enable knowledge transfer, we also assume there are large amounts of unlabeled data that have representations in both the source and target domains, i.e., DU = {(xUSn , xUMn )}N U n=1 , and such data are usually easy to collect in practice [Qi et al., 2012]. Our goal is to learn an appropriate distance metric AM for the target domain.

2.1 ProblemFormulation

We propose a general framework for learning distance metric AM in the target domain by making use of the information from both target and source domain, as well as the unlabeled data. The framework is motivated by the privileged information transfer strategy presented in [Vapnik and Izmailov, 2015], where the knowledge in a privileged space ˜ X is represented as a set of functions ˜κ(˜pc, ˜x), c = 1, 2, . . . , r. Here, ˜pc is called fundamental element, which is a vector from the space ˜ X, and ˜κ(˜pc, ˜x) is called fragment of knowledge with the kernel function ˜κ. If we choose the quadratic kernel function, i.e., ˜κ(˜xi, ˜xj) = 〈˜xi, ˜xj〉2 , the fundamental elements can be found exactly by solving an eigenvalue problem [Vapnik and Izmailov, 2015]. To transfer knowledge from the privileged space to the original decision space X , some functions {φc(x)}rc=1 are found in space X to approximate the knowledge fragments {˜κ(˜pc, ˜x)}rc=1 . Here, x and ˜x are the representations of a given sample in the original decision space and privileged space respectively.

In [Vapnik and Izmailov, 2015], both the finding of fundamental elements and knowledge transfer are under the theme of support vector machines (SVM), where sufficient data with class labels and corresponding privilege information are provided for training. Our setting is much more challenging in that: 1) we only have weakly supervised side information for limited data; 2) the weakly labeled data in the target domain are scarce and are usually different from the source domain. Consequently, the method presented in [Vapnik and Izmailov, 2015] is not appropriate for DML, and cannot be used in the heterogeneous transfer setting. To tackle this problem, we propose the following heterogeneous transfer distance metric learning (HTDML) framework.

The framework is based on a generalized notion of the Mahalanobis distance [Kulis, 2012]. In the literature of distance metric learning (DML), most methods focus on learn the Mahalanobis distance, which is often denoted as

Here, A is the metric, which is a positive semi-definite matrix and can be factorized as A = UU T . By applying some simple algebraic manipulations, we have dstA(x1i , x2i ) = ‖Ux1i - Ux2i ‖22 . In order to take the structure of data distribution into consideration, we propose to conduct DML in the feature space determined by a mapping ψ, i.e., dstA(x1i , x2i ) = ‖Uψ(x1i ) - Uψ(x2i )‖22 . Then the distance can be further denoted as

Here, φ(·) = Uψ(·) is an integrated mapping function, which is unspecified and can be either linear or nonlinear. Then the learning of the target metric AM is reformulated as learning the mapping φM, and the general formulation of the proposed HTDML for learning φM is given by

where E(φM) = 1 NM ∑i L(φM; x1Mi , x2Mi , yMi) is the empirical loss w.r.t. φM in the target domain. We choose L(φM; x1Mi , x2Mi , yMi) = g(yMi[1 - dstφM (x1Mi , x2Mi )]) and adopt the hinge loss for g, i.e., g(z) = max(0, b - z). Here, b is set to be zero, and the distance between any pair of samples is given by (2). The regularization term R({φMc(·)}, {fSc(·)}) is to enforce knowledge transfer from the source domains to the target domain, where φMc is the c'th coordinate of the vector-valued mapping function φM and fSc(·) is the c'th fragment of knowledge in source domain. The knowledge transfer is performed by using the mapping functions {φMc(·)} in the target domain to approximate the fragments of knowledge in the source domains {fSc(·)}. In this way, the knowledge in the source domain is incorporated to learn the mapping function φM, i.e., the distance metric in the target domain. The trade-off hyper-parameter γ ≥ 0.

The knowledge fragments in the source domain can be found in various ways. If classification labels are available, we can train SVM classifiers and use the obtained support vectors as the fundamental elements, and then construct the knowledge fragments using a pre-defined kernel. However, in DML, we are often only provided with side (weakly supervised) information, i.e., the similarity/dissimilarity between two samples xi and xj. Therefore, we first learn the metric for source domain using some existing DML algorithm. The output of a metric learning algorithm can be a distance metric AS [Davis et al., 2007] or feature mapping φS [Kedem et al., 2012]. For the distance metric, we decompose it as AS = PSP T S , and the columns {pSc}rc=1 of the matrix PS are adopted as the fundamental elements. Then the source knowledge fragment is given by fSc(·) = κS(pSc, ·), where κS is a pre-defined kernel in the source domain. For the feature mapping φS, the knowledge fragment is directly obtained as fSc(·) = φSc(·), where φSc is the c'th coordinate of φS.

Given the pre-trained source knowledge fragment fSc(xUSn ), we propose to minimize the divergence between φMc(xUMn ) and fSc(xUSn ), where xUSn , xUMn are representations in the source and target domain respectively for a given unlabeled sample. To this end, the regularization term in (3) can be defined as follows,

where r is the number of fundamental elements, and Div(·, ·) is a divergence measure, which can be the absolute difference, and least squares error.

In this paper, we adopt the absolute difference to suppress the effect of outliers. This leads to the following compact regularization term:

where

is the mapped matrix of the unlabeled data in the target domain, and FS is a knowledge fragment matrix represented by the unlabeled data in the source domain, i.e.,

with each fSc(xUSn ) = κS(pSc, xUSn ) or fSc(xUSn ) = φSc(xUSn ). Here, |A| = ∑i ∑j |Aij| is the sum of all the elements' absolute values of a matrix A. By substituting (5) into (3), we obtain the following specific optimization problem for HTDML:

In the following, we first assume φM = UM ∈ RdM×r is a linear transformation, and then extend it to the nonlinear case.

2.2 Linear Formulation and Optimization

When we choose φM = UM as a linear transformation, the problem (6) can be reformulated as

where XUM = [xUM1 , xUM2 , . . . , xUMN U ] ∈ RdM×N U is the data matrix of the unlabeled samples in the target domain. The constraint UM ⪰ 0 means that each element of UM is non-negative. This constraint not only narrows the hypothesis space for UM, but also makes the results easy to inspect and interpret.

For notation simplicity, we set δMi = x1Mi - x2Mi , so that ‖UM (x1Mi-x2Mi )‖22 = δTMiUMU TM δMi, and the optimization problem becomes

whereE(UM) = 1 NM ∑NM i=1 g(yMi[1-δTMiUMU TM δMi]) and Ω(UM) = γ|U TM XUM - FS|. We propose to solve the problem (8) efficiently by utilizing the projected gradient method (PGM) presented in [Lin, 2007]. Because the terms in both E(UM) and Ω(UM) are non-differentiable, we first smooth it according to [Nesterov, 2005]. Then the gradient of the smoothed ϵ(UM) is

where

and QM ∈ Rr×N U is a matrix with the entry qM,cn = median { uTMc xUMn-fS,cn σ ,-1, 1}. Here, uMc is the c'th column of UM and fS,cn is the (c, n)'th element of FS; σ is the smooth parameter, which is set as 0.5 in this paper. Due to limited page length, we omit the detailed derivation. Finally, based on the obtained gradient, we apply the improved PGM presented in [Lin, 2007] to minimize the smoothed primal ϵσ (UM), i.e.,

where the operator π[x] projects all the negative entries of x to zero, and µt is the step size that must satisfy the following condition:

where the parameter ρ is chosen to be 0.01 following [Lin, 2007]. The step size can be determined using the Algorithm 1 cited from [Lin, 2007] (Algorithm 4 therein), and the convergence of the algorithm is guaranteed according to [Lin, 2007]. The stopping criterion we utilized here is |ϵσ (U t+1 M ) - ϵσ (U tM )|/|ϵσ (U t+1 M ) - ϵσ (U 0M )| < ε), where the initialization U 0M is set as a randommatrix.

2.3 Nonlinear Extension

When we allow the mapping φM to be nonlinear, the problem (6) can be rewritten as

where fSn is the n'th column of the matrix FS. To find an appropriate nonlinear form for φM, we assume it is a gradient boosting function given by φM = φ0M + α ∑Tt=1 ℏMt, where φ0M is an initialization, and ℏMt is a regression tree, together with a learning rate α [Kedem et al., 2012]. The solution can be obtained by iteratively adding regression trees ℏMt to minimize the objective ϵ(φM) in a greedy way [Friedman, 2001].

In the following, we summarize the procedure of finding the (approximately) optimal tree in each iteration. For notation simplicity, we omit the subscripts S and M. In iteration t, the (approximately) optimal tree ℏ∗t is found by selecting a tree from the set of all regression trees T p to approximate the negative gradient of ϵ(φt-1) w.r.t. φt-1, which is the mapping learned at the previous iteration. Here, p is the depth of the trees. Similar to the linear formulation, we smooth the non-differentiable terms to calculate the gradients. Then the tree ℏ∗t (·) is learned by approximating it with the negative gradient negt(·) over each training sample, i.e.,

where negt(xi) = - ∂ϵ(φt-1) ∂φt-1(xi) . The tree is greedily learned by pGBRT [Tyree et al., 2011]. The problem (13) is nonconvex w.r.t. φM, so we initialize φM as φ0M = U ∗M , which is the optimal transformation learned by our linear formulation. This makes the extension to be a nonlinear refinement of the linear formulation.

The time complexity of the proposed algorithm for our linear formulation is O(T2T1rdM(NM +N U )), where T1 is the number of checks that are needed to find the step size, and T2 is the number of iterations for reaching the stop criterion. Suppose the number of trees utilized in the pGBRT algorithm is Γ, then the time complexity for our nonlinear formulation is O((T2T1r + Γlog(N B ))dM(NM + N U )), where N B ≪ (NM +N U ). The complexity is independent on the number samples NS and feature dimension dS in the source domain, and linear w.r.t. all the number r, dM, NM and N U . Thus, the proposed algorithm is quite efficient as long as N U is not very large.

3 Experiments

In this section, we evaluate the effectiveness of the proposed HTDML algorithm on both scene classification and object recognition. Prior to these evaluations, we present our experimental settings.

3.1 Experimental Setup

The comparison methods are listed as below:

• EU: directly computing the Euclidean distance between the normalized representations of different samples in the target domain.
• LMNN [Weinberger et al., 2005]: learning the distance metric for the target domain using the large margin nearest neighbor algorithm presented in [Weinberger et al., 2005]. The number of attracted target neighbors is chosen from 1 to 10.
• ITML [Davis et al., 2007]: learning the distance metric for the target domain using the information-theoretic metric learning algorithm presented in [Davis et al., 2007]. The trade-off hyper-parameter is tuned over the set {10i |i = -5, -4, . . . , 3, 4}.
• MTDA [Zhang and Yeung, 2011]: a heterogeneous multi-task learning algorithm by extending linear discriminant analysis to handle multiple heterogeneous domains. The hyper-parameter of intermediate dimensionality is set as a fixed value since the model is not very sensitive to it according to [Zhang and Yeung, 2011].

• DAMA [Wang and Mahadevan, 2011]: a heterogeneous domain adaptation algorithm by aligning the manifolds of different domains using the class labels. The hyper-parameter is determined according to the strategy presented in [Wang and Mahadevan, 2011].
• DT [Qi et al., 2012]: a heterogeneous distance function transfer algorithm by leveraging large amounts of corresponding data between the source and target domain. The similarity of two target domain samples is determined according to the similarities of their corresponding source domain samples. The candidate sets for the two balancing hyper-parameters are both {10i |i = -5, -4, . . . , 4}.
• MI [Dai et al., 2015]: a recently proposed metric imitation algorithm. The knowledge transfer is performed by manifold structure approximation between the source and target domains. The hyper-parameters are determined according to [Dai et al., 2015].
• HTDML: the proposed heterogeneous transfer distance metric learning algorithm. In the linear formulation, LMNN [Weinberger et al., 2005] is adopted to find the fundamental elements in the source domain. In the nonlinear extension, we employ GB-LMNN [Kedem et al., 2012] to learn the source knowledge fragments. Because GBRT is adopted to learn the mapping in the target domain, we call the proposed nonlinear extension GBHTDML. The hyper-parameter γ is optimized over the set {10i |i = -5, -4, . . . , 3, 4}.

The single domain distance metric learning (DML) algorithms (LMNN and ITML) only utilize the limited label or side information in each domain, and do not make use of any additional information from other domains. The heterogeneous transfer learning (HTL) approaches, MTDA and DAMA, mainly utilize the label or side information in the source and target domain to build a connection between them. DAMA also leverage large amounts of unlabeled data to preserve the topology in each domain. They do not aim to learn distance metric, so we derive the metric as A = UU T after learning the transformation matrix U ∈ Rd×r for the target domain. DT and MI are also HTL methods, but they focus on metric learning and perform knowledge transfer by utilizing the unlabeled correspondence information between the source and target domain. The chosen of an optimal dimensionality r of the mapped subspace is still an open problem, and we do not study it in this paper. To this end, for MTDA, DAMA, and the proposed HTDML, we perform comparisons on a set of varied r.

In all the following experiments, each feature space is regarded as a domain. The task in the target domain is to perform multi-class classification [Liu and Tao, 2016], where the k-nearest neighbor classifier is adopted. Parameter determination is still an open issue in heterogenous transfer learning due to the limited labeled samples in the target domain. Consequently, if unspecified, the hyper-parameters are tuned in the range mentioned above and the best results of different compared methods are reported. Both the classification accuracy and macroF1 [Sokolova and Lapalme, 2009] score are utilized as evaluation criteria. The side information in terms of pairwise similarity constraints are obtained according to whether two labeled training samples belong to the same class or not. The remained training data that have representations in both domains are used as unlabeled data. Ten random choices of the labeled instances or sample pairs are used, and the mean values with standard deviations are reported.

3.2 Scene Categorization

The dataset used in scene categorization is the Scene-15 [Lazebnik et al., 2006], which contains 4585 images belonging to 15 natural scene categories. We randomly split the image set into a training and test set of equal size. We choose the "expensive" CNN feature [Chatfield et al., 2014] as the source domain, and the "cheap" GIST feature [Oliva and Torralba, 2001] as the target domain. The used features are provided by [Dai et al., 2015], where the feature dimensions of CNN and GIST are 4096 and 20 respectively. We select 10 labeled instances for each category in both the source and target domain to see how much the "expensive" feature can help the metric learning of "cheap" feature [Dai et al., 2015]. In the following, we first select 2000 unlabeled cross-domain correspondences, and then investigate the performance of varying number of correspondences.

For all the compared methods except the proposed GBHTDML, we preprocess the features by kernel PCA (KPCA) to take the nonlinear structure of the data distribution into consideration. In the proposed linear HTDML with the KPCA preprocess, we adopt the linear kernel (for the preprocessed data) in the source domain. The result dimensions are 2000 and 20 for CNN and GIST respectively. We also compared the different methods without the KPCA preprocess, and found that the performance of all methods are worse than that of using the preprocess. This indicates that the distribution structures of the utilized visual features are indeed nonlinear, and KPCA is able to exploit such nonlinearity to some extent. We do not show the results without preprocess here due to the limited page length.

The classification results of using the preprocess are shown in Fig. 1. We can see from the results that: 1) the HTL approach DAMA is slightly better than the single domain DML algorithms. This is because KPCA helps to build the domain connection by exploiting the nonlinearity, and some source information is transferred to help learn the transformation in the target domain; 2) DT and MI, as well as MTDA

are only comparable to LMNN and ITML. The performance of the proposed HTDML with the KPCA preprocess is only a bit higher than LMNN. This indicates that such a simple preprocess can only bring limited benefits to the transfer approaches, and is not always helpful; 3) the proposed GBHTDML outperforms all other approaches significantly. This demonstrates that the nonlinearity in the data is successfully captured by the developed nonlinear algorithm. In particular, we obtain significant 11.8% and 12.3% relative improvements over the competitive DAMA in terms of accuracy and macroF1 respectively.

All DT, MI and the proposed HTDML make use of the unlabeled corresponding data between the source and target domain. In this set of experiments, we investigate how the number of correspondences affect their performance. We vary the number from 500 to 2000, and the results are shown in Fig. 2. It can be seen from the results that: 1) for DT and MI, there are only small improvements when the number of correspondences increases. Performance of DT and MI reach their peaks around 1500 and 1000 respectively. Whereas for the proposed GB-HTDML, the performance improves significantly with an increasing number of correspondences. This demonstrates that the KPCA preprocess cannot effectively capture nonlinearity of the data distribution, which is properly discovered by our GB-HTDML; 2) the improvements of GB-HTDML decrease when the amounts of corresponding data are more than 1500. This is because there is redundancy in the set of knowledge fragments, and the amount of new knowledge brought by including more correspondences becomes small when the size of the set is large enough.

3.3 Object Recognition

We further verify the proposed method in object recognition on a natural image dataset NUS-WIDE (NUS) [Chua et al., 2009]. The dataset contains 269, 648 images, and we conduct experiments on a subset that consists of 16, 519 images belonging to 12 animal concepts. Half of the images are used for training and the rest for test. In this dataset, we choose the 1000-D tag feature as source domain, and the 500-D bag of SIFT [Lowe, 2004] visual words (BOVW) as the target domain. The number of labeled instances for each concept is 6 in both domains to see how much the easily interpretable text feature can guide the metric learning of visual feature, which is often harder to interpret [Qi et al., 2012]. The number of unlabeled correspondences is 5000. Original features are used in the proposed GB-HTDML. For other methods, the dimensions of the tag and BOVW representations after the KPCA preprocess are both 300.

This set of experiments is more challenging than the scene categorization since there is semantic gap between the text and visual features [Qi et al., 2012]. From the results shown in Fig. 3, we can see that: 1) the improvements of the single domain DML algorithms and DT over the EU baseline are not that large as in scene categorization. This indicates that the effectiveness of the KPCA preprocess drops in this application; 2) MI is superior to them and this may benefit from the manifold structure exploited in the source domain; 3) DAMA fail on this dataset because of the semantic gap. MTDA outperforms DAMA since the former learns an additional hidden layer. The transfer is conducted between higher level patterns and thus the semantic gap is reduced; 4) the proposed GB-HTDML outperforms all other approaches significantly when the dimensionality of the mapped subspace is more than 10. This further verifies the superiority of the proposed method.

4 Conclusion

In this paper, we present a general heterogeneous transfer distance metric learning framework. The framework extracts a set of knowledge fragments from the source domain to help the metric learning in the target domain. Any existing distance metric learning (DML) algorithms can be adopted to learn the source knowledge fragments in an offline manner, and either linear or nonlinear metric can be learned for the target domain. Hence the proposed framework is general, flexible, and easy-to-use.

From the experimental evaluation on two popular applications, we mainly conclude that: 1) the performance of most of the current heterogeneous transfer learning (HTL) or metric transfer (imitation) approaches are unsatisfactory in the applications where data lie in a highly nonlinear feature space, or there is a semantic gap between the source and target domain. The KPCA preprocess can sometimes be helpful, but not always take effect; 2) by appropriately exploring the nonlinearity in both the source and target domains, we can obtain significant improvements over the KPCA counterpart.

Acknowledgments

This work is supported by Singapore MOE Tier 2 (ARC42/13), IMDA Grant GDCR01, NRF via GBIC, administered by BCA, and Australian Research Council Projects FT130101457, DP-140102164, LP-150100671.