On Combining Side Information and Unlabeled Data for Heterogeneous Multi-Task Metric Learning

1 Introduction

Distance metric learning (DML) aims to find an appropriate distance or similarity measure between data. It plays a crucial role in diverse research areas, ranging from the simple k-nearest neighbor (kNN) classification, k-means clustering, to the sophisticated kernel machines (such as support vector machine, or SVM for brief) [Xu et al., 2013] and learning to rank [McFee and Lanckriet, 2010]. It is therefore essential to learn a robust distance metric to reveal the data relationships. To achieve this goal, we need a large amount of side information [Xing et al., 2002] such as the constraints that indicate whether a pair of samples is similar or not.

Recently, some transfer metric learning (TML) [Zha et al., 2009; Zhang and Yeung, 2012] methods were proposed for DML when the side information is scarce in the domain of interest (target domain), while we have abundant side information in certain related, but different source domains [Ammar et al., 2015; Luo et al., 2014]. Traditional DML algorithms usually fail in this scenario because the data distributions between the source and target domain may be quite different, and TML [Zha et al., 2009; Zhang and Yeung, 2012] tries to reduce the impact of such difference and utilize the labeled information from the source domains to help the target metric learning. Specifically, multi-task metric learning (MTML) [Zhang and Yeung, 2012] assume the side information for each of the source and target domains is limited [Goetschalckx et al., 2015; Luo et al., 2013; 2016], and the objective is to improve the metric learning of all domains simultaneously.

One major limitation of most existing TML algorithms is that they assume samples of the related domains are of the same feature dimensionality or lie in the same feature space. This assumption may be not valid for many applications. A typical example is the cross-lingual document classification, where the feature representations of the documents written in different languages vary since the utilized vocabularies are different. Moreover, in multi-view natural image classification and multimedia retrieval, the instances in different domains are often represented in different types of features (such as local SIFT [Lowe, 2004] and global wavelet texture) or have different modalities (such as image, audio and text).

To manage heterogeneous representations, many heterogeneous transfer learning [Shi et al., 2010; Wang and Mahadevan, 2011; Zhou et al., 2014] approaches have been proposed in the literature. A frequently utilized strategy in these methods is to transform the heterogeneous features into a common subspace, where the difference between heterogeneous domains is reduced [Zhou et al., 2014]. The learned transformation for each domain can be used to derive a metric. Although effective in some cases, most of them are limited for only two domains (one source domain and one target domain). However, we usually have more than two domains in many real-world applications. For example, five languages are used in the news articles of the Reuters multilingual collection, and different kinds of local, global, as well as biologically inspired features are popular utilized in visual analysisbased tasks such as image annotation.

To this end, we develop a novel heterogeneous multi-task metric learning (HMTML) framework that handles an arbitrary number of domains by combining side information and unlabeled data. In this paper, we assume there are abundant unlabeled samples that have feature representations in all domains. In particular, HMTML learns the metrics for all different domains in a single optimization problem by minimizing empirical losses w.r.t. the metric for each domain. At the same time, we transform different representations of the given unlabeled samples into a common subspace using the feature transformations derived from the metrics. Because the different representations are modelling the same instance, they should be close to each other in the subspace. By maximizing the high-order covariance between the transformed data representations, we find a shared subspace for all domains and thus all of their side information can be further incorporated to learn this shared subspace of maximum reliability. Hence a more reliable metric is obtained for each domain since the (Mahanobias) metric learning is equivalent to learn a subspace under certain optimization criterion [Kulis, 2012]. Intuitively, the common subspace provides a bridge for side information transfer. In this way, different domains help each other in metric learning, so the learned metrics are more reliable than the results of learning them separately, especially for those domains that have limited side information.

