Exploiting High-Order Information in Heterogeneous Multi-Task Feature Learning

1 Introduction

Multi-task learning (MTL) [Caruana, 1997; Liu et al., 2017] learns multiple related tasks simultaneously. It aims to choose an appropriate hypothesis space for each learning task by utilizing the shared information across all tasks, and thus improves their generalization performance. A dozen MTL methods [Luo et al., 2013; Ammar et al., 2015; Wang et al., 2016; Luo et al., 2016; Gonc¸alves et al., 2017] have been proposed in the past decades. For example, a common representation is learned in [Caruana, 1997] for multiple similar tasks by sharing hidden units in neural networks. In [Ammar et al., 2015], some latent factors are assumed to be shared across multiple tasks in lifelong reinforcement learning. The MTL methods can be divided into several groups, and one representative group is multi-task feature learning (MTFL) [Argyriou et al., 2008], which improves the performance of each task by learning some shared features between tasks. It has been widely applied to many real-world applications, such as handwritten letter recognition [Liu et al., 2009], spoken language recognition [Gong et al., 2013], disease diagnosis [Argyriou et al., 2008], and medical state examination [Gong et al., 2013].

An implicit assumption of most existing MTFL algorithms is that the data samples of related domains have the same feature dimensionality or lie in the same feature space, and thus the same feature mapping is learned for all tasks. This assumption may be not valid for many applications. For example, in multilingual document classification, the feature representations of the documents written in different languages vary since the utilized vocabularies are different. In natural image classification and multimedia retrieval, the instances are often represented using different types of features [Xu et al., 2014; 2015] (such as local SIFT [Lowe, 2004] and global wavelet texture) or have different modalities (such as image, audio and text).

Recently, heterogeneous transfer learning (including MTL and domain adaptation) has been proposed to manage heterogeneous representations. These approaches often transform the heterogeneous features into a common subspace, so that the difference between heterogeneous domains is reduced. Although effective in some cases, most of them are limited for only two domains (one source and one target domain). Only a few approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011; Jin et al., 2015] could learn transformations for more than two domains. In these approaches, only the statistics (correlation information) between each representation and the shared representation [Zhang and Yeung, 2011; Jin et al., 2015], or pairs of representations [Wang and Mahadevan, 2011] is explored, while highorder statistics (correlation information) [Tao et al., 2007a; 2007b] that can only be obtained by simultaneously examining all domains is ignored.

To deal with an arbitrary number of domains and exploit the high-order information, we develop a tensor based heterogeneous multi-task feature learning (THMTFL) framework. In particular, THMTFL learns the feature mappings for all domains in a single optimization problem. Predictive structures of the different domains are pre-learned to enable knowledge transfer. Following the multi-task learning strategies presented in [Ando and Zhang, 2005; Quattoni et al., 2007], we project the predictive structures of different domains into a common subspace using the feature mappings. In this paper, we assume the application tasks in different domains are the same [Wang and Mahadevan, 2011], such as to classify an article into one of several predefined categories. Consequently, the predictive structures (parameterized by the weight vectors of classifiers) should be close to each other in the subspace. By minimizing the divergence between the transformed predictive structures, we build a connection between the transformations. The label information (included in the predictive structures) of all domains is transferred in the subspace to help learning the transformation (feature mapping) of each domain. Hence the learned feature mappings are more discriminative than the results of learning them separately, especially for those domains that have limited label information.

Our method is superior to existing heterogeneous transfer learning approaches in that: 1) we aim to directly explore the relationship between all domains by analyzing the high-order covariance tensor over their prediction weights. The highorder correlations can thus be encoded in the learned transformations, and hopefully better performance can be achieved; 2) the predictive structures can be learned beforehand, and thus the complexity of learning the feature mapping is reduced. The original data can be invisible in the feature learning. Hence the proposed method can be used in applications where original data are not available due to privacy or security reasons. We perform experiments on two popular applications: text categorization and social image annotation. The results validate the superiority of the proposed THMTFL.

2 Tensor Based Heterogeneous Multi-task Feature Learning

In contrast to the traditional multi-domain heterogeneous transfer learning approaches [Wang and Mahadevan, 2011; Zhang and Yeung, 2011; Jin et al., 2015], which learn linear transformation for each domain by only considering the pairwise correlations, we propose tensor based heterogeneous MTFL (THMTFL) to learn transformations by exploiting the high-order tensor correlation between all domains. Given M heterogeneous domains (such as "English", "Italian", and "German" in multilingual document classification), we assume there are limited labeled samples for each of them. For the m'th domain, we construct multiple prediction (such as binary classification) problems and use the labeled data to learn a set of prediction weight vectors {wpm}Pp=1 , where P is the number of prediction problems. Here, each wpm is learned by assuming the prediction base classifier for each domain is linear, i.e., f p (xm) = (wpm)T xm. The P prediction problems are generated using the Error Correcting Output Codes (ECOC) scheme [Dietterich and Bakiri, 1995]. Then we use the feature mapping Um to transform the weight vectors into a common subspace as {vpm = U Tmwpm}Pp=1 . Because the application tasks in all domains are the same (as mentioned in the Introduction), the transformed weight vectors of different domains {vp 1 , vp 2 , . . . , vpm} should be close to each other in the subspace. Finally, by minimizing the tensor based highorder divergence (or equivalently maximizing high-order covariance [Luo et al., 2015]) between all transformed weight vectors, we learn improved U ∗m by utilizing additional information from other domains.

