1
$\begingroup$

I was studying SVM ML alghorythm and I was wondering about solution for non-linear cases. As I understand it for know, SVM tries to find hyperplane or object in defined n-dimensional space, which separates datapoints according to their classes.

This object has n-1 dimensions, so if there are two features (feature space is 2-dimensional), then hyperplane is actually just line splitting this space.

However, in many cases it is not possible to separate data linearly, and this in case a projection to higher-dimensional space can sometimes help, because then the possibility that data will be linearly separable is higher.

Also, i read about radial basis function and RBF kernel. As i understand it, the purpose of kernel, is to make computation more efficient (here is the first place where i have doubts whether i understand it correctly). But i dont want to ask about kernel, the most important question is about the radial basis function itself.

From what i read it seems to me that this function uses some radius around each data point belonging to one of the classes, and then elevates this point to another dimension, while creating some margin around it, specified by that radius (size of that radius is called gamma). To define shape of the margin, some other function (for example Gaussian) is used.

I also tried to simulate it via some graphs:

First i created very simple dataset with one feature (position on x) and two classes (green and purple):

enter image description here

Because our feature space is 1-dimensional, the hyperplane splitting this space should be just a point (0-dimensional). As you can see, it is not possible to separate data that way - there is no point which could separate data into purple and green groups.

So i decided to elevate (or project?) datapoints of one class (if it would be projection of both, it would not made any change, am i right?) to second dimension - on y axis (red points):enter image description here

Now I created Gaussian RBF (the blue line), using formula which i found on Wikipedia: enter image description here

Here is formula which i used (x2 are red points, h is gamma parameter):

enter image description here

I have several questions what to do next/how to understand it:

1) How hyperplane (line in this case) is set now? Would not be better to use guassian function (the blue line) as a "separator" of what should belong to green/purple class?

2) If this "cheat" with projection to another space is used, isn't it completely messing the original purpose of support vector machines and leading to immediate overfitting? This seems like using target variable as a regular feature, which should be unacceptable (the only acceptable information is distribution on x axis, which may be similar with test dataset, and thus it can be important information)

3) Isn't this very similar to KNN classifier? Like KNN uses closest neighbors - position in space generated by features, this way - RBF - also tries to guess class using the position of sample in space generated by features)

4) The most important one I really suspect myself, that i completely misunderstood whole concept of RBF, because my intuition tells me that the way I did it is much more stupid than it should be, so please, dont get angry if whole concept of my understanding is wrong. Thats why i am asking here.

$\endgroup$

1 Answer 1

1
$\begingroup$

One thing has to be said at the beginning RBF is not classification algorithm. It is used in SVM as a kernel, because it has properties of the kernel. SVM doeas all the work with finding hyperplane. I said that because you often mix them :"RBF - also tries to gues class". No, RBF only measures the similarity.

Ad.1 Finding hyperplane in SVM is done by maximizing the margin between 'classes'. This is linear programming problem. As most problems are not separable in their original dimension, kernel trick is used. Kernel is projecting(automatically) data points to higher dimension where hyperplane can be found. RBF is used as a kernel function in SVM. Its great feature is that it is projecting data to infinite dimension. There you are finding the hyperplane separating classes, and project back to your dimension. Most importantly, to understand kernels, you have to be aware that kernel is measuring similarity between points. The greater the value, more similar points are. Gaussian RBF is doing great job in this.

Ad.2 it is not cheating, as we are not using information from the target. Only data to build kernel is similarity between data points, but in higher dimension.

Ad.3 You have great intuition. In fact SVM with Gaussian RBF can be called smooth KNN. It is because SVM+RBF is drawing Gaussian RBF around every data point, which is smooth bump with radius defined by gamma. While Knn is drawing sphere around every point with radius defined by distance to k nearest neighbors. This also clear when we look at math formula of SVM dual problem:

enter image description here

and KNN:

enter image description here

Ad.4 I don't understand this question. RBF is just a function. SVM uses it as a kernel, to 'send' points to infinite dimension(this is because Taylor expansion of this function is infinite, but can be easily calculated).

Anyway, in your case, first thing you do is to calculate kernel matrix with GRBF: enter image description here

in python:

K = np.apply_along_axis(lambda x1 : np.apply_along_axis(lambda x2: GRBF(x1, x2), 1, X),
                          1, X)

When you plot the first row you will see that further points have less influence on the assigned label: enter image description here

If you recall the formula of SVM dual, you will see that those kerne values will be multiplied by target values y_i. That means, closer points have bigger impact on overall sign. And decision boundary will look like this: enter image description here

$\endgroup$

Your Answer

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

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