5
$\begingroup$

The kernel trick gets used very heavily in SVMs. And it is impressive: not only can you get the inner product in a larger-dimensional space (including an infinite-dimensional one) that comes from a transform $\phi$ through calculations solely in the lower dimensional space, but you can do it without ever even knowing the actual mapping.

It is easy enough to see that you have all the 'ingredients' in the lower dimensional space. For example, if you have vetors $[x,y]$, and $\phi$ is the mapping $\phi [x,y]\to [x, y, xy]$, anything you calculate (like an inner product) in the transformed space is still a function only of $x$ and $y$.

But it seems there must be some deeper mathematical structure or formalism that guarantees that inner products in the bigger space are calculable in the smaller.

In actual examples, one often posit the kernel function (which is what we are looking for) to start. So, someone says $K(x,y)=\phi(x) \cdot \phi(y)) = (x \cdot y)^2$. If the original space if 2 dimensions, then $K(x,y)=(x1y1+x2y2)^2=x_1^2y_1^2+2\cdot x_1x_2y_1y_2+x_2^2y_2^2$.

This corresponds to a $\phi$ of $\phi(x)=[x_1^2, x_2^2, \sqrt{2x_1x_2}]$ and $\phi(y)=[y_1^2, y_2^2, 2y_1y_2]$, whose inner product is, indeed, the same as comes from the stipulated kernel function, $K(\cdot ).$

Is this something blindingly obvious I am missing, or is there something more profound that always guarantees a mapping, $\phi$, will always exist? It feels like some relationship between vector spaces, inner products, and polynomials is lurking around here.

By way of metaphor, it is almost like if we wanted to calculate the 'trace' of a vector by adding its components. Obviously the mapping from 2 dimension to 4 of $[x,y]\to [x, y, x-y, y-x]$ would not change the trace because the elements of both add to $x+y$, with the last two terms in 4-space cancelling each other out. But that was manufactured. Kernels seem to rely on some symmetry or constraint that makes them always work out.

$\endgroup$
  • 2
    $\begingroup$ The deeper, more profound, math is embodied in Mercer's theorem and Reproducing Kernel Hilbert Spaces; here is a nice introduction: cs.cmu.edu/~epxing/Class/10715/lectures/lecture6.pdf $\endgroup$ – jbowman Oct 19 '17 at 0:56
  • $\begingroup$ Greatly appreciated. $\endgroup$ – eSurfsnake Oct 19 '17 at 3:45
  • $\begingroup$ Fantastic find on your part. $\endgroup$ – eSurfsnake Oct 19 '17 at 5:16

Your Answer

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

Browse other questions tagged or ask your own question.