Gaussian and Wishart Hyperkernels

Risi Kondor, Tony JebaraNeurIPS 2006 · OpenReview

In kernel-based machine learning—such as Support Vector Machines (SVMs) or Gaussian Processes—the choice of the kernel function is paramount. The kernel defines the "geometry" of the data by determining how similarity between two points is measured. While practitioners often default to the standard Gaussian RBF kernel, real-world data is frequently heterogeneous, noisy, or anisotropic (exhibiting different properties in different directions).

The paper "Gaussian and Wishart Hyperkernels" by Risi Kondor and Tony Jebara presents a principled approach to move beyond picking a fixed kernel. Instead, they propose learning the optimal kernel directly from the data using hyperkernels. Unlike previous abstract frameworks, the authors introduce two new families of hyperkernels—Gaussian and Wishart—that offer closed-form solutions and interpretable regularization, significantly outperforming standard SVMs in complex tasks.

The Convolution Hyperkernel Framework

Building on the "Hyper-Representer Theorem," which posits that the optimal kernel for a task can be expressed as a weighted sum of hyperkernel evaluations over pairs of training points, the authors introduce the Convolution Hyperkernel framework. They frame similarity as a diffusion process: two points are similar if they are both "close" to the same intermediate points. Hyperkernels allow the model to weight these intermediate points differently across the space.

Within this framework, they derive two specific, computable hyperkernels:

  1. The Gaussian Hyperkernel: By setting the internal components of the hyperkernel to Gaussian functions, the authors derive a closed-form expression. This acts as a "localized Gaussian," allowing the model to learn a highly flexible kernel that places different Gaussian "intensities" on different regions of the input space based on where the training data is most informative. It includes a regularization scheme that mirrors the familiar RBF kernel, aiding interpretability.
  2. The Wishart Hyperkernel: To handle anisotropic data where scaling and rotation matter, the authors utilize the Inverse Wishart distribution (a probability distribution over covariance matrices). By treating the covariance matrix as a latent variable, the model learns not just how much points are similar, but in which direction that similarity is strongest.

Learning the kernel involves solving a quadratic programming problem. The authors explore both "conic" hyperkernels (which guarantee a valid, positive-definite kernel) and "linear" hyperkernels (which are faster but less theoretically strict).

Key Results and Empirical Performance

The authors evaluated their methods on two primary benchmarks, demonstrating significant improvements over standard baselines.

Superior Separation on NIST Digits

The first test involved a subset of '3's and '8's from the NIST Handwritten Digits dataset, randomly rotated by ±45 degrees to increase the difficulty of the metric learning task.

Clustering of rotated 3s and 8s using hyperkernels vs standard kernels

The hyperkernel space achieved an Area Under the Curve (AUC) of 0.7341, compared to just 0.5575 in the original input space. Visualizations of the learned space showed that the hyperkernel successfully clustered the digits by class, whereas a fixed RBF kernel left them totally intermixed.

Face Recognition and Robustness

The second benchmark used the Olivetti Faces dataset (400 images of 40 individuals in various poses) to test relational learning across different facial orientations.

AUC performance comparing Conic HyperKernel, Linear HyperKernel, and standard SVM

In this task, the Conic Hyperkernel achieved an AUC of nearly 0.90 with only 20 training examples. In stark contrast, a standard SVM baseline struggled to reach an AUC of 0.75. Furthermore, the "conic" version of the hyperkernel consistently outperformed the "linear" version across various parameter settings, proving that maintaining the mathematical property of positive definiteness is crucial for robust performance.

Limitations and Future Work

The primary limitation of this approach is computational complexity. While standard kernel methods typically scale at $O(m^3)$ (where $m$ is the number of data points), hyperkernel learning scales at $O(m^6)$. This makes the out-of-the-box algorithm prohibitively slow for large-scale datasets.

To address this, future work will need to focus on developing more efficient optimization routines to handle larger datasets. Additionally, the authors suggest applying these hyperkernels to online learning settings—where the kernel can be updated dynamically as new data arrives—and exploring their use for automated feature selection and dimensionality reduction via Kernel PCA.

Summary updated

Abstract

We propose a new method for constructing hyperkenels and define two promising special cases that can be computed in closed form. These we call the Gaussian and Wishart hyperkernels. The former is especially attractive in that it has an interpretable regularization scheme reminiscent of that of the Gaussian RBF kernel. We discuss how kernel learning can be used not just for improving the performance of classification and regression methods, but also as a stand-alone algorithm for dimensionality reduction and relational or metric learning.
BibTeX
@inproceedings{kondor2006gaussian,
  author = {Risi Kondor and Tony Jebara},
  title = {{Gaussian and Wishart Hyperkernels}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=SJZK0PbdWr},
}
Figure