Random Laplace Feature Maps for Semigroup Kernels on Histograms

TitleRandom Laplace Feature Maps for Semigroup Kernels on Histograms
Publication TypeConference Paper
Year of Publication2014
AuthorsYang, J., Sindhwani V., Fan Q., Avron H., & Mahoney M. W.
Other Numbers3677

With the goal of accelerating the training and testing complexity of nonlinear kernel methods, several recent papers have proposed explicit embeddings of the input data into low-dimensional feature spaces, where fast linear methods can instead be used to generate approximate solutions. Analogous to random Fourier feature maps to approximate shift-invariant kernels, such as the Gaussian kernel, on R(d), we develop a new randomized technique called random Laplace features, to approximate a family of kernel functions adapted to the semigroup structure of R(d[+]). This is the natural algebraic structure on the set of histograms and other non-negative data representations. We provide theoretical results on the uniform convergence of random Laplace features. Empirical analyses on image classification and surveillance event detection tasks demonstrate the attractiveness of using random Laplace features relative to several other feature maps proposed in the literature.

Bibliographic Notes

Proceedings of the IEEE Conference of Computer Vision and Pattern Recognition (CVPR), Columbus, Ohio

Abbreviated Authors

J. Yang, V. Sindhwani, Q. Fan, H. Avron, and M. W. Mahoney

ICSI Research Group

Big Data

ICSI Publication Type

Article in conference proceedings