10
$\begingroup$

I am attempting to use SVMs for my class project. For this project, I have selected the gaussian kernel as, well, the kernel. That is,

$$ k(\mathbf{x}_1, \mathbf{x}_n) = e^{-\gamma ||\mathbf{x}_1 - \mathbf{x}_n ||^2} $$

What I do not understand, is how this kernel is then 'written as a dot-product'. How do we get around doing that? This is because my professor says that when we finalize the training, we will be performing a dot-product between a new vector and the SVs. But given this kernel, how is this dot-product being done?

Improve this question
$\endgroup$
5
  • $\begingroup$ I recommend reading up about reproducing kernel Hilbert spaces (RKHS). That should help you understand that a great many things can be a dot product in some feature space. $\endgroup$
    – Marc Claesen
    Commented Nov 10, 2014 at 15:51
  • 2
    $\begingroup$ @MarcClaesen Thanks for the link I will read up on it. What appeared to be confusing me was the fact that the computer isn't doing an explicit dot-product in code, whereas my professor was adamant that it was; I now understand that what is meant is that it a "dot-product equivalent in some other feature space". Cheers! $\endgroup$
    – Spacey
    Commented Nov 10, 2014 at 15:53
  • 1
    $\begingroup$ A better term would be "inner product", which is defined over abstract vector spaces. $\endgroup$
    – Arthur B.
    Commented Nov 10, 2014 at 16:50
  • $\begingroup$ @ArthurB. Yeah, it could have been better phrased by the prof. $\endgroup$
    – Spacey
    Commented Nov 10, 2014 at 18:53
  • 2
    $\begingroup$ Your answer is here: youtube.com/watch?v=XUj5JbQihlU&t=25m53s The idea is expanding based on a series of infinite size. $\endgroup$
    – Daniel
    Commented Nov 12, 2014 at 9:54

2 Answers 2

Reset to default
8
$\begingroup$

Look up "kernel trick". The idea is that, under certain conditions (Mercer's condition), a function $k(x,x')$ can be expressed as a dot product $<\phi(x),~\phi(x')>$, where $\phi$ is a function that transforms $x$ into a high dimensional (possibly infinite) representation.

The trick is that, as long as your optimization problem can be expressed solely with dot products, you do not need to know or compute $\phi$, you simply use the kernel function $k$.

More details on Wikipedia

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ It is not known explicitly, the entire point of the technique is that you don't need to ever calculate $\phi$ or know what $\phi$ is. However, there has been some work to find approximations for the Gaussian kernel, to speed up computation, see for instance arxiv.org/pdf/1109.4603v1.pdf For all intent and purposes, if you're starting with SVM, the message should be: "we know that $\phi$ exists but we don't know exactly what it is, nor do we need to calculate it, and that's great" $\endgroup$
    – Arthur B.
    Commented Nov 10, 2014 at 15:16
  • 1
    $\begingroup$ Arthur, I see. However that means, that when we compute - when the computer literally computes - what a new vector $x_1$ is based on a trained SVM model, the computer is NOT doing a dot product anywhere? Is that correct? By that I mean, that the computer is actually going to be explicitly_ doing $e^{-\gamma ||\mathbf{x}_1 - \mathbf{x}_n ||^2}$? It confuses me because my professor is saying that in SVM classification (post-training) we are computing "the dot products of the input vector with the support vectors". This is my main point/question. Thanks again $\endgroup$
    – Spacey
    Commented Nov 10, 2014 at 15:26
  • 1
    $\begingroup$ Ah! Ok, yes that is somewhat confusing! He should say that through the RBF, we are effectively performing a dot-product, but the actual computation is not an explicit dot product. Thanks for your help! Please incorporate those details into your answer so I can accept it. $\endgroup$
    – Spacey
    Commented Nov 10, 2014 at 15:47
  • 3
    $\begingroup$ Good answer (+1), but a few things: kernels are typically used to map onto a higher dimensional feature space, but in fact most kernels do not correspond to an infinite-dimensional feature space (RBF does). Secondly, explicit representations may or may not be known but as you correctly said they are not necessary (for the RBF kernel the analytical form of $\phi(\mathbf{x})$ is known (but infinite dimensional)). $\endgroup$
    – Marc Claesen
    Commented Nov 10, 2014 at 15:57
  • 4
    $\begingroup$ @Tarantula no, it means that the feature space that is being mapped to is infinite dimensional, e.g. $\phi(\mathbf{x})$ has infinitely many dimensions (but thanks to the kernel trick we never need to compute it explicitly). The polynomial kernel, for instance, maps to a finite dimensional feature space (degree-2 polynomial kernel maps to a feature space that uses all interactions and squares of inputs, for instance). $\endgroup$
    – Marc Claesen
    Commented Nov 10, 2014 at 16:51
5
$\begingroup$

Once you derive this term: $$ k(\vec x, \vec y) = e^{-\gamma ||\vec x - \vec y ||^2} $$

you get terms that only depend on $\vec x$, terms that only depend on $\vec y$, and terms that are mixed.

The terms that separate nicely, aren't a problem, as you could write them as a dot product.

e.g. in the simple case where x is 1-D:

$$ k(\vec x, \vec y) = e^{-\gamma ||x - y ||^2} = e^{-\gamma (x^2 -2xy + y^2)} \\ e^{-\gamma (x^2 + y^2)} = e^{-\gamma (x^2)} e^{-\gamma (y^2)} $$

Here you see the separate terms can be separated into a (dot) product.

The terms that are mixed are a problem - but the trick is to use Taylor series to separate them into an infinite series of products:

$$ e^{2\gamma xy} = \sum_{k = 0}^{\infty} \frac{(2\gamma xy)^k}{k!} $$

Here $x, y$ are products. So the gaussian kernel can be written as the dot product between the following vectors:

$$ e^{-\gamma (x^2)}<1, \sqrt{2 \gamma}x, \frac{2 \gamma x^2}{\sqrt 2}, ...> \cdot e^{-\gamma (y^2)}<1, \sqrt{2 \gamma}y, \frac{2 \gamma y^2}{\sqrt 2}, ...> $$

Improve this answer
$\endgroup$

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.