Tree-Based & Instance Methods

Question 1 (12)

(a) Parent $p_A=0.6, p_B=0.4$. $H=-0.6\log_2 0.6 - 0.4\log_2 0.4 = 0.6(0.7370)+0.4(1.3219)=0.4422+0.5288=\mathbf{0.9710}\text{ bits}$ (1 formula, 1 substitution, 1 answer)

(b) Left child pure → $H_L=0$. Right child $p_A=2/6, p_B=4/6$: $H_R=-\tfrac13\log_2\tfrac13-\tfrac23\log_2\tfrac23=0.3333(1.585)+0.6667(0.585)=0.5283+0.3900=0.9183$ Weighted: $\frac{4}{10}(0)+\frac{6}{10}(0.9183)=\mathbf{0.5510}$. Information gain $=0.9710-0.5510=\mathbf{0.4200}$ bits. (1 $H_L$, 1 $H_R$, 1 weighted, 1 gain)

(c) Parent Gini $=1-(0.6^2+0.4^2)=1-0.52=\mathbf{0.48}$. Left Gini $=0$. Right Gini $=1-((1/3)^2+(2/3)^2)=1-(0.1111+0.4444)=0.4444$. Weighted $=0.4(0)+0.6(0.4444)=\mathbf{0.2667}$. (1 parent, 1 right, 1 weighted)

(d) Both measure node impurity and are monotone-similar convex functions of class proportions, so they rank splits almost identically; Gini avoids the logarithm, so it's computationally cheaper. (2)

Question 2 (12)

(a) Uniform weights $=0.2$; 1 of 5 wrong → $\varepsilon_1 = 0.2$. $\alpha_1=\tfrac12\ln\frac{1-0.2}{0.2}=\tfrac12\ln 4 = \tfrac12(1.3863)=\mathbf{0.6931}$ (2 error, 2 alpha)

(b) Update $w \leftarrow w\,e^{-\alpha y h}$: correct→$e^{-\alpha}$, wrong→$e^{+\alpha}$. Correct: $0.2\,e^{-0.6931}=0.2(0.5)=\mathbf{0.1}$. Wrong: $0.2\,e^{0.6931}=0.2(2.0)=\mathbf{0.4}$. (2 correct, 2 wrong)

(c) There are 4 correct (0.1 each) and 1 wrong (0.4): $Z_1=4(0.1)+0.4=0.8$. Normalized correct $=0.1/0.8=\mathbf{0.125}$; wrong $=0.4/0.8=\mathbf{0.5}$. Sum $=4(0.125)+0.5=0.5+0.5=1$. ✓ (1 Z, 1 normalized, 1 sum check)

(d) As $\varepsilon_1\to0.5$, $\alpha_1\to\tfrac12\ln1=0$: a learner no better than random gets zero vote. (1)

Question 3 (12)

import numpy as np
from collections import Counter
 
def knn_predict(X_train, y_train, x_query, k, metric='euclidean'):
    X_train = np.asarray(X_train); x_query = np.asarray(x_query)
    if metric == 'euclidean':
        dists = np.sqrt(np.sum((X_train - x_query)**2, axis=1))
    elif metric == 'manhattan':
        dists = np.sum(np.abs(X_train - x_query), axis=1)
    else:
        raise ValueError("unknown metric")
    idx = np.argsort(dists)[:k]
    labels = [y_train[i] for i in idx]
    return Counter(labels).most_common(1)[0][0]

Marks: distances (3), argsort/top-k (2), majority vote (2), metric branch (1) = 8.

Complexity: $O(nd)$ to compute distances + $O(n\log n)$ (or $O(n)$ with partial selection) for the sort → $O(nd + n\log n)$ per query. (2)

Scaling: Euclidean distance sums squared differences across features, so a large-scale feature dominates the distance and biases neighbours; scaling equalizes contributions. A decision tree splits one feature at a time by threshold and is invariant to any monotone rescaling, so scaling has no effect on tree splits. (2)

Question 4 (10)

(a) Each of $n$ draws independently picks the specific point with prob $1/n$, misses with prob $1-1/n$. Never selected over $n$ draws: $P=\left(1-\tfrac1n\right)^n \xrightarrow{n\to\infty} e^{-1}\approx\mathbf{0.3679}$ (2 setup, 2 expression, 1 limit)

(b) Expected OOB fraction $\approx e^{-1}\approx\mathbf{36.8\%}$ of points are OOB for a given tree. (2)

(c) Each training point is predicted by only those trees for which it was OOB; these OOB predictions are aggregated (vote/average), and OOB error is the mean loss over all points. Since each point's prediction uses only trees that never saw it, it acts as held-out data, so OOB error is a nearly unbiased estimate of generalization error without a separate CV split. (3)

Question 5 (8)

(a) $L=\tfrac12(y-F)^2$, $\dfrac{\partial L}{\partial F}=-(y-F)$, so $r_i=-\frac{\partial L}{\partial F}\Big|_{F_{m-1}} = y_i - F_{m-1}(x_i)$ i.e. the ordinary residual — the error the current ensemble still makes on point $i$. (2 derivative, 2 interpretation)

(b) GBM treats $F$ as the variable being optimized; the pseudo-residuals are the negative functional gradient of the loss, and fitting a tree to them then adding $\nu\cdot$tree takes a descent step in the space of functions. (2)

(c) Any two, e.g.: learning rate/shrinkage (scales each tree's contribution), max_depth / min_child_weight (limits per-tree complexity), subsample / colsample (stochastic sampling), $\lambda,\alpha$ L2/L1 regularization on leaf weights. (1 each)

Question 6 (6)

(a) Randomness sources: (1) bootstrap resampling of rows for each tree, (2) random feature subset considered at each split. Feature subsampling prevents every tree from repeatedly choosing the same dominant feature at the top splits, so trees become structurally different and their prediction errors are less correlated. (3)

(b) For $B$ trees each with variance $\sigma^2$ and pairwise correlation $\rho$, the average has variance $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$. Lowering $\rho$ (via decorrelation) drives variance down as $B$ grows, but averaging leaves the individual trees' expected value unchanged, so bias is unaffected. (3)

[
  {"claim":"Q1 parent entropy = 0.9710 bits","code":"import sympy as sp\nH=-0.6*sp.log(0.6,2)-0.4*sp.log(0.4,2)\nresult = round(float(H),4)==0.9710"},
  {"claim":"Q1 information gain = 0.4200 bits","code":"import sympy as sp\nHp=-0.6*sp.log(0.6,2)-0.4*sp.log(0.4,2)\nHr=-(sp.Rational(1,3))*sp.log(sp.Rational(1,3),2)-(sp.Rational(2,3))*sp.log(sp.Rational(2,3),2)\ngain=Hp-0.6*Hr\nresult = round(float(gain),4)==0.42"},
  {"claim":"Q1 weighted Gini = 0.2667","code":"g=0.6*(1-((sp.Rational(1,3))**2+(sp.Rational(2,3))**2))\nresult = round(float(g),4)==0.2667"},
  {"claim":"Q2 alpha1 = 0.6931 and Z1=0.8","code":"a=sp.Rational(1,2)*sp.log((1-sp.Rational(1,5))/sp.Rational(1,5))\nZ=4*0.2*sp.exp(-a)+0.2*sp.exp(a)\nresult = (round(float(a),4)==0.6931) and (round(float(Z),4)==0.8)"},
  {"claim":"Q4 OOB limit prob = 1/e = 0.3679","code":"result = round(float(sp.exp(-1)),4)==0.3679"}
]