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

Original solution basis:
Attributes with many unique values (like Customer ID) yield pure single-item subsets with zero entropy, maximizing Information Gain spuriously. Gain Ratio normalizes by Split Information.

Deep Dive
Information Gain can favour attributes with many distinct values. An identifier-like feature may split the training data into many tiny or single-example groups, producing very low child entropy without providing useful generalization. Gain Ratio divides Information Gain by Split Information, penalizing splits that fragment the data excessively.

Key Points to Remember:
• Gain Ratio = Information Gain / Split Information (when SplitInfo is nonzero).
• It reduces the many-valued-attribute bias of Information Gain.
• A very small SplitInfo requires care because the ratio can become unstable.

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:
SplitInfo measures potential information generated by splitting dataset S into partitions S_v based on attribute A.

Deep Dive
Let $p_v$=|$S_v$|/|S| be the fraction of samples sent to branch v. Split Information is -$\Sigma _v p_v log₂p_v$. It measures how broadly the attribute divides the data, independently of class labels. C4.5 uses it as the denominator in Gain Ratio.

Key Points to Remember:
• SplitInfo = -$\Sigma _v p_v log₂p_v$.
• It depends on branch proportions, not class impurity within branches.
• Gain Ratio = IG/SplitInfo, provided SplitInfo is nonzero.

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:
Post-pruning builds a full tree and then removes branches that increase validation error or minimize cost-complexity loss $R_{alpha}$(T) = R(T) + $\alpha |T|$.

Deep Dive
Post-pruning first grows a relatively large tree and then removes branches that do not improve validation performance or the chosen complexity criterion. In cost-complexity pruning, a common objective is R$\alpha (T)=R(T)+\alpha |T|$, where R(T) measures tree error and |T| measures tree size. Increasing $\alpha places a stronger penalty on complexity$.

Key Points to Remember:
• Pre-pruning stops growth early; post-pruning trims a grown tree.
• Cost-complexity pruning balances fit against tree size.
• The pruning strength is selected using validation or cross-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:
For continuous feature X, unique values are sorted x_1 < x_2 < ... < x_n and candidate splits t_i = (x_i + x_{i+1})/2 are evaluated for best impurity reduction.

Deep Dive
For a continuous feature, sort its observed values. Candidate thresholds are commonly placed between consecutive distinct sorted values, such as tᵢ=(xᵢ+xᵢ₊₁)/2. For each candidate, partition samples into values on either side and calculate the impurity reduction. The best threshold is selected according to the tree's splitting criterion.

Key Points to Remember:
• Continuous splits use threshold tests such as xⱼ$\le t$.
• Midpoints between adjacent sorted values are candidate thresholds.
• The chosen threshold maximizes impurity reduction or minimizes the relevant regression loss.

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

Deep Dive
A hard-margin linear SVM seeks the separating hyperplane wᵀx+b=0 with the largest geometric margin. The two supporting hyperplanes are wᵀx+b=1 and wᵀx+b=-1. Their perpendicular separation is 2/||w||, so maximizing the margin is equivalent to minimizing (1/2)||w||² subject to yᵢ(wᵀxᵢ+b)$\ge 1$ for every training example. This assumes the data are linearly separable.

Key Points to Remember:
• Hard-margin objective: minimize (1/2)||w||².
• Constraints: yᵢ(wᵀxᵢ+b)$\ge 1$.
• Margin width between support hyperplanes is 2/||w||.

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