Learning the Graph of Relations Among Multiple Tasks

Andreas A. Argyriou, Stéphan Clémençon, Ruocong ZhangSPIRE 2013

Abstract

We propose multitask Laplacian learning, a framework for jointly learning clusters of related tasks without prior knowledge of their relationship structure. By treating the task graph as a learnable parameter within a continuously parameterized kernel, our method discovers latent task correlations during the training process. We develop an optimization algorithm based on Douglas-Rachford splitting to solve the resulting semidefinite program. Experimental results on financial indices and recommendation systems demonstrate that our approach outperforms independent learning and existing multitask methods by effectively partitioning tasks into meaningful clusters.

1. Introduction

Multitask learning (MTL) leverages shared information across multiple related tasks to improve overall predictive performance, a strategy particularly beneficial when data per task is limited. A persistent challenge in MTL is the dependency on a known task relationship structure. Most existing methods assume tasks are either all related or follow a pre-defined graph. However, in many practical applications, the underlying relationships are unknown and must be inferred from the data itself.

This work introduces multitask Laplacian learning, which simultaneously learns task-specific models and the graph representing their relationships. By optimizing the Graph Laplacian, the framework identifies clusters of tasks that "borrow strength" from one another more effectively than from unrelated tasks.

2. Methodology

The proposed framework centers on a joint optimization problem that balances task-specific loss with a relationship-aware penalty.

2.1 The Laplacian Penalty and Perturbation

The method employs a penalty based on the Graph Laplacian $L$ to enforce similarity between the parameters of related tasks. A critical refinement introduced here is the addition of a small identity perturbation ($\epsilon I$) to the Laplacian. This technical adjustment ensures the resulting kernel is strictly positive definite, preventing the model from being restricted to the null space of the Laplacian and allowing for a more expressive search across the parameter space.

2.2 Alternating Optimization

To solve the joint problem of learning task parameters and the graph structure, we use an alternating minimization approach:

  • Task Update: Given a fixed graph, the problem reduces to a standard MTL formulation (e.g., multitask ridge regression), which can be solved efficiently.
  • Graph Update: Given fixed task parameters, the graph structure is updated by solving a Semidefinite Program (SDP).

To ensure scalability, we implement a first-order optimization algorithm using Douglas-Rachford splitting, which decomposes the complex SDP into simpler, iterative proximal steps.

3. Experimental Results

The efficacy of multitask Laplacian learning was evaluated on both synthetic and real-world datasets.

3.1 Financial Sector Prediction

The model was applied to predict future returns for 7 European industry sectors based on historical market data. Multitask Laplacian learning achieved a Mean Squared Error (MSE) of 1.85, outperforming independent ridge regression (2.03) and state-of-the-art clustered MTL methods (1.97). The algorithm successfully identified clusters of "defensive" sectors, such as Food & Beverage and Health Care, aligning with economic intuition.

3.2 MovieLens 100k

In a recommendation setting where each user represents a task, our method significantly outperformed independent learning and trace-norm regularization. Unlike other clustered MTL approaches that force rigid projections, the Laplacian framework's flexibility allowed it to better capture the nuanced preferences of users.

4. Conclusion

Multitask Laplacian learning provides a robust framework for discovering latent task structures. By integrating graph learning into the optimization process, it eliminates the need for prior knowledge of task relationships and enables dynamic clustering. Future research will focus on improving computational efficiency for large-scale applications involving thousands of tasks and exploring the theoretical convergence properties of the alternating minimization scheme.

Summary updated

Abstract

We propose multitask Laplacian learning, a new method for jointly learning clusters of closely related tasks. Unlike standard multitask methodologies, the graph of relations among the tasks is not assumed to be known a priori, but is learned by the multitask Laplacian algorithm. The algorithm builds on kernel based methods and exploits an optimization approach for learning a continuously parameterized kernel. It involves solving a semidefinite program of a particu-lar type, for which we develop an algorithm based on Douglas-Rachford split-ting methods. Multitask Laplacian learning can find application in many cases in which tasks are related with each other to varying degrees, some strongly, oth-ers weakly. Our experiments highlight such cases in which multitask Laplacian learning outperforms independent learning of tasks and state of the art multitask learning methods. In addition, they demonstrate that our algorithm partitions the tasks into clusters each of which contains well correlated tasks. 1
BibTeX
@inproceedings{argyriou2013learning,
  author = {Andreas A. Argyriou and Stéphan Clémençon and Ruocong Zhang},
  title = {{Learning the Graph of Relations Among Multiple Tasks}},
  booktitle = {SPIRE},
  year = {2013},
}
Figure