How to find max margin for non-separable SVM? I am new to Machine Learning. Suppose a training set of positive (square) and negative (circle) points is given like:



Obviously there would be no nice linear separator of positive and negative points. So assume there exist a transformation for (x1,x2) points as:
y1 = (x1-5)^2, y2 = (x2-5)^2 in (y1,y2) space. We will then map all positive points to (25,25) and all negative points to (1,1).

Now, the question is how can I find the maximum-margin separator in new space? That is, what curve in the original space transforms to the straight-line boundary in the transformed space? Using that I need to determine that should a new point be considered positive or negative.
Map all the points to the new space.  Then find the maximum-margin linear separator of those mapped points.  Algorithms for finding a maximum-largin linear separator are described in the literature on SVMs (that's exactly what you need to do to train a linear SVM).  In other words, you can map the points to the new space, then can take those mapped points and train a linear SVM on them.  That's conceptually how to do it.

In practice, nonlinear SVMs use clever tricks to do the same thing, but do it faster (using the kernel trick).