Multi-Task Model and Feature Joint Learning

1 Introduction

Multi-task learning jointly learns multiple tasks by exploring the interdependence between them. Recent works have witnessed the fast development of multi-task learning in various research areas, such as web image and video search

∗This work is supported by the NSFC 61201413 and 61390514, the Fundamental Research Funds for the Central Universities WK2100060011 and WK2100100021, Australian Research Council Projects: FT-130101457, DP-140102164, and LP-140100569. Y. Li and X. Tian are with the CAS Key Laboratory of Technology in Geospatial Information Processing and Application System, University of Science and Technology of China, China. T. Liu and D. Tao are with the Centre for Quantum Computation & Intelligent Systems and the Faculty of Engineering and Information Technology, University of Technology, Sydney, 81 Broadway Street, Ultimo, NSW 2007, Australia

Tongliang Liu, Dacheng Tao

University of Technology, Sydney tliang.liu@gmail.com, dacheng.tao@uts.edu.au

[Wang et al., 2009], disease prediction [Zhang and Shen, 2012], relative attributes learning [Chen et al., 2014], etc. The basic assumption in MTL is that tasks are related, so learning one task will benefit from learning other tasks. The key problem in MTL, therefore, is how to model the relatedness/interdependence across tasks. Existing multitask learning algorithms have two principal ways to learn the relatedness: sharing common models/parameters [Evgeniou and Pontil, 2004; Xue et al., 2007; Yu et al., 2005; Rai and Daume, 2010], and sharing common features representations [Argyriou et al., 2008; Jebara, 2011; Lapin et al., 2014].

MTL in the category of sharing common models/parameters (multi-task model learning) assumes that the tasks are related in such a way that the true models have something in common in their parameters. For example, Xue et al. constructed a hierarchical Bayesian framework for learning task relatedness using the Dirichlet process and assumed that the Bayesian models shared a common prior [Xue et al., 2007]. Evgeniou and Pontil developed a novel multi-task learning method based on the minimization of regularization functions, similar to support vector machines, and assumed that the hyperplanes of all tasks are close to a mean SVM hyperplane [Evgeniou and Pontil, 2004].

MTL in the category of sharing common feature representations (multi-task feature learning) assumes that the tasks are related in the sense that they all share a small set of features. For example, a framework was proposed for learning sparse representations shared across multiple tasks [Argyriou et al., 2008]. It is based on the well-known L1-norm regularized single-task learning and controls the number of learned common features across tasks. Jebara gave a summary of feature selection and kernel selection in [Jebara, 2011]. In considering the effectiveness of multi-task learning for high dimensional feature space, Lapin et al. proposed a novel multi-task learning method to learn a low dimensional representation jointly with corresponding classifiers [Lapin et al., 2014].

Neither multi-task model learning nor multi-task feature learning can model relatedness well. Recent works have attempted to simultaneously learn model relatedness and feature relatedness [Li et al., 2014; Yang et al., 2013]. Multitask model learning directly mines relatedness in the original feature space. However, the performance of multi-task model learning may be degraded, as relatedness measured by the original features may not be obvious in a real world dataset. Multi-task feature learning solves this problem by mining potentially common feature representations, but ignores the model relatedness between tasks in the learned common feature space. In this paper we propose a multi-task learning method, which jointly learns shared model and shared feature representation. In our multi-task model-feature joint learning method, we learn a set of common features shared by multiple tasks to maximize task relatedness, therefore common models shared across tasks can be optimally learned simultaneously. The proposed method is formalized as a non-convex problem. We propose an alternating algorithm to solve this challenging problem. Theoretical analyses are also presented which prove that joint model and feature learning is able to model task relatedness well.

2 Multi-task model and feature joint learning

Our main idea is to learn a shared model and shared feature representations simultaneously, as illustrated in Figure 1. Multiple tasks in real world applications may not be closely related due to complexity and noise. In other words, they have weak interdependence and their models/hyperplanes may differ significantly in the original feature space. We hope to learn a feature mapping matrix U, through which the hyperplanes of all tasks are closely related, enabling them to share a common hyperplane a0. at is the offset of the t-th task, which compensates for the limitation of the study ability of the mapping matrix U and reflects its own unique characteristics.

2.1 The proposed formulation

Assume we are given T different learning tasks. Each task t is associated with a set of data:

where xti is the i-th input feature and yti is its corresponding output. xti ∈ Rd , yti ∈ R, t ∈ {1, 2, ..., T}, and i ∈ {1, 2, ...,mt}. Our goal is to learn T different linear functions using the above T datasets {D1, D2, ..., DT } as follows:

