Theory of the GMM Kernel

Ping Li, Cun-Hui ZhangWWW 2016 · OpenReview

Abstract: In web search, data mining, and machine learning, two popular measures of data similarity are the cosine and the resemblance (the latter is for binary data). In this study, we develop theoretical results for both the cosine and the GMM (generalized min-max) kernel, which is a generalization of the resemblance. GMM has direct applications in machine learning as a positive definite kernel and can be efficiently linearized via probabilistic hashing to handle big data. Owing to its discrete nature, the hashed values can also be used to build hash tables for efficient near neighbor search. We prove the theoretical limit of GMM and the consistency result, assuming that the data follow an elliptical distribution, which is a general family of distributions and includes the multivariate normal and t-distribution as special cases. The consistency result holds as long as the data have bounded first moment (an assumption which typically holds for data commonly encountered in practice). Furthermore, we establish the asymptotic normality of GMM. We also prove the limit of cosine under elliptical distributions. In comparison, the consistency of GMM requires much weaker conditions. For example, when data follow a t-distribution with ν degrees of freedom, GMM typically provides a better estimate of similarity than cosine when ν < 8 (ν = 8 means the distribution is very close to normal). These theoretical results help explain the recent success of GMM and lay the foundation for further research.

Introduction

Measuring similarity between data vectors is a cornerstone of modern machine learning and information retrieval. While cosine similarity has long been the industry standard, it relies on the assumption of bounded second moments (finite variance). However, real-world datasets—such as word frequencies or web traffic—often exhibit heavy-tailed behavior where these assumptions fail. This paper provides a rigorous theoretical foundation for the Generalized Min-Max (GMM) kernel, demonstrating its superior stability and consistency in these challenging scenarios.

The GMM Kernel and Elliptical Distributions

The GMM similarity between two vectors $x$ and $y$ is defined as: $$GMM(x, y) = \frac{\sum_{i=1}^n [\min(x_{i+}, y_{i+}) + \min(x_{i-}, y_{i-})]}{\sum_{i=1}^n [\max(x_{i+}, y_{i+}) + \max(x_{i-}, y_{i-})]}$$ where $x_{i+}$ and $x_{i-}$ are the positive and negative components, respectively.

To analyze GMM, the authors utilize the framework of elliptical distributions, a broad class including Gaussian and multivariate $t$-distributions. This framework allows for a formal proof of consistency: GMM converges to a fixed limit ($f_\infty$) provided the data has a bounded first moment. This is a significantly more relaxed condition than the bounded second moment required for the stability of cosine similarity.

Key Insights

  • The ν < 8 Rule: GMM typically outperforms cosine similarity when the data's degrees of freedom (ν) are less than 8. Given that most natural power-law datasets have ν between 1 and 2, GMM is often the more reliable choice.
  • Robustness without Penalty: Even in perfectly Gaussian settings (ν → ∞), GMM performs nearly as well as cosine similarity, making it a safe "drop-in" replacement.
  • Asymptotic Normality: The authors derived explicit variance formulas, establishing that GMM estimates follow a normal distribution as sample sizes increase, which is critical for statistical inference.

Key Results

Convergence and Consistency

The theoretical boundary for GMM consistency is the existence of the first moment. Simulations using the bivariate $t$-distribution confirm that for ν ≥ 1, the GMM mean converges rapidly to its theoretical limit as the sample size $n$ increases.

GMM Mean convergence for heavy-tailed data (ν=1).

When the first moment does not exist (e.g., ν = 0.5), the measure fails to converge, as evidenced by the lack of overlap between curves for different sample sizes $n$. This confirms the theoretical limits established in the paper.

Lack of convergence for extremely heavy-tailed data (ν=0.5).

Practical Efficiency

Beyond theoretical stability, GMM is computationally advantageous. It can be linearized via probabilistic hashing, enabling efficient near-neighbor searches in large-scale systems. In correlation estimation tasks, GMM-based estimators consistently showed lower Mean Square Error (MSE) than cosine-based alternatives in heavy-tailed scenarios.

Conclusion

By establishing the consistency and asymptotic normality of the GMM kernel under elliptical distributions, this work explains why GMM often succeeds where cosine similarity fails. Its robustness to heavy tails and computational efficiency make it a powerful tool for modern big data applications.

Summary updated

Abstract

In web search, data mining, and machine learning, two popular measures of data similarity are the cosine and the resemblance (the latter is for binary data). In this study, we develop theoretical results for both the cosine and the GMM (generalized min-max) kernel, which is a generalization of the resemblance. GMM has direct applications in machine learning as a positive definite kernel and can be efficiently linearized via probabilistic hashing to handle big data. Owing to its discrete nature, the hashed values can also be used to build hash tables for efficient near neighbor search. We prove the theoretical limit of GMM and the consistency result, assuming that the data follow an elliptical distribution, which is a general family of distributions and includes the multivariate normal and t-distribution as special cases. The consistency result holds as long as the data have bounded first moment (an assumption which typically holds for data commonly encountered in practice). Furthermore, we establish the asymptotic normality of GMM. We also prove the limit of cosine under elliptical distributions. In comparison, the consistency of GMM requires much weaker conditions. For example, when data follow a t-distribution with ν degrees of freedom, GMM typically provides a better estimate of similarity than cosine when ν < 8 (ν = 8 means the distribution is very close to normal). These theoretical results help explain the recent success of GMM and lay the foundation for further research.
BibTeX
@misc{li2016theory,
  author = {Ping Li and Cun-Hui Zhang},
  title = {{Theory of the GMM Kernel}},
  year = {2016},
  eprint = {1608.00550},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.00550},
}
Figure