It should be noted that the learned weights may be not reliable given the limited labeled samples. Fortunately, we can construct sufficient base classifiers using the ECOC scheme. Hence robust transformations can be obtained even some learned base classifiers are inaccurate or incorrect. The technical details of the proposed method are given below, and we start by briefing the frequently 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 ∈ 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(m) = UA(m). Specifically, the series of m-mode product in (2) can be expressed as a series of Kronecker products and is given by

where {c1, c2, . . . , cK} = {m + 1,m + 2, . . . ,M, 1, 2, . . . ,m - 1} is a forward cyclic ordering for the indices of the tensor dimensions that map to the column of the matrix. Let u be an Im-vector, the contracted m-mode 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 labeled training set for the m'th domain is given by Dm = {(xmn, ymn)}Nm n=1 , where xmn ∈ Rdm and its corresponding class label ymn ∈ {1, 2, . . . ,C}. Here, we assume that the different domains are about the same application, and thus share the same label set [Wang and Mahadevan, 2011; Jin et al., 2015]. To enable knowledge transfer across domains in the learning of the feature mappings {Um}, we first construct P binary classification problems and learn a set of classifiers {wpm}Pp=1 for each of the M domains using the labeled training data. This learning process can be carried out offline and thus have no impact on the computational cost of subsequent feature mapping learning. Then we propose to transform wpm using the mapping Um as vpm = U Tmwpm and minimize the divergence of the transformed weight vectors, i.e., {vp 1 , vp 2 , ..., vpM }. Here, we start from two domains, i.e., M = 2, and then generalize the model for M > 2.

When M = 2, the formulation is given by

where Um ∈ Rdm×r is the mapping for the m'th domain, and r is the number of common factors shared by different domains; {γm} are positive trade-off hyper-parameters, the l1norm‖Um‖1 = ∑di=1 ∑rj=1 |umij| is the sumof the absolute values of Um's elements, and ⪰ indicates that each element of Um is non-negative. We enforce Um to be sparse since a feature in one domain is usually represented by only a small subset of features in another domain, and the non-negativity constraints are to preserve non-negative correlation between the feature representations.

To generalize (6) for M > 2, we reformulate it as

Considering that G = U1ErU T 2 and by using the tensor notation, we have G = Er ×1 U1 ×2 U2, where Er is an identity matrix of size r. Thus, the formulation (7) for M > 2 is:

where each Um ⪰ 0 and G = Er ×1 U1 ×2 U2 . . . ×M UM is a transformation tensor, Er ∈ Rr×r×...×r is an identity tensor (the entries are 1 in the diagonal, and 0 otherwise). The problem (8) is not convenient to optimize, so we reformulate it by utilizing the following theorem.

Theorem 1 The following equality holds for ‖wpm‖22 = 1, p = 1, . . . , P;m = 1, . . . ,M:

where ◦ is the outer product.

Due to limited page length, we omit the proof. By substituting (9) into (8) and replacing G with E ×1 U1 ×2 U2 . . . ×M UM, we obtain the following reformulation of (8):

where Wp = wp 1 ◦ wp 2 . . . ◦ wpM is the prediction weights covariance tensor among all domains. Intuitively, minimization of the first term in (10) corresponds to find a subspace where the weight vectors of all domains are close to each other. Knowledge (label information) is transferred in this subspace and thus different domains can help each other in learning the mapping Um.

2.3 Optimization Algorithm

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

where B = E×1U1 . . .×m-1Um-1×m+1Um+1 . . .×M UM and by applying the metricizing property of the tensor-matrix product, we have G(m) = UmB(m). Besides, it is easy to verify that ‖Wp - G‖2F = ‖W p (m) -G(m)‖2F . Therefore, the sub-problem of (10) w.r.t. Um becomes:

where Φ(Um) = 1 2P ∑Pp=1 ‖W p (m) - UmB(m)‖2F , and Ω(Um) = γm‖Um‖1. We propose to solve the problem (11) efficiently by utilizing the projected gradient method (PGM) presented in [Lin, 2007]. However, the term in Ω(Um) is non-differentiable, we thus first smooth it according to [Nesterov, 2005]. For notational clarity, we omit the subscript m in the following derivation. According to [Nesterov, 2005], the smoothed version of the l1-norm l(uij) = |uij | can be

