Fast and scalable polynomial kernels via explicit feature maps

By Ninh D. Pham, Rasmus Pagh. 2013

367 citations recorded by the source corpus.

Approximation of non-linear kernels using random feature mapping has been successfully employed in large-scale data analysis applications, accelerating the training of kernel machines. While previous random feature mappings run in O(ndD) time for $n$ training samples in d-dimensional space and D random feature maps, we propose a novel randomized tensor product technique, called Tensor Sketching, for approximating any polynomial kernel in O(n(d+D \log{D})) time. Also, we introduce both absolute and relative error bounds for our approximation to guarantee the reliability of our estimation algorithm. Empirically, Tensor Sketching achieves higher accuracy and often runs orders of magnitude faster than the state-of-the-art approach for large-scale real-world datasets.

Subfields: Artificial Intelligence, Computational Mathematics, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Computational Mathematics

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “See also Kar and Karnick (2012), Vedaldi and Zisserman (2012), Le et al. (2013), Pham and Pagh (2013) and references therein for a generalization of this idea.”
Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, background): “Pham and Pagh [2013] suggested feature maps for the polynomial kernels.”
Bilinear CNN Models for Fine-Grained Visual Recognition (2015, methodology): “he overall representation can be reduced to 512 64 dimensions by projecting one of the features to a lower-dimensional space. Alternatively, the compact bilinear pooling [19] applies tensor sketching [48] to aggregate low-dimensional embeddings that approximate the bilinear features. In Section5.1we”
Compact Bilinear Pooling (2015, methodology): “the count sketch of two vectors’ outer product is the convolution of individual’s count sketch [27].”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “For polynomial kernels, k(x, x′) = (〈x, x′〉+ c), a random tensor sketching approach can also be used [20].”
Deep Multimodal Feature Encoding for Video Ordering (2020, methodology): “We are interested in capturing such pairwise interactions between modalities for video clips, and propose a new deep multimodal feature encoding inspired by [56, 15, 43].”
Deep Multimodal Representation Learning: A Survey (2019, background): “Particularly, the count sketch of the outer product can be decomposed into a convolution of separated count sketches [71], which means that the computation of an outer product can be avoided.”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, background): “For polynomial kernels, k ( x, x (cid:48) ) = ( (cid:104) x, x (cid:48) (cid:105) + c ) p , a random tensor sketching approach can also be used [22].”
Spherical Random Features for Polynomial Kernels (2015, methodology): “Although these methods are general in the sense that they are applicable to any real-valued input data, in practice polynomial kernels are commonly used on `2-normalized input data [15] because they are otherwise unbounded.”
Kernel Pooling for Convolutional Neural Networks (2017, methodology): “[31] and Subspace Embedding by Avron et al.”
Learning Action Recognition Model from Depth and Skeleton Videos (2017, methodology): “This idea is based on the Tensor Sketch algorithm of [16].”
Compact Generalized Non-local Network (2018, methodology): “In the area of kernel learning [21], there are many prior works such as compact bilinear pooling (CBP) [5] that uses the Tensor Sketching [18] to address this problem.”
Recent Advances of Large-Scale Linear Classification (2012, background): “Examples include random Fourier projection [83], random projections [84]– [87], polynomial approximation [88], and hashing [89]–[92].”
High-Performance Kernel Machines With Implicit Distributed Optimization and Randomization (2014, background): “TensorSketch [21] is designed for approximating the polynomial kernel k(x, z) = (xy + c) for some q and c.”
Deep Temporal Linear Encoding Networks (2016, methodology): “To tackle this problem, compact bilinear pooling [11] was proposed which uses the Tensor Sketch Algorithm [23], to project features from a high dimensional space to a lower dimensional one, while retaining state-ofthe-art performances.”
Hierarchical Bilinear Pooling for Fine-Grained Visual Recognition (2018, background): “Gao et al. [6] applied Tensor Sketch [23] to approximate the second-order statistics and to reduce feature dimension.”
Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding (2016, methodology): “In contrast to Rohrbach et al. (2016), we include a linear embedding of the visual representation and L 2 normalization of both input modalities, instead of batch normalization (Ioffe and Szegedy, 2015), which we found to be beneﬁcial when using MCB for the grounding task.”
Subspace Embeddings for the Polynomial Kernel (2014, methodology): “Unlike the work of Pham and Pagh [16], which only used that H was 2-wise independent, our analysis needs this stronger property of H .”
Coded Computing for Federated Learning at the Edge (2020, methodology): “For this, we leverage the popular kernel embedding based on random Fourier features (RFF) (Rahimi & Recht, 2008a; Pham & Pagh, 2013; Kar & Karnick, 2012), that has been a popular approach for dealing with kernelbased inference on large datasets.”