Chebyshev Approximations to the Histogram χ2 Kernel

Fuxin Li, Guy Lebanon, Cristian Sminchisescu

Abstract

We propose a new analytical approximation to the $\chi^2$ kernel that converges geometrically. The analytical approximation is derived with elementary methods and adapts to the input distribution for optimal convergence rate. Experiments show the new approximation leads to improved performance in image classification and semantic segmentation tasks using a random Fourier feature approximation of the $\exp-\chi^2$ kernel. Besides, out-of-core principal component analysis (PCA) methods are introduced to reduce the dimensionality of the approximation and achieve better performance at the expense of only an additional constant factor to the time complexity. Moreover, when PCA is performed jointly on the training and unlabeled testing data, further performance improvements can be obtained. Experiments conducted on the PASCAL VOC 2010 segmentation and the ImageNet ILSVRC 2010 datasets show statistically significant improvements over alternative approximation methods.

Introduction

In computer vision, histograms such as SIFT or HOG are standard representations for image data. The $\chi^2$ kernel is widely regarded as the "gold standard" for comparing these histograms because it effectively captures their underlying distributions. However, the non-linear nature of the $\chi^2$ kernel presents significant scalability challenges. Using it with standard tools like Support Vector Machines (SVMs) requires computing a kernel matrix that grows quadratically with the number of images ($O(N^2)$). For massive datasets like ImageNet, which contains millions of images, this quadratic complexity makes exact kernel methods computationally infeasible.

Previous attempts to "linearize" these kernels through approximations have often suffered from slow convergence rates or required excessively high dimensionality to maintain accuracy. This paper addresses these limitations by introducing a novel analytical approximation that achieves geometric convergence, making non-linear kernel learning efficient for large-scale applications.

Methodology

The authors propose two primary analytical approximations to bridge the gap between non-linear performance and linear efficiency:

  1. Direct Approximation: This primary contribution utilizes a recursive formula to approximate the harmonic mean. Unlike standard Monte Carlo methods that improve at a rate of $O(1/\sqrt{d})$, this method enjoys geometric convergence, where the error drops exponentially as more terms are added. It incorporates a greedy algorithm to adapt parameters to the specific distribution of the input data, ensuring optimal accuracy where the data density is highest.
  2. Chebyshev Approximation: An alternative series derived using Fourier cosine expansions. While theoretically elegant, empirical results indicate it converges more slowly than the direct method.

To manage the high dimensionality of these approximations, the authors developed RF-PCA (Random Features + PCA), an out-of-core Principal Component Analysis method. This allows for feature space reduction without loading the entire dataset into RAM. Furthermore, a semi-supervised variant performs PCA on both training and unlabeled test data, enabling the model to prioritize frequency components most relevant to the target classification task.

Approximation error on 300-dim BOW features. The Direct method (blue) demonstrates significantly faster error reduction (geometric convergence) compared to the VZ (green) and Chebyshev (red) methods.

Experimental Evaluation and Results

The proposed methods were evaluated on the PASCAL VOC 2010 dataset for semantic segmentation and the ImageNet ILSVRC 2010 dataset for large-scale classification.

Accuracy and Convergence

In head-to-head comparisons, the Direct approximation reached low error levels with only 2 terms—a level of precision that previous state-of-the-art methods, such as the VZ approximation, could not achieve even with 10 or more terms. This efficiency allows for high-performance non-linear learning with minimal computational overhead.

Classification accuracy on BOW (left) and HOG (right) features. The Direct approximation (blue) consistently outperforms VZ and Chebyshev methods, reaching peak accuracy with fewer terms.

Large-Scale Performance

On the ImageNet 2010 dataset, the approximation provided a substantial performance boost. While a standard linear classifier achieved 11.6% accuracy, the PCA-Chebyshev approximation reached 18.65%. This result demonstrates that the benefits of non-linear kernels can finally be scaled to datasets containing millions of images. On PASCAL VOC, the approximation performed nearly as well as exact kernel methods while being significantly faster and more memory-efficient.

Conclusion

This work introduces a powerful framework for approximating the $\chi^2$ kernel with geometric convergence. By combining distribution-aware analytical approximations with out-of-core PCA, the authors enable the application of high-performance non-linear kernels to massive datasets. While the Direct recursive method proved empirically superior to the Chebyshev-based approach in terms of convergence speed, both represent significant advances over existing Monte Carlo-based random features. Future research may focus on extending these geometric approximation techniques to other additive kernels, such as the Histogram Intersection kernel.

Summary updated

Abstract

We propose a new analytical approximation to the $\chi^2$ kernel that converges geometrically. The analytical approximation is derived with elementary methods and adapts to the input distribution for optimal convergence rate. Experiments show the new approximation leads to improved performance in image classification and semantic segmentation tasks using a random Fourier feature approximation of the $\exp-\chi^2$ kernel. Besides, out-of-core principal component analysis (PCA) methods are introduced to reduce the dimensionality of the approximation and achieve better performance at the expense of only an additional constant factor to the time complexity. Moreover, when PCA is performed jointly on the training and unlabeled testing data, further performance improvements can be obtained. Experiments conducted on the PASCAL VOC 2010 segmentation and the ImageNet ILSVRC 2010 datasets show statistically significant improvements over alternative approximation methods.
BibTeX
@inproceedings{li2012chebyshev,
  author = {Fuxin Li and Guy Lebanon and Cristian Sminchisescu},
  title = {{Chebyshev Approximations to the Histogram χ2 Kernel}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2012},
  url = {https://openreview.net/forum?id=ByZamTW_-S},
}
Figure