This paper presents a significant step forward in making Bayesian Multiple Kernel Learning (MKL) practical for real-world applications. By introducing BEMKL (Bayesian Efficient Multiple Kernel Learning), the authors replace slow, sampling-based Bayesian methods with a fast, deterministic variational approximation. This breakthrough allows researchers to combine hundreds or thousands of kernels in under a minute, achieving state-of-the-art accuracy on bioinformatics and image recognition tasks.
The Challenge of Multiple Kernel Learning
Kernel-based algorithms, such as Support Vector Machines (SVMs), rely on a "kernel function" to measure the similarity between data points. Because choosing the right kernel is often the most difficult part of the modeling process, Multiple Kernel Learning (MKL) was developed to automatically learn a weighted combination of many different kernels.
While discriminative MKL (based on SVMs) is efficient, it lacks the benefits of a probabilistic framework, such as the natural handling of uncertainty and principled hyperparameter tuning. Existing Bayesian MKL methods offered these benefits but were notoriously slow. They typically relied on Dirichlet priors to constrain kernel weights, which are not "conjugate" to the rest of the model. This lack of conjugacy forced researchers to use computationally expensive techniques like Markov Chain Monte Carlo (MCMC) or importance sampling, making it nearly impossible to scale to datasets with a large number of kernels.
BEMKL: A Fully Conjugate Probabilistic Model
To overcome these computational bottlenecks, the authors propose a "fully conjugate" probabilistic model.
The framework is built on four key innovations:
- Normal Weights instead of Simplex Constraints: Unlike previous models that forced kernel weights to lie on a simplex (summing to one and strictly non-negative), BEMKL assumes kernel weights are normally distributed. This mathematical "relaxation" allows for significantly faster inference.
- Intermediate Latent Variables: The model introduces a latent variable ($G$) that represents the output of each individual kernel. This decoupling makes the underlying mathematics cleaner and the parameter updates more efficient.
- Variational Bayes (VB) Inference: Instead of simulating the model via sampling (MCMC), the authors derive a deterministic approximation. This shifts the learning process into an iterative optimization problem where parameters are updated until they converge.
- Flexible Sparsity: By adjusting Gamma hyper-parameters, the model can produce either "sparse" combinations (using only a few kernels, similar to an $\ell_1$-norm) or "non-sparse" combinations (using many kernels, similar to an $\ell_2$-norm).
Key Insights
- The Power of Conjugacy: By choosing priors that "play nice" with the likelihood (Normal and Gamma distributions), the authors successfully bypassed the "sampling trap" that crippled previous Bayesian MKL models.
- Computational Bottlenecks: The algorithm's complexity is dominated by matrix inversions, scaling at either $O(N^3)$ (where $N$ is the number of data points) or $O(P^3)$ (where $P$ is the number of kernels). This flexibility means users can choose the most efficient update path based on whether their dataset has more instances or more features.
- Information Sharing in Multiclass: In multiclass problems, forcing different classifiers to share the same kernel weights—rather than learning them independently—leads to better generalization. It allows the model to learn a universal similarity measure across all classes.
Empirical Results
The authors evaluated BEMKL across several diverse benchmarks, including 8 standard UCI datasets, a Protein Fold Recognition dataset, and complex image recognition tasks (Oxford Flowers 17/102 and Caltech101).
The results demonstrated significant improvements in both speed and predictive performance:
- Unprecedented Speed: On benchmark datasets with up to 793 kernels (such as the
sonardataset), BEMKL trained in less than 60 seconds on a standard PC. - Image Recognition: BEMKL achieved a standout 68.9% accuracy on the challenging Oxford Flowers102 dataset, nearly doubling the performance of a previous Gaussian Process-based MKL method (40.0%). On Caltech101, BEMKL (73.1%) outperformed the popular discriminative MKL algorithm by Varma & Babu (71.1%).
- Bioinformatics: On the Protein Fold Recognition dataset, BEMKL achieved 71.5% accuracy, significantly outperforming the previous state-of-the-art Bayesian MKL (68.1%).
Limitations and Future Work
While BEMKL is highly efficient for large numbers of kernels, the $O(N^3)$ scaling still poses a memory and computational challenge for "Big Data" scenarios involving hundreds of thousands of instances. The authors suggest that low-density assumptions or other sparse approximations might be necessary for massive scales.
Looking forward, extending this framework to multitask learning—by enforcing similarity between kernel weights across different but related tasks—is a promising direction. Additionally, while this paper focuses heavily on classification, the underlying BEMKL framework is easily adaptable to regression tasks.
Summary updated