Online Heterogeneous Transfer Metric Learning

1 Introduction

Distance metric learning (DML) aims to learn a proper distance function to reveal the underlying data relationship [Xing et al., 2002]. It has been demonstrated to be successful in diverse applications, such as nearest-neighbor classification [Weinberger et al., 2005], clustering [Xing et al., 2002], content based image retrieval [Jain et al., 2008] and face verification [Chopra et al., 2005].

To learn an appropriate distance metric, we often need large amount of label information, such as class labels or pair (similar/dissimilar) or triplet (relative comparison) constraints. However, in real-world applications, the provided information is usually scarce due to the high labeling cost and DML is likely to fail in this scenario. Transfer metric learning (TML) [Zha et al., 2009] is able to alleviate this issue by transferring information or knowledge from other related source domains [Shao et al., 2016; Liu et al., 2017; Wang et al., 2017], where the distance metric is better. Directly applying the source metric to the target domain is infeasible when samples in the source and target domain lie in different feature spaces or have semantic gap. Such challenging heterogeneous TML (HTML) setting is popular in realworld applications. For example, we can use a large corpus of labeled English documents to help classify Spanish documents. The dimensions of the English and Spanish document representations are different due to the utilized different vocabularies. It is advantageous to use some existing expensive (high-performing but computational intensive) features (such as deep CNN [Chatfield et al., 2014]) to help learn a better metric for cheap features (such as LBP [Ojala et al., 2002]). We may also use the semantic tags to guide the metric learning of visual features.

Heterogeneous transfer learning (HTL) [Luo et al., 2017a; 2017b; Li et al., 2017] is able to handle the heterogeneous features [Xie et al., 2016; 2017], and some HTL approaches learn feature transformations to map the source and target samples into a common subspace [Wang and Mahadevan, 2011]. The learned transformation in the target domain can be used to derive an improved target distance metric. However, most of these approaches conduct the learning process on the entire training set. Hence, they are not applicable in the online setting, where training samples are provided sequentially (one by one). In addition, it is exhausted to retrain the model when new (labeled) training samples are available.

To tackle this issue, we develop a novel online HTML (OHTML) method, which updates the target metric using the source knowledge and only one labeled target sample at each step. In particular, we first learn the distance metric in the source domain using some existing DML algorithms. The source metric learning can be performed offline, and only the obtained metric is needed in the target metric learning. Alternatively, if the source feature (such as deep CNN) is much more expressive than target feature, we can directly employ the simple Euclidean metric (or some other pre-defined metrics) in the source domain. To build a connection between the source and target domains, we assume there are abundant unlabeled training samples that have representations in both the source and target domains. For each pair of such unlabeled samples, if they are close to each other in the source domain, their distances in the target domain should also be small. By formulating this as a manifold regularization term [Belkin et al., 2006], and simultaneously minimizing the empirical loss w.r.t. the current labeled training sample, we learn an improved distance metric for the target domain. Besides, LogDet divergence [Davis et al., 2007; Jain et al., 2008] is enforced to minimize the differences between the new obtained target metric and the previous one. This ensures that the updated metric parameter automatically satisfy the positive semi-definite (PSD) constraint. We do not require the costly PSD projection, and thus the updating algorithm is quite efficient.

There is a recent work of metric imitation (MI) [Dai et al., 2015] that aims to utilize the expensive source feature to learn an improved metric for the cheap target feature. Their formulation is also based on manifold learning, but it discards the valuable label information, and the target metric (parameterized by a linear transformation) is learned in a batch manner. Eigenvalue decomposition is involved in the optimization and thus their training complexity is high. The proposed OHTML is more advantageous than MI in that: 1) the target metric can be updated dynamically and adapt to patterns in the new coming data; 2) the optimization is much more efficient. We compare the proposed method with representative online DML algorithms [Jain et al., 2008; Jin et al., 2009] and competitive HTML approaches [Wang and Mahadevan, 2011; Dai et al., 2015] in various applications including object categorization, scene clustering, face verification, as well as image retrieval. The results demonstrate both effectiveness and efficiency of our method.

2 Online Heterogeneous Transfer Metric Learning

