Hashing for Large Scale Kernel Machine Linearization

This direction is merged into another direction: random feature kernel approximation. Its last version stays readable and citable here.

Version 1 of 117 papers24 conceptsfrozen 2026-10-04

Machine learning often presents a trade-off between the expressive power of nonlinear models and the computational efficiency of linear ones. Nonlinear kernel methods, such as Support Vector Machines (SVMs) with RBF or Min-Max kernels, can capture complex data relationships but suffer from a "kernel tax": they typically require computing an $N \times N$ similarity matrix, which becomes prohibitively expensive as the number of samples $N$ grows into the millions.

To solve this, a body of research led by Ping Li and colleagues has developed a framework for linearizing these kernels. By using specialized hashing algorithms, they transform high-dimensional data into compact, sparse binary representations where a simple linear inner product approximates the original nonlinear similarity.

The Intuition: Similarity as Collision

The core idea relies on the property of Locality Sensitive Hashing (LSH). In standard hashing, we want to avoid collisions; in LSH, we want the probability of two items "colliding" (having the same hash value) to be exactly proportional to their similarity.

For example, in b-Bit Minwise Hashing for Large-Scale Linear SVM, Ping Li and Arnd Christian König demonstrate that the probability of two sets having the same minhash value is equal to their Jaccard similarity. If we can turn this probability into a feature, we can use a linear solver to "count" these collisions.

The Linearization Trick

The breakthrough that makes this practical for training is the expansion trick. A hash value itself (e.g., "42") is categorical and cannot be used directly in a linear dot product. To bridge this gap, researchers expand each hash value into a one-hot encoded binary vector.

If we use $k$ hash functions and each hash has $2^b$ possible values, a single data point is transformed into a very long, very sparse binary vector. As shown in Hashing Algorithms for Large-Scale Learning, when you take the inner product of two such expanded vectors, the result is simply the number of hash collisions between the two points. Because this inner product now approximates the nonlinear kernel, a fast linear SVM solver can achieve the accuracy of a kernel SVM at a fraction of the cost.

Beyond Binary Sets: The GMM Kernel

While minwise hashing works for binary sets, real-world data is often numerical. Ping Li extended this logic to non-negative data through the Generalized Min-Max (GMM) kernel and Consistent Weighted Sampling (CWS).

In Min-Max Kernels, the author argues that the min-max similarity—defined as the sum of minimums divided by the sum of maximums across features—is a more powerful metric than standard linear kernels. By using CWS to generate "0-bit" or "b-bit" hashes, Generalized Min-Max Kernel and Generalized Consistent Weighted Sampling provides a way to linearize these complex similarities. This allows models to handle non-binary, sparse data with the same efficiency as binary sets.

Scaling to Massive Datasets

The practical impact of this research is the ability to run "heavy" nonlinear tasks on "light" linear infrastructure. Yadong MU, Shih-Fu Chang, and others introduced Hash-SVM, a framework that approximates kernel geometries with binary hash signatures. This allows massive visual classification datasets to be processed on a single machine, reducing training times from minutes to seconds.

Similarly, in the domain of Natural Language Processing, Sahil Garg and Irina Rish showed in Kernelized Hashcodes that transforming implicit structural kernels into explicit binary hashcodes allows complex linguistic relationships to be processed by efficient ensemble classifiers.

Tunability and Performance

Recent iterations of this work have moved from parameter-free hashes to "tunable" kernels. In Tunable GMM Kernels, Ping Li demonstrates that by adding exponentiation parameters to the hashing scheme, these linearized models can actually outperform deep neural networks and boosted trees on certain large-scale benchmarks.

By treating hashing not just as a compression tool, but as a way to explicitly construct a high-dimensional feature space, this research direction provides a mathematically grounded path to scaling the most expressive tools in machine learning to the era of big data.

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_hashing_for_large_scale_kernel_machine_l_b1edfba3,
  title = {Hashing for Large Scale Kernel Machine Linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hashing-for-large-scale-kernel-machine-linearization/rdr_b1edfba3f08e409cbdc88db171b7154d},
  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_hashing_for_large_scale_kernel_machine_l_b1edfba3_v1,
  title = {Hashing for Large Scale Kernel Machine Linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hashing-for-large-scale-kernel-machine-linearization/rdr_b1edfba3f08e409cbdc88db171b7154d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}