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

Original solution basis:
A kd-Tree partitions spatial dimensions hierarchically, enabling nearest neighbor lookups in average O(d log N) time.

Deep Dive
A kd-tree recursively partitions a low-dimensional feature space using axis-aligned splits. During a query, entire regions can often be excluded, so the search visits far fewer than N points. The often-quoted O(d log N) behaviour is an approximate average-case description under favourable low-dimensional conditions, not a worst-case guarantee. In the worst case, search can approach O(Nd).

Key Points to Remember:
• kd-trees are most useful in low-dimensional spaces.
• Average query cost can be substantially below brute force, but depends on data and dimension.
• Worst-case nearest-neighbour search can still examine nearly all points.

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:
In high dimensions, volume grows exponentially and distance contrast disappears, forcing lookups to backtrack through nearly all nodes.

Deep Dive
In high dimensions, distances tend to become less discriminative: the nearest and farthest points may have similar distances. A kd-tree then cannot safely prune many regions, so it must backtrack and inspect much of the tree. The search approaches brute-force cost O(Nd). This is one manifestation of the curse of dimensionality.

Key Points to Remember:
• Distance concentration weakens spatial pruning in high dimensions.
• kd-tree performance is data- and dimension-dependent.
• Dimensionality reduction or approximate-neighbour methods may help.

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:
Naive Bayes assumes P($X_1$, $X_2$, ..., X_d | Y) = prod_{i=1}^d P(X_i | Y), vastly simplifying parameter estimation.

Deep Dive
Naive Bayes applies Bayes' theorem and makes the simplifying assumption that features are conditionally independent once the class is known. Thus P(X₁,...,$X_d$|Y=c)=ΠᵢP(Xᵢ|Y=c). This assumption is often unrealistic, but it makes parameter estimation and prediction computationally simple.

Key Points to Remember:
• Conditional independence is assumed given the class, not unconditional independence.
• The likelihood factors into a product of per-feature likelihoods.
• Naive Bayes can still classify well even when the assumption is imperfect.

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:
If P(x_i | c) = 0, multiplying conditionally independent probabilities makes P(X | c) = 0 regardless of all other strong matching features.

Deep Dive
Naive Bayes multiplies feature likelihoods. If one observed feature has likelihood zero for a class, the entire product becomes zero, regardless of the other features. This is the zero-frequency or zero-probability problem. Smoothing methods assign a small positive probability to unseen categorical events.

Key Points to Remember:
• A single zero likelihood makes the class-conditional product zero.
• The issue is common with sparse categorical/text data.
• Laplace/additive smoothing avoids zero estimates.

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:
Laplace smoothing adds 1 to numerator and V to denominator, ensuring non-zero estimates and valid probability sums.

Deep Dive
For a categorical feature with V possible values, add one pseudo-count to the observed value and add V pseudo-counts to the class total. The estimate is [count(xᵢ,c)+1]/[count(c)+V]. The denominator is adjusted by V because one count is added for each possible category. This is the multinomial categorical-feature form of add-one smoothing.

Key Points to Remember:
• Add-one smoothing adds 1 to each category count.
• The denominator increases by the number V of possible categories.
• For additive smoothing parameter $\alpha , use (count+\alpha )/(total+\alpha V)$.

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