Single-task learning methods learn the T different linear functions separately using their own data (such as linear regression, SVMs), while multi-task learning methods learn the T different functions jointly by mining the relationships between tasks.

Our objective is to learn an orthogonal feature mapping matrix U through which all tasks can share a central hyperplane a0 but also preserve their unique model at,

The central hyperplane a0 represents the interdependent information across tasks. The offset at captures the unique characteristic of each task. Both a0 and at are learned in the new feature space. We give our proposed multi-task learning model as follows:

where V = [v1, v2, ..., vT ]. 1 is a 1 × T vector with all entries being 1. ‖a0‖2 is the 2-norm of vector a0, which can

be formulated as ‖a0‖2 = ( d∑ i=1 |a0i|2 ) 1 2 . This regularization term is used to guarantee the smoothness of the central hyperplane a0. ‖V - a0 ∗ 1‖2,1 represents the (2, 1)- norm of matrix (V - a0 ∗ 1), which can be formulated as

matrix V . The (2, 1)-norm regularization ensures that common features will be selected across all tasks. It encourages the group sparse property, which means that many rows of the learned matrix (V - a0 ∗ 1) are all zero.

Note vt = at + a0, problem (3) can be rewritten as

where A = [a1, a2, ..., aT ].

Our proposed formulation differs from the formulation proposed in [Argyriou et al., 2008] in three main aspects. First, the method proposed in [Argyriou et al., 2008] ignores the limitation of the learning ability of feature mapping matrix U. It may be more feasible to select the common features by regularizing V around a0 ∈ Rd rather than the original point. Our proposed problem (3) learns the shared feature around point a0 instead of the original point. Second, the method proposed in [Argyriou et al., 2008] focused on learning shared features and did not consider the relationships of task models. After the shared feature was learned, they treated multiple tasks independently when learning their model parameters. From the formulation of problem (4), we can see that our method jointly learns the shared features and shared common parameters. Third, the minimization of our proposed objective function will be more difficult because we learn the shared features and shared common parameters simultaneously. This will be shown in the following section.

2.2 Equivalent convex optimization problem

Problem (4) is a non-convex problem. It is difficult to solve such a non-convex optimization problem directly. We will give an equivalent convex optimization problem of problem (4) in this section [Argyriou et al., 2008].

Theorem 1. Problem (4) is equivalent to the following convex optimization problem:

In particular, if ( ˆ A, ˆ a0, ˆU) is an optimal solution of problem (4), then ˆW = ˆU ˆ A, ˆ w0 = ˆU ˆ a0, ˆD = ˆUDiag( ‖ˆai ‖2 ‖ ˆ A‖2,1 )di=1 ˆU T is an optimal solution of problem (5). Conversely, if ( ˆW, ˆ w0, ˆD) is an optimal solution of problem (5) then any ( ˆ A, ˆ a0, ˆU), such that the columns of ˆU form an orthonormal basis of eigenvectors of ˆD and ˆ A = ˆU T ˆW, ˆ a0 = ˆU T ˆ w0 is an optimal solution of problem (4).

Noting that Sd+ represents the set of positive semidefinite symmetric matrices and range(W) denotes the set {x ∈ Rn : x = Wz, for some z ∈ RT }. Diag(a0)di=1 represents a diagonal matrix with the components of vector a0 on the diagonal. D+ is the pseudoinverse of matrix D.

2.3 An optimization algorithm

In this section, we propose an alternating algorithm to solve problem (5) by alternately minimizing it with respect to (W,w0) and D, as presented in Algorithm 1. We can ultimately obtain the solution to problem (4) through the relationships between the optimal solution of problem (4) and problem (5) in Theorem 1.

In Algorithm 1, we first fix D and minimize the problem over (W,w0). When D is fixed, the minimization over wt cannot simply be separated into T independent problems because of the existence of w0. Therefore, it is more difficult to Algorithm 1 Multi-task model and feature joint learning

• 1: Initialize D = Id , d is the dimension of the data
• 2: while ‖W-Wprev‖ > tol1 or ‖w0-w0prev‖ > tol2 do

• 4: D = (WW T ) 1 2 trace(WW T ) 1 2
• 5: end while

solve our proposed problem. It is shown as follows:

We consider the situation in which the loss function is a least squared loss and make changes to solve the above problem. Suppose Xt = [xt1, xt2, ..., xtmt ] ∈ Rd×mt represents all data points in task t. Yt = [yt1, yt2, ..., ytmt ]T ∈ Rmt represents the outputs of the mt data points in task t. M is the total number of data points of all T tasks:

