2
$\begingroup$

So I have been reading about Reproducible Kernel Hilbert Spaces (RKHS), and I am confused with how people use it in regards to the kernel trick seen in Machine Learning.

For example, in this blog post (Section 4.), they provide an example saying that they define the map $\phi:\mathcal{X} \rightarrow \mathcal{H}$ to be $\phi(x) = K_x$ where $K_x$ is the reproducing kernel of the element $x \in \mathcal{X}$.

And then we have the kernel function:

$$K(x,z) = \langle \phi(x), \phi(z)\rangle_{\mathcal{H}}$$

Ok so far, I understand this as the "feature map" is a map from the set $\mathcal{X}$ to the hilbert space of functions $\mathcal{H}$.

However, in the example they provide, further down in section 4, they define $\phi(x)$ has a a vector in $\mathbb{R}^{10}$. This confuses me, as I thought that $\phi(x)$ should be an element of the hilbert space of functions $\mathcal{H}$ and not a vector.

Is it because, the vector represents a function by some linear combination of functions?

$\endgroup$
3
  • 1
    $\begingroup$ Yes, your guess is right. In the example, they're taking $\mathcal{X} = \mathbb{R}^3$ and $\mathcal{H}$ to be the Hilbert space of polynomial functions in $3$ variables of degree $\leq 2$, which is $10$-dimensional. So, while elements of $\mathcal{H}$ are polynomial functions, they can be represented as vectors in $\mathbb{R}^{10}$ (after choosing a basis for $\mathcal{H}$). $\endgroup$
    – Jesse Madnick
    Mar 12 at 19:41
  • 1
    $\begingroup$ Of course there's nothing special about $10$ here. In general, if $\mathcal{H}$ is an $n$-dimensional vector space (e.g., every RKHS is a vector space), then by choosing a basis of $\mathcal{H}$, elements of $\mathcal{H}$ can be represented as vectors in $\mathbb{R}^n$. $\endgroup$
    – Jesse Madnick
    Mar 12 at 19:45
  • $\begingroup$ Thanks for your comments. So given the degree 2 polynomial kernel, as it is a kernel we know there exists a RKHS such that the kernel is given by its reproducing kernel. But, why can we then rewrite the kernel $K(x,y) = \langle k_x, k_y \rangle_{\mathcal{H}}$ as an inner product in $\mathbb{R}^{10}$. $\endgroup$
    – Dylan Dijk
    Mar 13 at 16:24

1 Answer 1

Reset to default
3
$\begingroup$

That blog post uses (imo) ambiguous notations and terminology, so I totally understand your confusion.

The short answer is that the definition given in that blog post is wrong : for a given kernel $K$, a feature map $\varphi$ is a map from $\mathcal X$ to any Hilbert space $F$ (called a feature space) such that the following relation holds : $$K(x,y)=\langle\varphi(x),\varphi(y) \rangle_F \ \ \text{for all } x,y\in \mathcal X \tag1 $$ In particular, observe that $F$ needs not be equal to $\mathcal H$. (In fact, there always exist infinitely many feature maps and feature spaces for a given kernel $K$)

When we use the kernel trick to solve problems in practice, we don't really care about the feature map itself : the whole point of using kernel methods is that we can implicitly perform computations in $\mathcal X$ while implicitly using the higher dimensional representations in $F$.

Feature maps are however useful as they tell us the dimensionality of the space $F$ in which the computations are implicitly performed (and we know that more dimensions implies more representation power).

$\endgroup$
5
  • $\begingroup$ Thanks for your answer, it is starting to make more sense. But why can we write that: Given a kernel $K(x,y)$ $\; \exists \; \phi: \mathcal{X} \rightarrow F$ such that $K(x,y) = \langle \phi(x), \phi(y) \rangle_{F}$ . Is this related to Mercer's theorem? $\endgroup$
    – Dylan Dijk
    Mar 13 at 15:46
  • $\begingroup$ As so far from my knowledge of RKHS and Moore' Theorem we can only say that given a kernel $K(x,y)$ there exists a RKHS such that $K(x,y) = \langle k_x, k_y \rangle_{\mathcal{H}}$ . Where $k_x$ is a reproducing kernel of the element $x$. $\endgroup$
    – Dylan Dijk
    Mar 13 at 15:49
  • 1
    $\begingroup$ Well, a "trivial" feature map which is always guaranteed to exist is $\varphi : x \mapsto K(x,\cdot)\in\mathcal H$. Similarly, since for most practical cases, the RKHS $\mathcal H$ is separable, it is isomorphic to $\ell^2$ and you could thus find a feature map $\phi : \mathcal X \to \ell^2$ which represents $K$. So yes, there always exist feature maps, but the "most relevant" ones are the ones with feature space of least dimension, since they tell us how expressive the RKHS associated with $K$ is. $\endgroup$
    – Stratos supports the strike
    Mar 13 at 17:55
  • $\begingroup$ Ok thanks again that makes sense, so there exists multiple possible feature maps that give the same kernel, but a single unique RKHS. I was wondering if you knew anything about Mercer's theorem and how it relates to this topic, does it help with finding such feature maps that give the kernel? $\endgroup$
    – Dylan Dijk
    Mar 13 at 20:51
  • 1
    $\begingroup$ Yeah, Mercer's theorem is intimately related to kernel methods and the idea of implictly lifting the input space $\mathcal X$ to a feature space $F$. You should have a look at this blog post by Gregory Gundersen to learn further about this. $\endgroup$
    – Stratos supports the strike
    Mar 14 at 3:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .