Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Francis Bach

Source-linked AI summary

Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning

Francis Bach

arXiv:0809.1493v1Sep 9, 2008cs.LGstat.ML

TL;DR

The paper addresses how to select useful components from very large kernel feature spaces without making optimization intractable. It introduces DAG-structured hierarchical multiple kernel learning with sparsity-inducing regularization, and reports competitive or improved predictive performance across synthetic and UCI datasets. The framework provides computational efficiency at the cost of consistently estimating only the hull of relevant variables.

Problem
Large kernels may decompose into exponentially many component kernels, creating a need for feasible selection while assessing predictive and feature-selection benefits of sparsity-inducing penalties.
Method
The paper embeds component kernels in a DAG and uses hierarchical sparsity-inducing norms with an optimization algorithm polynomial in the number of selected kernels.
Results
The framework is always competitive and often improves performance over regular ℓ2-regularization on synthetic and UCI regression and classification datasets.
Takeaways & Limitations
Sparsity-inducing penalties can advantageously explore large feature spaces, including polynomial and Gaussian kernels for nonlinear variable selection.
Takeaways & Limitations
The framework consistently estimates only the hull of relevant variables, so computational efficiency is obtained by restricting statistical model-selection power.

Abstract

from arXiv · show

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.

1 Introduction

The paper investigates sparsity-inducing penalties inside large kernel feature spaces, where only a small number of features may be needed. It asks whether optimization and selection remain computationally feasible and whether they improve predictive performance and feature selection.

Motivation: The paper bridges kernel methods with sparsity-inducing norms by applying ℓ1-type regularization inside large feature spaces.The motivation is that estimated predictors may require only a small number of features.
Research questions: It studies whether optimization in very large feature spaces can have cost polynomial in the input-space size.
Research questions: It also asks whether sparsity-inducing penalties improve predictive performance and feature selection.
Problem setting: The kernel is decomposed into many positive definite basis or local kernels, enabling selection among smaller concatenated feature spaces through multiple kernel learning.
Problem setting: Because the number of component kernels can be exponential in input dimension, applying multiple kernel learning directly to the decomposition is intractable.
Contribution: Embedding component kernels in a DAG enables hierarchical selection with polynomial complexity in selected kernels and supports nonlinear variable selection.Experiments compare the framework with regular ℓ2-regularization on synthetic and UCI regression and classification datasets.
Contribution: The framework is reported to be always competitive and often better than regular ℓ2-regularization across the evaluated datasets.

2 Hierarchical multiple kernel learning (HKL)

HKL represents a large kernel as structured basis kernels in a DAG and uses hierarchical sparsity to select kernels while respecting graph constraints. The framework covers nonlinear interactions and supports efficient optimization over large feature spaces.

Graph-structured kernels: The kernel is decomposed into basis kernels whose feature spaces concatenate into the full feature space.Predicting with the full feature map is equivalent to jointly estimating one component βv in each basis-kernel feature space.
Graph-structured kernels: Products of sums yield (q+1)^p basis kernels arranged in a p-dimensional directed grid.The grid connects each kernel to coordinate-wise successors, encoding a product structure across variables.
Graph-structured kernels: The DAG restricts selection so an interaction is selected only after its sub-interactions have been selected.This makes the framework naturally suited to nonlinear variable selection with polynomial and Gaussian kernels.
Kernel decompositions: Gaussian kernels can be decomposed into q+1 components using truncated Hermite-polynomial expansions, with an alternative adaptive kernel-PCA decomposition.The simulations found no significant difference between the two decomposition strategies.
Graph-based regularization: A hierarchical block ℓ1-norm forces descendant groups of basis kernels to become exactly zero, producing hull-structured sparsity.The associated Hilbertian norm is an ℓ1-norm of ℓ2-norms and selects a kernel only after its ancestors under stated conditions.
Graph-based regularization: The proposed optimization algorithm has polynomial complexity in the number of selected groups or kernels for arbitrary group sizes, DAGs, and losses.This extends beyond the settings where tree-specific path algorithms are efficient.

3 Optimization problem

The optimization framework reformulates hierarchical kernel selection through DAG-adapted regularization and solves exponentially large problems using polynomial-time checks and kernel search. Its directed-grid implementation has complexity polynomial in observations and selected kernels, while exploiting structure to manage exponentially many candidates.

DAG-adapted regularization: Hierarchical norms encode DAG-consistent sparsity, with descendant kernel weights no larger than ancestor weights.This enforces selection patterns in which descendant kernels are selected only after their ancestors.
Multiple-kernel reformulation: The reformulation reduces the problem to supervised learning with a weighted sum of kernel matrices, parameterized by α and η.For fixed η and associated ζ, the combined kernel matrix is K = Σ_w ζ_w K_w.
Optimality conditions: Optimality can be checked through separate primal-dual conditions and duality gaps, recovering standard multiple-kernel conditions when the DAG has no edges.The sufficient condition can be approximated to guarantee a total duality gap below ε.
Polynomial-time optimization: The main technical result solves optimization over exponentially many dimensions in polynomial time by exploiting DAG structure and factorized sums in directed grids.In directed grids, factorization enables sums over descendants to be computed efficiently rather than enumerated explicitly.
Kernel search algorithm: The kernel-search algorithm iteratively expands active sets with violating variables until reaching an ε duality gap or the maximum kernel limit Q.Some iterations only improve certification of ε-optimality without changing the solution.
Complexity: O(n3R + n2Rp2 + n2R2p) is the directed-grid running-time complexity, where n is observations, R selected kernels, and p grid dimensions.The terms correspond to solving O(R) single-kernel problems, caching O(Rp) kernels, and computing O(R2p) quadratic forms.