Let X = bdiag(X1,X2, ...,XT ) ∈ RdT×M and Y = [Y T 1 , Y T 2 , ..., Y T T ]T ∈ RM , X represents a block diagonal matrix with the data of T different tasks as the diagonal elements. Y is the output vector of all data points in the T tasks by aligning the outputs of each of the tasks. Let D0 =

bdiag(D,D, ...,D

︸ ︷︷ ︸

T

0 , ...,wT

) ∈ RdT×M , W0 = [wT

0 ,wT

︸

︷︷

0

︸

Problem (6) can be reformulated as

T

]T ∈

have

where Z = [Z T 1 ,Z T 2 ] and P = [√ Tγ (D+ 0 )- 12 , √ 1β I0]. Then problem (7) can be formulated as follows:

The above problem is a standard 2-norm regularization problem and has an explicit solution:

W and W0 can be derived from Z, then problem (6) is solved.

The second step of Alogorithm 1 is to fix (W, w0) and minimize problem (5) over D. We just need to solve the following problem for a fixed W and w0:

The optimal solution is given as follows [Argyriou et al., 2008]:

3 Theoretical Analysis

In this section, we derive a generalization bound for proposed problem (4). We change the soft constraints γ T ‖A‖22,1 and β‖a0‖22 into hard constraints. Then, problem (4) becomes:

Note that problem (13) is equal to problem (4) and that both ε1 and ε2 are of order O(1) (see [Vainsencher et al., 2011]). Let ε1 = ε2 = O(1), problem (13) becomes:

Thus, a problem with soft constraints can be analyzed in the form of hard constraints. Mehta and Gray [Mehta and Gray, 2013] directly set ε = 1 to analyze a soft constraint problem by changing it into a hard constraint problem. We will analyze proposed problem (4) in the same way and provide a generalization bound to the following problem:

To upper bound the generalization error, we assume that the loss function l satisfies the following Lipschitz-like condition, which has been widely used (see [Mohri et al., 2012]).

Definition 1. A loss function l is c-admissible with respect to the hypothesis class H if there exists a c ∈ R+, where R+ denotes the set of non-negative real numbers, such that for any two hypotheses h, h′ ∈ H and example (x, y) ∈ X × R, the following inequality holds:

The result is as follows:

Theorem 2. Let the loss function l be upper bounded by B, that is l(y, f(x)) ≤ B, and be c-admissible with respect to the linear function class. For any A, a0 and U learned by problem (4) with the soft constraints about γ 1 T ‖A‖22,1 and β‖a0‖22 being replaced by the hard constraints ‖A‖22,1 ≤ Tγ and ‖a0‖22 ≤ 1β , and for any δ > 0, with probability at least 1 - δ, we have

where S(Xt) = tr ( ˆΣ(xt)) = 1 mt ∑mt i=1 ‖xti‖22 is the empirical covariance for the observations of the t-th task. Let m1 = . . . = mT = m and ‖xt‖2 ≤ r, t = 1, . . . , T, with probability at least 1 - δ, we have

Remark 1. According to Theorem 2, the two terms 2cr √γm and 2cr √βmT are the generalization bounds with respect to the learning of A = (a1, . . . , aT ) and a0, respectively, where A corresponds to the specific task in the set of multiple tasks, and a0 corresponds to the shared hyperplane of the multiple tasks. Our theoretical result shows that a0 can be learned with the order of O(√1/mT), which means the shared hyperplane can be successfully learned by increasing the number of tasks. We have therefore theoretically justified that the proposed multi-task learning is superior to single task learning. Additionally, the employed orthogonal operator U and regularization on ‖A‖2,1 will encourage a0 to be as large as possible. The generalization bound of problem (4) will therefore converge faster than that of problem proposed in [Argyriou et al., 2008], which means the proposed method is more efficient.

4 Experiments

In this section, we present extensive experiments conducted on several real-world datasets including School, SARCOS, and Isolet. These datasets have been wildly used for evaluation in previous multi-task learning works, for example in [Argyriou et al., 2008; Gong et al., 2012b; Chen et al., 2011; Kang et al., 2011; Gong et al., 2012a]. We compare the performance of our proposed multi-task model and feature joint learning (MFJL) method with two single-task learning methods and five state-of-the-art multi-task learning methods. The two single-task learning methods are ridge regression (Ridge) and least squares with L1-norm regularization (Lasso). The five multi-task learning methods are least squares with trace norm regularization (TraceNorm), least squares with low-rank and sparse structures regularization (Sparse-LowRank) [Chen et al., 2012], convex multitask feature learning (CMTL) [Argyriou et al., 2008], robust multi-task learning with low-rank and group-sparse structures (RMTL) [Chen et al., 2011] and dirty model multi-task regression learning (DirtyMTL) [Jalali et al., 2013]. We choose these five multi-task learning methods as our competitors because their objective formulations are similar to ours and they have achieved top-level performance on benchmark datasets. All these methods use a least square loss function.

