Group LASSO with Asymmetric Structure Estimation for Multi-Task Learning

1 Introduction

Multi-task learning (MTL) deals with the problem of learning multiple related tasks simultaneously in such a way that similar tasks can share information with each other. By using this interplay between tasks we can improve the overall performance of learning models [Caruana, 1997; Baxter, 1997; Thrun and O'Sullivan, 1996].

In real world scenarios where the tasks present groups of coupled features, the Group LASSO regularization has been widely used to encourage group sparsity across tasks [Liu et al., 2009; Wang et al., 2012; Liu et al., 2018]. The drawback so far is that these methods do not estimate a transference structure among tasks, using regularization techniques to enforce a priori knowledge into the transference scheme.

In the structure estimation literature, several proposals to capture the tasks interplay have been presented: estimating a transference structure imposing a shared prior over the precision matrix of tasks parameters [Zhang and Yeung, 2010; Gonc¸alves et al., 2016]; clustering/grouping tasks in a space [Kumar and Daum´e, 2012]; using local learning methods in a k-nearest-neighbor fashion [Zhang, 2013]; and sharing information regarding tasks losses [Lee et al., 2016]. These structure estimation mechanisms in MTL have not only improved the overall performance on individual tasks, but the estimated task relationship has also proven to be helpful on the comprehension of underlying processes expressed in the data. Despite estimating a transference structure, these methods learn a symmetric task relationship structure, imposing the amount of information transferred from task A to B to be equal to that transferred from task B to A, which might not be a valid assumption. It is also likely that two tasks might only be related at a particular group of covariates and completely unrelated at other groups.

In an attempt to acquire the best from those formulations, more specifically: (i) properly capture the task transference structure, (ii) account for different task relations for each group of covariates, and (iii) promote asymmetric sharing between tasks; our proposal is the first initiative in the literature to conceive a Group LASSO formulation for MTL with an asymmetric structure estimation. A relationship matrix is learned for each group of covariates, allowing a more flexible and possibly more realistic model.

2 RelatedWork

The Group LASSO regularization (standard and latent versions [Yuan and Lin, 2006; Jacob et al., 2009]) was proposed to allow sparse solutions for applications where the feature set is composed of grouped features. For instance, suppose we want to map a brain imaging dataset to some condition, a classification task indicating if the condition is present or not. We also know that features representing nearby areas of the brain are related and can be tagged into Regions of Interest (ROI). Group LASSO allows us to embody this information inside the model by treating each ROI as a group of features.

In MTL literature, several approaches have employed Group LASSO as a way to deal with grouped features. [Liu et al., 2009] proposed a model that encourages group-structured sparsity across all tasks, exploring potential parameter coupling between tasks. Extending [Liu et al., 2009], [Wang et al., 2012] also enforces sparsity within each group. MT-SGL [Liu et al., 2018] uses a group-based approach as in [Wang et al., 2012] but decoupling the tasks and encouraging sparsity in a feature level across all tasks. In other words, each task is free to find its own sparsity pattern at a group level, but each feature is coupled among all tasks.

Other methods do not consider group information but estimate a structure that relates tasks to each other. MTRL [Zhang and Yeung, 2010] propose a convex formulation in which a matrix-variate prior distribution is placed on the task coefficients to model task relationship. In [Gonc¸alves et al., 2016] a sparse precision matrix is learned from the data to capture tasks relationship and help to isolate unrelated tasks. A LASSO penalty is also applied to task parameters for automatic feature selection. The model uses a semi-parametric Copula distribution as prior for the tasks parameter matrix, thus also capturing non-linear correlation among tasks.

Another direction is to model transference among tasks using a latent basis, where each task is represented by a linear combination of the basis vectors. In MTFL [Kang et al., 2011], tasks are grouped into a pre-defined number of disjoint groups and each feature is coupled with all tasks of the same group using an l(2,1)-norm [Argyriou et al., 2008]. Both [Kumar and Daum´e, 2012] and [Kang et al., 2011] recover a latent basis with no direct interpretation. AMTL [Lee et al., 2016] estimates an asymmetric transference matrix where more confident tasks may transfer more information to less confident ones than the converse.

We propose a Group LASSO formulation for MTL that estimates an asymmetric transference structure at a group level: for each group of features, we learn an asymmetric task relationship matrix. Considering that tasks may relate to each other in different ways for different groups, our model brings more flexibility than the presented methods that can estimate a transference structure. Compared to other Group LASSO models for MTL, we explicitly learn the relationship of the tasks without any strong assumption.

Notation: Matrices are represented using uppercase letters, while scalars are represented by lowercase letters. Vectors are lowercase in bold. For any matrix A, a¯i is the i-th row of A, and aj is the j-th column. Also, aij is the scalar at row i and column j of A. The i-th element of any vector a is represented by (a)i. In is the identity matrix of size n × n. For any two vectors x, y the Hadamard product is denoted by (x ⊙ y)i = (x)i(y)i.

3 The GAMTL Formulation

The Group Asymmetric Multi-Task Learning (GAMTL) formulation is presented in what follows. Let T be the number of tasks and T = {1, · · · , T} the set of task indices. For each task t, the data consists of the design matrix Xt ∈ Rmt×n and the vector of labels yt ∈ Rmt . Let G = {1, · · · ,G} be the set of groups. A group g ∈ G defined as g ⊆ {1, · · · , n} is a group of covariates of Xt, ∀t ∈ T , with cardinality |g| containing related covariates that should be penalized together. As an example, consider again the case where our dataset is composed of brain images annotated with Regions Of Interest. Each feature could be a pixel in the image, and a group of covariates contains several pixels of the same ROI.

Let W ∈ Rn×T be the parameter matrix, where each column wt represents the parameters of task t. W g ∈ Rn×T is the parameter matrix restricted to group g, where (wg )i = (w)i when i ∈ g, and (wg )i = 0 otherwise. When the groups overlap, we assume that the adequate columns of Xt are duplicated, and W is set accordingly [Jacob et al., 2009].

To model the relationship among tasks in an explainable manner, we assume that the parameters of task t can be represented by a sparse linear combination of the parameters of the other tasks, considering each group of attributes independently, i. e., wg t ≈ W g bgt , ∀g. Let Bg ∈ RT×T be the relationship matrix of group g, where bgij represents how much task i contributes to task j in group g. A column bgi indicates how much all tasks contribute to task i, while a row bg ¯i indicates how much task i contributes to all other tasks. Let L : Rn → R be a suitable task specific convex loss function, e.g., squared loss for regression or logistic loss for classification, the optimization problem associated with GAMTL is:

where λ1, λ2, and λ3 are regularization hyper-parameters. The normalizing factor 1 mt avoids that tasks with a large number of samples dominate the entire cost function. dg is usually set to √|g| to account for group sizes in the overall function.

The first term of Eq. (1) considers the loss function and uses it to weight all transferences from t to other tasks (row t of Bg ). It learns the task parameters while avoiding transference from tasks with a higher cost to tasks with lower cost. The l1 penalization in each row of Bg enforces a sparse subset of tasks on the combination. The loss also strengthens this penalization: the higher the loss of a task, the higher the penalization. The second term enforces the transference between tasks at the group level. This is achieved by penalizing the Euclidean distance between a task parameter vector and its estimate given by the linear combination of the parameters of the other tasks. The third term and the constraint on wt account for the latent Group LASSO regularization [Jacob et al., 2009]. The second restriction ensures that all values in our transference structure are positive. Figure (1) shows the structural configuration of the model parameters, which will be estimated from data (X, y) from all T tasks.

Problem (1) integrates our goals into one formulation: estimating task parameters with a transference structure among all tasks, at the group level. Considering the simultaneous adjustment of all parameters, the problem is not jointly convex. However, when optimizing (1) in terms of wt, while holding bgt fixed, and vice versa, the overall non-convex problem becomes two easier-to-handle convex problems. The resulting problems are solved in an alternating optimization manner in wt and bgt , ∀g ∈ G, t ∈ T . The complete process is presented in Algorithm (1).

When λ1 = 0, λ2 = 0, and λ3 = 0, independent Single Task Learning (STL) linear models are recovered. If only λ3 ̸= 0 we still have independent linear models per task but with Group LASSO regularization active. When λ2 ̸= 0 transference between tasks will occur, with λ1 controlling the sparsity of the transference. Eq. (1) allows two variants: with and without the second constraint. Restricting or not the values of Bg will depend on the application and on the meaning of a task being negatively related with other tasks. Compared to other MTL algorithms such as MTFL, MTRL, and AMTL, GAMTL has only one additional parameter while providing an explainable transference structure for each group.

Algorithm 1 GAMTL

3.1 Solving for wt

Isolating Eq. (1) in terms of wt, t = 1, 2, · · · , T , we have:

To solve Eq. (2) we use the accelerated proximal method FISTA [Beck and Teboulle, 2009]. We decompose our objective function into f : Rn → R and h : Rn → R ∪ {∞}, both closed proper convex functions, f being L-Lipschitz continuous while h being non-differentiable:

Function h is the group LASSO regularization

The proximal operator for the group LASSO regularization is

We estimate the L constant with a backtracking procedure.

3.2 Solving for bgt

Since a task cannot be represented by itself, bgtt = 0. Isolating Eq. (1) in terms of bgt , let ˜wt = wt - ∑˜ g ∈ G\g W ˜ g b˜ gt , and let W g = [wg 1 /L(w1), · · · ,wgT /L(wT )]. The resulting problem is:

This problem is similar to the Adaptive LASSO [Zou, 2006]. Without the constraints in Eq. (4), it can be solved using any standard method for LASSO. Here we will derive the case where the constraints are required, using the Alternating Direction Method of Multipliers (ADMM) [Boyd et al., 2011]. In the ADMM framework, the inequality constraint can be transformed by means of an indicator function:

where h1 = h, and h2(z2) is defined as

The augmented Lagrangian of Formulation (5) is then, Lρ1,ρ2 = Lρ1,ρ2 (x, z1, z2, u1, u2):

The ADMM updating steps are:

Notice that the two steps in zi-update are executed in parallel. The same occurs for ui. The zi-update steps are solved by the proximal operators: soft-thresholding, Sκ(a) = (1 - κ/|a|)+a; and projection onto the non-negative orthant R+, S(a) = (a)+ = max(0, a). The x-update step is a convex problem with a differentiable function f plus quadratic terms, which can be solved in closed-form via Cholesky decomposition or by any gradient-based method. The Python code associated with GAMTL is available online 1 .

3.3 Complexity Analysis

The complexity of an iteration of GAMTL is driven by the steps 4 and 8 of the Algorithm (1), which involve a FISTA and an ADMM execution, respectively.

For step 4, we compute ∇f and proxλg . The overall cost of the proximal operator is G[gmax]2n, where gmax is the size of the largest group; and to compute the derivative of Eq. 3 we need T 2Ggmax flops. Bigger costs involved in the gradient computation are in order of T 2Gn, with other negligible costs. The overall cost of the full computation of ∇f is then O(T 2Gn). Therefore, a FISTA iteration has then a total cost of O(T 2Gn).

In step 8, we prepare ˜wt using GTn+n flops. For W g , we compute the loss function of each task with cost of n2 +mn, and it is reused for all iterations over the same g. ADMM requires the computation of a soft-thresholding operator, the projection of z, and the update of u. All with negligible costs. Solving the x-update in closed-form via Cholesky decomposition uses T 3 flops, with a back-solve cost of n2 . This results in a overall cost of Tn2 when considering n > T. The cost of a complete ADMM iteration is on order of O(Tn2 ).

In summary, one iteration of GAMTL consists of T FISTA and GT ADMM executions. Therefore, setting a fixed number of iterations, the overall GAMTL time complexity of O(T 3Gn + T 2Gn2 ).

1 https://github.com/shgo/gamtl

4 Experiments and Discussion

For all experiments we denote GAMTLnr as GAMTL without considering the constraints on Bg , ∀g ∈ G.

4.1 Artificial Dataset

To illustrate the components of our proposal and validate the model, we designed an artificial dataset as follows. We generate 8 regression tasks with 50 attributes partitioned into groups g1 = [1, . . . , 25] and g2 = [26, · · · , 50]. For tasks t = [1, 2], w1 t ∼ N(0, I25) while w2 t = 0. The opposite holds for tasks t = [3, 4], where w2 ∼ N(0, I25) while w1 = 0. For the last four tasks t = [5, · · · , 8],w1 t = W 1 [1,2]b1t and w2 t = W 2 [3,4]b2t , where each bgt is sampled from a truncated Gaussian distribution, having positive values. The first column of Figure 3 depicts these vectors concatenated as Bg matrices. For each task t, Xt ∼ N(0, I50), and yt = Xtwt + σ, where σ = 0.3 in the first four tasks, and σ = 0.9 in the last four tasks. This difference in the amount of noise makes the derived tasks more difficult to be solved. In this case, we expect the transference to occur from tasks with low cost to the tasks with a higher cost, thus recovering the transference structure.

The number of samples varied from 30 to 100, by steps of 10 samples. We split the dataset so that 70% of the samples are used for training and 30% for testing. For each amount of samples, the parameters of all methods were chosen by crossvalidation using 30% of the training set. The best performing parameters are selected, and we repeat the training process 30 times. As λ3 directly impacts the group sparsity, we can use results from the parameter tuning of Group LASSO to aid this selection: as λ1 and λ2 are related, it is possible to express one as a function of the other, resulting in just one parameter to choose in the end. However, in practice, setting each parameter independently led to better performance. Our recommendation is to choose initial values for λ1 and λ2 in a similar range but independently from λ3.

The performance of all methods are compared by the normalized mean squared error (NMSE) metric, defined as

where yt and ˆyt are the true and predicted labels for task t, respectively. We considered LASSO [Tibshirani, 1996] and Group LASSO [Jacob et al., 2009] as STL contenders; AMTL [Lee et al., 2016] as the MTL contender that can recover a similar structure, and GAMTL with the squared loss.

Figure 2 shows the NMSE of all methods when varying the total number of samples. Mean and standard deviation from 30 independent runs are reported. Since we start the experiment with an ill conditioned scenario due to small training sample size, all methods perform poorly. But even in this case, GAMTL achieves better performance when 30 ≤ m ≤ 60. As m increases, all methods start to perform similarly.

The gains of GAMTL can be possibly explained by the flexibility of its transference structures (bgt ) that reduces negative transfer often introduced by symmetric information sharing across tasks. In contrast to AMTL, that considers all attributes to transfer, our model fits local relationships. Figure 3 shows the generated B matrices for the two groups, and the estimated transferences of GAMTL with 30, 70, and 100 samples. A column bgt in Bg contains the coefficients of the approximation of task t parameters, and thus its components represent how other tasks affect wg t . A row bg¯ t represents how task t affects the parameters of other task on group g only. Notice that the last four tasks are related with the first four tasks in both groups, but not in the same way.

When the sample size is small (m = 30), we observe that the last columns of the relationship matrices of both groups have higher values than their transposed coordinates. This indicates that all tasks are related but tasks with smaller costs are influencing tasks with higher costs more than the opposite. Since the Bg matrices regularize the task parameters in the direction of tasks with smaller costs, even when the sample size is small, GAMTL makes use of this structure to improve performance on all tasks. When m = 70 the relationship matrices are sparser, with only the more meaningful relations between tasks remaining; and when m = 100 the structures are close to the true matrices.

The estimated transferences from tasks with lower cost are close to the generated values, and some small transference occurs back as tasks are linearly dependent, with results gradually converge to the last column of Figure (3). With enough samples, GAMTL does not transfer between unrelated tasks. Nonetheless, only GAMTL is capable of providing the asymmetric structural relationship required for this problem.

4.2 Real Dataset

The ADNI dataset was collected by the Alzheimer's Disease Neuroimaging Initiative (ADNI) and pre-processed by a team from University of California at San Francisco, as described in [Liu et al., 2018], who performed cortical reconstruction and volumetric segmentation with the FreeSurfer image analysis suite. It consists of information from 816 subjects. There are 116 groups of features in this application corresponding to ROI in the brain. From the total group set, 46 of these groups have a single covariate and 70 groups have four covariates.

The tasks consist of the prediction of 5 cognitive scores based on physical characteristics of each individual's brain extracted from structural MRI images. Note that all tasks use the same input matrix (X). The cognitive scores used in this study are: Rey Auditory Verbal Learning Test (RAVLT) Total score (TOTAL), RAVTL 30 minutes delay score (T30), RAVLT recognition score (RECOG), Mini Mental State Exam score (MMSE), and Alzheimer's Disease Assessment Scale cognitive total score (ADAS). Those are important tasks in the domain of research related to AD, since the use of these scores impacts on drug trials, assessments of the severity of symptoms of AD, the progressive deterioration of functional ability, and deficiencies in memory, as highlighted in [Liu et al., 2018]. Note that for this experiment, understanding how certain areas of the brain impact the outcome of each cognitive score and how they share this impact amongst each other is of high relevance. Our model presents explainable transference structures that can aid researchers to explore further relationships.

GAMTL and GAMTLnl used the squared loss for regression tasks, and the contenders are LASSO, Group LASSO, and AMTL. We add other related MTL formulations: MTSGL, that is also based on group sparsity; MTRL that includes transference structure; and MTFL that accounts for task grouping but has no transference structure estimation.

Following [Liu et al., 2018], the dataset is partitioned into training (95%) and test (5%) sets. All performance comparisons used NMSE as metric. Regularization parameters for the methods are chosen by a 5-fold cross-validation procedure using training data. Then we train each method using the training set and evaluate on the test set. To account for variability in the data, 30 independent executions were performed. The limits of the search grid used to tune parameters for MTRL were ρ1 ∈ [0.06, · · · , 5] and ρ2 ∈ [0.08, · · · , 5]. For MTFL we had 2, 3 as the number of task groups, and ρ1, ρ2 ∈ [0.001, · · · , 10]. For AMTL we used µ ∈ [0.001, · · · , 1], λ ∈ [0.01, · · · , 1]. All variants of GAMTL used λ1 ∈ [10e-5 , · · · , 0.03], λ2 ∈ [0.01, · · · , 0.5], and λ3 ∈ [0.008, · · · , 0.15].

Table (1) summarizes the performance of all methods, pre-

• (a) Left Inferior Lateral Ventricle (b) Corpus Callosum Posterior
• (c) Left Choroid Plexus
• (d) Right Inferior Parietal
• (e) Right Ventral DC

Table 2: MSE (mean and standard deviation over 30 runs) of methods with best performance per task in the ADNI dataset. Best results are highlighted in bold.

senting mean and standard deviation of NMSE over all runs. We can see that GAMTL obtained the best score. We used a Mann-Whitney U test with p ≤ 0.05 to determine whether there was a statistically significant difference between the scores, and it resulted positive when comparing GAMTL scores with the results of other methods.

Table 2 summarizes the MSE (mean and standard deviation over all runs) of the methods with best performance on each task. We highlighted the best MSE of each task. GAMTL exceeded in all but RAVLT TOTAL and T30, where LASSO outperformed all methods.

Note that GAMTL allows the relationship between tasks to be independent for each group of active attributes. We allow the practitioner to understand how the groups of variables are relating to each other by choosing a group and looking straight onto the specific relationship matrix. This turns GAMTL into a more explainable model, as task parameters can be interpreted with all procedures to understand linear regression tasks, and transferences on each ROI are of direct interpretation. In 25 of 30 run, only 5 of 116 ROIs had

‖Bg ‖2 ≥ 0.01. Figure (4) shows the Bg recovered for the 5 ROIs with most transference activity. GAMTL was able to estimate the transference on ROIs of interest on AD literature research. For instance: rates of ventricular enlargement were found to increase over time in both subjects with mild cognitive impairment (MCI) and AD, representing a feasible shortterm marker of disease progression for multi-centre studies [Leung et al., 2013]; measurement of corpus callosum size allows in vivo mapping of neocortical neurodegeneration in AD over a wide range of clinical dementia severities and may be used as a surrogate marker for evaluation of drug efficacy [Teipel et al., 2002].

5 Conclusion and FutureWork

GAMTL is a flexible and explainable model for MTL, suitable for domains where features can be partitioned into a predefined overlapping group structure. Without any strong assumption, we can estimate an asymmetric transference structure involving all tasks in a way that each group of covariates has its own relationship matrix and can properly isolate unrelated tasks. This leads to an easy interpretation of the underlying relationship supported by the tasks, which is desired in several domains. We validated our model on an artificial dataset and also on the ADNI dataset, whose tasks are the prediction of 5 cognitive scores related to the progress and symptoms of Alzheimer's disease. GAMTL not only obtained competitive performance but also estimated a meaningful relationship structure on results supported by the AD research literature. The next research steps include the exploration of new applications, the inspection of other restrictions on the relationship matrices, and the investigation of other visual representations for the estimated structure.

Acknowledgements

We acknowledge the grants #1418812015-1 and #3072282018-5 from the Brazilian National Council for Scientific and Technological Development (CNPq), grant #201307559-3 from S˜ao Paulo Reseach Foundation (FAPESP), and the Coordination for the Improvement of Higher Education Personnel (CAPES).