Problem setting: given a source and target domains with heterogeneous feature representations. The training set with side information for the target domain is given by DLM = {x1Mk , x2Mk , yMk}NM k=1 , where x1Mk , x2Mk ∈ RdM , and yMk = ±1 indicates x1Mk and x2Mk are similar/dissimilar to each other. In the target domain, the number of sample pairs NM is small and the utilized feature is cheap. Hence the resulting distance metric obtained by applying existing DML algorithms may perform poorly. To improve the target metric, we assume there is a relevant source domain with training set DL S = {x1Sk , x2Sk , yMk}NS k=1 . In the source domain, either the samples with side information are abundant (i.e., NS is large), or the feature is more expressive or interpretable than that in the target domain. Therefore, a better distance metric can be obtained. To help the target metric learning use the source domain knowledge, we 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 . Such data are usually easy to collect in practice.

2.1 ProblemFormulation

Our ultimate goal is to learn an appropriate Mahalanobis distance metric for the target domain by transferring knowledge from the source domain. The Mahalanobis distance is often defined as

where A is the metric (parameter of the distance function), which is an positive semi-definite (PSD) matrix. To facilitate knowledge transfer [Du et al., 2013; Shao et al., 2014], we learn distance metric in the source domain beforehand using some existing DML algorithms, such as LMNN [Weinberger et al., 2005] and ITML [Davis et al., 2007]. This can be conducted offline and does not have impact on the computational complexity of target metric learning. In the target domain, the labeled training pairs are provided sequentially, i.e., only one labeled pair is available at each step. Suppose the pre-trained source metric is AS, then we have the following general formulation for updating the target metric AM:

where Ψ(AM) = V (AM; x1Mk , x2Mk , yMk) is the empirical loss w.r.t. AM on the current training pair. We choose V (AM; x1Mk , x2Mk , yMk) = g(yMk[1 - dAM (x1Mk , x2Mk )]), where g(z) = max{0, b - z} is the hinge loss, and we set b = 0 in this paper. For notational simplicity, we set δk = x1k - x2k so that dA(x1k , x2k ) = δT k Aδk. The regularization term Div(AM,AkM ) measures the difference between the new and previously obtained metric parameters. In this paper, we choose Div(·, ·) to be the LogDet divergence [Davis et al., 2007], which is desirable in DML since it is scale-invariant and can make AM automatically satisfy the PSD constraint AM ⪰ 0.

For any two unlabeled samples (xUi , xUj ) in DU , we calculate their distances dAM (xUMi , xUMj ) and dAS (xUSi , xUSj ) in the target and source domain respectively. Since the two distances correspond to the same unlabeled sample pair, they should agree with each other (dAM should be small if dAS is small). This intuition is formulated in the regularization term RI , which enables the source metric to guide the metric learning in the target domain. Different types of regularization can be employed for RI , such as the absolute difference between the distances if the source and target features have been properly normalized. In this paper, we design a manifold based regularizer since it can take the geometry of the data distribution into consideration. Because the matrix AM is positive semi-definite, we decompose it as AM = UMU TM . Hence the distance dAM (xMi, xMj) = (xMi - xMj)T UMU TM (xMi - xMj) = ‖U TM xMi - U TM xMj‖22 . Then we define a regularizer so that the transformation UM is smooth over the source manifold, i.e.,

where the source manifold is approximated by the data adjacency graph WS calculated based on the distances dAS

in the source domain, LS is the graph Laplacian given by LS = DS -WS, WS is constructed using k nearest-neighbor (kNN) method, and DS is a diagonal matrix with the element DSii = ∑N U j=1 WSij. In this paper, we choose WSij to be a binary weight, i.e., WSij = 1 if the j-th unlabeled sample is the neighbor of the i-th sample, and 0 otherwise. By substituting (3) into (2), we obtain the following specific optimization problem:

where we initialize A0M as an identity matrix.

2.2 Solution

The solution of the optimization problem (4) is given as in the following theorem.

Theorem 1. The optimal solution of problem (4) is given by:

Proof. For notational simplicity, we omit the subscript M in the following derivation. By introducing the Lagrangian multipliers τ ≥ 0, and λ ≥ 0, we obtain the following Lagrangian of (4):

where HS = XU LS(XU )T . By taking the derivative of L with respect to A, and setting it to be zero, we have

Here Bk = ((Ak )-1 + γI γA HS)-1 and Zk = ykδkδT k . By using the Sherman-Morrison inverse formula, i.e., (B + uvT )-1 = B-1 - (B-1 uvT B-1 ) 1+vT B-1 u , we obtain:

