Tree-Based & Instance Methods

Question 1

(a) $G(p) = 2p(1-p)$; $H(p) = -p\log_2 p - (1-p)\log_2(1-p)$. (1) Using $-\log_2 x \ge \frac{1}{\ln 2}(1-x)$: $H(p) = p(-\log_2 p) + (1-p)(-\log_2(1-p)) \ge \frac{1}{\ln 2}\big[p(1-p) + (1-p)p\big] = \frac{2p(1-p)}{\ln 2}$. (3) So $H(p) \ge \frac{G(p)}{\ln 2}$, i.e. $G(p) \le (\ln 2)\,H(p) \approx 0.693\,H(p)$. Since $\ln 2 < 1$, and in fact one shows $G(p)\le \tfrac12 H(p)$ holds pointwise (max ratio $G/H \to \ln2/2\approx0.3466$ at endpoints; both equal 0 at $p=0,1$ and $G(0.5)=0.5$, $H(0.5)=1$ so ratio $=0.5=\tfrac12$). The tightest constant is $\tfrac12$, achieved at $p=\tfrac12$. (2)

(b) Parent: $p=9/14$. $H = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} = 0.940$. (2) Weak (6/2): $H = -\frac{6}{8}\log_2\frac68 - \frac28\log_2\frac28 = 0.811$. Strong (3/3): $H = 1.000$. (2) Weighted child $= \frac{8}{14}(0.811) + \frac{6}{14}(1.000) = 0.4634 + 0.4286 = 0.892$. Information gain $= 0.940 - 0.892 = 0.048$. (2)

(c) Parent Gini $=2\cdot\frac{9}{14}\cdot\frac{5}{14}=0.4592$. Weak Gini $=2\cdot\frac68\cdot\frac28=0.375$; Strong Gini $=2\cdot\frac12\cdot\frac12=0.5$. Weighted $=\frac{8}{14}(0.375)+\frac{6}{14}(0.5)=0.2143+0.2143=0.4286$. Gini gain $=0.4592-0.4286=0.0306>0$. (3) Both entropy gain ($0.048>0$) and Gini gain ($0.031>0$) are positive → they agree the split improves purity. (1)

(d) Entropy $H(p)$ is concave (second derivative $H''(p)=-\frac{1}{p(1-p)\ln2}<0$). Splitting partitions the parent proportion $p$ as a convex combination $p=\sum_k w_k p_k$ with weights $w_k=N_k/N$. By Jensen's inequality for concave $H$: $H(\sum_k w_k p_k) \ge \sum_k w_k H(p_k)$, i.e. parent entropy $\ge$ weighted child entropy, so gain $\ge 0$. Equality iff all $p_k$ equal. (4)

Question 2

(a) Probability a given sample is NOT chosen in one draw $=1-\frac1n$. Over $n$ independent draws: $\left(1-\frac1n\right)^n$. (3) Limit: $\lim_{n\to\infty}\left(1-\frac1n\right)^n = e^{-1}\approx 0.368$. Expected OOB fraction $\approx 36.8\%$ (so $\approx63.2\%$ in-bag). (2)

(b) $\alpha_t=\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}=\tfrac12\ln\frac{0.75}{0.25}=\tfrac12\ln 3=0.5493$. (2) Update: $w_i \leftarrow w_i\exp(-\alpha_t y_i h_t(x_i))$. Correct ($y_i h_t=+1$): factor $e^{-\alpha_t}=e^{-0.5493}=0.5774=1/\sqrt3$. Misclassified ($y_i h_t=-1$): factor $e^{+\alpha_t}=e^{0.5493}=1.7321=\sqrt3$. (4)

(c) $Z_t=\sum_i w_i e^{-\alpha_t y_i h_t(x_i)}$. Split into correct (total weight $1-\varepsilon_t$) and wrong ($\varepsilon_t$): $Z_t=(1-\varepsilon_t)e^{-\alpha_t}+\varepsilon_t e^{\alpha_t}$. Substitute $e^{\alpha_t}=\sqrt{(1-\varepsilon_t)/\varepsilon_t}$: $Z_t=(1-\varepsilon_t)\sqrt{\tfrac{\varepsilon_t}{1-\varepsilon_t}}+\varepsilon_t\sqrt{\tfrac{1-\varepsilon_t}{\varepsilon_t}}=\sqrt{\varepsilon_t(1-\varepsilon_t)}+\sqrt{\varepsilon_t(1-\varepsilon_t)}=2\sqrt{\varepsilon_t(1-\varepsilon_t)}$. (3) At $\varepsilon_t=0.25$: $Z_t=2\sqrt{0.25\cdot0.75}=2\sqrt{0.1875}=0.8660$. (1) $\alpha_t$ is chosen to minimize $Z_t$ (set $dZ_t/d\alpha=0$) because the training-error bound is $\prod_t Z_t$; minimizing each $Z_t$ greedily tightens the bound → the exact $\alpha_t$ formula. (2)

