GATE 2024 DA Q.17: solution and answer

Official answer: DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Positives: ${\mathbf{x}}_1=(1,0)$, ${\mathbf{x}}_2=(0,1)$, ${\mathbf{x}}_5=(2,2)$. Negatives: ${\mathbf{x}}_3=(0,-1)$, ${\mathbf{x}}_4=(-1,0)$, ${\mathbf{x}}_6=(-2,-2)$. The data are linearly separable, since $x_1+x_2\ge 1$ for every positive and $\le -1$ for every negative.

2. A hard-margin SVM finds the separating line with the largest margin. Equivalently, the boundary is the perpendicular bisector of the shortest segment joining the convex hull of the positives to the convex hull of the negatives.

3. Compute $x_1+x_2$ for each point. Positives: $1,1,4$ for ${\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_5$. Negatives: $-1,-1,-4$ for ${\mathbf{x}}_3,{\mathbf{x}}_4,{\mathbf{x}}_6$.

4. Take $\mathbf{w}=(1,1)$ and $b=0$. Then $y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)=1$ for $i=1,2,3,4$, and it equals $4$ for $i=5,6$. All constraints $y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)\ge 1$ hold, and the points with value exactly $1$ are ${\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,{\mathbf{x}}_4$.

5. Check that this is the maximum margin. The point $(0.5,0.5)$ lies on the segment ${\mathbf{x}}_1{\mathbf{x}}_2$ (in the positive hull) and $(-0.5,-0.5)$ lies on the segment ${\mathbf{x}}_3{\mathbf{x}}_4$ (in the negative hull). Their distance is $\sqrt{2}$, so no separating margin can be wider than $\sqrt{2}$. The solution above has margin width $2/\Vert \mathbf{w}\Vert =2/\sqrt{2}=\sqrt{2}$, so it is optimal. The hard-margin SVM solution is unique, so this is the trained classifier.

6. Support vectors are the training points lying exactly on the margin. Here these are ${\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,{\mathbf{x}}_4$. Indeed $\mathbf{w}={\sum }_i{\alpha }_i{y}_i{\mathbf{x}}_i=(1,1)$ is attainable, for example with ${\alpha }_1={\alpha }_2={\alpha }_3={\alpha }_4=\frac{1}{2}$, which also satisfies ${\sum }_i{\alpha }_i{y}_i=0$.

7. Options A, B and C each contain ${\mathbf{x}}_5$, but $y_5({\mathbf{w}}^{\top }{\mathbf{x}}_5+b)=4>1$, so ${\mathbf{x}}_5$ lies strictly outside the margin and cannot be a support vector. The answer is D.