where sk = δT k Bkδk, and γA + τyksk ̸= 0. By setting ∂L(A,ξk ,λ,τ ) ∂ξk = 0, we have

Algorithm 1 The proposed online heterogeneous transfer metric learning (OHTML) algorithm.

Input: Labeled training pairs in the source and target domains, i.e., {x1Sk , x2Sk , ySk} and {x1Mk , x2Mk , yMk}; unlabeled corresponding data in both domains, i.e., {(xUSn , xUMn )}.

Pre-calculation: Learn AS in using the labeled data in the source domain, and calculate HS using the unlabeled corresponding data based on the learned AS.

Hyper-parameters: γA and γI.

Output: Ak+1

• 1: Initialize A0M = I.

M .

• 2: for k = 0, 1, 2, · · · do
• 3: Receive a labeled training pair: (x1Mk , x2Mk , yMk).
• 4: Calculate the empirical loss Ψ(AM) based on AkM .
• 5: If the loss is greater than zero:
• 6: Pre-compute BMk and sMk;
• 7: Update Ak+1 M using (5).
• 8: Else Ak+1 M ←AkM .

• 9: end for

Since λ ≥ 0, we have τ ≤ 1. By substituting (8) and (9) into (6), we obtain a sub-problem L(τ) w.r.t. τ. By setting ∂L(τ ) ∂τ = 0 and considering Bk = ((Ak )-1 + γI γA HS)-1 , we have

Considering that 0 ≤ τ ≤ 1, we obtain

By substituting (11) into (8), we have

This completes the proof.

In practice, we can calculate BMk using the ShermanMorrison inverse formula, i.e., (A + UV )-1 = A-1 - A-1U(I + V A-1U)-1V A-1 , and obtain

We summarize the main procedure of the proposed OHTML algorithm in Algorithm 1. The following theorem guarantees that the obtained resulting matrix Ak+1 M calculated using Algorithm 1 is positive definite.

Theorem 2. The resulting matrix Ak+1 M in (5) is positive definite.

Proof. For notational simplicity, we omit the subscript M in the following derivation. We use S d+ and S d++ to denote the sets of positive semi-definite and positive definite matrices respectively. We have that the matrix HS ∈ S d+, since the integrated Laplacian matrix LS ∈ S d+. Because the inverse of a positive definite matrix is also positive definite, we conclude that Bk ∈ S d++ and sk = δT k Bkδk > 0 for any non-zero vector δk.

If γA(1- 1 sk ) ≤ 0, it is obvious that xT Ak+1x = xT Bkx > 0. This indicates that Ak+1 ∈ S d++.

If 0 < γA(1- 1

sk ) < 1,

It is easy to verify that (xT Bkx)(δT k Bkδk) - (xT Bkδk)2 ≥ 0 according to the Cauchy-Schwarz inequalities. Therefore, xT Ak+1x > 0 for any non-zero vector x, and Ak+1 ∈ S d++. If γA(1 - 1 sk ) ≥ 1, when yk = 1, for any vector x ∈ Rd , we have

Hence Ak+1 ∈ S d++. When yk = -1, we have γA > sk since γA( 1 sk - 1) ≥ 1. Therefore, for any vector x ∈ Rd , we also have

This completes the proof.

The complexity of the proposed algorithm mainly depends on calculation of the matrix BMk, which involves multiplication and inversion of dM ×dM matrices. Therefore, the complexity of the proposed algorithm is O(NMdcM ), where NM and dM are the number of labeled training pairs and feature dimension in the target domain respectively. The constant c ≤ 3 is determined by the utilized multiplication and inversion algorithms. It should be noted that the matrix HS can be pre-computed and hence the complexity is independent on the source domain, as well as the number of unlabeled correspondences. Therefore, the proposed method is quite efficient as long as dM is not very large.

3 Experiments

In this section, we evaluate the proposed OHTML algorithm in four different applications: object categorization, scene clustering, face verification and image retrieval. In the first three applications, we investigate how much the source domain with powerful but computationally expensive feature could help DML in the target domain with cheap feature. In the last application, we utilize the interpretable text feature to help DML with visual feature, which is often hard to be interpreted.

3.1 Experimental Setup

Specifically, we compare with the following methods:

