Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

By Francis R. Bach. 2008

257 citations recorded by the source corpus.

For supervised and unsupervised learning, positive definite kernels allow to use large and potentially infinite dimensional feature spaces with a computational cost that only depends on the number of observations. This is usually done through the penalization of predictor functions by Euclidean or Hilbertian norms. In this paper, we explore penalizing by sparsity-inducing norms such as the l1-norm or the block l1-norm. We assume that the kernel decomposes into a large sum of individual basis kernels which can be embedded in a directed acyclic graph; we show that it is then possible to perform kernel selection through a hierarchical multiple kernel learning framework, in polynomial time in the number of selected kernels. This framework is naturally applied to non linear variable selection; our extensive simulations on synthetic datasets and datasets from the UCI repository show that efficiently exploring the large feature space through sparsity-inducing norms leads to state-of-the-art predictive performance.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Fast ConvNets Using Group-Wise Brain Damage (2015, methodology): “Such elimination can be explicitly encouraged within our approach using hierarchical group-sparsity regularizers [4, 24].”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, methodology): “Keywords: Neural networks, non-parametric estimation, convex optimization, convex relaxation”
Optimization with Sparsity-Inducing Penalties (2011, background): “The next concept we introduce is the dual norm, which is important to study sparsityinducing regularizations [9, 66, 99].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “ct nresponses yi∈ R, from nobservations xi ∈ Rp, for i ∈ {1,...,n}. In this monograph, we focus on linear predictors of the form f(x) = w⊤x, where w∈ Rp (for extensions to non-linear predictions, see [5, 6] and references therein). We consider estimators obtained by the following regularized empiric”
Group Lasso with Overlaps: the Latent Group Lasso approach (2011, background): “One of the first natural approaches to structured sparsity has been to consider extensions of the `1/`2 penalty to situations in which the set of groups considered overlap, so that the possible support pattern exhibit some structure (Bach, 2009; Zhao et al., 2009).”
Learning Triggering Kernels for Multi-dimensional Hawkes Processes (2013, background): “Its learning has been addressed extensively in recent literature where one tries to learn a better positive definite kernel by combining several positive definite kernels (Cortes et al., 2012; Argyriou et al., 2006; Bach, 2008; Dinuzzo et al., 2011; Sonnenburg et al., 2006).”
Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials (2010, methodology): “Similar to (Bach, 2008), we develop an active set method that can incrementally add higher order factors.”
Feature Selection as a One-Player Game (2010, methodology): “An extension of the above to non-linear spaces is given by Multiple Kernel Learning (MLKL) (Bach, 2008), achieving a layer-wise exploration of the “kernel lattice” as opposed to the feature lattice.”
Learning Nonlinear Functions Using Regularized Greedy Forest (2011, background): “The general concept of graph-structured sparsity were considered in [1, 2, 18].”
High-Dimensional Feature Selection by Feature-Wise Kernelized Lasso (2012, background): “Note that SpAM is closely related to the hierarchical multiple kernel learning (Bach, 2009), which employs a sparse additive model with an alternative sparsity-inducing regularizer.”
A Convex Feature Learning Formulation for Latent Task Structure Discovery (2012, methodology): “(2009); Bach (2008), we propose the following novel regularizer for the problem at hand:”
Group lasso with overlap and graph lasso (2009, background): “…covariates for multi-task learning (Obozinski et al., 2009) and penalties to enforce hierarchical selection of covariates, e.g., when one has a hierarchy over the covariates and wants to select covariates only if their ancestors in the hierarchy are also selected (Zhao et al., 2009; Bach, 2009).”
A Regularization Approach to Nonlinear Variable Selection (2010, background): “…mention a series of related works considering the problem of nonlinear dimensionality reduction, either in the supervised setting (see Wu et al. (2008) and references therein) or in the unsupervised setting – see KPCA (Schölkopf and Smola, 2002) and manifold learning (Belkin and Niyogi, 2008).”
Semantic Kernel Forests from Multiple Taxonomies (2012, methodology): “Hierarchical regularization was previously explored in [34], where a mixed (1, 2)-norm is used to regularize the relative sizes between the parent and the children.”
Learning Non-Linear Combinations of Kernels (2009, methodology): “Another method, hierarchical multiple lear ning [3], considers learning a linear combination of an exponential number of linear kernels, which can be efficiently represented as a product of sums.”
Structure Discovery in Nonparametric Regression through Compositional Kernel Search (2013, background): “Kernel learning There is a large body of work at-tempting to construct a rich kernel through a weighted sum of base kernels (e.g. Christoudias et al., 2009; Bach, 2009).”