A Unifying View of Multiple Kernel Learning

Marius Kloft, Ulrich Rückert, Peter L. Bartlett

Abstract

This paper introduces a unified optimization framework for Multiple Kernel Learning (MKL) that integrates various regularization strategies—including $\ell_1$, $\ell_p$ block norms, and elastic net—into a single generalized criterion. By deriving a modular dual representation and utilizing Moreau-Yosida regularization, the authors enable flexible, smooth optimization and provide theoretical generalization bounds. Empirical evaluations demonstrate that non-sparse MKL configurations, such as $\ell_\infty$-norm MKL, frequently outperform traditional sparse methods in real-world tasks.

Introduction

In kernel-based machine learning, such as Support Vector Machines (SVMs), the selection of an appropriate kernel is a critical yet challenging task. Multiple Kernel Learning (MKL) addresses this by learning an optimal combination of base kernels from a predefined set. However, the MKL landscape has historically been fragmented, with various researchers proposing disparate regularization strategies—such as $\ell_1$ norms for sparsity, block norms for grouped contributions, and elastic net penalties for a balance between the two.

Because these formulations were mathematically distinct, they necessitated highly specific optimization algorithms, making it difficult to compare methods or develop general-purpose solvers. This paper tackles this fragmentation by proposing a single, unifying mathematical framework that encompasses these diverse MKL variants, simplifying both theoretical analysis and practical implementation.

A Generalized MKL Framework

The authors formulate a generalized primal MKL optimization problem centered on a combination of an $\ell_{2,p}$ block norm and an $\ell_2$ norm. By adjusting two primary parameters—the norm $p$ and a mixing weight $\mu$—this single objective function can recover standard regularization schemes:

  • Block-norm regularization (e.g., $\ell_p$)
  • Kernel mixture regularization
  • Elastic net regularization

Optimization via Dual Representation

To solve this generalized problem efficiently, the authors transition to the dual space using Fenchel-Legendre conjugates and Inf-Convolution. This modular dual derivation mathematically separates the loss function from the regularization term, providing several advantages:

  1. Smoothing via Moreau-Yosida Regularization: The Inf-Convolution acts as a Moreau-Yosida approximate, which "smoothens" the optimization landscape. This allows even non-differentiable initial problems to be solved using standard, efficient quasi-Newton techniques like L-BFGS-B.
  2. Algorithmic Flexibility: Practitioners can swap loss functions or regularizers without redesigning the optimization algorithm from scratch.

Theoretical Generalization Bounds

The authors employ Rademacher complexity to derive uniform convergence bounds for this generalized class of classifiers. These bounds are significant because they smoothly interpolate between known bounds for specific cases (such as $\ell_1$ and $\ell_2$ regularization). Specifically, the theory proves that as the sparsity parameter in an elastic net is decreased, the model's capacity increases toward the $\ell_2$ setting, providing a rigorous mathematical foundation for the intuition behind these regularizers.

Empirical Evaluation

The framework was evaluated across three distinct scenarios to test the impact of sparsity and regularization on performance.

Datasets

  1. Artificial Data: Designed to control the sparsity of the underlying signal, ranging from a single informative kernel to information spread uniformly across all kernels.
  2. Gene Start Recognition: A bioinformatics dataset focused on detecting transcription start sites in genomic DNA using five sequence-based kernels.
  3. Network Intrusion Detection: A dataset of HTTP traffic containing normal and malicious entries, utilizing 10 spectrum kernels representing 1-gram to 10-gram features.

Key Results

  • The Sparsity Myth: While $\ell_1$ MKL performed well in highly sparse artificial scenarios, it was consistently outperformed in real-world tasks. In the bioinformatics dataset, the non-sparse $\ell_\infty$-block-norm MKL achieved the highest predictive accuracy (AUC 87.67%), significantly better than the classical sparse $\ell_1$ MKL (84.83%).
  • Robustness of Intermediate Norms: In artificial tests, the $\ell_{4/3}$ norm proved the most robust across varying noise levels, maintaining an error rate below 0.1%.
  • High-Precision Performance: In network intrusion detection, the $\ell_\infty$ configuration again dominated, particularly in the critical low false-positive regime (AUC 99.68%).

Conclusion

This work demonstrates that unification in MKL not only simplifies the algorithmic landscape but also reveals critical insights into model performance. The empirical findings challenge the prevailing bias toward sparse models, suggesting that when data relies on multiple informative features, non-sparse norms like $\ell_\infty$ are more robust. Future research may extend this framework to other loss functions, such as logistic loss, to determine if the dominance of non-sparse MKL holds across broader classification and regression contexts.

Summary updated

BibTeX
@inproceedings{kloft2010unifying,
  author = {Marius Kloft and Ulrich Rückert and Peter L. Bartlett},
  title = {{A Unifying View of Multiple Kernel Learning}},
  booktitle = {ECML/PKDD},
  year = {2010},
  doi = {10.1007/978-3-642-15883-4\_5},
}
Figure