GATE 2025 DA Q.53: solution and answer

Official answer: B, CSource: Official answer key, GATE 2025 DA (IIT Roorkee)

1. Label Class-1 as $y=+1$ and Class-2 as $y=-1$. The hard-margin SVM is: minimise $\frac{1}{2}\Vert w{\Vert }^2$ subject to $y_i(w^{\top }{x}_i+b)\ge 1$ for all four points.

2. The four constraints are: $(0,0)$ gives $-b\ge 1$, so $b\le -1$. $(2,0)$ gives $2w_1+b\ge 1$. $(0,2)$ gives $2w_2+b\ge 1$. $(2,2)$ gives $2w_1+2w_2+b\ge 1$.

3. Since $b\le -1$, the second constraint gives $w_1\ge \frac{1-b}{2}\ge 1$, and the third gives $w_2\ge \frac{1-b}{2}\ge 1$. Hence for every feasible $(w,b)$ we have $\Vert w{\Vert }^2=w_1^2+w_2^2\ge 2$.

4. The bound is attained at $w=(1,1{)}^{\top }$, $b=-1$. Check all constraints: $(0,0)$: $-(0-1)=1\ge 1$; $(2,0)$: $2-1=1\ge 1$; $(0,2)$: $2-1=1\ge 1$; $(2,2)$: $4-1=3\ge 1$. So this is the optimum, and it is unique because the minimum of $w_1^2+w_2^2$ over $w_1,w_2\ge 1$ occurs only at $(1,1)$.

5. Support vectors are the points whose constraint is tight, $y_i(w^{\top }{x}_i+b)=1$. These are $(0,0)$, $(2,0)$ and $(0,2)$; the point $(2,2)$ has value $3>1$, so it is not one. The number of support vectors is 3, so (B) is correct.

6. Margin width $=\frac{2}{\Vert w\Vert }=\frac{2}{\sqrt{2}}=\sqrt{2}$. Check: the line $x_1+x_2=1$ is at distance $\frac{1}{\sqrt{2}}$ from each of the two supporting lines $x_1+x_2=0$ and $x_1+x_2=2$, so the gap is $\sqrt{2}$. So (C) is correct.

7. (A) is false: with $w=(4,4{)}^{\top }$, $b=1$ the point $(0,0)$ gives $y(w^{\top }x+b)=-1\ngeqq 1$, so it is not even feasible (and it is not the optimum). (D) is false: the data are linearly separable, so the hard-margin SVM classifies all 4 points correctly, giving training accuracy $100\%$, not $98\%$ (with 4 points, accuracy can only be 0, 25, 50, 75 or 100 percent).