There exist a few approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011] that could learn transformations and derive metrics for more than two domains. However, in these approaches, only the statistics (correlation information) between each representation and the shared representation [Zhang and Yeung, 2011], or pairs of representations [Wang and Mahadevan, 2011] is explored, while high-order statistics that can only be obtained by simultaneously examining all domains is ignored. Besides, these approaches mainly focus on utilizing the side information and thus may fail given insufficient side information. Our method is superior to these methods in that we aim to directly maximize the correlation between all domains by analyzing their high-order feature covariance tensor, which is calculated using large amounts of unlabeled data. Much more correlation information can thus be encoded in the learned transformations and also metrics, and hopefully better performance can be achieved. We perform experiments on two popular applications: multilanguage text categorization and multi-view social image annotation. In addition to the Euclidean (EU) and single domain regularized DML (RDML) baselines, we further compare the proposed method with two representative heterogeneous transfer learning approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011] for multiple domains. The results validate the effectiveness of the proposed HMTML.

2 Heterogeneous Multi-taskMetric Learning

In contrast to DAMA [Wang and Mahadevan, 2011] and MTDA [Zhang and Yeung, 2011], which learn linear transformation for each domain by only considering the pairwise domain correlations, we propose tensor based heterogeneous MTML (HMTML) to learn transformations for metric learning by exploiting the high order tensor correlation between all domains. The diagram of the proposed HMTML is shown in Figure 1. Taking the multilingual text classification as an example, we assume that limited side information (in the form of paired sample similarity) is provided for each of the M heterogeneous domains, such as "English", "Italian", and "Germany". For the m'th domain, we minimize the empirical losses w.r.t. the metric Am on the labeled data DLm. Since the side information is scarce for each domain, learning the different metrics independently may be unreliable. To enable information being shared across all domains so that they can help each other in metric learning, we assume that we are also given abundant unlabeled samples that are represented in all M domains, i.e., ¶xUmn ♦N U n=1 ↪m = 1↪ 2↪ ▷ ▷ ▷ ↪M. Then we decompose the metric Am as Am = UmU Tm, and using Um to transform the original heterogeneous representations into a common space as ¶zUmn ♦N U n=1 ↪m = 1↪ 2↪ ▷ ▷ ▷ ↪M. Finally, by maximizing tensor based high-order covariance between all transformed representations, we learn improved U ⇤m by utilizing additional information from other domains, and so more reliable metric A⇤m = U ⇤m(U ⇤m)T is obtained. The technical details are given below, and we start by briefing the used notations and concepts of multilinear algebra in this paper.

2.1 Notations

Let A be an M-order tensor of size I1 ⇥ I2 ⇥ ▷ ▷ ▷ ⇥ IM, and U be a Jm ⇥ Im matrix. The m-mode product of A and U is then denoted as B = A⇥m U , which is an I1 ⇥ ▷ ▷ ▷ ⇥ Im-1 ⇥ Jm ⇥ Im+1 ▷ ▷ ▷ ⇥ IM tensor with the element

The product of A and a sequence of matrices ¶Um 2 RJm⇥Im ♦Mm=1 is a J1 ⇥ J2 ⇥ ▷ ▷ ▷ ⇥ JM tensor denoted by

The mode-m matricization of A is denoted as an Im ⇥ (I1 ▷ ▷ ▷ Im-1Im+1 ▷ ▷ ▷ IM) matrix A(m), which is obtained by mapping the fibers associated with the m'th dimension of A as the rows of A(m), and aligning the corresponding fibers of all the other dimensions as the columns. Here, the columns can be ordered in any way. The m-mode multiplication B = A ⇥m U can be manipulated as matrix multiplication by storing the tensors in metricized form, i.e., B(p) = UA(p). Let u be an Im-vector, the contracted mmode product of A and u is denoted as B = A¯⇥mu, which is an I1⇥▷ ▷ ▷⇥Im-1⇥Im+1 ▷ ▷ ▷⇥IM tensor of order M-1, and the entries are calculated by:

Finally, the Frobenius norm of the tensor A is given by

2.2 ProblemFormulation

