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

Original solution basis:
Classification traverses down a single root-to-leaf path comparing 1 feature per node, taking O(D) operations where D is tree depth.

Deep Dive
A decision-tree prediction follows one path from the root to a leaf. At each node, it evaluates one split condition and chooses a child. If the maximum path depth is D, at most D such tests are performed, so prediction time is O(D), assuming each feature comparison is constant time.

Key Points to Remember:
• Prediction follows one root-to-leaf path, not every node.
• Time is O(D), where D is the depth.
• A balanced tree has depth around O(log N); a highly unbalanced tree may have depth O(N).

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:
Brute-force k-NN calculates distance from query point to all N training points in d dimensions, taking O(N d) operations.

Deep Dive
Brute-force k-NN computes the distance from the query to each of N stored examples. Each distance over d features costs O(d), so all distances cost O(Nd). Selecting the k smallest distances adds selection/sorting overhead, but the dominant distance-computation cost is O(Nd).

Key Points to Remember:
• Brute-force distance computation costs O(Nd).
• The d-dimensional feature comparison is repeated for all N training points.
• Spatial indexes can help in low dimensions, but may degrade in high dimensions.

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:
Hard-margin (C -> infinity) enforces strict zero slack xi_i = 0. If non-separable, no hyperplane satisfies all constraints simultaneously.

Deep Dive
A hard-margin SVM imposes yᵢ(wᵀxᵢ+b)$\ge 1$ for every training point, with no slack variables. If the data are not linearly separable, no hyperplane can satisfy all these constraints simultaneously, so the hard-margin optimization problem is infeasible. A soft-margin SVM is used when violations must be allowed.

Key Points to Remember:
• Hard margin requires perfect linear separability.
• Non-separable data make the hard-margin constraints infeasible.
• Soft margin introduces slack variables and a penalty parameter C.

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:
Linear models define boundaries via w^{T} x + b = 0, which forms hyperplanes in input space.

Deep Dive
A linear classifier predicts using the sign or threshold of wᵀx+b. Its decision boundary is wᵀx+b=0, a hyperplane in the input feature space. Linear SVM, logistic regression, and the perceptron all have this form, although their training objectives differ.

Key Points to Remember:
• A linear decision boundary is a hyperplane wᵀx+b=0.
• Linear SVM, logistic regression, and perceptron are linear classifiers.
• A kernel SVM can create nonlinear boundaries in the original input space.

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:
Multiplying probabilities of highly correlated features treats duplicate evidence as independent, overestimating posterior certainty.

Deep Dive
Naive Bayes multiplies conditional likelihoods as though features were independent given the class. If strongly correlated features carry overlapping information, the model may count the same evidence more than once. This can make posterior probabilities too extreme or poorly calibrated, even if the predicted class is sometimes still correct.

Key Points to Remember:
• Naive Bayes assumes conditional independence given the class.
• Correlated features can lead to duplicated evidence and overconfident posteriors.
• Classification accuracy can remain useful despite imperfect probability calibration.

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