Tree-Based & Instance Methods

Q1. (4 marks) — 1 mark each

• (a) Root node: the topmost node containing the entire dataset before any split.
• (b) Leaf node: a terminal node with no children that outputs a prediction (class/value).
• (c) Splitting: partitioning the samples at a node into child nodes based on a feature threshold/value.
• (d) Depth: the length of the longest path from the root node to any leaf node.

Q2. (4 marks) (a) $p_+ = p_- = 0.5$. $H = -0.5\log_2 0.5 - 0.5\log_2 0.5 = -0.5(-1) - 0.5(-1) = 1.0 \text{ bit}$ (2 marks) — max entropy for balanced binary node.

(b) $G = 1 - (0.5^2 + 0.5^2) = 1 - 0.5 = 0.5$ (2 marks) — max Gini = 0.5 for binary.

Q3. (6 marks) Parent entropy: $p=0.5$ → $H_{parent}=1.0$. (1 mark)

Left child (4 pos, 0 neg): pure → $H_L = 0$. (1 mark)

Right child (1 pos, 5 neg), total 6: $p_+=1/6,\ p_-=5/6$. $H_R = -\tfrac{1}{6}\log_2\tfrac{1}{6} - \tfrac{5}{6}\log_2\tfrac{5}{6}$ $= -0.16667(-2.585) - 0.83333(-0.26303) = 0.4308 + 0.2192 = 0.6500$ (2 marks)

Weighted child entropy (weights 4/10 and 6/10): $H_{split} = 0.4(0) + 0.6(0.6500) = 0.3900$ (1 mark)

Information gain: $IG = 1.0 - 0.3900 = 0.6100 \text{ bits}$ (1 mark)

Q4. (4 marks)

• Overfitting description (2 marks): the tree grows very deep, creating leaves that fit noise/individual training points; near-perfect training accuracy but poor test/generalization accuracy; decision boundaries become overly complex.
• Two techniques (1 mark each): pruning (pre/post), limiting max depth, minimum samples per leaf/split, ensembling (bagging/random forest), setting a minimum impurity decrease. Any two valid.

Q5. (4 marks)

• Pre-pruning (early stopping) (2 marks): stop growing the tree before it fully fits the data. Example criterion: stop when max depth reached / node has fewer than $n$ samples / information gain below threshold.
• Post-pruning (2 marks): grow full tree then remove/collapse branches that don't improve validation performance. Example: cost-complexity (weakest-link) pruning, reduced-error pruning.

Q6. (6 marks)

• Bagging (3 marks): generate $B$ bootstrap samples (sample with replacement) from the training set; train a separate tree on each; aggregate predictions by majority vote (classification) or averaging (regression). This reduces variance since averaging many high-variance trees stabilizes the prediction.
• Random Forest difference (3 marks): in addition to bagging the samples, at each split a random subset of features (e.g. $\sqrt{p}$ features) is considered rather than all features. This decorrelates the trees, reducing ensemble variance further than plain bagging.

Q7. (5 marks)

• Definition (2 marks): OOB error is a validation estimate computed by predicting each training sample using only the trees for which that sample was not in the bootstrap set, then measuring the error on those predictions.
• Fraction ≈ 36.8% (1 mark).
• Why (2 marks): probability a sample is NOT chosen in $n$ draws with replacement from $n$ items is $\left(1-\tfrac{1}{n}\right)^n \to e^{-1} \approx 0.368$. So about 37% of samples are OOB per tree.

Q8. (5 marks)

• AdaBoost (2.5 marks): fits weak learners sequentially, re-weighting samples — misclassified points get higher weights so the next learner focuses on them. Final prediction is a weighted vote where learner weight depends on its error.
• Gradient Boosting (2.5 marks): fits each new learner to the negative gradient (residuals) of a differentiable loss function; adds it to the ensemble with a learning rate. Generalizes boosting to arbitrary loss functions via gradient descent in function space.

Q9. (4 marks) Difference vector: $(4-1, 6-2, 3-3) = (3,4,0)$. (a) Euclidean: $\sqrt{3^2+4^2+0^2} = \sqrt{25} = 5$ (2 marks) (b) Manhattan: $|3|+|4|+|0| = 7$ (2 marks)

Q10. (6 marks)

• Too small $K$ (e.g. $K=1$) (2 marks): low bias, high variance; very sensitive to noise/outliers; jagged decision boundary; overfits.
• Too large $K$ (2 marks): high bias, low variance; over-smoothed boundary; may include distant irrelevant neighbors and misclassify; underfits (extreme $K=N$ predicts majority class always).
• Curse of dimensionality (2 marks): in high dimensions distances become nearly uniform (all points roughly equidistant), so "nearest" neighbors are not meaningfully closer; neighborhoods become sparse, degrading KNN accuracy and requiring exponentially more data.

[
  {"claim":"Q2a entropy of balanced binary node = 1.0", "code":"p=Rational(1,2); H=-p*log(p,2)-p*log(p,2); result = (H==1)"},
  {"claim":"Q2b Gini of balanced binary node = 0.5", "code":"p=Rational(1,2); G=1-(p**2+p**2); result = (G==Rational(1,2))"},
  {"claim":"Q3 information gain approx 0.61 bits", "code":"HR=-Rational(1,6)*log(Rational(1,6),2)-Rational(5,6)*log(Rational(5,6),2); Hsplit=Rational(4,10)*0+Rational(6,10)*HR; IG=1-Hsplit; result = abs(float(IG)-0.61) < 0.01"},
  {"claim":"Q7 OOB fraction approx 0.368", "code":"val=limit((1-1/n)**n, n, oo); result = abs(float(val)-0.3679) < 0.001"},
  {"claim":"Q9 Euclidean=5 and Manhattan=7", "code":"a=Matrix([1,2,3]); b=Matrix([4,6,3]); d=b-a; euc=sqrt(sum(x**2 for x in d)); man=sum(abs(x) for x in d); result = (euc==5 and man==7)"}
]