🌏 中文版
Video status: Checked: no corresponding recording link listed on the public official page. Source details
This is CMU 07-280 Spring 2026 Lecture 6: Decision Trees. Lecture 5 said to find a low-empirical-risk function in a hypothesis class. This lecture makes H concrete and exposes a central tradeoff: do not enumerate every possible tree; greedily choose one informative split at each node.
The inherited question: once the hypothesis class is chosen, how is a model found
An internal decision-tree node asks about an attribute, an edge represents an answer, and a leaf outputs a label. The apartment example asks about rent, deposit, distance, and transit before deciding whether to visit. Its prediction path can be read as a rule. The training data, however, do not tell the learner which question to ask first.
In the binary version, X={0,1}^d and Y={0,1}. A decision stump makes one split. A full tree splits recursively. When attributes are exhausted or all labels at a node agree, the algorithm creates a leaf using majority vote.
Full conceptual path: greedy construction and information
At each node, the lecture's algorithm calls BestAttribute(S,A), splits samples by the chosen attribute's value, then recurses. This is greedy: it takes the locally best split for computational efficiency, without guaranteeing the globally smallest or most accurate tree.
“Best” can mean lowest post-split training error or an impurity measure. This lecture develops information theory:
H(Y) = Σ_y P(Y=y) log2(1/P(Y=y))
H(Y|W) = Σ_w P(W=w) H(Y|W=w)
I(Y;W) = H(Y) - H(Y|W)Entropy measures uncertainty in the labels. Conditional entropy is the weighted average child entropy after observing attribute W. Mutual information is the reduction in uncertainty, so BestAttribute chooses the largest I(Y;W).
Continuous features can use thresholds such as x2 ≥ 4.5. An attribute need not always be removed after use; a numerical feature can be split again at another threshold. Stopping rules control tree size—for example, stop when a split barely reduces training error.
A reproducible example: how much information is in one bit
Suppose eight examples contain four positive and four negative labels:
H(Y) = -0.5 log2 0.5 - 0.5 log2 0.5 = 1 bitAttribute W1 perfectly places all positives in one child and negatives in the other. Both child entropies are 0, so H(Y|W1)=0 and I(Y;W1)=1.
Both children of W2 contain two positives and two negatives. Conditional entropy remains 1, so I(Y;W2)=0. Drawing two branches did not reduce label uncertainty; the split learned nothing useful for distinguishing the classes.
Recitation and homework connection
Recitation 3 first defines decision trees, entropy, conditional entropy, and mutual information. It then calculates entropy for a fair coin, deterministic coin, and die. A weather-and-running dataset leads through H(Y), H(Y|X), and a best split, followed by discussion of when information gain can still produce an undesirable tree.
HW4's first question presents a training set and asks about candidate splits. The prompt explicitly says entropy need not be calculated for that part; the target is reading the class composition after each split. The recitation's arithmetic and the homework's structural judgment complement one another.
Further comparison: interpretable does not mean stable or globally optimal
A single path through a tree is readable, but training is greedy. A small data change can replace the root split and rebuild every descendant subtree. Mutual information evaluates current uncertainty reduction, not the globally optimal future tree.
“Human interpretable” should therefore mean that a prediction path can be inspected—not that training has no tradeoffs, the model must be small, or the result is stable.
What to do tonight
- Calculate the entropy of a fair coin, an always-tails coin, and a fair six-sided die.
- Compute conditional entropy and mutual information for two attributes in an eight-example binary dataset.
- Use the best attribute as the root and recurse until labels agree or attributes are exhausted.
Course video sources
The official Spring 2026 schedule has been checked: it lists slides, notes and exercises, but no public recording link for the lectures covered here. This article therefore links to course materials and has no corresponding lecture player. Géron/Karpathy videos are supplementary readings; the CMU-Qatar NumPy recording is a separate Recitation 0, not the lecture covered here.
Official sources:
Checked on 2026-10-10.
Official materials and reading scope
I read the complete Decision Trees lecture notes, pre-reading, Recitation 3 and solution, and checked HW4. No lecture recording is public.
Update Log
- 2026-10-10: Added explicit video status and checked recording sources and access notes.
- 2026-10-10: Rechecked video status. Re-verified the live official course pages and public video sources; no public recording for this lecture was found, so the status stands.
References
Loading...