Fast Multiple Kernel Learning With Multiplicative Weight Updates

John Moeller, Parasaran Raman, Avishek Saha, Suresh VenkatasubramanianarXiv 2012 · OpenReview

TL;DR

This paper introduces a novel geometric formulation for Multiple Kernel Learning (MKL), reframing it as finding a kernel that maximizes the minimum distance between two convex polytopes. This leads to a significantly faster and more scalable optimization algorithm that outperforms existing methods on various datasets.

What Problem Does This Paper Address?

Multiple Kernel Learning (MKL) aims to combine multiple kernel functions to improve the performance of machine learning models, particularly Support Vector Machines (SVMs). The challenge lies in efficiently learning the optimal combination of these kernels. Traditional MKL methods often rely on computationally expensive semidefinite programming (SDP) solvers or iterative optimization techniques that are slow and require substantial memory, limiting their scalability to large datasets. This paper addresses the need for a faster, more memory-efficient, and scalable MKL algorithm.

Methods

The core contribution of this paper is a new geometric interpretation of the MKL problem. Instead of directly optimizing kernel weights within an SVM framework, the authors reframe the problem as finding a kernel that maximizes the minimum distance between two convex polytopes. This geometric insight allows them to reduce the MKL problem to a Quadratically Constrained Quadratic Program (QCQP).

They then leverage a variant of the Matrix Multiplicative Weight Update (MMWU) algorithm, originally designed for general SDPs. However, by exploiting the specific structure of the MKL QCQP, they develop a simplified, alternating optimization approach. This approach involves:

  • Forward Step: Identifying "violating" support vectors with respect to the current kernel estimate.
  • Backward Step: Reweighting the kernels based on these support vectors using an efficiently computable closed-form matrix exponentiation.

This method avoids explicit calls to commercial SDP solvers or SVM libraries and boasts provable convergence with a fixed number of iterations and a significantly reduced memory footprint (O(mn)).

Datasets

The paper evaluates their proposed MWUMKL algorithm on eleven UCI datasets. These datasets are categorized by size:

  • Small: Iono, Breast Cancer, Pima, Sonar, Heart, Vote, WDBC, WPBC.
  • Medium: Mushroom.
  • Large: Adult, CodRna, Web.

For experiments, they use a base kernel family of 3 polynomial kernels (degree 1-3) and 9 Gaussian kernels.

Key Insights and Ideas

  • Geometric Reinterpretation: Viewing MKL as maximizing the minimum distance between convex polytopes provides a powerful new perspective that simplifies the optimization problem.
  • MMWU Specialization: Adapting the general MMWU algorithm to the specific structure of MKL QCQPs leads to a much simpler and faster alternating optimization routine.
  • Efficient Updates: The key to the algorithm's speed lies in the sparse updates to support vectors and the closed-form computation of kernel reweighting, avoiding expensive matrix operations.
  • Scalability Breakthrough: The algorithm achieves a memory footprint of O(mn), a significant improvement over previous methods that struggled with large datasets and many kernels.

Key Results

  • Speed: MWUMKL is significantly faster than existing legacy MKL implementations and comparable to or faster than LibLinear+ with Nyström approximations, especially on larger datasets.
  • Accuracy: The algorithm achieves competitive or superior test accuracies compared to UNIFORM (uniform kernel weighting) and LibLinear+ on small datasets.
  • Scalability: The method demonstrates excellent scalability with both the number of data points and the number of kernels, outperforming UNIFORM on large datasets where UNIFORM fails due to memory constraints.
  • Memory Efficiency: The O(mn) memory footprint allows the algorithm to handle scenarios with millions of kernels or large numbers of data points, a feat not possible with many prior methods.

Limitations and Future Work

  • Single Machine Focus: The current work focuses on optimizing MKL on a single machine.
  • Future Work: The authors propose adding parallelization techniques to further improve scalability for very large datasets and numerous kernels. They suggest that the MWUMKL algorithm lends itself well to the Bulk Synchronous Parallel (BSP) framework, allowing for "sharding" by either kernels or data points.

Summary updated

Abstract

We present a geometric formulation of the Multiple Kernel Learning (MKL) problem. To do so, we reinterpret the problem of learning kernel weights as searching for a kernel that maximizes the minimum (kernel) distance between two convex polytopes. This interpretation combined with novel structural insights from our geometric formulation allows us to reduce the MKL problem to a simple optimization routine that yields provable convergence as well as quality guarantees. As a result our method scales efficiently to much larger data sets than most prior methods can handle. Empirical evaluation on eleven datasets shows that we are significantly faster and even compare favorably with a uniform unweighted combination of kernels.
BibTeX
@misc{moeller2012fast,
  author = {John Moeller and Parasaran Raman and Avishek Saha and Suresh Venkatasubramanian},
  title = {{Fast Multiple Kernel Learning With Multiplicative Weight Updates}},
  year = {2012},
  eprint = {1206.5580},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1206.5580},
}
Figure