Given M heterogeneous domains, we suppose the training set with side information for the m'th domain is given by DLm = ¶(xmi↪ xmj↪ ymij)♦Nm i↪j=1 , where xmi↪ xmj 2 Rdm and ymij = ◦1 indicates xmi and xmj are similar/dissimilar to each other. The number of training samples Nm is very small for each domain, so we assume there are large amounts of unlabeled data that have representations in all domains DU = ¶(xU1n ↪ xU2n ↪ ▷ ▷ ▷ ↪ xUMn )♦N U n=1 , and these data are usually easy to collect in practice [Qi et al., 2012]. Then the general formulation of the proposed HMTML for learning the metrics ¶Am♦Mm=1 is given by

where (Am) = 2 Nm(Nm-1) Pi<j L(Am; xmi↪ xmj ↪ ymij ) is the empirical loss w.r.t. Am in the m'th domain, and R(A1↪A2↪ ▷ ▷ ▷ ↪AM) is some regularizer to enforce information transfer across different domains. Following [Jin et al., 2009], we choose L(Am; xmi↪ xmj↪ ymij) = g(ymij[1 - kxmi - xmjk2Am ]) and adopt the hinge loss for g, i.e., g(z) = max(0↪ b - z). Here, b is set to be zero, and kxmi - xmjk2Am = (xmi - xmj)T Am(xmi - xmj). For notation simplicity, we denote xmi, xmj and ymij as x1mk , x2mk and ymk respectively, where k = 1↪ 2↪ ▷ ▷ ▷ ↪N 0m = Nm(Nm-1) 2 . We also set δmk = x1mk - x2mk so that kx1mk -x2mk k2Am = δTmkAmδmk, and the loss term becomes (Am) = 1 N 0m PN 0m k=1 g (ymk(1 - δTmkAmδmk)).

To enable knowledge transfer across domains, we propose to decompose the positive semi-definite metric Am as Am =

UmU Tm, and then using the feature mapping Um 2 Rdm⇥r to project the unlabeled data points of different domains into a common subspace, where the correlation of all domains are maximized. This leads to the following optimization problem:

where corr(zU1n ↪ zU2n ↪ ▷ ▷ ▷ ↪ zUMn ) = (zU1n ⊙ zU2n ⊙ ▷ ▷ ▷ ⊙ zUMn )T e is the correlation of the projected representations ¶zUmn = U TmxUmn ♦Mm=1 among all domains for the n'th sample. Here, ⊙ is the element-wise product, and e 2 Rr is an all ones vector. This correlation is equivalent to G ¯⇥1(xU1n )T ▷ ▷ ▷ ¯⇥M(xUMn )T according to [Luo et al., 2015], where G = Prq=1 (uq1 ◦uq2 ◦▷ ▷ ▷◦uqM ) = Ir⇥1U1⇥2U2 ▷ ▷ ▷⇥M UM is the covariance tensor of the mappings. Here, ◦ is the outer product, Ir 2 Rr⇥r⇥▷▷▷⇥r is an identity tensor (the entries are 1 in the diagonal, and 0 otherwise) of size r, which is the number of common factors shared by all domains. Then the problem (6) becomes

Let C U n = xU1n ◦ xU2n ◦ ▷ ▷ ▷ ◦ xUMn be the covariance tensor of the original feature representations among all domains for the n'th sample, the above problem can be further reformulated as follows according to [De Lathauwer et al., 2000a],

By regarding the objective of (8) as the regularizer in (5), we obtain the following specific optimization problem for HMTML:

where γ and ¶γm♦ are all positive tradeoff parameters. We enforce the feature mapping to be sparse as suggested in [Zhou et al., 2014] and the non-negativity constraints are to preserve non-negative correlation between the original feature representations. Intuitively, minimization of the second term in (9) corresponds to find a latent subspace where the representations of all domains are close to each other. Knowledge is transferred in this subspace and so different domains can help each other in learning the mapping Um, or equivalently the metric Am.

2.3 Optimization Algorithm

