2013 FastandScalablePolynomialKernel

• (Pham & Pagh, 2013) ⇒ Ninh Pham, and Rasmus Pagh. (2013). “Fast and Scalable Polynomial Kernels via Explicit Feature Maps.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487591

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Fast+and+Scalable+Polynomial+Kernels+via+Explicit+Feature+Maps
• http://dl.acm.org/citation.cfm?id=2487575.2487591&preflayout=flat#citedby

Quotes

Author Keywords

• Classifier design and evaluation; count sketch; fft; polynomial kernel; svm; tensor product

Abstract

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 [math]\displaystyle{ O(ndD) }[/math] time for [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ O (n (d + D\log{D})) }[/math] 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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 FastandScalablePolynomialKernel	Ninh Pham Rasmus Pagh			Fast and Scalable Polynomial Kernels via Explicit Feature Maps				10.1145/2487575.2487591		2013