Multiple Kernel Learning Algorithms

Authors: Mehmet Gönen, Ethem Alpaydın
Published: 2011
Journal: Journal of Machine Learning Research
Link: PDF

Summary

This comprehensive survey provides a unified view of multiple kernel learning (MKL) algorithms. It categorizes existing methods, discusses their properties, and provides practical guidance for choosing among them.

Key Contributions

1. Unified Framework

The paper presents MKL as learning a combination function: $K = f_\eta(K_1, K_2, \ldots, K_M)$

where $\eta$ are combination parameters and different choices of $f$ give different MKL variants.

2. Taxonomy of MKL Methods

By combination function:

• Linear: $K = \sum_m \mu_m K_m$
• Non-linear: $K = g(\sum_m \mu_m K_m)$
• Data-dependent: $K(x,x') = \sum_m \mu_m(x,x') K_m(x,x')$

By learning method:

• Fixed rules (heuristic)
• Optimization-based
• Bayesian approaches

3. Learning Approaches

Simultaneous: Learn kernel weights and classifier parameters together

Two-stage:

1. Learn kernel alignment/combination
2. Train classifier with combined kernel

Boosting-based: Add kernels sequentially

Linear MKL Methods

Formulation

$K = \sum_{m=1}^M \mu_m K_m, \quad \mu_m \geq 0$

with various constraints:

• $\sum_m \mu_m = 1$ (simplex)
• $\|\mu\|_p \leq 1$ ($\ell_p$ ball)
• $\mu_m \in \{0, 1\}$ (selection)

SVM-based MKL

Primal: $\min_{w,b,\xi,\mu} \frac{1}{2}\sum_m \frac{\|w_m\|^2}{\mu_m} + C\sum_i \xi_i$ $\text{s.t.} \quad y_i(\sum_m \langle w_m, \phi_m(x_i)\rangle + b) \geq 1 - \xi_i$

Key algorithms:

1. SimpleMKL (gradient descent)
2. SILP (semi-infinite linear programming)
3. Level method
4. SMO-MKL

Alignment-based MKL

Maximize kernel-target alignment: $\max_\mu \frac{\langle \sum_m \mu_m K_m, yy^T \rangle}{\|\sum_m \mu_m K_m\|_F}$

Efficient closed-form solution exists.

Non-linear MKL

Polynomial Combinations

$K = \left(\sum_m \mu_m K_m\right)^d$

More expressive but loses convexity for $d > 1$.

Product Kernels

$K = \prod_m K_m^{\mu_m}$

Useful when features are multiplicatively related.

Localized MKL

Gating Functions

$K(x,x') = \sum_m \eta_m(x) \eta_m(x') K_m(x,x')$

where $\eta_m(x)$ are gating functions assigning samples to kernels.

Implementation

Learn gates $\eta_m$ via:

• Clustering
• Neural networks
• Kernel-based gates

Bayesian MKL

Generative Model

$\mu \sim \text{Dir}(\alpha_0)$ $y | X, \mu \sim \mathcal{N}(0, \sum_m \mu_m K_m + \sigma^2 I)$

Inference

Use variational inference or MCMC to estimate: $p(\mu | X, y) \propto p(y | X, \mu) p(\mu)$

Algorithm Comparison

Algorithm	Complexity	Sparsity	Scalability
SimpleMKL	$O(M \cdot \text{SVM})$	High	Good
SILP	$O(M^2 \cdot \text{LP})$	High	Moderate
LevelMKL	$O(M \cdot \text{QP})$	High	Good
$\ell_p$-MKL	$O(M \cdot \text{SVM})$	Variable	Good
Bayesian MKL	$O(M \cdot n^3)$	Low	Limited

Practical Guidelines

When to use MKL?

1. Multiple feature representations available
2. Unknown optimal kernel for the problem
3. Interpretability of feature importance needed
4. Heterogeneous data sources

Choosing MKL variant

• For sparsity: Use $\ell_1$-MKL
• For smooth weights: Use $\ell_2$-MKL
• For locality: Use gated MKL
• For uncertainty: Use Bayesian MKL

Base Kernel Selection

• Include kernels at multiple scales
• Use domain knowledge for kernel types
• Start with canonical kernels (RBF, polynomial)

Impact on Machine Learning

This survey:

1. Unified view: Organized diverse MKL literature
2. Practical guidance: Helped practitioners choose methods
3. Research directions: Identified open problems
4. Benchmarking: Established comparison framework

Citation

@article{gonen2011multiple,
  title={Multiple kernel learning algorithms},
  author={G{\"o}nen, Mehmet and Alpayd{\i}n, Ethem},
  journal={Journal of Machine Learning Research},
  volume={12},
  pages={2211--2268},
  year={2011}
}

Further Reading

• Cortes, C. (2009). Can learning kernels help performance?
• Kloft, M., et al. (2011). $\ell_p$-norm multiple kernel learning
• Wilson, A., et al. (2016). Deep kernel learning