Harvard CS181 HW4 (Part 3): Decision Trees, Random Forests, and Mixture of Experts

🌏 中文版

⚠️ Version and access: Based on hw4_release.tex from CS1810 Spring 2026 HW4 and §3 of the Section 6 notes, opened on 2026-09-29. The course is A3 overall, with no current-term recordings and no homework solutions. I did not get the Week 7 Non-parametric Models / Decision Trees lecture slides. Problem 3 is pen-and-paper only, with no notebook code; its header gives no total, and the marked sub-parts add up to 35 points.

This is post 8 of the Harvard CS181 weekly guide and the last problem in HW4. The previous two posts covered Transformers and autoencoders to VAEs.

First: this problem doesn't test growing a tree

The HW4 handout says up front that no problem asks you to build a decision tree by hand, and points you to the last exercise in the Section 6 notes for review.

That exercise is in Section 6 §3.3: six days of a runner's habits with two features, Outlook and Humidity. You compute the overall entropy, compare information gain to pick the root, and draw the final tree. The solutions have the answers. Do it before Problem 3, because Problem 3 assumes you already know why single trees are unstable. Section 6 §3.4 says small changes in data can produce a different tree, so in practice we use shallow trees for interpretability and ensembles for accuracy.

Problem 3 asks: how far can ensembling push accuracy, what caps it, and how does it differ from the MoE inside LLMs?

1. Independent trees voting: the Hoeffding bound (15 pts)

Setup: B independently trained binary classifiers, each correct with the same probability p > ½ on a test point, predicting by majority vote. The number of correct trees is X ~ Binomial(B, p), and the ensemble is right when X > B/2.

(a) 5 pts: derive the error bound

The handout gives Hoeffding's inequality and asks you to show:

P(X ≤ B/2) ≤ exp(−2B(p − ½)²)

Hint: the ensemble errs when the mean Z̄ = X/B ≤ ½. Each Zᵢ ∈ {0, 1}, so bᵢ − aᵢ = 1 and the denominator is B. Set t = p − ½ and substitute.

(b) 5 pts: plug in numbers

With p = 0.6, (p − ½)² = 0.01, so the bound is exp(−0.02B):

To get the bound below 10⁻⁶ you need 0.02B > ln 10⁶ ≈ 13.8, so B ≥ 691. The right column is my own computation, summing binomial probabilities in Python (ties count as errors). The homework doesn't ask for it; it's there to show how conservative the Hoeffding bound is.

The last question, "is that good or necessary?", has no single answer, but think about two things. A 10⁻⁶ error rate is far beyond what most applications need. And the whole derivation assumes the trees are independent, which the next sub-part takes apart.

(c) 5 pts: correlation and feature subsampling

In practice, bagged trees train on overlapping bootstrap samples and are correlated. You explain two things intuitively:

• Why correlation weakens the convergence guarantee: if all trees err on the same points, more votes can't fix those errors
• How random forest feature subsampling (each split considers only m random features) reduces correlation: a strong feature can't be the root of every tree, so tree structures are forced apart

2. Correlated trees: the ensemble variance formula (16 pts)

This turns the intuition from 1(c) into a formula. B trees, each with prediction variance σ², and every pair with correlation ρ.

(a) 8 pts: prove it

Var( (1/B) Σ T_b(x) ) = ρσ² + (1 − ρ)σ²/B

(b) 4 pts: read the formula

• As B → ∞ the second term vanishes and the variance converges to ρσ². As long as ρ > 0, no number of trees gets it to zero
• ρ = 0 is the independent case from 1(a), with variance falling as 1/B. ρ = 1 is the same tree copied B times, and ensembling does nothing. You're asked for a practical scenario for each: nearly identical bootstrap samples, or every tree picking the same dominant feature, both push ρ toward 1

(c) 4 pts: why m = 1 is a bad idea

The classification default is m = ⌊√d⌋. With m = 1, each split can only use one random feature. That minimizes ρ, but trees are often forced to split on useless features, so each tree gets worse. In terms of the formula from (a), m affects both ρ and the individual tree's error, and lowering ρ costs you weaker trees. The problem wants you to name that tradeoff.

Section 6 §3.5 gives the rule of thumb m ≈ √d for classification and m ≈ d/3 for regression.

3. Random forests vs. Mixture of Experts (4 pts)

The handout puts both in one frame:

• A random forest is a dense ensemble: every tree processes every input
• An MoE is a sparse ensemble: a learned gating network routes each input to only a few experts, and the output is a weighted combination y = Σ g_k(x) E_k(x) with most g_k = 0

The handout's example is Mixtral 8x7B: about 47B total parameters, with each token routed to 2 of 8 experts so only about 13B are active (numbers from the handout; original source is the Mixtral paper). It also notes two differences. MoE experts specialize, random forest trees don't. And MoE suffers from expert collapse, where the gate sends most inputs to one or two experts, usually addressed with an auxiliary load-balancing loss.

Your answer compares, in 3–5 sentences, how each handles the tradeoff between capacity and compute, and explains why a random forest can't scale up the way an MoE can. A direction to think in: each extra tree adds inference cost linearly, and by part 2, the benefit of extra trees is capped at ρσ². An MoE can keep adding total parameters while per-input compute is set by the number of experts each input is routed to.

Connecting back to LLMs

Quite a few of the large models in use today are MoE architectures. Looking back at this problem, the classic idea of ensembling has turned around in LLMs: a random forest lowers variance by averaging many similar models, while an MoE routes inputs so different experts divide the work, trading sparse activation for a larger total capacity.

That wraps up HW4. HW5 moves to learning without labels: clustering, PCA, and self-supervised learning.

Further reading

• CS336 Lecture 4: attention alternatives and MoE: the systems side of MoE routing, load balancing, and expert parallelism
• Generalization: bias-variance, double descent, and sample complexity (CS229 notes chapter 8): another use of Hoeffding's inequality, in learning theory
• Breiman 2001, Random Forests: the original random forest paper

Previous / next

• Previous: HW4 (Part 2): why autoencoders can't generate, and what VAEs add
• Next: HW5 (Part 1): K-means, HAC, and PCA

References

• CS1810 Spring 2026 HW4 handout hw4_release.tex
• CS1810 Spring 2026 HW4 handout PDF
• CS1810 Spring 2026 Section 6 (Decision Trees in §3) (solutions)
• CS1810 Spring 2026 official schedule (Google Sheet)
• Jiang et al. 2024, Mixtral of Experts
• Breiman 2001, Random Forests
• CS181 2026 course website