Tree-Guided Group Lasso for Multi-Task Regression with Structured Sparsity

By Seyoung Kim, Eric P. Xing. 2009

478 citations recorded by the source corpus.

We consider the problem of learning a sparse multi-task regression, where the structure in the outputs can be represented as a tree with leaf nodes as outputs and internal nodes as clusters of the outputs at multiple granularity. Our goal is to recover the common set of relevant inputs for each output cluster. Assuming that the tree structure is available as prior knowledge, we formulate this problem as a new multi-task regularized regression called tree-guided group lasso. Our structured regularization is based on a group-lasso penalty, where groups are defined with respect to the tree structure. We describe a systematic weighting scheme for the groups in the penalty such that each output variable is penalized in a balanced manner even if the groups overlap. We present an efficient optimization method that can handle a large-scale problem. Using simulated and yeast datasets, we demonstrate that our method shows a superior performance in terms of both prediction errors and recovery of true sparsity patterns compared to other methods for multi-task learning.

Subfields: Genetics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

In Statistics and Probability

In Optimization & Training

Citations in the corpus

An Overview of Multi-Task Learning in Deep Neural Networks (2017, background): “[Kim and Xing, 2010] extend the group lasso to deal with tasks that occur in a tree structure, while [Chen et al., 2010] apply it to tasks with graph structures.”
A Survey on Multi-Task Learning (2017, methodology): “Similar to [33] where a priori information is given to describe task relations in a hierarchical/tree structure, Kim and Xing [35] utilize the given tree structure to design a regularizer on W as f(W) = ∑d i=1 ∑ v∈V λv‖wi,Gv‖2, where V denotes the set of nodes in the given tree structure, Gv denotes”
Theory-Guided Data Science: A New Paradigm for Scientific Discovery from Data (2016, background): “By treating the set of variables observed at every location as a group, the use of group Lasso ensured that if a location is selected, all of the climate variables observed at that location will be used as relevant features.”
Regularizing Text Categorization with Clusters of Words (2016, background): “, through sets, trees (Kim and Xing, 2010; Liu and Ye, 2010; Mairal et al., 2010) or graphs (Jenatton et al.”
Learning Structured Sparsity in Deep Neural Networks (2016, methodology): “Because group Lasso can effectively zero out all weights in some groups [14][15], we adopt it in our SSL.”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “Reducing parsimony to finding the model of lowest cardinality turns out to be limiting, and structured parsimony [15, 62, 64, 66] has emerged as a natural extension, with applications to computer vision [32, 62, 70], text processing [68], bioinformatics [64, 73] or audio processing [80].”
Distributed Multi-Task Learning (2015, methodology): “It has been successfully exploited in, e.g., spam ﬁltering [Weinberger et al., 2009], web search [Chapelle et al., 2010], disease prediction [Zhou et al., 2013] and eQTL mapping [Kim and Xing, 2010].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “3) lead to applications to hierarchical dictionary learning and topic models [113], structured priors for image denoising [113, 114], background subtraction [142], and bioinformatics [107, 119].”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “…subspace (Chen et al., 2010; Negahban and Wainwright, 2011) and a common set of shared features (Argyriou et al., 2008; Gong et al., 2012; Kim and Xing, 2009; Kolar et al., 2011; Lounici et al., 2009; Liu et al., 2009; Negahban and Wainwright, 2008; Obozinski et al., 2006; Yang et al., 2009;…”
Multi-Task CNN Model for Attribute Prediction (2015, background): “If tasks are related and especially when one task lacks training data, it may receive visual knowledge from other, more fit tasks [1], [4], [19], [23], [31].”
Learning Multi-Level Task Groups in Multi-Task Learning (2015, background): “For example, to find the cross-talks from gene expressions, the correlated genes are often interacted with multi-level clusters as studied in (Kim and Xing 2010; Han et al. 2014).”
Optimization for machine learning (2010, background): “, 2009; Bach, 2008a; Schmidt and Murphy, 2010), multi-task regression of gene expressions (Kim and Xing, 2010) and also for the design of localized features in face recognition (Jenatton et al.”
Discriminative Transfer Learning with Tree-based Priors (2013, background): “A large class of discriminative models [12, 25, 11] have also been used for transfer learning that enable discovering and sharing information among related classes.”
Semantic Kernel Forests from Multiple Taxonomies (2012, background): “Metric learning and feature selection can also benefit from an object hierarchy, either by preferring to use disjoint feature sets to discriminate super- and sub-classes [10], by using a taxonomy-induced loss for structured sparsity [21], or by sharing parameters between metrics along the same path ”
Multi-target regression via input space expansion: treating targets as inputs (2012, methodology): “Most methods assume that all tasks are related to each other (Evgeniou and Pontil 2004; Ando and Zhang 2005; Argyriou et al 2006, 2008; Chen et al 2009, 2010a; Obozinski et al 2010), while there are methods assuming that tasks are organized in structures such as clusters (Jacob et al 2008; Zhou et a”
Traffic Sign Recognition via Multi-Modal Tree-Structure Embedded Multi-Task Learning (2017, methodology): “Combining (5) and (16) we obtain the following form: qL(Wt) = argmin W ( 1 2 ‖W −V‖2F + λ̃1‖W‖T ) = arg min W1,...,WD D∑ i=1 ( 1 2 ‖Wi −Vi‖2F + λ̃1‖Wi‖T ) (17) where Wi, Vi denotes the ith row of the matrix W, V respectively.”
Hierarchical Regularization Cascade for Joint Learning (2013, methodology): “…work investigating the sharing of information at different levels either assume that the structure of sharing is known, or solve the hard problem of clustering the tasks into sharing groups (Torralba et al., 2007; Kang et al., 2011; Jawanpuria & Nath, 2012; Kim & Xing, 2010; Zhao et al., 2011).”
Feature Selection Based on Structured Sparsity: A Comprehensive Study (2017, background): “However, in practical applications, the features have some essential structures, such as disjoint groups [52], [53], overlapping groups [54], graphs [55], and trees [56].”
Privacy-Preserving Distributed Multi-Task Learning with Asynchronous Updates (2017, methodology): “Examples of commonly used MTL regularizations include shared feature subspace via low-rank modeling [2, 11] and shared feature subset via group sparsity [12, 31, 46].”
Learning deep features for multiple object tracking by using a multi-task learning strategy (2014, background): “Multi-task learning [11, 32, 33, 34, 35, 36, 37] has been proven to be more effective than single task learning as multiple tasks are learned simultaneously rather than independently.”