Random Fourier Approximations for Skewed Multiplicative Histogram Kernels
Approximations based on random Fourier features have recently emerged as an efficient and elegant methodology for designing large scale kernel machines [4] By expressing the kernel as a Fourier expansion, features are generated based on a finite set of random basis projections with inner products that are Monte Carlo approximations to the original kernel. However, the original Fourier features are only applicable to translation invariant kernels and are not suitable for histograms that are always non negative. This paper extends the concept of translation invariance and the random Fourier feature methodology to arbitrary, locally compact Abelian groups. Based on empirical observations drawn from the exponentiated kh2 kernel, the state of the art for histogram descriptors, we propose a new group called the skewed multiplicative group and design translation invariant kernels on it. Experiments show that the proposed kernels outperform other kernels that can be similarly approximated. In a semantic segmentation experiment on the PASCAL VOC 2009 dataset, the approximation allows us to train large scale learning machines more than two orders of magnitude faster than previous nonlinear SVMs.
DAGM Symposium