We consider the problem of improving kernel approximation via feature maps. These maps arise as Monte Carlo approximation to integral representations of kernel functions and scale up kernel methods for larger datasets. We propose to use more efficient numerical integration technique to obtain better estimates of the integrals compared to the state-of-the-art methods. Our approach allows to use information about the integrand to enhance approximation and facilitates fast computations. We derive the convergence behavior and conduct an extensive empirical study that supports our hypothesis. Kernel methods proved to be an efficient technique in numerous real-world problems. The core idea of kernel methods is the kernel trick -compute an inner product in a high-dimensional (or even infinite-dimensional) feature space by means of a kernel function k:k(x, y) = ψ(x ), ψ(y ) ,where ψ : X → F is a non-linear feature map transporting elements of input space X into a feature space F. It is a common knowledge that kernel methods incur space and time complexity infeasible to be used with large-scale datasets directly. For example, kernel regression has O(N 3 + N d 2 ) training time, O(N 2 ) memory, O(N d) prediction time complexity for N data points in original d-dimensional space X . One of the most successful techniques to handle this problem BID18 ) introduces a low-dimensional randomized approximation to feature maps: DISPLAYFORM0 This is essentially carried out by using Monte-Carlo sampling to approximate scalar product in (1). A randomized D-dimensional mappingΨ(·) applied to the original data input allows employing standard linear methods, i.e. reverting the kernel trick. In doing so one reduces the complexity to that of linear methods, e.g. D-dimensional approximation admits O(N D 2 ) training time, O(N D) memory and O(N ) prediction time.It is well known that as D → ∞, the inner product in (2) converges to exact kernel k(x, y). Recent research BID22 ; BID9 ; BID4 ) aims to improve the convergence of approximation so that a smaller D can be used to obtain the same quality of approximation.This paper considers kernels that allow the following integral representation k(x, y) = E q(w) g xy (w) ≈ E p(w) f xy (w) = I(f xy ), p(w ) = 1 (2π) d/2 e − w 2 2 ,where q(w) is a density associated with a kernel, e.g. the popular Gaussian kernel has q(w) = p(w), so the exact equality holds with g xy (w) = f xy (w) = φ(w x) φ(w y), where φ(·) = [cos (·), sin( ·)] .The class of kernels admitting the form in (3) covers shift-invariant kernels (e.g. radial basis function (RBF) kernels) and Pointwise Nonlinear Gaussian (PNG) kernels. They are widely used in practice and have interesting connections with neural networks BID3 BID21 ).The main challenge for the construction of low-dimensional feature maps is the approximation of the expectation in (3) which is d-dimensional integral with Gaussian weight. While standard MonteCarlo rule is easy to implement, there are better quadrature rules for such kind of integrals. For example, BID22 apply quasi-Monte Carlo (QMC) rules and obtain better quality kernel matrix approximations compared to random Fourier features of BID18 .Unlike other research studies we refrain from using simple Monte Carlo estimate of the integral, instead, we propose to use specific quadrature rules. We now list our contributions:1. We propose to use advanced quadrature rules to improve kernel approximation accuracy. We also provide an analytical estimate of the error for the used quadrature rules. 2. We note that for kernels with specific integrand f xy (w) in (3) one can improve on its properties. For example , for kernels with even function f xy (w) we derive the reduced quadrature rule which gives twice smaller embedded dimension D with the same accuracy. This applies, for example, to any RBF kernel. 3. We use structured orthogonal matrices (so-called butterfly matrices ) when designing quadrature rule that allow fast matrix by vector multiplications. As a result, we speed up the approximation of the kernel function and reduce memory requirements. 4. We demonstrate our approach on a set of regression and classification problems. Empirical results show that the proposed approach has a better quality of approximation of kernel function as well as better quality of classification and regression when using different kernels. In this work we proposed to apply advanced integration rule that allowed us to achieve higher quality of kernel approximation. Our derivation of the variance of the error implies the dependence of the error on the scale of data, which in case of Gaussian kernel can be interpreted as width of the kernel. However, as we have seen earlier, accuracy on the final task has no direct dependence on the approximation quality, so we can only speculate whether better approximated wide kernels deliver better accuracy compared to the poorer approximated narrow ones. It is interesting to explore this connection in the future work.To speed up the computations we employed butterfly orthogonal matrices yielding the computational complexity O(d log d). Although the procedure we used to generate butterfly matrices claims to produce uniformly random orthogonal matrices, we found that it is not always so. However, the comparison of the method H (uses properly distributed orthogonal matrices) with method B (sometimes fails to do so) did not reveal any differences. We also leave it for the future investigation.Our experimental study confirms that for many kernels on the most datasets the proposed approach delivers better kernel approximation. Additionally, the empirical results showed that the quality of the final task (classification/regression) is also higher than the state-of-the-art baselines. The connection between the final score and the kernel approximation error is to be explored as well.
Quadrature rules for kernel approximation. The paper proposes improving the kernel approximation of random features by using quadrature rules like stochastic spherical-radial rules. The authors propose a novel version of the random feature map approach to approximately solve large-scale kernel problems. This paper shows that techniques due to Genz & Monahan (1998) can be used to achieve low kernel approximation error under the framework of random fourier feature, a new way to apply quadrature rules to improve kernel approximation.