3
$\begingroup$

This is a question that I can't find the solution. I don't know it is a open question or it is a well-known result that can be attained from several lemmas.

Here are the definition of Matérn class kernel:

$M_{\sigma^2,\nu,\rho}(x,y)=\sigma^2\frac{2^{1-\nu}}{\Gamma(\nu)}(\sqrt{2\nu}\frac{||x-y||}{\rho})^{\nu}K_{\nu}(\sqrt{2\nu}\frac{||x-y||}{\rho})$

where $\sigma^2$ is a length scale parameter, $\Gamma(.)$ is gamma function, $K_{\nu}$ is the modified Bessel function of the second kind, and $\nu,\rho$ are non-negative parameters of covariance.

I use the definition of universal kernel in Universal Kernels(Charles A. Micchelli):

Given any prescribed compact subset Z of a Hausdorff topological space X, A kernel is universal if for any positive number $\epsilon$ and any function f ∈ C(Z) (continuous function on Z) there is a function g ∈ K(Z) (RKHS space generated by the kernel) such that sup norm $||f-g||_{Z}<\epsilon$

I know that frequently used Gaussian and Laplacian kernels are universal kernels and they are special case of Matérn class so I am wondering what kind of $\nu$ will lead to a universal kernel.

I am interesting in this problem because I am now studying Gaussian Process and Bayesian Optimization [Niranjan Srinivas,Jonathan Scarlett, Jasper Snoek] and I find that not only in theory they consider Matérn/Gaussian Kernel but also in real-world implementation. The default Kernel choice of many Bayesian optimization tools are Matérn 5/2. I don't think it is reasonable if it's not universal but I don't know how to prove it.

$\endgroup$
2
$\begingroup$

Yes, Matérn kernels are universal, for any parameters.

First note that $M_{\sigma^2,\nu,\rho}(x, y) = \Psi(x - y)$, i.e. the kernel is translation-invariant. It is also bounded and continuous.

The first main result we'll need is from:

Sriperumbudur, Fukumizu, and Lanckiret. Universality, Characteristic Kernels and RKHS Embedding of Measures. JMLR 12(Jul):2389−2410, 2011.

They show that the notion they call $cc$-universal is equivalent to the universality of Michhelli et al. (Remark 3). They also show that for bounded, continuous, translation-invariant kernels on $\mathbb R^d$, being characteristic implies being $cc$-universal (Figure 1 part 3).

It was previously shown that bounded continuous translation-invariant kernels on $\mathbb R^d$ are characteristic if and only if the Fourier transform of $\Psi$, which we know to be a nonnegative measure from Bochner's theorem, has support on all of $\mathbb R^d$: Theorem 7 of

Sriperumbudur, Gretton, Fukumizu, Lanckriet, and Schölkopf. Injective Hilbert Space Embeddings of Probability Measures. 21st Annual Conference on Learning Theory, 2008.

But the Fourier transform of $\Psi$ for the Matérn kernel, from equation (4.15) of Rasmussen and Williams, Gaussian Processes in Machine Learning (chapter 4 pdf), is the density $$ S(s) = \sigma^2 \frac{2^d \pi^{d/2} \Gamma(\nu + d/2) (2 \nu)^\nu}{\Gamma(\nu) \rho^{2 \nu}} \left( \frac{2 \nu}{\rho^2} + 4 \pi^2 \lVert s \rVert^2 \right)^{-\nu + d/2} $$ where $d$ is the dimension. This of course has support on all of $\mathbb R^d$, so the Matérn kernel is characterestic, so it's $cc$-universal.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much for your self-contained and clear answer. To be honest, I do find Sriperumbudur's paper and find that Matern class is cc-universal. But I just read the introduction so I don't realize that they are equivalent. And I also have Gaussian Processes in Machine Learning at hand. So I guess the reason why we often use Matern 3/2 and Matern 5/2 is because that they have simple form and is 1/2-times differentiable. $\endgroup$ – Wei-Cheng Lee Jun 28 '18 at 17:34
  • 1
    $\begingroup$ I think that I need to study more math. If I want to understand the story between Gaussian Process and RKHS space, what reference would you recommend me to study? $\endgroup$ – Wei-Cheng Lee Jun 28 '18 at 17:37
  • 1
    $\begingroup$ GPML has a decent basic overview. I don't know of a good more-detail-than-that-but-not-mega-technical source; it's a significant gap in kernel methods right now imo.... $\endgroup$ – Dougal Jun 28 '18 at 19:55
  • $\begingroup$ Could you further explain the last sentence, what is the current interest in kernel method right now? I am a CS master student. I am a layman of kernel method, I study it because I try to understand Bayesian Optimization and since they often use GP as a prior, kernel is everywhere. I only treat kernel as a tool to control smoothness (Kridging and kernel correspond to mean square differentibility) it will be good to know what kernel method specialist actually cares about right now. $\endgroup$ – Wei-Cheng Lee Jun 28 '18 at 20:53
  • 1
    $\begingroup$ Sorry, I didn't mean that it's a research gap, just that I'm not aware of a book that is detailed but not too hardcore mathy. Berlinet-Thomas/Agnan and Steinwart/Christmann are excellent detailed mathematical books about the topic. $\endgroup$ – Dougal Jun 28 '18 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.