4 points not separable by SVM

Question

We know in a support vector machine:

Considering we have a linear feature mapping $\phi(x_n)=x_n$ We have 2 classes, class 1 $ t_+=+1$ the XOR problem and class 2 $t_-=-1$ and 4 points where $x_1, x_2$ are from class1 and $x_3, x_4$ are from class2.

Therefore we can write, $w=a_1x_1+a_2x_2-a_3x_3-a_4x_4$ and $a_1+a_2-a_3-a_4=0$

How can we prove the 4 points are not separable?

Answer 1

This has nothing to do with SVM, XOR is not linearly separable, which can be prooved in various ways. SVM is in particular, a linear model (for this phi function) so if there is no linear discriminator for this points, than SVM also cannot discriminate them.

The simplest proof goes like this:

1. Take a middle point (the one in the center of your four points), call it x
2. x lies on the convex hulls of both positive and negatives classes
3. Linear model separates space into convex subspaces
4. Take any linear model that correctly classifies both positive and negative points (your XOR), it now has to give the same label to each of the point inside of the convex hull, so x should have both positive and negative label, contradiction