A two-point machine

Topic: Support vector machines · more questions on this topic
‹ Distance to a hyperplane Which points matter? ›

Points x_1=(3,3) with y_1=+1 and x_2=(1,1) with y_2=-1. Solve the hard-margin dual: find \alpha_1=\alpha_2, w, b, and the margin. Verify that the margin equals the distance between the points.

Worked answer (click to show)

The constraint \sum_i\alpha_i y_i=0 forces \alpha_1=\alpha_2=\alpha. Then w=\alpha\bigl[(3,3)-(1,1)\bigr]=\alpha(2,2) and

Q(\alpha)=2\alpha-\tfrac12\alpha^2\lVert x_1-x_2\rVert^2=2\alpha-4\alpha^2,

since \lVert(2,2)\rVert^2=8. The maximum is at \alpha=\tfrac14. So w=(0.5,0.5)^\top, and from the support vector x_1,

b=y_1-w^\top x_1=1-3=-2.

Check with x_2: y_2(w^\top x_2+b)=-(1-2)=1. The margin is

\frac{2}{\lVert w\rVert}=\frac{2}{0.7071}=2.828=\sqrt{8}=\lVert x_1-x_2\rVert.

With only two points the separator is the perpendicular bisector of the segment joining them. The boundary is 0.5 x_1+0.5 x_2=2, that is x_1+x_2=4.