• EU: calculating the distance between samples in the target domain by applying the simple Euclidean metric, which is served as the baseline.
• LEGO [Jain et al., 2008]: a competitive online DML algorithm based on LogDet regularization.
• RDML [Jin et al., 2009]: an efficient online DML algorithm that is robust for high dimensional data.
• DAMA [Wang and Mahadevan, 2011]: a competitive heterogeneous transfer learning (HTL) approach based on manifold alignment. It utilizes class labels to align the heterogeneous domains.
• MI [Dai et al., 2015]: a recently proposed metric imitation approach that utilizes the expensive feature to help learn a good metric for cheap feature. Large amounts of unlabeled correspondences are used for knowledge transfer via manifold approximation.
• OHTML: the proposed online HTML method. OHTML(EU) means that we set AS as an identity matrix in term (3), i.e., do not learn the source metric and directly employ Euclidean metric in the source domain.

For the single DML algorithms (LEGO and RDML), only the limited labeled training pairs in the target domain are utilized, and no additional information from the source domain is leveraged. For DAMA and MI, a linear transformation UM is learned for the target domain and we derive the metric parameter as AM = UMU TM . The candidate set for choosing the trade-off hyper-parameters is {10i |i = -5, · · · , 4} if unspecified in the original papers. The hyper-parameters γA and γI are tuned on the set {10i |i = -5, · · · , 4} and {10i |i = -2, · · · , 7} respectively. Hyper-parameter determination is still an open issue in HTL due to the limited labeled data. To this end, best performance over the candidate sets are reported for all compared methods.

For all the different methods, kernel principal component analysis (KPCA) is adopted to explore some nonlinearity in the data, and also reduce the dimensionality. We run the experiments ten times by randomly choosing the labeled set. The algorithms are implemented using Matlab and the experiments are conducted on a 3.4 GHz Intel Xeon E5-2687W (8 cores) computer.

3.2 Object Categorization

This set of experiments is conducted on the popular Caltech101 [Fei-Fei et al., 2004] dataset, which contains 8, 677 images that belong to 101 object categories. The expensive deep CNN [Chatfield et al., 2014] and cheap PHOG [Bosch et al., 2007] are adopted as the feature representations in the source and target domains respectively. The features are provided by [Dai et al., 2015], where the original feature dimensions

30

30

Figure 1: Classification accuracy and training cost w.r.t. the number of labeled training samples for each category on the Caltech dataset.

are 4096 and 40 respectively. The resulting dimensions after KPCA are 512 and 40. Half of the dataset is used for training and the remaining is for test. In both the source and target domains, we randomly select {10, 15, 20, 25, 30} labeled training samples for each category. The labeled training pairs are constructed according to the strategy in [Weinberger et al., 2005], and kNN is adopted as the classifier.

Performance w.r.t. Different Number of Labeled Samples

The classification accuracies and training costs w.r.t. a varied number of labeled training samples are shown in Fig. 1. We do not show the curve of OHTML(EU) in the time cost figure since the source metric AS is pre-calculated and the training costs of OHTML and OHTML(EU) are the same. From the results, we observe that: 1) the accuracies of all different methods improve with an increasing number of labeled samples. The single domain DML algorithms (LEGO and RDML) are only slightly better than the EU baseline, while the HTL approaches (DAMA, MI and OHTML) outperform them significantly. This demonstrates that knowledge of the source domain can help the target metric learning and be successfully transferred to the target domain by the different HTL approaches; 2) MI is better than DAMA when the number of labeled data is small (such as 10), but DAMA is better when more labeled data are provided. This is because MI only utilizes the unlabeled corresponding data to facilitate knowledge transfer, while DAMA relies on labeled data; 3) the proposed OHTML outperforms MI consistently since we can leverage the label information in the target domain. OHTML(EU) is a bit worse than OHTML since we do not learn the source metric in OHTML(EU). The accuracy decrease is not significant since the utilized source feature is much more expressive than the target feature and the estimated data ad- Accuracy

0.2

0.4

1.0

Unlabeled correspondences (%{training data})

jacency graph WS in the source domain can be used to guide the target metric learning even without learning the source metric; 4) OHTML is also superior to DAMA given limited labeled data since we use the unlabeled correspondences to build domain connection; 5) the training time of DAMA increases sharply when more labeled instances are given, while the proposed OHTML is much steady and the costs are only slightly higher than the single domain DML algorithms, and much lower than MI and DAMA. This demonstrate efficiency of our method.