where Q = {Q : -1 ≤ qij ≤ 1,Q ∈ Rd×r } and σ is the smooth hyper-parameter, which is empirically set it as 0.5 in our implementation according to the comprehensive study of the smoothed l1-norm in [Zhou et al., 2010]. By setting the objective function of (12) to become zero and then projecting qij on Q, we obtain the following solution:

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

To utilize the PGM for optimization, we have to compute the gradient of the smoothed l1-norm to determine the descent direction. It is easy to derive that the gradient ∂lσ (U) ∂U = Q, where Q is the matrix defined in (12). Therefore, the gradient of the smoothed F(Um) is

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 π[x] projects all the negative entries of x to zero, and µt is the step size that must satisfy the following condition:

where the hyper-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 |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 (10) are obtained by alternatively updating each Um using Algorithm 1 until the stop criterion |OBJk+1 - OBJk|/|OBJk| < ϵ is reached, where OBJk is the objective value of (10) in the k'th iteration step. Because the objective value of (11) decreases at each iteration of the alternating procedure, i.e., F(U k+1 m , {U km′}m′ ̸=m) ≤ F({U km}). This indicates that F({U k+1 m }) ≤ F({U km}). Consequently, the convergence of the proposed THMTFL 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 transformed features X∗m = U ∗mT Xm.

In Algorithm 1, suppose the number of checks that is needed to find the step size is T1, and the number of iterations for Algorithm 1 The improved projected gradient method for solving Um.

Input: B(m) andW p (m) , p = 1, . . . , P .

Algorithm hyper-parameters: γm.

Output: Um.

• 1: Set µ0 = 1, and β = 0.1. Initialize U 0m as the results of the previous iterations in the alternating optimization of all {Um}Mm=1 .
• 2: For t = 1, 2, . . .
• 3: (a) Assign µt ← µt-1;
• 4: (b) If µt satisfies (17), repeatedly increase it by µt ← µt/β, until either µt does not satisfy (17) or Um(µt/β) = Um(µt).

Else repeatedly decrease µt ← µt ∗ β until µt satisfy (17);

• 5: (c) Update U t+1 m = π[U tm -µt∇F σ (U tm)].
• 6: Until convergence

reaching the stop criterion is T2, then the time complexity of the proposed THMTFL is (ΓM[r ∏Mm=1 dm + T2T1r2 ¯ dm]), where ¯ dm is the average feature dimension of all domains, and Γ is the number of iterations for alternately updating all {Um}Mm=1 . The complexity is linear w.r.t. M and ∏Mm=1 dm, and quadratic in the numbers r. Besides, it is common that Γ < 10, T2 < 20, and T1 < 50, so the complexity is not very high.

3 Experiments

In this section, we evaluate the effectiveness of the proposed THMTFL on both document categorization and image annotation. Prior to these evaluations, we present the used datasets, evaluation criteria, as well as our 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, Italian, and Spanish) and regard each of them as a domain. The provided TF-IDF features are adopted for document representation. We preprocess these representations by performing principal component analysis (PCA) and this results in 245, 213, and 107 features for documents of the three domains respectively. The preprocessing is mainly to: 1) find comparable and high-level patterns for transfer; 2) pervent overfitting; and 3) reduce computational demands in the experiments. 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. In the training set, we randomly select 10 labeled samples for each category.

In image annotation, we employ a challenging 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 the 500-D local bag of SIFT [Lowe, 2004], 128-D global wavelet texture, and 1000-D tag to represent each image. We preprocess the different features using kernel PCA (KPCA) 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 is 6.

In both datasets, the task in each domain is to perform multi-class classification [Liu and Tao, 2016], where the SVM classifiers are adopted. In all the following experiments, both the classification accuracy and macroF1 [Sokolova and Lapalme, 2009] score are utilized as evaluation criteria. The average performance of all domains is calculated for comparison. Ten random choices of the labeled instances are used, and the mean values with standard deviations are reported.

3.2 Experimental Results and Analysis

The compared methods are listed as below:

