0

We know in a support vector machine:

enter image description here

Considering we have a linear feature mapping $\phi(x_n)=x_n$ and the XOR problem. We have 2 classes in $R^2$, class 1 $ t_+=+1$ 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?

Coordinates for $x_1=1,1; x_2=-1,-1; x_3=1,-1, x_4=-1,-1$?

user136542
  • 113
  • 5
  • this clearly depends on the coordinates of ${\bf x}_i$. Also, both ${\bf x}_i$'s and ${\bf w}$ should be vectors, so you'll have 3 equations. Then show that the equations have no solution. – PA6OTA May 18 '14 at 15:15
  • Considering x1= 1,1; x2=-1,-1; x3=1,-1; x4=-1,1.Can u show the start – user136542 May 18 '14 at 15:20

1 Answers1

0

the straight forward thing to do it is to assume that it is possible. Note that separability is something that is independent from the SVM. so we just have to proof, that there is no separating hyperplane and don't need to find an SVM solution. Thus we can optimize in the space of $w$.

This gives the following 4 inequalities the solution must satisfy:

$w^T x_1 +b > 0\\ w^T x_2 +b > 0\\ w^T x_3 +b < 0\\ w^T x_4 +b < 0$

now insert the coordinates of the points and try to solve for $w_1$ and $w_2$. You will see, that this is not possible.

Ulfi
  • 1