Learning Non-Linear Combinations of Kernels

Corinna Cortes, Mehryar Mohri, Afshin RostamizadehNeurIPS 2009 · OpenReview

TL;DR

This paper moves beyond the standard practice of learning simple linear combinations of kernels by introducing a framework for learning polynomial combinations of base kernels. By reducing a complex minimax optimization problem to a simpler minimization task and proving that the optimal solution always lies on the boundary of the search space, the authors provide an efficient, projection-based gradient descent algorithm that consistently outperforms linear baselines in regression tasks.

What Problem Does This Paper Address?

Kernel-based algorithms (like Support Vector Machines or Kernel Ridge Regression) rely heavily on the choice of a "kernel function," which defines the similarity between data points. Since picking the "perfect" kernel is difficult, researchers developed Multiple Kernel Learning (MKL), where the algorithm learns the best combination of several base kernels.

However, most MKL research has focused on linear combinations. The frustrating reality is that these learned linear combinations often fail to perform better than a simple uniform average of kernels. The authors argue that linear combinations are too restrictive. They tackle the challenge of learning non-linear (polynomial) combinations, which are more expressive but significantly harder to optimize because they result in non-convex objective functions.

Methods

The authors focus on Kernel Ridge Regression (KRR). Their approach involves several key steps:

  1. Defining the Kernel Family: Instead of a simple sum ($\sum \mu_i K_i$), they define a polynomial kernel of degree $d$. To keep the number of parameters manageable, they use a specific form where the coefficients are products of a weight vector $\mu$, reducing the parameter count from $O(p^d)$ to just $p$ (the number of base kernels).
  2. Optimization Simplification: The standard formulation is a "minimax" problem (minimizing over kernel weights while maximizing over regression parameters). The authors show this can be reduced to a direct minimization of a single objective function: $F(\mu) = y^\top (K_\mu + \lambda I)^{-1} y$.
  3. The Algorithm: They propose a Projection-based Gradient Descent Algorithm. Even though the objective function is not convex everywhere (it has concave regions near the origin), they prove that the global minimum must lie on the boundary of the feasible set.
Projection-based Gradient Descent Algorithm
  1. Theoretical Guarantees: They provide necessary and sufficient conditions for the algorithm to reach a global optimum and derive the explicit gradient using Hadamard (pointwise) products of matrices.

Datasets

The authors evaluated their "Non-linear Kernel Ridge Regression" (NKRR) on three types of data:

  • UCI Repository: Standard benchmarks including Parkinsons, Ionosphere (Iono), Sonar, and Breast Cancer.
  • Sentiment Analysis: A text-based dataset of Amazon user reviews for Electronics and Kitchen products, using word n-grams as features.
  • Delve Repository: The kin-8nm dataset, used specifically to test higher-order polynomials (up to degree 4).

Key Insights and Ideas

  • The Boundary is Key: One of the most important theoretical findings is that the optimal kernel weights $\mu$ always lie on the boundary of the constraint set. This simplifies the search space significantly for the gradient descent algorithm.
  • Expressivity vs. Overfitting: While non-linear combinations are more complex, the authors found that learned quadratic combinations are actually better regularized than a standard "flat" quadratic kernel. This allows the model to perform well even when the number of features is much larger than the number of data points.
  • Vanishing Gradients at the Origin: The objective function is concave near $\mu=0$. This explains why starting the optimization away from the origin and using projection is vital for success.

Key Results

  • UCI Performance: On datasets like Iono and Sonar, the quadratic combinations achieved lower Root Mean Squared Error (RMSE) than linear baselines. For example, on Iono, the quadratic $\ell_2$ approach reached an RMSE of 0.60 compared to 0.82 for the linear base.
  • Text Analysis: In sentiment analysis, the learned quadratic kernels significantly improved performance over the baseline as the number of bigrams (and thus kernels) increased. The $\ell_2$ regularization approach consistently yielded the lowest RMSE.
RMSE vs. Number of Bigrams for Sentiment Analysis
  • Higher-Order Gains: On the kin-8nm dataset, increasing the polynomial degree to 4 provided a "clear performance improvement," especially when training data was relatively scarce (subsampling factors of 10-50).
  • Efficiency: The algorithm is fast, typically converging in fewer than 25–30 iterations, with each iteration taking a fraction of a second on standard hardware.

Limitations and Future Work

  • Non-Convexity: While the authors provide conditions for convergence, the objective function is generally non-convex. This means the choice of the initial $\mu$ and the regularization parameter $\Lambda$ remains sensitive.
  • Regression Focus: This specific analysis and the resulting simplification of the minimax problem are tailored to regression. Extending this theoretical "global solution on the boundary" proof to classification (SVMs) is suggested as a separate challenge.
  • Complexity of Higher Degrees: While degree 4 worked well for kin-8nm, the paper notes that for many standard datasets, the benefits of going beyond quadratic (degree 2) combinations were marginal or non-existent, suggesting a "sweet spot" for non-linearity.

Summary updated

Abstract

This paper studies the general problem of learning kernels based on a polynomial combination of base kernels. It analyzes this problem in the case of regression and the kernel ridge regression algorithm. It examines the corresponding learning kernel optimization problem, shows how that minimax problem can be reduced to a simpler minimization problem, and proves that the global solution of this problem always lies on the boundary. We give a projection-based gradient descent algorithm for solving the optimization problem, shown empirically to converge in few iterations. Finally, we report the results of extensive experiments with this algorithm using several publicly available datasets demonstrating the effectiveness of our technique.
BibTeX
@inproceedings{cortes2009learning,
  author = {Corinna Cortes and Mehryar Mohri and Afshin Rostamizadeh},
  title = {{Learning Non-Linear Combinations of Kernels}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=HyZe9IbOZB},
}
Figure