0
$\begingroup$

I understand that the point of using the kernel trick is to project the problem onto a higher dimensional space, where the problem is linearly separable. In this explanation, https://www.quora.com/What-is-the-kernel-trick, it states that the inner product $\langle x,y \rangle$ will be equal to $\langle \phi(x),\phi(y)\rangle$. Understanding this equality seems to be key to understanding how this trick works.

My question is, how do know that our function $\phi$ will preserve the inner product and what are the conditions for this to happen?

I have tried google searching this and despite many references to the kernel trick, I do not believe that this has been answered anywhere.

$\endgroup$

1 Answer 1

1
$\begingroup$

It doesn't mean that $\langle x, y \rangle = \langle \phi(x), \phi(y)\rangle$.

Kernel method in general means that for an algorithm that involve $\langle x, y\rangle$, we can replace it with a function $K(x,y)=\langle \phi(x), \phi(y)\rangle$ where computing $K(x,y)$ is easy. It is known that for $K$ that satisfies Mercer's theorem, there is a corresponding $\phi$ which is the map to the higher dimensional space.

We do not need to know $\phi$ explicitly and $\phi$ can be very complicated.

$\endgroup$
6
  • $\begingroup$ what gives you the right to replace with $K(x,y)$? Also are you saying that the equality in the guys post is by chance? $\endgroup$
    – Trajan
    Commented Sep 22, 2019 at 8:11
  • $\begingroup$ for some algorithms, we might find that it just involve inner product with some features space, in that case, rather than computing $\langle x, y \rangle$, that is working with $x$ directly, we might like to perform a transformation $\phi(x)$, and then work with it. Since it just involves inner product, what matters is just $\langle \phi(x), \phi(y) \rangle$, and we can compute it via $K(x,y)$ and we don't really care about $\phi$ explicitly sometimes. As for the "by chance" thing, I might need you to be more explicit. $\endgroup$ Commented Sep 22, 2019 at 8:17
  • $\begingroup$ what is the justification for be able to swap to $K(x,y)$? $\endgroup$
    – Trajan
    Commented Sep 22, 2019 at 9:59
  • $\begingroup$ The justification is rather than working with $x$ directly, we want to work with $\phi(x)$, for example, rather than working with $x$, you might want to work with $(x, x^2)$. Then you want to work with inner product of $(x, x^2)$ and $(y, y^2)$, this is denote as $K(x,y)= \langle (x, x^2), (y, y^2) \rangle$. $\endgroup$ Commented Sep 22, 2019 at 10:05
  • $\begingroup$ Yes but why can you swap $x$ for $\phi(x)$? What are the requirements on $\phi$? $\endgroup$
    – Trajan
    Commented Sep 22, 2019 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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