Learning with Indefinite Similarity Functions

This direction is merged into another direction: positive semi-definite constraint. Its last version stays readable and citable here.

Version 1 of 128 papers36 conceptsfrozen 2026-10-04

For decades, the "kernel trick" has been the cornerstone of similarity-based learning. It allows algorithms like Support Vector Machines (SVMs) to operate in high-dimensional feature spaces without ever explicitly computing the coordinates of the data. However, this power comes with a strict mathematical tax: the kernel must be Positive Semi-Definite (PSD).

A PSD kernel is essentially a generalized dot product. It implies that your similarity measure corresponds to a valid inner product in some hidden Hilbert space. While mathematically elegant, this requirement is often a straightjacket for practitioners. Many intuitive ways to measure similarity—such as the edit distance between DNA sequences, structural overlaps in graphs, or even the attention mechanisms in modern transformers—do not satisfy the PSD condition.

Recent research has moved to liberate machine learning from the "PSD shackles," providing both the theoretical justification and the algorithmic tools to learn with indefinite similarity functions.

The Problem with the Mercer Constraint

In traditional kernel methods, the PSD requirement (often called the Mercer condition) ensures that the optimization problem is convex and that a corresponding feature space exists. As Michael E. Tipping noted in his work on The Relevance Vector Machine, these constraints limit flexibility, preventing the use of arbitrary similarity measures that might better capture domain-specific nuances.

When a practitioner encounters a non-PSD similarity measure, the standard "fix" is to force it into a PSD shape—for example, by ignoring negative eigenvalues or shifting the diagonal of the kernel matrix. But as Maria Florina Balcan and Nathan Srebro argue in A theory of learning with similarity functions, this modification often destroys the very information that made the similarity measure useful in the first place.

Redefining a "Good" Similarity Function

The breakthrough in this field came from shifting the focus away from Hilbert spaces and toward a more intuitive definition of similarity. Balcan and Srebro proposed that for a similarity function to be "good" for learning, it doesn't need to be a dot product. It simply needs to satisfy a much more basic property: on average, an object should be more similar to points in its own class than to points in the opposite class.

In their seminal paper, On a theory of learning with similarity functions, they proved that any similarity function meeting this "goodness" criterion can be used to map data into a low-dimensional space where a linear classifier can achieve high accuracy. This mapping doesn't require symmetry or positive definiteness; it only requires that the similarity function captures the underlying structure of the categories.

Geometry Beyond Hilbert Spaces: Krein Spaces

If we move away from Hilbert spaces, where do our kernels live? The answer often lies in Krein spaces—mathematical spaces that possess an indefinite inner product. Unlike Hilbert spaces, where the "distance" of a vector to itself is always positive, Krein spaces allow for negative "squared lengths."

Stefanos Zafeiriou pioneered the use of these spaces for dimensionality reduction. In Subspace Learning in Krein Spaces, he introduced Indefinite Kernel PCA (IKPCA). This framework allows algorithms to natively handle indefinite kernels by treating the positive and negative components of the kernel separately, rather than discarding the negative ones. This approach has proven particularly effective in fields like face recognition, where non-metric similarities are common.

Similarly, Bernhard Schölkopf expanded the geometric bridge in The Kernel Trick for Distances, showing how "conditionally positive definite" kernels allow us to work with distances directly, further relaxing the requirements for kernel-based learning.

Practical Algorithms for Indefinite Kernels

The shift toward indefinite kernels isn't just theoretical; it has led to several robust algorithms:

  1. Sparsity and Pursuit: Pascal Vincent and Yoshua Bengio developed Kernel Matching Pursuit, a greedy algorithm that builds a model by selecting the most informative basis functions one by one. Because it doesn't rely on the global optimization of a convex quadratic program, it can use any similarity function, PSD or not.
  2. Regularization: To prevent overfitting when using highly complex or indefinite kernels, Corinna Cortes and colleagues proposed Voted Kernel Regularization. This method uses Rademacher complexity to penalize model complexity, allowing for the use of non-PDS metrics like string edit distance while maintaining generalization guarantees.
  3. Two-Stage Learning: Jun Wang and others proposed Two-Stage Metric Learning, which first maps data points into a probability space based on their similarity to "anchor points" and then learns a distance metric. This bypasses the PSD requirement entirely by transforming the problem into a density estimation task.

Why It Works: The Intuition of Landmarks

The most intuitive way to understand why indefinite similarity functions work is the landmark perspective.

Imagine you want to classify points, but you only have a non-PSD similarity function $S(x, y)$. Instead of trying to find a high-dimensional feature map $\phi(x)$, you pick a set of "landmark" points from your training data. For any new point $x$, you create a feature vector where each coordinate is the similarity of $x$ to one of those landmarks: $f(x) = [S(x, L_1), S(x, L_2), \dots, S(x, L_k)]$.

As Balcan and Srebro demonstrated, if your similarity function is "good," these landmark-based features will naturally cluster classes together. You have effectively turned a complex, non-linear similarity problem into a simple linear classification problem in "similarity space."

This realization—that similarity is a sufficient feature in itself—is what allows modern machine learning to move beyond the rigid geometry of Hilbert spaces and embrace the messy, non-metric similarities of the real world. As Fanghui Liu notes in Generalization Properties of hyper-RKHS, this flexibility is increasingly vital for understanding modern architectures like transformers, where dot-product attention often behaves like an indefinite kernel.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_learning_with_indefinite_similarity_func_cdb56477,
  title = {Learning with Indefinite Similarity Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-with-indefinite-similarity-functions/rdr_cdb56477a54e4fa08be41f8ca62c3dca},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_learning_with_indefinite_similarity_func_cdb56477_v1,
  title = {Learning with Indefinite Similarity Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learning-with-indefinite-similarity-functions/rdr_cdb56477a54e4fa08be41f8ca62c3dca/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}