The problem (9) can be solved by iteratively updating only one variable Um at a time and fixing all the other Um, m0 6= m. According to [De Lathauwer et al., 2000b], we have

where B = Ir⇥1U1 ▷ ▷ ▷⇥m-1Um-1⇥m+1Um+1 ▷ ▷ ▷⇥MUM. By applying the metricizing property of the tensor-matrix product, we have G(m) = UmB(m). Besides, it is easy to verify that kC U n -Gk2F = kC U n(m) -G(m)k2F . Therefore, the sub-problem of (9) w.r.t. Um becomes:

where Φ(Um) = 1 N 0m PN 0m k=1 g (ymk(1 - δTmkUmU Tmδmk)) + γmkUmk1, and ⌦(Um) = γ N U PN U n=1 kC U n(m) - UmB(m)k2F . We propose to solve the problem (10) efficiently by utilizing the projected gradient method (PGM) presented in [Lin, 2007]. However, the terms in Φ(Um) are non-differentiable, we thus first smooth it according to [Nesterov, 2005]. For notation clarity, we omit the subscript m in the following derivation. According to [Nesterov, 2005], the smoothed version of the hinge loss g(U; δk↪ yk) = max¶0↪ -yk(1 - δT k UU T δk)♦ can be given by

where Q = ¶⌫ : 0  ⌫k  1↪ ⌫ 2 RN 0 ♦ and σ is the smooth parameter, which is set as 0▷5 in this paper. By setting the gradient of the objective function in (11) to become zero and then projecting ⌫k on Q, we obtain the following solution,

By substituting the solution (12) back into (11), we have the piece-wise approximation of g, i.e.,

To utilize the PGM for optimization, we have to compute the gradient of the smoothed hinge loss to determine the descent direction. We summarize the results in the following theorem.

Theorem 1. The sum of gradient of the smoothed hinge loss gσ (U; δk↪ yk) over all samples is

Here, ⌫k is related to U.

It is easy to prove this theorem according to (12) and (13), so we do not present the proof here due to the limited space. Similarly, for the sparse term kUk1 = Pdi=1 Prj=1 l(uij), where l(uij) = ♣uij♣, we have the following piece-wise approximation of l with the smooth parameter σ:

The gradient of smoothed kUk1 is given by @(Pdi=1 Prj=1 lσ (uij))◁@U = O with each oij = median¶ uij σ ↪-1↪ 1♦. In addition, it is easy to deduce that the gradient of ⌦(U) w.r.t. U is

Therefore, the gradient of the smoothed F(Um) is

Finally, based on the obtained gradient, we apply the improved PGM presented in [Lin, 2007] to minimize the smoothed primal F σ (Um), i.e.,

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

F σ (U t+1 m )-F σ (U tm)  rF σ (U tm)T (U t+1 m -U tm)↪ (19) where the parameter  is chosen to be 0▷01 following [Lin, 2007]. The step size can be determined using the Algorithm 4 in [Lin, 2007], and the convergence of the algorithm is guaranteed according to [Lin, 2007]. The stopping criterion we utilized here is ♣F σ (U t+1 m ) - F σ (U tm)♣◁(♣F σ (U t+1 m ) - F σ (U 0m)♣ < ✏), where the initialization U 0m is the set as the results of the previous iterations in the alternating of all ¶Um♦Mm=1 .

Finally, the solutions of (9) are obtained by alternatively updating each Um until the stop criterion ♣OBJk+1 - OBJk♣◁♣OBJk♣ < ✏ is reached, where OBJk is the objective value of (9) in the k'th iteration step. Because the objective value of (10) decreases at each iteration of the alternating procedure, i.e., F(U k+1 m ↪ ¶U km0♦m0 6=m)  F(¶U km♦). This indicates that F(¶U k+1 m ♦)  F(¶U km♦). Therefore, the convergence of the proposed HMTML algorithm is guaranteed. Once the solutions ¶U ⇤m♦Mm=1 have been obtained, we can conduct subsequent learning, such as multi-class classification in each domain using the learned metric A⇤m = U ⇤mU ⇤mT .

