Tree-Based & Instance Methods

Question 1 (14 marks)

Parent: 6 positives, 4 negatives, $p_+ = 0.6$, $p_- = 0.4$.

(a) Entropy: $H = -0.6\log_2 0.6 - 0.4\log_2 0.4 = 0.6\cdot0.7370 + 0.4\cdot1.3219 = 0.9710$ (2 marks — correct formula 1, value 1)

Gini: $G = 1 - 0.6^2 - 0.4^2 = 1 - 0.36 - 0.16 = 0.48$ (2 marks)

(b) Split at $t=6.5$: left = indices 1–6 (all $+$), 6 samples, pure. Right = indices 7–10 (all $-$), 4 samples, pure.

Left entropy $= 0$, right entropy $= 0$. Weighted child entropy $= \tfrac{6}{10}(0) + \tfrac{4}{10}(0) = 0$. Information gain $= H_{parent} - 0 = 0.9710$. (3 marks)

Weighted Gini $= \tfrac{6}{10}(0) + \tfrac{4}{10}(0) = 0$. (3 marks)

(c) Because the labels are perfectly ordered (all $+$ then all $-$) and $X$ is monotonically increasing, the threshold $t=6.5$ separates the classes with zero impurity. No split can do better than weighted Gini $= 0$ (the theoretical minimum). So $t=6.5$ IS optimal; the best achievable weighted Gini is $0$. (4 marks: recognise perfect separation 2, state min Gini = 0 with justification 2)

Question 2 (14 marks)

Initial weights: $D_1(i) = 0.2$ each. Misclassified: points 2, 4.

(a) $\varepsilon_1 = 0.2 + 0.2 = 0.4$. (2 marks) $\alpha_1 = \tfrac12\ln\frac{1-0.4}{0.4} = \tfrac12\ln 1.5 = \tfrac12(0.4055) = 0.2027$ (2 marks)

(b) Update rule: $D_2(i) \propto D_1(i)\,e^{-\alpha_1 y_i h(x_i)}$; multiply misclassified by $e^{\alpha_1}$, correct by $e^{-\alpha_1}$.

$e^{\alpha_1} = e^{0.2027} = 1.2247$, $e^{-\alpha_1} = 0.8165$.

Unnormalized:

• Correct points (1,3,5): $0.2 \times 0.8165 = 0.1633$ each
• Misclassified (2,4): $0.2 \times 1.2247 = 0.2449$ each

Sum $Z = 3(0.1633) + 2(0.2449) = 0.4899 + 0.4899 = 0.9798$.

Normalized:

• Correct: $0.1633/0.9798 = 0.1667$ each
• Misclassified: $0.2449/0.9798 = 0.2500$ each

$D_2 = [0.1667,\ 0.2500,\ 0.1667,\ 0.2500,\ 0.1667]$ (Update rule 2, unnormalized 2, normalized values 2)

(c) After normalization, weighted error of $h_1$ under $D_2$ = sum of misclassified weights $= 0.25 + 0.25 = 0.5$. This is a general AdaBoost property: the reweighting makes the current learner have exactly 50% weighted error on the new distribution (equivalent to random guessing), forcing the next learner to focus on the previously hard points. (numeric confirmation 2, interpretation 2)

Question 3 (10 marks)

(a) Probability a specific point NOT chosen in one draw $= 1 - 1/n$. Independent over $n$ draws: $P(\text{OOB}) = \left(1 - \frac1n\right)^n$ Limit: $\lim_{n\to\infty}(1-1/n)^n = e^{-1} \approx 0.3679$. (formula 2, limit 2)

(b) $n=5$: $(1 - 1/5)^5 = 0.8^5 = 0.32768 \approx 0.3277$. (3 marks)

(c) Fraction of trees for which a point is OOB $\approx 0.368$. For 200 trees: $200 \times 0.368 \approx 73.6 \approx 74$ trees. OOB error for that point = aggregate prediction (majority vote / average) using only those ~74 trees that did not train on it; the overall OOB error averages this over all points, giving a validation-free generalization estimate. (count 2, computation of OOB error 1)

Question 4 (12 marks)

