In modern data science, items are frequently represented as probability distributions—for instance, a document as a distribution over topics, or a user as a distribution over watched videos. To find "similar" items in these contexts, practitioners rely on information-theoretic distance measures like Jensen-Shannon (JS) divergence or Mutual Information Loss (MIL).
While standard techniques like Locality-Sensitive Hashing (LSH) excel at accelerating searches for simple Euclidean ($L^2$) distances, they struggle with these complex measures. Previous attempts to hash JS divergence were either data-dependent (requiring recalculation if the dataset changes) or lacked rigorous theoretical guarantees. This paper bridges the gap between information theory and efficient search by developing the first provably efficient, data-independent LSH schemes for $f$-divergences and Kreĭn kernels.
Two Paths to Efficient Hashing
The authors tackle the challenge of hashing complex probability distributions through two distinct mathematical frameworks: an approximation path and a lossless path.
1. The Approximation Path for $f$-Divergences
The authors propose a simple but powerful reduction tool for $f$-divergences. They demonstrate that if a complex divergence (like Generalized JS) can be approximated using a "hashable" distance (like the squared Hellinger distance), it can inherit the LSH properties of that simpler distance.
The core insight—termed the Hellinger Bridge—is the proof that the squared Hellinger distance is essentially half of the $L^2$ distance between the square roots of the probability vectors. Because $L^2$ hashing is well-understood, the authors can hash $f$-divergences by simply taking the square root of the data and applying standard Gaussian random projections.
This provides a tight, two-sided approximation result showing that Generalized JS divergence is bounded by the squared Hellinger distance. For JS divergence, the approximation factor is shown to be at least 0.69, and for triangular discrimination, it is at least 0.5.
2. The Lossless Path for Kreĭn Kernels
A Kreĭn kernel is a function that can be expressed as the difference between two positive definite kernels ($K = K_1 - K_2$). The authors develop a general method to reduce any Kreĭn kernel search to a Maximum Inner Product Search (MIPS).
By using explicit feature maps, they transform the data into a space where the kernel value corresponds to a simple dot product. Unlike the $f$-divergence approach, this reduction is theoretically "lossless." Crucially, the authors prove that Mutual Information Loss (MIL)—a vital metric for model compression and feature clustering—is a Kreĭn kernel, allowing it to be hashed efficiently for the first time.
Empirical Validation and Key Results
The authors evaluated their algorithms on several standard machine learning benchmarks, treating the data as probability distributions (e.g., Reuters-21578 for topic distributions, and $L^1$-normalized MNIST/CIFAR-10 images).
- Data Independence: Unlike prior work requiring Singular Value Decomposition (SVD) on the entire dataset, these new methods are data-independent. Hash functions can be generated without prior knowledge of the data points, vastly improving scalability.
- Empirical Speedup: On the Fashion MNIST dataset, the proposed LSH scheme achieved a 10x to 12x speedup over brute-force search while maintaining high precision (the fraction of true nearest neighbors correctly retrieved).
- Robustness: The performance of the Generalized JS hashing remained stable across different values of the weight parameter $\lambda$, proving the method's versatility across various applications.
Limitations and Future Directions
While these methods represent a significant leap forward, the authors note a few limitations. In the Kreĭn-LSH section, they acknowledge a known issue in MIPS reductions: adding a "norm-balancing" term can sometimes dominate the distance, potentially degrading LSH performance. They suggest using "norm-ranging" (partitioning data by its length) to mitigate this effect.
Additionally, while the Kreĭn kernel approach is lossless, the $f$-divergence approach remains an approximation. Future research may investigate whether lossless transforms exist for a broader range of $f$-divergences, and how to better handle extremely sparse distributions that might challenge the random projection step.
Summary updated