3 Experiments

In this section, we evaluate the effectiveness of the proposed HMTML on both multi-lingual document categorization and multi-view image annotation. Prior to these evaluations, we present the experimental settings.

3.1 Datasets, Features, and Evaluation Criteria

The dataset used in document categorization is the Reuters multilingual collection (RMLC) [Amini et al., 2009], which contains news articles written in five languages, and from six populous categories. In this dataset, we choose three languages (i.e., English (EN), Italian (IT), and Spanish (SP)) and regard each of them as a domain. The provided TF-IDF features are adopted for document representation. We preprocess these representations by performing PCA to find comparable patterns for meaningful transfer and 20% energy is preserved. This results in 245, 213, and 107 features for documents of the three domains respectively. The number of samples for the three domains are 18↪ 758, 24↪ 039, and 12↪ 342 respectively. In each domain, the sample sets are randomly split into equal size to form the training and test sets, and we randomly choose ¶5↪ 10↪ 15♦ labeled samples for each category in the training set to determine the performance of the compared methods w.r.t. the number of labeled instances.

In image annotation, we employ a challenge natural image dataset NUS-WIDE (NUS) [Chua et al., 2009]. The dataset contains 269↪ 648 images, and our experiments are conducted on a subset that consists of 16↪ 519 images belonging to 12 animal concepts: bear, bird, cat, cow, dog, elk, fish, fox, horse, tiger, whale, and zebra. In this dataset, we choose three types of features, namely 500-D bag of visual words (BOVW) based on SIFT [Lowe, 2004] descriptors, 144-D color autocorrelogram (CORR), and 128-D wavelet texture (WT), to represent each image. We preprocess the different features using PCA and the result dimensions are all 100. Each image representation is regarded as a domain. In each domain, we randomly split the image set into a training set of 8↪ 263 images and a test set of 8↪ 256 images, and the number of labeled instances for each concept varies in the set ¶4↪ 6↪ 8♦.

In both datasets, the task in each domain is to perform multi-class classification, where the nearest neighbor (1NN) classifier is adopted. 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 all domains are used as unlabeled data. The parameters are determined using leave-one-out cross validation on the labeled set. The classification accuracy is utilized as evaluation criteria. The average performance of all domains is calculated for comparison. In all the following experiments, five random choices of the labeled instances are used, and the mean values are reported.

3.2 Experimental Results and Analysis

The comparison baselines are listed as below:

• ÷ EU: directly computing the Euclidean distance between samples based on their original feature representations in each domain.
• ÷ RDML [Jin et al., 2009]: learning the distance metric for each domain separately using the efficient and competitive regularized distance metric learning algorithm presented in [Jin et al., 2009]. This method only utilizes the given limited labeled samples in each domain, and does not make use of any additional information from
• other domains. The trade-off parameter is chosen from the set ¶10i ♣i = -5↪ -4↪ ▷ ▷ ▷ ↪ 4♦.
• ÷ DAMA [Wang and Mahadevan, 2011]: constructing mappings Um to link multiple heterogeneous domains using manifold alignment. The parameter is determined according to the strategy presented in [Wang and Mahadevan, 2011].
• ÷ MTDA [Zhang and Yeung, 2011]: performing supervised dimension reduction simultaneously for heterogeneous features (domains) using the multi-task extension of linear discriminative analysis. The learned transformation Um = WmP, which consists of a domain specific part Wm, and a common part P shared by all domains. The intermediate dimensionality parameter is set as 100 for both datasets since the model is not very sensitive to the parameter according to [Zhang and Yeung, 2011].
• ÷ HMTML: the proposed heterogeneous multi-task metric learning method. The parameters γm are set as the same value, and we tune both γ and γm over the set ¶10i ♣i = -5↪ -4↪ ▷ ▷ ▷ ↪ 4♦.