Performance w.r.t. Different Number of Unlabeled Correspondences

A certain percentage of training data is used as the unlabeled corresponding data. The classification accuracies and training costs w.r.t. a varied percentage are shown in Fig. 2. We only report the performance of MI and OHTML since other approaches do not use such data. It can be seen from the results that: 1) accuracies of both MI and OHTML increase when more unlabeled correspondences are provided, and the proposed method outperforms MI consistently; 2) the training cost of MI increases dramatically while OHTML is much steady.

0.280

0.270

0.260

0.250

0.240

3.3 Scene Clustering

We conduct scene clustering on the Scene-15 [Lazebnik et al., 2006] dataset. It consists of 4, 585 images from 15 natural scene categories. CNN [Chatfield et al., 2014] and LBP [Ojala et al., 2002] are used as the feature representations of the source and target domains respectively. The resulting dimensions after KPCA are 512 and 50 respectively. We randomly split the dataset into equal size for training and test. The number of labeled samples is 10 for each category. Following [Dai et al., 2015], spectral clustering is applied to group the data and the evaluation criterion is the purity of clustering. we report the performance in Table 1.

We can see from the results that the HTL approaches are much better than the single domain DML algorithms, which are only comparable to the EU baseline. MI and OHTML outperforms DAMA significantly and the computational cost of DAMA is low. This is because the total number of labeled samples (15×10) is quite small in this set of experiments. The standard deviation of MI is zero since: 1) it is an unlabeled approach and the learned target metric does not dependent on the varied labeled sets; 2) the labeled set is not utilized for test in clustering.

3.4 Face Verification

In this subsection, we employ the well-known labeled face in the wild (LFW) [Huang et al., 2007] dataset, where there are 13, 233 face images of 5, 749 individuals. The source and target features are CNN and LBP [Chen et al., 2013] respectively. The dimension of LBP is reduced to 400 suggested by [Chen et al., 2013]. We conduct experiments under the unrestricted protocol since DAMA needs the class label information, and no outside data are utilized. We adopt the standard 10-folds split of the dataset [Huang et al., 2007], and each fold is used for test in turn. The performance is reported in Table 2.

From the results we can see that: 1) although the single domain DML algorithms are very efficient, the improvements on accuracy are quite limited compared with the EU baseline; 2) DAMA is superior to MI since the provided label information in both domains is enough for it to achieve satisfactory performance. By making use of both the unlabeled corresponding data and label information in the target domain, we obtain the best accuracy, and is more efficient than MI and DAMA.

3.5 Image Retrieval

We further apply the different methods to image retrieval and the Corel5K [Duygulu et al., 2002] dataset is used for evaluation. The dataset contains 5, 000 images belonging to 50 concepts (100 images for each concept). The semantic tag is used as the source feature and the bag-of-visual word (BoVW) based on the local SIFT [Lowe, 2004] is adopted as the target feature. Dimensions of both the tag and BoVW features are reduced to 100, and half of the data are used for training. Following [Dai et al., 2015], mean average precision (MAP) is adopted as the evaluation criterion, and the results are shown in Table 3.

In this application, DAMA is only comparable to the EU baseline and single domain DML algorithms. This may be because there is semantic gap between the textual and visual features. Thus it is harder to build connections between the source and target domains using the limited label information. MI and the proposed OHTML are much better and our method outperforms MI in terms of both MAP score and training cost.

4 Conclusion

This paper presents a general online model for heterogeneous transfer metric learning (HTML). The model is based on the direct pairwise distance minimization between the source and target domain. By formulating it under the manifold regularization theme, we obtain an efficient online HTML (OHTML) algorithm. Both effectiveness and efficiency of the proposed method are verified in diverse applications. We mainly conclude from the results that: 1) it is advantageous to utilize the expensive or interpretable feature to help learning a relatively good metric for the cheap feature or the feature that is hard to interpret; 2) the developed online model can significantly accelerate HTML with little accuracy sacrifice in most cases, especially when the labeled data are limited in the target domain.

Acknowledgments

This work is supported by Singapore NRF2015ENCGDCR01001-003, administrated via IMDA, NRF2015ENCGBICRD001-012, administrated via BCA, and Australian Research Council Projects FL-170100117, DP-140102164, and LP-150100671.