Fastfood-computing hilbert space expansions in loglinear time
Venue
International Conference on Machine Learning (2013) (to appear)
Publication Year
2013
Authors
Quoc V. Le, Tamas Sarlos, Alex Smola
BibTeX
Abstract
Despite their successes, what makes kernel methods difficult to use in many large
scale problems is the fact that computing the decision function is typically
expensive, especially at prediction time. In this paper, we overcome this
difficulty by proposing Fastfood, an approximation that accelerates such
computation significantly. Key to Fastfood is the observation that Hadamard
matrices when combined with diagonal Gaussian matrices exhibit properties similar
to dense Gaussian random matrices. Yet unlike the latter, Hadamard and diagonal
matrices are inexpensive to multiply and store. These two matrices can be used in
lieu of Gaussian matrices in Random Kitchen Sinks (Rahimi & Recht, 2007) and
thereby speeding up the computation for a large range of kernel functions.
Specifically, Fastfood requires O(n log d) time and O(n) storage to compute n
non-linear basis functions in d dimensions, a significant improvement from O(nd)
computation and storage, without sacrificing accuracy. We prove that the
approximation is unbiased and has low variance. Extensive experiments show that we
achieve similar accuracy to full kernel expansions and Random Kitchen Sinks while
being 100x faster and using 1000x less memory. These improvements, especially in
terms of memory usage, make kernel methods more practical for applications that
have large training sets and/or require real-time prediction.
