GATE DA Supervised Learning – Data Science & AI | Set 1

Original solution basis:
Large C heavily penalizes slack variables xi_i (narrower margin, fewer errors / potential overfit), while small C allows more margin violations (wider margin / potential underfit).

Deep Dive
The parameter C controls the penalty assigned to slack variables ξᵢ in the soft-margin objective. A large C makes violations expensive and encourages fewer training errors, often at the cost of a narrower margin and greater sensitivity to noise. A small C tolerates more violations and places relatively more emphasis on a wider margin.

Key Points to Remember:
• C controls the trade-off between margin size and training violations.
• Large C: stronger penalty for slack; small C: more tolerance.
• C is a regularization parameter and should be tuned using validation.

Exam tip:
Identify the governing definition or theorem first, write the formula, substitute the given values, and check dimensions/signs before selecting the option.

Original solution basis:
Support vectors satisfy y_i $(w^{T}$ x_i + b) <= 1 and have non-zero Lagrange multipliers alpha_i > 0. The decision boundary depends solely on them.

Deep Dive
Support vectors are the training points with nonzero Lagrange multipliers $\alpha ᵢ$. In the soft-margin formulation, these points lie on the margin or inside it (and may be misclassified). Points strictly outside the margin normally have $\alpha ᵢ=0$. The classifier's decision function is determined by the support vectors.

Key Points to Remember:
• Support vectors have $\alpha ᵢ>0$.
• For soft-margin SVM, they lie on or within the margin, including possible violations.
• Non-support vectors have zero dual coefficient and do not contribute to the decision expansion.

Exam tip:
Identify the governing definition or theorem first, write the formula, substitute the given values, and check dimensions/signs before selecting the option.

Original solution basis:
Kernel trick evaluates inner products K(x, y) in transformed space directly in O(d) time, avoiding explicit high-dimensional mapping $\phi(x)$.

Deep Dive
A nonlinear feature map \phi (x) may transform data into a higher-dimensional space where a linear separator is possible. The dual SVM formulation depends on inner products $\phi (xᵢ)ᵀ\phi (xⱼ)$. A kernel function computes this inner product directly as K(xᵢ,xⱼ), avoiding explicit construction of $\phi (x)$.

Key Points to Remember:
• Kernel trick replaces feature-space inner products with K(x,y).
• The feature mapping may be high- or infinite-dimensional.
• A valid kernel must satisfy positive-semidefinite Gram-matrix conditions.

Exam tip:
Identify the governing definition or theorem first, write the formula, substitute the given values, and check dimensions/signs before selecting the option.

Original solution basis:
RBF kernel is K(x, y) = \exp(- \gamma ||x - y||^2), corresponding to an infinite-dimensional feature space mapping.

Deep Dive
The Gaussian/RBF kernel assigns similarity according to squared Euclidean distance: K(x,y)=$\exp(-\gamma ||x-y||²)$, with $\gamma >0$. Identical points have similarity 1, and similarity decreases as their distance increases. A larger \gamma makes the influence more local and can create a more flexible decision boundary.

Key Points to Remember:
• RBF kernel: $\exp(-\gamma ||x-y||²)$.
• \gamma controls the width/locality of the Gaussian similarity.
• RBF is a widely used positive-semidefinite kernel for $\gamma >0$.

Exam tip:
Identify the governing definition or theorem first, write the formula, substitute the given values, and check dimensions/signs before selecting the option.

Original solution basis:
By Mercer's Theorem, K is a valid kernel iff for any finite set of points, the kernel Gram matrix is symmetric positive semi-definite.

Deep Dive
For any finite set x₁,...,xₙ, form the Gram matrix with entries Kᵢⱼ=K(xᵢ,xⱼ). A valid real-valued Mercer kernel must produce a symmetric positive-semidefinite Gram matrix for every such set. Positive semidefinite means zᵀKz$\ge 0$ for every vector z. This condition ensures the kernel behaves like an inner product in some feature space.

Key Points to Remember:
• Kernel Gram matrix must be symmetric positive semidefinite.
• PSD means all eigenvalues are nonnegative, not necessarily strictly positive.
• A kernel need not be bounded between 0 and 1 or strictly positive at every pair.

Exam tip:
Identify the governing definition or theorem first, write the formula, substitute the given values, and check dimensions/signs before selecting the option.