Conceptual Understanding of Kernels

Question

I'm currently reading up on Kernels specifically related to SVM. My understanding of Kernels is that the data points are projected to another dimension and an SVM run on these new values.

My understanding seems to fall down on how the initial kernel values are created. From my reading it seems that the first step is to create a value 'l' for every single x value and then get a similarity score (Kernel score using a Gaussian formula) between the actual value x and the value of l. This seems to be done for each value of x for every single value of y.

So for example if I have 3 attributes, I have 3 values for 'l'. I get a similarity score (the kernel) between the three values of x and every single value of y resulting in a 3*3 comparison. I then put the results into a vector and use that vector when minimizing my cost function for SVM.

My questions are:

• Is my understanding correct?
• Does this mean that if I had not used the kernel I would have had 3 attributes to estimate parameters against? On the flip side with the kernel function in play would I have nine?

Thank you kindly for your time

Answer 1

Sort of, but not quite.

Suppose you have a two-dimensional feature space, that is, for each item (that can get classified as '+' or '-') you have a tuple with two values: ($x_1, x_2$). Now suppose you have a kernel like the polynomial kernel, $K(x,y)=(x^Ty+c)^d$. If c is zero, and d is 2, then when we have two input vectors $(x_1,x_2)$ and $(y_1,y_2)$ their representation in the expanded feature space is $$(x_1y_1+x_2y_2)^2=x_1^2y_1^2+2x_1y_1x_2y_2+x_2^2y_2^2$$

As you can see, there are three terms in the new feature space. But imagine if $d$ were a much larger number, like 100. Then the number of terms would be huge in the feature space. In fact, it is possible to have an $infinite-dimensional$ feature space. How big the vectors/inner product are in the feature space is driven by the kernel you choose.

The amazing thing is that we can compute the inner product in the feature space without going into it - and all its dimensions - by applying the kernel function on our current space.

The math of why this works gets a little deep and mysterious; why the 'kernel trick' seems to work so often has to do with positive semi-definiteness and the Mercer condition.

I think this professor at Cal Tech does a great job explaining it; I love his 'guardian of the feature space' metaphor: https://www.youtube.com/watch?v=XUj5JbQihlU