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, comparing histograms (e.g., Bag-of-Visual-Words) is a fundamental task. The $\chi^2$ kernel is widely recognized for its superior accuracy in these comparisons compared to simple linear dot products. However, its computational cost is prohibitive for large-scale datasets like ImageNet, where non-linear Support Vector Machines (SVMs) fail to scale.
To address this, researchers employ "linearization" techniques such as Random Fourier Features (RFF) to map data into a space where linear operations approximate the non-linear kernel. Existing approximations often suffer from poor accuracy or high dimensionality. This paper introduces a novel analytical approximation for the $\chi^2$ kernel that achieves geometric convergence, enabling high-accuracy non-linear classification on massive datasets with the efficiency of linear models.
Methodology
The core contribution is a "Direct Approximation" derived through elementary methods that exhibits geometric convergence—the approximation error decreases exponentially as more terms are added.
Adaptive Direct Approximation
Unlike previous methods with fixed parameters, the proposed approach adapts to the input data distribution. By analyzing the histogram of the input data, the algorithm greedily selects parameters ($k_i$) to eliminate error peaks in high-density regions. This adaptive nature ensures the approximation is most precise where the data actually resides.
Dimensionality Reduction via Out-of-Core PCA
To maintain manageable feature vector sizes, the authors utilize Principal Component Analysis (PCA). For large-scale datasets that exceed RAM capacity, an "out-of-core" PCA implementation is used, computing the covariance matrix in chunks. Furthermore, incorporating unlabeled test data during PCA (semi-supervised PCA) helps capture the global data distribution, leading to significant performance gains.
Experimental Evaluation
The method was evaluated on PASCAL VOC 2010 (medium-scale) and ImageNet ILSVRC 2010 (large-scale).
Convergence and Accuracy
The Direct Approximation converges significantly faster than the state-of-the-art Vedaldi-Zisserman (VZ) approximation. As shown in the results, high accuracy is achieved with as few as two terms per dimension.
On PASCAL VOC, the proposed method reached 43.53% accuracy, nearing the 44.19% achieved by the exact $\chi^2$ kernel. On ImageNet, it achieved 18.65% accuracy, a substantial improvement over the 11.6% linear baseline prevalent at the time.
Conclusion
This work demonstrates that analytical approximations with geometric convergence, combined with efficient PCA techniques, can bridge the gap between the accuracy of non-linear kernels and the scalability of linear models. While the initial computation of the PCA Hessian remains a bottleneck, the approach offers a statistically significant performance boost for large-scale visual recognition tasks. Future work may explore extending these techniques to other kernel types like Histogram Intersection.
Summary updated