GATE 2025 DA Q.22: solution and answer

GATE 2025 · DAQ.22 · 1 mark · MCQ

Consider designing a linear classifier $y = sign (f (x; w, b))$ , $f (x; w, b) = w^{⊤} x + b$ on a dataset $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{N}, y_{N})}$ , $x_{i} \in R^{d}$ , $y_{i} \in {+ 1, - 1}$ , $i = 1, 2, \dots, N$ . Recall that the sign function outputs $+ 1$ if the argument is positive, and $- 1$ if the argument is non-positive. The parameters $w$ and $b$ are updated as per the following training algorithm: $w_{n e w} = w_{o l d} + y_{n} x_{n}$ , $b_{n e w} = b_{o l d} + y_{n}$ whenever $sign (f (x_{n}; w_{o l d}, b_{o l d})) \neq = y_{n}$ . In other words, whenever the classifier wrongly predicts a sample $(x_{n}, y_{n})$ from the dataset, $w_{o l d}$ gets updated to $w_{n e w}$ , and likewise $b_{o l d}$ gets updated to $b_{n e w}$ . Consider the case $(x_{n}, + 1)$ , $f (x_{n}; w_{o l d}, b_{o l d}) < 0$ . Then

(A)
$f (x_{n}; w_{n e w}, b_{n e w}) > f (x_{n}; w_{o l d}, b_{o l d})$
(B)
$f (x_{n}; w_{n e w}, b_{n e w}) < f (x_{n}; w_{o l d}, b_{o l d})$
(C)
$f (x_{n}; w_{n e w}, b_{n e w}) = f (x_{n}; w_{o l d}, b_{o l d})$
(D)
$y_{n} f (x_{n}; w_{o l d}, b_{o l d}) > 1$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct option is (A): after the perceptron update the score at $x_{n}$ rises by $∥ x_{n} ∥^{2} + 1$ , so $f (x_{n}; w_{n e w}, b_{n e w}) > f (x_{n}; w_{o l d}, b_{o l d})$ .

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

The sample has $y_{n} = + 1$ and $f (x_{n}; w_{o l d}, b_{o l d}) < 0$ . The sign function then outputs $- 1 \neq = y_{n}$ , so the sample is misclassified and the update fires: $w_{n e w} = w_{o l d} + x_{n}$ and $b_{n e w} = b_{o l d} + 1$ .
Evaluate the new score at the same point $x_{n}$ : $f (x_{n}; w_{n e w}, b_{n e w}) = (w_{o l d} + x_{n})^{⊤} x_{n} + b_{o l d} + 1.$
Expand: $f (x_{n}; w_{n e w}, b_{n e w}) = w_{o l d}^{⊤} x_{n} + b_{o l d} + x_{n}^{⊤} x_{n} + 1 = f (x_{n}; w_{o l d}, b_{o l d}) + ∥ x_{n} ∥^{2} + 1.$
Since $∥ x_{n} ∥^{2} \geq 0$ , the increment $∥ x_{n} ∥^{2} + 1 \geq 1 > 0$ . The score therefore strictly increases: $f (x_{n}; w_{n e w}, b_{n e w}) > f (x_{n}; w_{o l d}, b_{o l d})$ . This is option (A).
Options (B) and (C) contradict this strict increase. Option (D) is false, because $y_{n} f (x_{n}; w_{o l d}, b_{o l d}) = f (x_{n}; w_{o l d}, b_{o l d}) < 0$ , which is not greater than $1$ .

KEY IDEA

A perceptron update on a mistake always moves the score at that sample toward the correct side. For $y_{n} = + 1$ the score changes by $y_{n} (∥ x_{n} ∥^{2} + 1) = ∥ x_{n} ∥^{2} + 1 > 0$ . In general, the change in $f (x_{n})$ is $y_{n} (∥ x_{n} ∥^{2} + 1)$ .

WATCH OUT FOR

Assuming one update must fix the misclassification, or confusing the increase with $f_{n e w} > 0$ . The score increases by $∥ x_{n} ∥^{2} + 1$ , but the new score may still be negative. Another slip is forgetting the bias update, which contributes the extra $+ 1$ , or choosing (D), which wrongly asserts a margin condition on the old score.

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 5 Neural networks questions, with notes

GATE 2025 DA Q.22: solution and answer

Answer and solution

More Neural networks questions