Locality-Sensitive Hashing (LSH) is a cornerstone of efficient approximate nearest neighbor search. However, traditional LSH families are restricted to metric distances that satisfy the triangle inequality. This paper presents a novel LSH framework for non-metric distances—such as KL divergence and Chamfer distance—by embedding data into an indefinite reproducing kernel Kreĭn space. By preserving the structural information contained in negative eigenvalues, the proposed method significantly improves retrieval accuracy for complex perceptual similarities.
The Challenge of Non-Metric Similarity
Approximate nearest-neighbor (ANN) search is essential for scaling machine learning tasks. While LSH is a popular solution, it typically requires distances to be metrics (e.g., Euclidean or Cosine). In many real-world scenarios, human perceptual similarity is inherently non-metric.
As shown in Figure 1, a centaur may be perceived as similar to both a man and a horse, yet the man and horse are dissimilar. This violation of the triangle inequality makes standard LSH ineffective. Common non-metric measures like Kullback-Leibler (KL) divergence or Itakura-Saito divergence often result in indefinite kernels—matrices with both positive and negative eigenvalues.
Leveraging Indefinite Kernels in Kreĭn Spaces
Standard kernelized LSH methods assume a positive semi-definite (PSD) kernel, operating within a Hilbert space. When faced with indefinite kernels, these methods often discard negative eigenvalues as noise. However, these components often carry vital structural information.
Figure 3 illustrates that negative eigenvalues are not merely noise but represent a substantial portion of the kernel's spectrum. To capture this, the authors utilize reproducing kernel Kreĭn spaces (RKKS). A Kreĭn space is a vector space with an indefinite inner product, decomposable into two Hilbert spaces: $\mathcal{K}_+$ (positive-definite) and $\mathcal{K}_-$ (negative-definite).
The Non-Metric LSH Algorithm
The proposed algorithm follows a two-step process:
- Hilbert Space Projection: The indefinite kernel $K$ is decomposed into $K_+$ and $K_-$. Using $p$-stable distributions (specifically Gaussian), the data is projected into these respective Hilbert spaces, preserving $\ell^2$ distances within each.
- Kreĭn Space Hashing: The true distance in the Kreĭn space is derived from the difference between the distances in $\mathcal{K}_+$ and $\mathcal{K}_-$. The authors use an algebraic approximation to combine these projections into binary hash bits that reflect the Kreĭn distance.
For out-of-sample queries, a least-squares optimization estimates the query's projection coefficients, allowing new data to be hashed into the existing structure.
Experimental Results
The method was evaluated on four datasets (InternetAds, CIFAR-10, Local-Patch, and USPS-Digit) using various non-metric distances. The primary metric, Good Neighbor Ratio (GNR), measured the success of retrieving the top-5% nearest neighbors.
The results consistently showed that the Kreĭn space approach outperformed baselines that ignored negative eigenvalues. By integrating information from both the positive and negative spectral components, the algorithm achieved significantly higher retrieval accuracy, proving that the "negative" part of the kernel is essential for representing non-metric similarities accurately.
Summary updated