Nonlinear separation of XOR

Topic: Support vector machines · more questions on this topic
‹ A unit-norm constraint

The four XOR observations (0,0), (1,0), (0,1), (1,1) are labelled -1, +1, +1, -1. Consider the feature map \phi(x)=(x_1,x_2,x_1 x_2)^\top.

  1. Explain why a linear separator in the original two predictors is impossible.

  2. Show that f(x)=x_1+x_2-2x_1 x_2-1/2 correctly classifies the four observations by its sign.

  3. Explain how a linear separator in feature space can have a nonlinear boundary in the original space, and what a kernel supplies.

  1. The positive and negative convex hulls intersect at the centre of the square. No affine line can strictly separate them.

  2. The scores at (0,0), (1,0), (0,1) and (1,1) are -1/2, +1/2, +1/2 and -1/2, matching the labels -1,+1,+1,-1.

  3. In feature space, f=w^\top\phi(x)+b with w=(1,1,-2)^\top. Composing with a nonlinear \phi gives a nonlinear equation in x. A valid kernel evaluates feature-space inner products K(x,z)=\langle\phi(x),\phi(z)\rangle without necessarily constructing the features explicitly. This supports the optimisation and the prediction. It does not choose a kernel or the tuning parameters.