Joint covariate selection and joint subspace selection for multiple classification problems

By Guillaume Obozinski, B. Taskar, Michael I. Jordan. 2010

544 citations recorded by the source corpus.

We address the problem of recovering a common set of covariates that are relevant simultaneously to several classification problems. By penalizing the sum of ℓ2 norms of the blocks of coefficients associated with each covariate across different classification problems, similar sparsity patterns in all models are encouraged. To take computational advantage of the sparsity of solutions at high regularization levels, we propose a blockwise path-following scheme that approximately traces the regularization path. As the regularization coefficient decreases, the algorithm maintains and updates concurrently a growing set of covariates that are simultaneously active for all problems. We also show how to use random projections to extend this approach to the problem of joint subspace selection, where multiple predictors are found in a common low-dimensional subspace. We present theoretical results showing that this random projection approach converges to the solution yielded by trace-norm regularization. Finally, we present a variety of experimental results exploring joint covariate selection and joint subspace selection, comparing the path-following approach to competing algorithms in terms of prediction accuracy and running time.

Subfields: Computational Mechanics, Computer Networks and Communications, 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 Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

In Optimization & Training

Citations in the corpus

An Overview of Multi-task Learning (2018, background): “Concrete instances of the p, q regularization include the 2,1 regularization proposed in [8,9] and the ∞,1 regularization proposed in [10].”
Cross-Stitch Networks for Multi-task Learning (2016, background): “and their widespread applications in other fields, such as genomics [38], natural language processing [7, 8, 35] and computer vision [3, 10, 30, 31, 40, 51, 53, 58].”
A Survey on Multi-Task Learning (2017, methodology): “Many regularized multi-task algorithms can be classified into two main categories: learning with feature covariance [10], [16], [17], [20], [38], [39] and learning with task relations [4], [5], [43], [56], [61], [62], [63], [64], [65], [66], [78], [87], [90], [102].”
Kernels for Vector-Valued Functions: a Review (2011, neutral): “These latter methods cannot in general be cast in the framework of kernel methods and we refer the interested reader to [69] and references therein.”
Multimodal Multipart Learning for Action Recognition in Depth Videos (2015, methodology): “In joint feature selection, L 1 /L 2 norm can provide multitask learning by applying selection between the L 2 regularized parameters of each feature [29].”
Optimization with Sparsity-Inducing Penalties (2011, background): “A regularization norm exploiting explicitly this group structure, or `1-group norm, can be shown to improve the prediction performance and/or interpretability of the learned models [61, 83, 106, 116, 141, 156].”
Regularization Techniques for Learning with Matrices (2009, methodology): “It was also studied under the framework of group Lasso (Yuan and Lin, 2006; Obozinski et al., 2010; Bach, 2008).”
Optimal Transport for Domain Adaptation (2014, methodology): “The dataset consists in 51935 images of handwritten letters (of size 8×16 pixels) with 26 classes (the letters of the alphabet) written by 158 different writers [28, 29].”
Multi-task Sparse Structure Learning with Gaussian Copula Models (2016, methodology): “…great deal of attention in the past few years and consequently many algorithms have been proposed (Evgeniou and Pontil, 2004; Argyriou et al., 2007; Xue et al., 2007; Jacob et al., 2008; Obozinski et al., 2010; Zhou et al., 2011b; Zhang and Yeung, 2010; Yang et al., 2013; Gonçalves et al., 2014).”
Probabilistic Multi-Task Feature Selection (2010, background): “The objective functions of most existing multi-task feature selection methods [24, 17, 28, 1, 2, 15, 20, 16, 18] can be expressed in the following form:”
Feature Selection Based on Structured Sparsity: A Comprehensive Study (2017, methodology): “The well-known multitask feature selection methods in [112] also use the l2,1-norm.”
Structured Variable Selection with Sparsity-Inducing Norms (2009, background): “…on the structure of the sparse representation is available, e.g., for multiple kernel learning (Micchelli and Pontil, 2006), multi-task learning (Argyriou et al., 2008; Obozinski et al., 2009; Kim and Xing, 2009) and sparse matrix factorization problems (Mairal et al., 2010; Jenatton et al., 2010).”
$\ell_{p}-\ell_{q}$ Penalty for Sparse Linear and Sparse Multiple Kernel Multitask Learning (2011, methodology): “Obozinski et al. [ 36 ] use p = 1a ndq = 2, while Liu et al. [31], [32], Quattoni et al. [39], [40], and Chen et al. [11] have considered the use of p = 1a ndq =∞ . In all these works, the authors have focused on convex situations since � p,q is known to be convex whenever p, q ≥ 1 and nonconvex for”
Optimization for machine learning (2010, methodology): “A regularization norm exploiting explicitly this group structure can be shown to improve the prediction performance and/or interpretability of the learned models (Yuan and Lin, 2006; Roth and Fischer, 2008; Huang and Zhang, 2009; Obozinski et al., 2009; Lounici et al., 2009).”