• Original: directly using the original normalized feature representations in each domain.
• LDA [Wang et al., 2007]: learning the feature mapping for each domain separately using the linear (Fisher) discriminant analysis algorithm [Wang et al., 2007]. The algorithm only utilizes the given limited labeled samples in each domain, and does not make use of any additional information from other domains.
• DAMA [Wang and Mahadevan, 2011]: constructing mappings {Um} to link multiple heterogeneous domains using manifold alignment. The hyper-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 discriminant analysis. The intermediate dimensionality set as 100 since the model is not very sensitive to the hyper-parameter according to [Zhang and Yeung, 2011].
• MTNMF [Jin et al., 2015]: a recently proposed heterogeneous multi-task feature learning algorithm. It learns feature transformations for multiple heterogeneous domains jointly by performing matrix factorizations on their feature-label matrices and sharing the class representations. The trade-off hyper-parameter is optimized over the set {10i |i = -5, -4, . . . , 4}.
• THMTFL: the proposed tensor based heterogeneous multi-task feature learning method. Linear SVMs are adopted to learn the weight vectors of base classifiers for knowledge transfer. The hyper-parameters {γm} are set as the same value, and we tune γm over the set {10i |i = -5,-4, . . . , 4}. The hyper-parameter P is empirically set as 10⌈1.5 log C⌉.

If unspecified, the hyper-parameters are determined using leave-one-out cross validation on the labeled set. For DAMA, MTDA, MTNMF, and the proposed THMTFL, we do not tune the hyper-parameter r, which is the number of common factors (or dimensionality of the common subspace). The performance comparisons are performed on a set of varied r = {1, 2, 5, 8, 10, 20, 30, 50, 80, 100}. This also applies to the result dimension of LDA.

Document Categorization

The classification accuracies and macroF1 scores in relation to the number r are shown in Figure 1. The performance of different methods at their best numbers (of common factors) are summarized in Table 1. From these results, we observe that: 1) although the labeled samples in each domain is scarce, learning the feature mapping separately using LDA can still improve the performance significantly. This demonstrates the effectiveness of the supervised mapping learning method in this application; 2) all the heterogeneous transfer learning approaches (DAMA, MTDA, MTNMF, and THMTFL) achieve much better performance than the single domain LDA algorithm. This indicates that it is useful to leverage information from other domains; 3) overall, the proposed THMTFL outperforms all DAMA, MTDA and MTNMF 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. However, in DAMA only the pairwise relationships are explored, and in MTDA and MTNMF the different domains must communicate with each other through an intermediate structure, where some important information contained in the original features may be lost; 4) the performance under the accuracy and macroF1 criteria are consistent. In particular, we obtain a significant relative improvement of 3.4% over the competitive MTNMF in terms of macroF1 score.

We also show the performance for the individual domains of different methods at their best numbers in Figure 2. It can be seen from the results that: 1) the heterogeneous transfer learning methods has larger improvements than LDA in the domains that the discriminative ability of the original representations is not very good, such as EN (English) and IT (Italian). This demonstrates that the knowledge is successfully transferred between different domains; 2) in the good performing SP (Spanish) domain, MTDA is comparable to LDA and DAMA is even worse than LDA. It seems that the discriminative domain obtains little benefits from the other relatively non-discriminative domains in DAMA and MTDA. Although MTNMF performs well in the SP domain, it fails in the IT domain. The proposed THMTFL achieves satisfactory improvements in all domains. This demonstrates that the high-order correlation information between all domains is well discovered, and that exploring this kind of information is much better than only exploring the correlation information between pairs of domains (as in DAMA) or through an intermediate shared structure (as in MTDA and MTNMF).

Image Annotation

We show the annotation accuracies and MacroF1 scores of the compared methods in Figure 3, and summarize the results at their best numbers (of common factors) in Table 2. It can be observed from the results that: 1) the improvements of LDA compared with the original feature baseline are not that large as in the RMLC dataset. This may be because the data of different concepts in this dataset are less separable than the ones in RMLC. Hence the effectiveness of the supervised feature mapping learning method decreases given the limited label information; 2) DAMA is only comparable to LDA, and the improvements of MTDA compared with LDA are marginal. The main reason is that in this application, the different domains corresponding to different kinds of features. This setting is much more challenging 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. Therefore, it is very hard to find some common expressive factors across all domains by only exploiting the pairwise relationships between them. Nevertheless, the proposed THMTFL achieves satisfactory performance by simultaneously exploring all domains, and is superior to the competitive MTNMF at most numbers (of common factors). This further verifies the superiority of the proposed method. The tendency of the macroF1 score curves are similar to that of the accuracy.

4 Conclusion

This paper presents a method for heterogeneous multi-task learning. The proposed method can discover high-order statistics among multiple heterogeneous domains by analyzing the prediction weight covariance tensor of them. The knowledge shared by the different domains is successfully transferred in a common subspace to help each of them in the feature learning by minimizing their high-order divergence in the subspace. We develop an efficient algorithm for optimization, and the exploited high-order correlation information was demonstrated empirically to be superior to the pairwise correlations utilized in the traditional approaches.

From the experimental validation on two popular applications we mainly conclude that: 1) the labeled data deficiency problem can be alleviated by learning 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 mappings so that it has the capability to handle complicated domains.

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.