How does the shape of a decision boundary in relate between the original and kernel feature space?

Question

I'm trying to get my head around the mathematics and implementation of SVM and hopefully gain some intuition into how kernels work and perhaps being able to, with a bit more confidence, define my own kernel.

So far, what I understand (and I might be wrong) is that kernels map the samples in the training set into higher dimensions where the classes in the training set are linearly separable. We can then, in this new dimension use a hyperplane to separate the classes. A hyperplane is, for example, a straight line, in 2 dimensions, or a flat surface (a plane), in 3 dimensions.

Questions

If the original feature space is in 2 dimensions and the mapping is to 3 dimensions, then, in short, I'm wondering:

• When mapping a training set, generated around a quadratic function, which originally has features in the form $(X,Y)$ to $(X,Y,X^2)$, see below, doesn't seem linearly separable when plotted in a 3D space. Yet the decision boundary in the original space makes a perfect parabola and classifies samples correctly. How come?
• Can we and, if so, how can we visualize the decision boundary as it looks in the "extended" feature space? Can we then see how the looks in the extended feature space relate to the looks original space?

Experiment

In order to get some image of what this looks like I attempted the following, see github for more details:

• Generated 130 data points around a simple quadratic equation (2 features),
• Points above the quadratic curve were assigned one class points below another. With a very small overlap between the classes.

• Knowing that the shape of the decision boundary was a quadratic equation I defined a kernel (for sci-kit learn's SVC) where I added a third dimension by squaring the X coordinate. I understand this as extending the feature space, from the book I'm following. The code for the kernel looks like this:

  def custom_non_linear_kernel(X,Y):
      new_dim_x = np.power(X[:,0:1],2)
      new_dim_y = np.power(Y[:,0:1],2)
      X = np.append(X,new_dim_x, axis=1)
      Y =  np.append(Y,new_dim_y, axis=1)
      return np.dot(X,Y.T)
  

  My thinking was that this would basically creates a linear kernel (and therefore a linear classifier?) but in 3 dimensions rather than 2.

A linear SVC in 3 dimension would, in my mind, be a plane but if one plot the data when mapped in 3 dimensions one get this: And I can't really see how one could separate the two classes (red and blue) with a flat plane. In fact if I try to create a linear classifier on this extended dataset, rather than using the kernel created, I get the following: Which doesn't separate the classes very well.

The kernel does seem to work though, when plotting the decision boundary in the original feature space I get: Where the top right plot is using the kernel I described. It correctly classifies everything under a quadratic function as one class and data above as the other class.

What is happening here, I'm sure I've misunderstood something but what?

EDIT: An extra thought, I was wondering whether this has to do with the basis I'm using for the extended feature space, is there some assumption one has to do when choosing the basis for it?

Answer 1

I am also learning the SVM and a novice. In your case, this is my thought:

Initially you had two points (X,Y) in 2D space. When you transform into feature space(3D in your case), I believe you don't have to add X² term to the existing variable. The X² term is an extra coordinate to identify your 2 D points in 3 D. Here X² can be considered as a point in 3rd axis to identify the points in 2D.

The way I understood the relation between feature space and original dimension is by the following example. Consider you want to create separation between two gender(Male and Female) by their age and height. You can easily plot them 2D. But on plotting you see that the separation between these two genders are not clear. So we transform it to feature space. By saying feature space, I mean that probably we can find a weight in 3D or an extra parameter in another dimension so that we can distinguish between the the two classes. Here weight can be considered as a feature.

You are including a third coordinate along with your existing 2 coordinate and asking how to draw a separation among these three coordinate which I think is not the right way to interpret. You still be having two classes in third dimension but your third coordinate might help you to distinguish the two classes by drawing better plane. In this case X².