Inductive Regularized Learning of Kernel Functions

Prateek Jain, Brian Kulis, Inderjit S. DhillonNeurIPS 2010 · OpenReview

TL;DR

This paper bridges the gap between learning a static kernel matrix for a fixed dataset and learning a generalizable kernel function. The authors propose a unified framework proving that learning a regularized kernel matrix is equivalent to learning a linear transformation in the feature space. This equivalence enables "inductive" learning—the ability to apply a learned kernel to brand-new data points without the need for retraining.

The Out-of-Sample Problem in Kernel Learning

In machine learning, "kernels" allow algorithms to model complex, non-linear relationships by implicitly mapping data into high-dimensional spaces. However, most methods for learning these kernels are transductive: they produce a kernel matrix optimized for a specific set of training points but offer no clear, mathematically sound way to handle a new, unseen test point (often called the "out-of-sample" problem).

Existing inductive methods, such as Multiple Kernel Learning (MKL) or hyperkernels, are frequently either too computationally expensive for large datasets or too restrictive in the types of kernels they can learn. The authors aim to create a flexible, scalable framework that learns a kernel function from side-information (e.g., pairwise constraints like "point A should be closer to B than C") that generalizes naturally to new data.

A Unified Framework for Inductive Kernels

The authors introduce a general regularized framework for learning a kernel matrix $K_W$, built on two key components:

  1. The Equivalence Theorem: The core theoretical contribution is proving that solving a kernel matrix learning problem (minimizing a spectral function $f$ subject to constraints) is mathematically equivalent to learning a Linear Transformation (LT) kernel. Specifically, the learned kernel takes the form $\kappa_W(x, y) = \phi(x)^T W \phi(y)$, where $W$ is a positive semi-definite matrix. This provides a constructive method to apply the learned kernel to new data points.
  2. Parameter Reduction for Scalability: To handle large-scale data, the authors introduce a technique to limit the number of parameters in the optimization. By constraining the underlying transformation matrix to a lower-rank form ($W = \alpha I + \Phi J L J^T \Phi^T$), they reduce the computational complexity from $O(n^2)$ to $O(r^2)$, where $r \ll n$.
  3. Trace-SSIKDR: As a specific application, they propose Trace-norm based Semi-Supervised Inductive Kernel Dimensionality Reduction. By using the trace-norm (a proxy for rank) as a regularizer, the model learns a low-rank transformation that effectively performs dimensionality reduction in the kernel space while respecting semi-supervised constraints.

Key Insights

  • Kernelization as a Special Case: The paper demonstrates that many popular Mahalanobis metric learning algorithms (like ITML and POLA) are actually special cases of their framework. This provides a principled way to "kernelize" these existing algorithms.
  • Induction via Linear Transformation: The critical realization is that one does not need to explicitly construct a high-dimensional $W$ matrix. Because of the equivalence theorem, the learned kernel for new points can be computed using only the original kernel function and a learned coefficient matrix $S$.
  • Trace-norm for Low-Rank Embeddings: While previous kernel dimensionality reduction methods (like Kernel PCA) are often unsupervised, Trace-SSIKDR allows the use of labels or side-information to guide the reduction, ensuring the most important features for the specific task are preserved.

Experimental Results

The framework was evaluated on several diverse benchmarks, including 10 standard datasets from the UCI Machine Learning Repository, the challenging Caltech-101 object recognition dataset, and USPS Digits.

  • Classification Accuracy: On UCI datasets, the proposed regularizers (Frobenius and LogDet) significantly outperformed the baseline Gaussian kernel. For example, on the Wine dataset, accuracy jumped from 0.80 to 0.94.
  • Dimensionality vs. Performance: The Trace-SSIKDR method achieved competitive accuracy while drastically reducing the rank of the kernel. On the Ionosphere dataset, it matched the accuracy of full-rank methods while using a rank of only 19 (compared to the full 337).
Performance on Caltech-101 and USPS digits
  • Caltech-101: The method showed a clear lead in mean recognition accuracy as the number of training examples per class increased, outperforming standard baseline kernels.
  • Visualization: Qualitative results on USPS digits showed that Trace-SSIKDR could separate digit classes in a 2D embedding much more effectively than unsupervised Kernel PCA, even when trained on a very small subset of data (100 digits).

Limitations and Future Directions

  • Heuristics for Parameter Reduction: The efficiency of the large-scale version depends on the choice of a matrix $J$. The authors suggest simple heuristics (like random sampling or clustering), but a more principled way to choose $J$ remains an open question.
  • Computational Overhead: While optimized, the Trace-SSIKDR algorithm still requires computing the top $k$ eigenvectors at each iteration. For extremely high-dimensional or massive datasets, this could still be a bottleneck.
  • Hyperparameter Sensitivity: The performance of the regularizers (like the $\tau$ parameter in trace-norm) requires tuning, which can be sensitive depending on the specific domain.

Summary updated

Abstract

In this paper we consider the fundamental problem of semi-supervised kernel function learning. We propose a general regularized framework for learning a kernel matrix, and then demonstrate an equivalence between our proposed kernel matrix learning framework and a general linear transformation learning problem. Our result shows that the learned kernel matrices parameterize a linear transformation kernel function and can be applied inductively to new data points. Furthermore, our result gives a constructive method for kernelizing most existing Mahalanobis metric learning formulations. To make our results practical for large-scale data, we modify our framework to limit the number of parameters in the optimization process. We also consider the problem of kernelized inductive dimensionality reduction in the semi-supervised setting. We introduce a novel method for this problem by considering a special case of our general kernel learning framework where we select the trace norm function as the regularizer. We empirically demonstrate that our framework learns useful kernel functions, improving the $k$-NN classification accuracy significantly in a variety of domains. Furthermore, our kernelized dimensionality reduction technique significantly reduces the dimensionality of the feature space while achieving competitive classification accuracies.
BibTeX
@inproceedings{jain2010inductive,
  author = {Prateek Jain and Brian Kulis and Inderjit S. Dhillon},
  title = {{Inductive Regularized Learning of Kernel Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=ryEeWd-u-B},
}
Figure