In DAMA and MTDA, after learning Um, we derive the metric for each domain as Am = UmU Tm. For DAMA, MTDA, and the proposed HMTML, the number r of the common factors (or dimensionality of the common subspace) used to explain the original data of all domains varies in ¶1↪ 2↪ 5↪ 8↪ 10↪ 20↪ 30↪ 50↪ 80↪ 100♦.

Multilingual Document Categorization

The classification accuracies in relation to the number r are shown in Figure 2. From these results, we observe that: 1) the performance of all the compared methods improves with an increased number of labeled instances; 2) although the labeled samples in each domain is scarce, learning the distance metric separately using RDML can still improve the performance significantly. This demonstrates the effectiveness of distance metric learning (DML) in this application; 3) all the three heterogeneous transfer learning approaches achieve much better performance than RDML. This indicates that it is useful to leverage information from other domains in DML; Besides, the optimal number r is usually less than 30. This can be interpreted as using only 30 common factors (topics) is enough to distinguish the different categories in the dataset; 4) DAMA is superior to MTDA when the number of labeled samples is small, since MTDA is a discriminative method and highly relies on the label information, while DAMA preserves topology in each domain and this is helpful given insufficient labeled instances. The proposed HMTML is superior to DAMA even limited labeled samples are provided, since we make use of large amounts of unlabeled data to connect different domains; 5) overall, the proposed HMTML outperforms both DAMA and MTDA at most numbers (of common factors). This indicates that the learned factors by our method are more expressive than the other approaches. The main reason is that our method directly examining the high-order statistics of all domains simultaneously, whereas, in DAMA only the pairwise relationships are explored, and in MTDA the different domains must communicate with each other through an intermediate structure, where some important information contained in the original features may be lost; 6) in particular, we obtain significant relative improvements of 16▷8%, 9▷4%, and 4▷2% over the competitive MTDA when the number of labeled samples are 5, 10, and 15 respectively.

Multi-view Image Annotation

We show the annotation accuracies of the compared methods in Figure 3. It can be observed from the results that: 1) the accuracy of RDML is lower than directly using the Euclidean distance (EU) when the number of labeled samples is small (e.g., 4). This may be because RDML is a linear metric learning approach, while structure of the data distribution of image features is usually nonlinear; 2) DAMA totally fails in this application, and MTDA only obtain satisfactory accuracies when enough (e.g., 8) labeled instances are provided. The main reason is that in this application, the different domains corresponding to different kinds of features. This setting is much more challenge than the multilingual document classification, where the feature types (TF-IDF) are the same and only the vocabulary varies. The statistical properties of the different kinds visual features utilized here are quite different from each other, so it is very hard to find some common expressive factors across all domains by only exploiting the pair-wise relationships between them. Nevertheless, the proposed HMTML achieves satisfactory performance by simultaneously exploring all domains.

4 Conclusion

This paper presents a method for heterogeneous metric learning. The proposed method can not only effectively make use of the limited side information in each domain, but also discover high order statistics among multiple heterogeneous domains by analyzing their feature covariance tensor calculated using large amounts of unlabeled data. The knowledge shared by the different domains is successfully transferred in a common subspace to help each of them in metric learning by maximizing their high-order covariance in the subspace. We develop an efficient algorithm for optimization with convergence guarantee, and the exploited high-order correlation information was demonstrated empirically to be superior to the pairwise correlations utilized in traditional approaches.

From the experimental validation on two popular applications we mainly conclude that: 1) learning metric for each domain separately may deteriorate the performance if given insufficient side information, and the labeled data deficiency problem can be alleviated by learning metrics for multiple heterogeneous domains simultaneously. This is consistent with the results of multi-task learning literatures; 2) the shared knowledge of different domains exploited by the transfer learning methods can benefit each domain if appropriate common factors are discovered, and the high-order statistics (correlation information) is critical in discovering such factors; In the future, we plan to extend the proposed method to learn nonlinear metrics so that it has the capability to handle complicated domains.

Acknowledgments

This work is supported by Singapore MOE Tier 2 (ARC42/13).