(a) Query $q=(3,2)$.

Euclidean:

• A(1,1): $\sqrt{4+1}=\sqrt5=2.2361$
• B(2,2): $\sqrt{1+0}=1.0000$
• C(4,4): $\sqrt{1+4}=\sqrt5=2.2361$
• D(5,1): $\sqrt{4+1}=\sqrt5=2.2361$

Manhattan:

• A: $2+1=3$
• B: $1+0=1$
• C: $1+2=3$
• D: $2+1=3$

(3 marks Euclidean, 3 marks Manhattan)

(b) 1-NN: nearest is B (dist 1.0) → Red. 3-NN: nearest three are B (1.0), then a tie among A, C, D (all 2.2361). Choosing any 3, e.g. {B, and two of A/C/D}. With B=Red, A=Red, then one Blue → 2 Red vs 1 Blue → Red. (Note tie must be broken; a reasonable tie-break like taking A and C gives {B:Red, A:Red, C:Blue} → Red.) Answer: 1-NN = Red, 3-NN = Red (with stated tie-breaking). (4 marks: 1-NN 2, 3-NN with tie note 2)

(c) With 100 noise features, Euclidean distances become dominated by noise-dimension variation; all pairwise distances concentrate (ratio of nearest to farthest → 1), so "nearest neighbour" is no longer meaningfully closer in the relevant features — predictions degrade. (2 marks)

Question 5 (10 marks)

(a) $F_0 = \bar y = (3+6+9+12)/4 = 30/4 = 7.5$. (1) Pseudo-residuals $r_i = y_i - F_0$: $[3-7.5,\ 6-7.5,\ 9-7.5,\ 12-7.5] = [-4.5,\ -1.5,\ 1.5,\ 4.5]$ (3 marks)

(b) Left leaf (points 1,2): $c = (-4.5 + -1.5)/2 = -3$. Right leaf (points 3,4): $d = (1.5 + 4.5)/2 = 3$. $F_1 = F_0 + 0.5 h_1$:

• pts 1,2: $7.5 + 0.5(-3) = 6.0$
• pts 3,4: $7.5 + 0.5(3) = 9.0$

$F_1 = [6.0,\ 6.0,\ 9.0,\ 9.0]$ (leaf values 2, $F_1$ 2)

(c) Gradient boosting fits each new learner to the negative gradient (residuals) of the loss, performing functional gradient descent, so it directly reduces the loss for any differentiable loss. AdaBoost's reweighting is a special case for exponential loss; residual-fitting generalizes to arbitrary losses and continuous targets. (2 marks)

[
  {"claim":"Q1a parent entropy = 0.9710 and Gini = 0.48","code":"from sympy import log, Rational, N\np=Rational(6,10); q=Rational(4,10)\nH=-(p*log(p,2)+q*log(q,2)); G=1-p**2-q**2\nresult = (abs(float(H)-0.9710)<1e-3) and (float(G)==0.48)"},
  {"claim":"Q2 alpha1 = 0.2027 and D2 misclassified weight = 0.25","code":"import sympy as sp\neps=sp.Rational(2,5)\nalpha=sp.Rational(1,2)*sp.log((1-eps)/eps)\nc=sp.Rational(1,5)*sp.exp(-alpha); m=sp.Rational(1,5)*sp.exp(alpha)\nZ=3*c+2*m\nresult = (abs(float(alpha)-0.2027)<1e-3) and (abs(float(m/Z)-0.25)<1e-6)"},
  {"claim":"Q3b OOB prob for n=5 is 0.32768","code":"result = abs((1-1/5)**5 - 0.32768) < 1e-9"},
  {"claim":"Q5 residuals and F1 correct","code":"y=[3,6,9,12]; F0=sum(y)/4\nr=[v-F0 for v in y]\nc=(r[0]+r[1])/2; d=(r[2]+r[3])/2\nF1=[F0+0.5*c,F0+0.5*c,F0+0.5*d,F0+0.5*d]\nresult = (F0==7.5) and (r==[-4.5,-1.5,1.5,4.5]) and (F1==[6.0,6.0,9.0,9.0])"}
]