Latent Group Structured Multi-task Learning

Multi-task learning (MTL) [6, 2] seeks to improve the performance of a specific task by sharing information across multiple related tasks. Specifically, this is done by simultaneously training many tasks, and promoting relatedness across each task’s feature weights. MTL continues to be a promising tool in many applications including medicine [24, 29], imaging [12], and transportation [25], and has recently become repopularized in the field of deep learning (e.g. [31, 26, 8, 7]).

A common approach to multi-task learning [2, 10] is to provide task-specific weights on features. There are two main approaches toward enforcing task relatedness. One is by promoting similarity between task weights, either through regularization in convex models [3, 17, 11] or structured priors in statistical inference [28, 27, 19]. The other is through enforcing a low-dimensional latent space representation of the task weights [32, 18, 21, 1, 9].

Where the main strength of multi-task learning is shared learning across tasks, a main weakness is contamination from unrelated tasks. Many MTL models have been proposed to combat this contamination. Weighted task relatedness can be imposed via the Gram matrix of the features [23] or a kernel matrix [10], or probabilistically using a joint probability distribution with a given covariance matrix. Pairwise relativeness can also be learned by optimizing for a sparse covariance or inverse covariance matrix expressing the relatedness between weights on different tasks; this can be done either by alternating minimization [30, 13, 16] or variational inference[27]. To encode specifically for group or cluster structure, one approach is to compose a combinatorial problem, in which group identity is represented by an integer [17, 4]. Another approach is to provide multiple sets of weights for each task, regularized separately to encode for different hierarchies of relatedness [14].

For latent space models, task relatedness and grouping can be imposed more simply, without many added variables or discrete optimization. Concretely, each task-specific feature vector can be modeled as $x^{t}\approx Ls^{t}$, where the columns of $L$ encode the latent space and a sparse vectors $s^{t}$ decide how the latent vectors are shared across tasks. In this context, [21] uses dictionary learning to learn a low rank $L$ and sparse $s^{t}$’s for each task; this representation is then applied to online learning tasks. Similarly, [18] uses the same model, but learns $L$ and $s^{t}$ through minimizing the task loss function. In both cases, the support of $s^{t}$ for different $t$’s may overlap, enabling this model to capture overlapping group structure in a completely unsupervised way.

In this paper, we take a step back and decompose this problem into two steps: first, learning task relatedness structure, and then, performing MTL. The main motivation for this two-step approach is that oftentimes, task-relatedness already given in the metadata. For example, in the task of interpreting geological photos, it may be helpful to use terrain labels (forest, desert, ocean) to help group the types of images. Similarly, in regressing school test scores, where each task corresponds to a school, a task group may be a specific district, or designation (private/public/parochial), or a cluster discovered from ethnic or socioeconomic makeup–in this way, the groups are intentionally interpretable. Once the (possibly overlapping) groups are identified, we solve the latent-space model with an overlapping group norm regularization on the variables $s^{t}$. Although the first step can be made significantly more sophisticated, we find this simple approach can already give superior performance on several benchmark tasks.

For a vector $x\in\mathbb{R}^{n}$, we denote $x_{i}$ as the $i$th element of $x$, and for some group $G\subseteq\{1,\ldots,n\}$, we denote $x_{G}=\{x_{i}\}_{i\in G}$ the subvector of $x$ indexed by $G$. We denote the Euclidean projection of a vector $x$ on a set $\mathcal{S}$ as $\textbf{proj}_{\mathcal{S}}(x)$. For a vector or matrix, we use $x^{\prime}$ to represent the transpose of $x$.

Although (2) is not convex, it is biconvex in L and S; we therefore solve (2) using an alternating minimization strategy:

where $\textbf{S}^{+},\textbf{L}^{+}$ are the new iterates. The optimization function in (5) is over a smooth, strongly convex function in L, and can be efficiently minimized either via accelerated gradient descent directly via backsolve if $\ell(y,x)=\|x-y\|_{2}^{2}$ (e.g. linear regression).

The optimization for S in (6) is less straightforward, since the group norm is nonsmooth; this is done via the fast iterative shrinkage-thresholding algorithm (FISTA), which to minimize $f(\textbf{S})+g(\textbf{S})$ where $f(\textbf{S})=\sum_{t}\sum_{i}\ell(y_{i}^{t},\textbf{s}_{t}^{\prime}\textbf{L}^{\prime}x_{i}^{t})$ is convex and differentiable, and $g(\textbf{S})=\|\textbf{S}\|_{1,\mathcal{G}}$ is nonsmooth. The FISTA iterates for a step size $t>0$ are then

for each row $i=1,\ldots,k$ of S. The proximal operator[20] is defined as

For $g(x)=\|x\|_{\mathcal{G}}$, we compute $\textbf{prox}_{tg}(x)$ as described in [22]. Define the sets $\mathcal{B}_{k}$ where $x\in\mathcal{B}_{k}\iff\|x_{G_{k}}\|_{2}\leq 1$, for $k=1,\ldots,g$. Define $\mathcal{B}=\mathcal{B}_{1}\cap\mathcal{B}_{2}\cap\cdots\cap\mathcal{B}_{g}$. That is,

By Fenchel duality,

Note that if the groups are not overlapping, then this projection decomposes to $g$ smaller projections:

and can be computed in one step. When the groups overlap, we adopt the simple cyclic projection algorithm proposed in [22, 5]. These steps are outlined precisely in Alg. 2.

The algorithm listing in Algorithm 1 outlines the alternating minimization steps for solving Equation 2. We adopt the method from [18] to initialize L. The individual task weight matrix $\textbf{w}_{t}$ are first learned independently using their own data $\textbf{Z}_{t}$, and stacked as the columns in W. The matrix L is then initialized with the top-k singular vectors of W. The main algorithm then alternately minimizes for L and S, and is terminated when there is small change of either L or S between consecutive iterations

In this section we provide experimental results to show the effectiveness of the proposed formulation for both regression and classification problems. We compare against three baselines:

• •

  Single task learning (STL): Each task is learned separately, through logistic or ridge regression.

• •

  MTL-FEAT [3]: A latent space MTL model that regularizes S via the 2,1 norm, e.g. solves

  $$\min_{\textbf{S},\textbf{L}}\sum_{t=1}^{T}\left(\sum_{i=1}^{n_{t}}\ell(y_{i}^{t},\textbf{s}_{i}^{\prime}\textbf{L}^{\prime}x_{i}^{t})+\mu\|s_{t}\|_{1}^{2}\right)$$

• •

  GO-MTL [18]: A latent space model that regularizes L for low rank and S for sparsity, e.g. minimizing

  $$\min_{\textbf{S},\textbf{L}}\sum_{t=1}^{T}\sum_{i=1}^{n_{t}}\ell(y_{i}^{t},\textbf{s}_{i}^{\prime}\textbf{L}^{\prime}x_{i}^{t})+\mu\|\textbf{S}\|_{1}+\lambda\|\textbf{L}\|_{F}$$

• •

  GS-MTL Our model.

Below, we test three MTL models on synthetic and real-world datasets. For each dataset, we apply a 60% / 20% / 20% train / validation / test split, with a grid search to determine the best $\lambda$ and $\mu$ over powers of 10.

In this paper, we proposed a novel framework for learning tasks’ relationship in multi-task learning, where a prior group structure is either determined beforehand by problem metadata or inferred via an independent method such as K-means. We build upon models that enforce task interdependence through a latent subspace, regularized accordingly to capture group structure. We give algorithms for solving the resulting nonconvex problem for overlapping and non-overlapping group structure, and demonstrate its performance on simulated and real world datasets.