4.1 School dataset

The School dataset is from the Inner London Education Authority. It consists of the examination scores of 15,362 students from 139 secondary schools in 1985, 1986 and 1987. There are 139 tasks in total, corresponding to examination scores prediction in each school. The input features include the year of the examination, 4 school dependent features and 3 student-dependent features. We follow the same setup as previous multi-task learning works and obtain a 27dimensional binary variable for each example.

We randomly select 10%, 20% and 30% of the examples in each respective task as a training set, and the remaining examples are used for testing. For each training ratio, we repeat the random splits of the data 10 times and report the average performance. The parameters of all methods are tuned via crossvalidation on the training set. We evaluate all these regression methods using normalized mean squared error (nMSE) and averaged mean squared error (aMSE) [Gong et al., 2012b; Chen et al., 2011].

The experimental results are shown in Table 1. From these results, we make the following observations. (1) All multitask learning methods outperform single-task learning methods, which proves the effectiveness of multi-task learning. (2) Our proposed joint learning method significantly and consistently outperforms all other baseline MTL methods, especially when the training ratio is small. This demonstrates that our method can successfully learn the optimal feature space in which multiple tasks are closely related.

We also show the absolute values of learned weight A0 = [a0, a0, ..., a0 ︸ ︷︷ ︸ T ] and A in Figure 2 and Figure 3, respectively.

Here, the training ratio is 20%. The black areas in the figures denote zero value. From Figure 3, we can see that the learned weight matrix A is very sparse, and there are about 15 nonzero rows referring to the shared features across tasks. As for matrix A0, we find that some features not shared in matrix A will be used in the central hyperplane a0, which will increase the utilization of information in the features.

4.2 SARCOS dataset

The SARCOS dataset is related to an inverse dynamic problem for a seven degree-of-freedom SARCOS anthropomorphic robot arm. It consists of 48,933 observations corresponding to seven joint torques. Each observation is described by a 21-dimensional feature vector, including seven joint positions, seven joint velocities, and seven joint accelerations, therefore we have seven tasks in total. Our task is to map the 21-dimensional features to the seven joint torques. We randomly select 50, 100 and 150 examples to form three separate training sets respectively, and randomly select 5000 examples as test sets. All experiments are run 15 times to avoid randomness. The validation methods are the same as described in the experiments on the School dataset for all the multi-task learning methods.

The experimental results in terms of averaged nMSE and aMSE are given in Table 2. We make similar observations to those in the experiment on the School dataset. Our proposed joint learning method again achieves much better performance than other baseline algorithms, which demonstrates the effectiveness and robustness of our proposed multi-task model and feature joint learning method.

4.3 Isolet dataset

We have also tested our method on the Isolet dataset. This dataset is collected from 150 speakers, each of whom speaks all the English letter of the alphabet twice, i.e., each speaker provides 52 data examples. The speakers are grouped into five subsets of 30 similar speakers; thus we have five tasks corresponding to the five speaker groups. The five tasks have 1560, 1560, 1560, 1558 and 1559 corresponding samples. Each English letter corresponds to a label (1-26) and we treat the English letter labels as regression values following the same setup as [Gong et al., 2012a]. We randomly select 15%, 20%, 25% of the samples to form three training sets and use the rest of the samples as test sets. We first preprocess the data with PCA by reducing the dimensionality to 100. Experiments are repeated 10 times.

Experiments on the School and SARCOS datasets have shown that Ridge and Lasso do not perform well for multitask learning problem, therefore we only compare MFJL with five multi-task learning algorithms in this experiment. The experimental results on the Isolet dataset in terms of averaged nMSE and aMSE are given in Table 3. It is clear that our MFJL outperforms the other five multi-task learning methods stably, which demonstrates that our method is suitable for problems in a variety of applications.

5 Conclusion

In this paper, we propose a novel multi-task learning method by jointly learning shared parameters and shared feature representations. A detailed description of our proposed multitask learning method is provided. Additionally, we present a theoretical bound which directly demonstrates that the proposed multi-task learning method performs better than singletask learning and is able to successfully model the relatedness between tasks. Various experiments are conducted on several landmark datasets and all results demonstrate the effectiveness of our proposed multi-task learning method.