Radial basis function kernel: Difference between revisions

Revision as of 21:28, 20 April 2023

Revision as of 01:01, 21 April 2023

Line 53:

where <math>\textstyle\varphi</math> is the implicit mapping embedded in the RBF kernel.

One way to construct such a ''z'' is to randomly sample from the [[Fourier transformation]] of the kernel<ref>Ali{{Cite journal |last=Rahimi and Benjamin|first=Ali |last2=Recht (|first2=Benjamin |date=2007). [http|title=Random Features for Large-Scale Kernel Machines |url=https://wwwproceedings.eecsneurips.berkeley.educc/~brechtpaper/papers2007/07hash/013a006f03dbc5392effeb8f18fda755-Abstract.rah.rec.nips.pdfhtml "Random|journal=Advances features for large-scale kernel machines"].in ''Neural Information Processing Systems'' |publisher=Curran Associates, Inc. |volume=20}}</ref><math display="block">\varphi(x) = \frac{1}{\sqrt D}[\cos\langle w_1, x\rangle, \sin\langle w_1, x\rangle, \cdots \cos\langle w_D, x\rangle, \sin\langle w_D, x\rangle]^T</math>where <math>w_1, ..., w_D</math> are independent samples from the normal distribution <math>N(0, \sigma^2 I)</math>. The proof boils down to evaluating the integral <math>\int_{-\infty}^{\infty} \frac{\cos (k x) e^{-x^2 / 2}}{\sqrt{2 \pi}} d x=e^{-k^2 / 2}</math>.

'''Theorem:''' <math>\mathbb E[\langle \varphi(x), \varphi(y)\rangle] = e^{\frac{\|x-y\|^2}{2\sigma^2}}</math>.

'''Proof:''' It suffices to prove the case of <math>D=1</math>. Use the trigonometric identity <math>\cos(a-b) = \cos(a)\cos(b) + \sin(a)\sin(b)</math>, the spherical symmetry of gaussian distribution, then evaluate the integral <math>\int_{-\infty}^{\infty} \frac{\cos (k x) e^{-x^2 / 2}}{\sqrt{2 \pi}} d x=e^{-k^2 / 2}</math>.

The variance of the estimator is <math>\propto D^{-1}</math>. (Appendix A.2<ref>{{Cite journal |last=Peng |first=Hao |last2=Pappas |first2=Nikolaos |last3=Yogatama |first3=Dani |last4=Schwartz |first4=Roy |last5=Smith |first5=Noah A. |last6=Kong |first6=Lingpeng |date=2021-03-19 |title=Random Feature Attention |url=http://arxiv.org/abs/2103.02143 |journal=arXiv:2103.02143 [cs]}}</ref>).