Introduction
In the realm of Support Vector Machines (SVMs), the "kernel" is the critical component that transforms data into a high-dimensional space, making it easier to separate distinct classes with a clear "margin." Because selecting the perfect kernel is difficult, Multiple Kernel Learning (MKL) attempts to automate this by finding the optimal combination of several basis kernels.
However, most traditional MKL methods rely solely on the Large Margin Principle, which harbors a fundamental flaw: the margin is highly sensitive to scaling. If an algorithm simply multiplies a kernel by a large constant, the margin artificially increases. The kernel appears better to the optimizer without actually improving its predictive power. This "scaling problem" leads to two major headaches:
- Convergence Issues: The optimization may struggle to converge because the algorithm assumes "bigger is always better."
- The Initialization Problem: The final learned kernel depends heavily on the arbitrary initial scales of the basis kernels.
To circumvent this, researchers typically impose artificial constraints (like $L_1$ or $L_2$ norms on the coefficients), but selecting the correct constraint often requires guesswork. This paper introduces Radius-based Kernel Learning (RKL), a novel framework that mathematically eliminates these scaling and initialization problems.
The Ruler Analogy and Radius-based Kernel Learning
To fix the scaling problem, the authors propose optimizing a new objective function. Instead of merely maximizing the margin ($\gamma$), RKL optimizes the ratio of the margin to the Radius ($R$) of the Minimum Enclosing Ball (MEB) of the data in the feature space.
Think of the margin as a physical distance. If you change your units of measurement from inches to miles, the numerical value changes, but the actual physical distance remains the same. The Radius ($R$) of the MEB acts as a "ruler" that provides the necessary scale. By measuring the margin relative to the spread of the data, the "distance" is evaluated consistently across entirely different kernel spaces.
Key Technical Innovations
- Invariant Formulation: The authors mathematically prove that their objective function is invariant to the scaling of the kernels. The "goodness" of the kernel is measured purely relative to the data's spread, rendering the choice between $L_1$ and $L_2$ norm constraints largely irrelevant.
- Tri-level Optimization: Calculating this ratio is computationally demanding. It requires solving three nested problems: finding the MEB, solving the SVM dual problem, and optimizing the kernel parameters at the top level.
- Differentiability Proof: By extending Danskin’s Theorem, the researchers prove that this complex, nested objective function is differentiable. This breakthrough allows them to use a standard, efficient gradient projection algorithm to find the optimal kernel.
Experimental Validation and Results
The researchers evaluated RKL on 11 publicly available datasets from the UCI repository and LIBSVM, covering diverse domains from medical diagnostics (Breast Cancer, Liver) to physical data (Ionosphere, Sonar). They utilized a mix of 10 Gaussian kernels and 10 polynomial kernels as the basis for their combinations.
The proposed RKL method ("Ours") was compared against standard SVMs (uniform kernel combination), margin-based MKL, and a previous radius-based method (KL-C). The results highlight several distinct advantages:
- Superior Accuracy: RKL outperformed all other methods on 8 out of 11 datasets under $L_1$ constraints and 10 out of 11 under $L_2$ constraints. On datasets like Splice, Liver, and Musk1, RKL improved accuracy by over 5% compared to standard MKL.
- Robustness to Initialization: Unlike previous methods, RKL's performance remained stable regardless of how the basis kernels were initially scaled, proving it successfully resolves the initialization problem.
- Natural Sparsity: Even without an $L_1$ constraint (which is typically used to force sparsity), RKL naturally selected a small subset of useful kernels (indicated by the "Nk" columns in the results). This suggests that the margin-to-radius ratio acts as a highly effective filter for redundant or noisy kernels.
Limitations and Future Work
While RKL offers a more robust and mathematically sound approach to kernel learning, it does come with trade-offs. Because the RKL objective is not strictly convex in the linear combination case, gradient-based methods only guarantee a local optimum, not necessarily the global best. Additionally, solving a tri-level optimization problem is inherently more computationally intensive than a standard SVM, although the authors mitigate this using "hot starts" to speed up the nested solvers.
Looking forward, while this paper focuses on linear combinations of kernels, the authors suggest that the margin-to-radius framework could be extended to more complex, non-linear kernel learning architectures, potentially unlocking even greater predictive performance.
Summary updated