Compact Random Feature Maps

By Raffay Hamid, Ying Xiao, Alex Gittens, Dennis DeCoste. 2013

88 citations recorded by the source corpus.

Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, methodology): “Hamid et al. [2014], working on the polynomial kernel, suggest ﬁrst generating a very large amount of random features, and then applying them a low-distortion embedding based the Fast Johnson-Lindenstruass Transform, so the make the ﬁnal size of the mapped vector rather small.”
Memory Efficient Kernel Approximation (2014, background): “In addition to shift invariant kernels, Kar and Karnick (2012) construct the random feature map for polynomial kernels, and Hamid et al. (2014) propose the condensed random feature map to improve performance.”
Sampled Softmax with Random Fourier Features (2019, background): “However, due to rank deficiency of the produced features, it requires large D in order to achieve small mean squared error [23, 24].”
Randomness in neural networks: an overview (2017, methodology): “One possibility to counter this problem is to draw a large number B of samples and then linearly downproject the resulting feature mapping to a low- dimensional space via the use of a RP.73 The error bound in this case is investigated by Hamid et al.73 Another, more principled line of research is to”
Randomized Nonlinear Component Analysis (2014, methodology): “For instance, their extensions to dot-product kernels (Kar & Karnick, 2012) and polynomial kernels (Hamid et al., 2014); the development of advanced sampling techniques using Quasi-Monte-Carlo methods (Yang et al., 2014) or their accelerated computation via fast Walsh-Hadamard transforms (Le et…”
Generalization Properties of Learning with Random Features (2016, methodology): “The favorable situation corresponds to random features such that case α = γ .”
Spherical Random Features for Polynomial Kernels (2015, background): “Moreover, much of the theoretical analysis developed in former work is based on normalized vectors [16].”
Learning with SGD and Random Features (2018, unknown): “[15].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Several groups proposed using structured random embeddings (Section 9) to accelerate this process; see (Pham and Pagh 2013, Le, Sarlós and Smola 2013, Hamid et al. 2014).”
A Survey of Modern Questions and Challenges in Feature Extraction (2015, methodology): “These methods include approximating the kernel matrix, for example with Nyström method (Drineas and Mahoney, 2005; Cortes et al., 2010c), or approximating the kernel function with random Fourier features (Rahimi and Recht, 2007; Pham and Pagh, 2013; Hamid et al., 2013).”
Subspace Embeddings for the Polynomial Kernel (2014, methodology): “This is true even of the sketching methods for polynomial kernels that do not use TENSORSKETCH [10, 7], as it only provides tail bounds for preserving the norm of a fixed vector, and has the aforementioned problems of extending it to a subspace, i.”
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets (2014, background): “There have been steady interests in using random projections to approximate diﬀerent kernels [23, 18, 28, 44].”