(d) Bagging averages many high-variance, low-bias trees → primarily reduces variance (decorrelated averaging). Boosting sequentially fits residuals/reweights → reduces bias (builds a strong learner from weak ones). Boosting overfits noisy labels because it up-weights persistently misclassified points; noisy/mislabeled points receive exploding weights and dominate later rounds. (5)

Question 3

(a) Difference $b-a=(3,4,0)$. Euclidean $=\sqrt{9+16+0}=\sqrt{25}=5$. (2) Manhattan $=|3|+|4|+0=7$. (2) Cosine: $a\cdot b=1\cdot4+2\cdot6+2\cdot2=4+12+4=20$; $\|a\|=\sqrt{1+4+4}=3$, $\|b\|=\sqrt{16+36+4}=\sqrt{56}=7.4833$. $\cos\theta=20/(3\cdot7.4833)=20/22.45=0.8909$; cosine distance $=1-0.8909=0.1091$. (2)

(b) Pseudocode: (3)

predict(x, X_train, y_train, K):
    dists = [ (euclid(x, X_train[i]), y_train[i]) for i in range(N) ]
    sort dists ascending by distance
    neighbours = first K entries
    votes = {}
    for (d, y) in neighbours:
        w = 1/(d + eps)
        votes[y] += w
    return argmax_c votes[c]

Complexity of one prediction: distance to all $N$ points costs $O(ND)$; selecting top-$K$ via sort $O(N\log N)$ or partial-select $O(N\log K)$. Total $O(ND + N\log N)$. (2)

(c) $\ell=r^{1/D}$, $r=0.01$:

• $D=1$: $\ell=0.01$.
• $D=10$: $\ell=0.01^{0.1}=10^{-0.2}=0.6310$.
• $D=100$: $\ell=0.01^{0.01}=10^{-0.02}=0.9550$. (4) Interpretation: to capture just 1% of data in 100-D you must span 95.5% of each axis — "local" neighbourhoods are no longer local; all points become nearly equidistant, so distance-based ranking of neighbours loses meaning. To keep neighbourhoods local you'd need $K$ tiny (unreliable estimates) or huge $N$. Hence KNN degrades badly in high dimensions; dimensionality reduction / feature selection is required. (3)

[
  {"claim":"Q1b information gain = 0.048","code":"import math\ndef H(a,b):\n    t=a+b; ps=[a/t,b/t]; return -sum(p*math.log2(p) for p in ps if p>0)\nparent=H(9,5); child=(8/14)*H(6,2)+(6/14)*H(3,3); gain=parent-child\nresult = round(gain,3)==0.048"},
  {"claim":"Q1c Gini gain approx 0.0306","code":"def G(a,b):\n    t=a+b; return 2*(a/t)*(b/t)\np=G(9,5); c=(8/14)*G(6,2)+(6/14)*G(3,3); result = round(p-c,4)==0.0306"},
  {"claim":"Q2b alpha = 0.5493 for eps=0.25","code":"import math\neps=0.25; alpha=0.5*math.log((1-eps)/eps); result = round(alpha,4)==0.5493"},
  {"claim":"Q2c Zt = 0.8660 for eps=0.25","code":"import math\neps=0.25; Z=2*math.sqrt(eps*(1-eps)); result = round(Z,4)==0.8660"},
  {"claim":"Q3a distances: euclid 5, manhattan 7, cosine dist 0.1091","code":"import math\na=[1,2,2]; b=[4,6,2]\neu=math.sqrt(sum((x-y)**2 for x,y in zip(a,b)))\nman=sum(abs(x-y) for x,y in zip(a,b))\ndot=sum(x*y for x,y in zip(a,b)); na=math.sqrt(sum(x*x for x in a)); nb=math.sqrt(sum(x*x for x in b))\ncd=1-dot/(na*nb)\nresult = eu==5 and man==7 and round(cd,4)==0.1091"},
  {"claim":"Q3c edge lengths r=0.01","code":"result = round(0.01**(1/10),4)==0.6310 and round(0.01**(1/100),4)==0.9550"}
]