4 Consistency conditions

The consistency analysis establishes conditions under which the framework consistently estimates coefficients and the hull of relevant variables, while clarifying that its sparsity pattern is limited to hull recovery.

The framework targets consistent estimation of the hull of the relevant sparsity pattern rather than the exact pattern itself.The solution’s sparsity pattern equals its hull, so consistency is formulated for hull recovery.
Under the sufficient condition and λ_n n^1/2 →∞ with λ_n →0, coefficients and the hull of relevant variables are consistently estimated.
A necessary condition is also derived for consistent estimation of the coefficients and the hull under some regularization sequence.
The consistency results require new analysis because the hierarchical groups overlap, unlike the corresponding flat multiple-kernel-learning results.
Reducing between-group correlation can support correct hull selection, while slowly increasing depth ratios permits consistent estimation of hull depth and interaction complexity.

5 Simulations

Experiments evaluate HKL on synthetic regression problems and UCI regression and classification datasets, showing strong regression performance but weaker results on some nonsparse classification problems.

Synthetic examples: Synthetic experiments compare HKL with alternative methods using the same polynomial kernel and decomposition on sparse fourth-order polynomial regression data.The experiments use 1024 samples and 22–27 variables generated from a random covariance matrix.
UCI datasets: HKL is compared on UCI regression datasets against Hilbertian regularization, greedy selection, lasso-α, and multiple kernel learning baselines.Polynomial degree-4 and Gaussian-RBF kernels are decomposed into nine kernels per dimension.
UCI datasets: HKL outperforms other methods particularly on bank-32nm, bank-32nh, pumadyn-32nm, and pumadyn-32nh, which target nonlinear regression.The experiments also demonstrate efficient exploration of DAGs with very large vertex counts.
UCI datasets: For binary classification, HKL performs better on some datasets such as spambase but slightly worse when the generating problem is known to be nonsparse, including ringnorm and twonorm.
UCI datasets: Table 1 reports mean squared errors multiplied by 100 and normalized so the total variance to explain equals 100.
UCI datasets: Table 2 reports binary-classification error rates multiplied by 100.

6 Conclusion

The conclusion presents HKL as a polynomial-time approach for exploring structured feature spaces with sparsity-inducing penalties and applies it to nonlinear variable selection.

HKL performs hierarchical multiple kernel learning in polynomial time in the number of selected kernels.
The framework applies to many positive definite kernels and is demonstrated with polynomial and Gaussian kernels for nonlinear variable selection.
The paper reports that ℓ1-type penalties can be advantageous inside the feature space and identifies further kernel applications under investigation.

A Optimization results

The optimization analysis derives relationships between the hierarchical weighting variables used in the associated optimization problems.

The section establishes the relationships between η and ζ as part of the optimization analysis.

A.1 Set of weights for trees

For tree-structured DAGs, the weight constraints reduce to nonnegative vertex weights ordered from each parent to its child; the resulting feasible set is convex. The paper conjectures nonconvexity for non-tree DAGs.

In a tree DAG, one root has no parent and every other vertex has exactly one parent.
Leaf weights satisfy ζv = ηv, while non-root weights obey ζπ(v) ⩾ ζv.
The constraint η ⩾ 0 is equivalent to ζ ⩾ 0 under the tree representation.
For DAGs that are not trees, the paper conjectures that the set Z is not convex.

A.2 Fenchel conjugates

The appendix uses Fenchel conjugates to formulate optimality and duality for general convex losses. It gives logistic-regression and support-vector-machine examples and derives dual optimization relationships for kernel learning.

Fenchel conjugates are introduced to derive optimality conditions for all losses.
The conjugate ψi is convex, and continuity of ϕi permits representing ϕi as the Fenchel conjugate of ψi.
Logistic regression uses ϕi(a) = log(1 + exp(−yiai)) with yi ∈ {−1, 1} and a specified piecewise ψi.
Support vector machine classification uses hinge loss ϕi(a) = max(0, 1 − yia) with a specified piecewise ψi.
The appendix recalls ℓ2-norm kernel-learning duality and derives a dual problem whose optimal β can be recovered from an optimal α.
A lemma establishes that each component ζw(η) is concave in η, supporting the subsequent dual formulation.

A.4 Duality gaps

The appendix establishes convex–concave dual formulations and uses them to derive duality-gap bounds and optimality conditions for truncated hierarchical kernel problems. It also states assumptions and norm bounds for sparsity-consistency analysis.

A.4 Duality gaps: The variational objective is convex in η and concave in α, and standard feasibility arguments establish no duality gap.
A.4 Duality gaps: The resulting upper bound yields Proposition 1 and an upper bound on the duality gap.
Optimality conditions: For a truncated problem, the hull J of active variables is used to derive necessary and sufficient conditions for optimality in the full problem.
Optimality conditions: Necessary conditions relax the dual constraints on κ, while sufficient conditions can use any candidate, including the relaxed solution.
Optimality conditions: Lower-bounding sums by maxima produces necessary conditions, whereas reusing the obtained κ yields sufficient-condition upper bounds.
Optimality conditions: Directional-derivative conditions characterize optimality for β relative to the hull of active variables.
Consistency: Under finite-dimensional features, square loss, invertible full covariance, and λn tending to zero faster than n−1/2, the estimator converges in probability.
Consistency: Consistency depends on whether the first-order expansion has the correct sparsity pattern, with inactive directions controlled through a dual-norm condition and bounds.