ID3 algorithm — Iterative Dichotomizer 3 — uses entropy and information gain to select the best attribute for splitting at each node. ID3 is a greedy algorithm: at each step it picks whichever attribute looks best right now, without worrying about whether a different choice would have produced a better overall tree. It never backtracks. Entropy measures impurity — how mixed-up the classes are. A pure node (all records belong to one class) has entropy 0. A 50-50 mix has maximum entropy (1 for binary). The formula: $$H=-\sum _i{p}_i{\log }_2{p}_i$$

where $p_i$ is the proportion of records belonging to class $i$. The sum runs over all classes. Each term $p_i{\log }_2{p}_i$ is negative (since ${\log }_2$ of a number under 1 is negative), and the leading minus sign makes entropy positive.

Why base-2 log? Entropy measures the minimum number of bits needed to encode the class of a randomly drawn example. A pure node needs 0 bits. A 50-50 split needs exactly 1 bit (a coin flip).

Information gain is how much "cleaner" the children are versus the parent: $$\text{IG}=H(\text{parent})-\sum _{\text{children}}\frac{|D_{\text{child}}|}{|D_{\text{parent}}|}H(\text{child})$$

The weighted average of children's entropies is subtracted from the parent's entropy. Bigger branches (more examples) carry more weight — a tiny branch with pure entropy 0 doesn't count for much.

Gain ratio fixes the problem of attributes with too many distinct values (like Customer ID, Date, or serial numbers). A Customer ID attribute splits the data into $n$ singleton subsets, each perfectly pure — giving artificially high information gain. But those splits are meaningless for predicting new examples. Gain ratio penalizes the branching factor: $$\text{Gain Ratio}=\frac{\text{Information Gain}}{\text{Split Information}}$$

where Split Information = $-{\sum }_j\frac{|S_j|}{|S|}{\log }_2\frac{|S_j|}{|S|}$ is the entropy of the attribute values themselves. For Customer ID splitting $n$ examples into $n$ subsets, Split Information = ${\log }_{2}n$ — a large denominator that kills the gain ratio. For a binary attribute that splits evenly, Split Information = 1 — a small penalty. This is why ID3 with gain ratio won't pick Customer ID as the root node.

Overfitting happens when a model learns the training data too well — it memorizes specific examples (including noise and random quirks) instead of learning the underlying pattern. The formal definition from Mitchell (1997):

A hypothesis $h\in H$ overfits the training data if there exists an alternative hypothesis $h^{\prime }\in H$ such that $h$ has smaller error than $h^{\prime }$ on the training data, but $h^{\prime }$ has smaller error than $h$ on the entire distribution of instances.

Three kinds of error to keep straight:

• Training error — mistakes on the data the model learned from. Also called resubstitution error or apparent error.
• Test error — mistakes on held-out data the model has never seen. This is our proxy for true error.
• Generalization error — the expected error over all possible future examples drawn from the same distribution. This is what we actually care about, but we can only estimate it via test error.

A decision tree is built by a greedy algorithm — at each step, it picks the attribute that gives the biggest immediate improvement in purity (highest information gain). It never looks ahead. It never backtracks.

The algorithm's default stopping condition is: stop when every leaf is pure — meaning every leaf contains only one class. But there's nothing in the algorithm that naturally says "this node has too few examples to split." So the tree can grow to unlimited depth, splitting nodes with just 2 or 3 training examples.

As the tree grows deeper:

• The number of samples per node shrinks.
• A split on a node with only 2 or 3 records is statistically meaningless — you're fitting noise, not signal.
• Coincidental regularities in the training data (patterns that exist purely by chance in a small sample) get encoded as if they were real rules.

Three broad strategies, in order of increasing sophistication:

1. Pre-pruning (Early Stopping): Set hard limits before or during tree construction — max depth, min samples per split, min information gain. Stop growing before the tree overfits. Simple and fast, but hard to know the right thresholds in advance.

1. Post-pruning: Let the tree grow to full depth (deliberately overfit), then cut back branches that don't help on a held-out validation set. More computationally expensive but often produces better results because the pruning decision is data-driven.

1. Ensemble methods (Random Forest): Instead of perfecting one tree, build hundreds of independent trees (each trained on a random subset of data and features), then average their predictions. Individual trees overfit in different ways, and those errors cancel out when averaged. Covered in a later lecture; not the focus of this session.

Occam's Razor (named after the 14th-century philosopher William of Occam) is a problem-solving principle, not specific to machine learning:

When presented with competing hypotheses that explain the same data equally well, select the one with the fewest assumptions.

In ML terms: prefer the simplest hypothesis that fits the data.

This isn't just philosophy — there's a mathematical argument. There are many more complex hypotheses than simple ones. A 500-node decision tree can be constructed in exponentially more ways than a 5-node tree. If a simple tree fits your data, it's unlikely to be a statistical coincidence — because there just aren't that many simple trees to accidentally line up with your data. But there are countless complex trees, and some will happen to fit purely by chance.

:::warning-box

Scope: Occam's Razor is a preference bias, not a guarantee. The simplest hypothesis isn't always correct — the world can be genuinely complex. But in the absence of other evidence, simpler is safer because simpler models generalize better (less variance). The razor is also representation-dependent: two learners using different internal representations may arrive at different "simplest" hypotheses for the same data. This is a known limitation (Mitchell 1997, §3.6.2).

In data science, Occam's Razor translates directly to pruning. A fully-grown decision tree hallucinates complexity — it creates branches for noise, outliers, and coincidental patterns in the training data. Pruning removes that unnecessary complexity.

Every pruning method — whether pre-pruning, post-pruning, or MDL-based — is essentially applying Occam's Razor: if removing this branch doesn't hurt performance (or helps it), remove it. The tree gets simpler without losing predictive power.

ID3's inductive bias is approximately Occam's Razor: it prefers shorter trees over longer ones. But because ID3 is greedy, it doesn't always find the shortest consistent tree — just a reasonably short one.

Pre-pruning (also called early stopping) means imposing constraints before or during tree construction so that certain branches are never grown. The tree is stopped from growing too deep.

It's simpler and computationally cheaper than post-pruning, but has a fundamental challenge: it's difficult to estimate when to stop. Cut too early and you underfit (the tree hasn't learned enough). Cut too late and you overfit (the tree has already memorized noise). With experience, domain knowledge, or by trying multiple options (cross-validation), the right threshold can be found.

1. Max Depth

Set a maximum depth for the tree (e.g., max_depth = 3). The tree stops growing when it reaches that level, regardless of whether nodes are pure. This is the most popular and easiest pre-pruning strategy. In scikit-learn, it's the max_depth parameter of DecisionTreeClassifier.

2. Minimum Samples Split

Require a minimum number of samples for a node to be split. For example, a node with fewer than 20 records cannot be split — it becomes a leaf. This prevents the tree from making decisions based on statistically insignificant sample sizes. In scikit-learn: min_samples_split.

3. Minimum Samples Leaf

Ensure every leaf node has at least N samples. A split that would produce a leaf with fewer than, say, 20 records is rejected. This is subtly different from min_samples_split: min_samples_leaf guards the children, not the parent. In scikit-learn: min_samples_leaf.

4. Information Gain Threshold

Set a minimum threshold on information gain. If the best possible split at a node yields information gain below the threshold, stop splitting. The node becomes a leaf, and its class is the majority class of the training records that reach it. This directly encodes "don't split unless you're learning something meaningful."

Shape = Round → Reject
Shape = Square → Allow (pruned — IG < 0.85)
Shape = Oval → Reject (pruned — IG < 0.85)

Post-pruning allows the tree to grow to full depth — deliberately letting it overfit the training data. Once fully grown, the tree is scanned bottom-up (from leaves toward root). At every decision node, the subtree is evaluated against a validation set (held-out data, never seen during training). If removing the subtree — replacing it with a leaf using majority voting — reduces or maintains the error rate on the validation set, the subtree is pruned. Otherwise, it's kept. The key insight: The tree is built on the training set, but pruning decisions are made using the validation set. This is called reduced-error pruning (Quinlan 1987).

Post-pruning is computationally more expensive because:

• The tree is grown to full depth first (more splits = more computation).
• Every subtree must be evaluated against the validation set.
• The process is bottom-up through the entire tree.

But it usually produces better-generalized trees because the pruning decision is data-driven (on held-out data) rather than based on arbitrary thresholds like pre-pruning.

Why post-pruning often beats pre-pruning: A split that looks weak in isolation (low information gain) might enable a very strong split below it. Pre-pruning kills that branch early. Post-pruning lets both splits grow, then evaluates the whole subtree — it can see the combined effect.

Shape = Round → Reject
Shape = Square → Size = Big → Allow
              → Size = Small → Reject
Shape = Oval → Color = Green → Reject
            → Color = Brown → Allow

Shape = Round → Reject
Shape = Square → Allow
Shape = Oval → Reject

The Minimum Description Length (MDL) principle comes from information theory (Rissanen 1978). It provides a rigorous, bit-counting way to choose between competing models — including pruning decisions in decision trees.

The central claim: the best explanation of a dataset is the one that compresses it the most.

Analogy — sending a file to a friend:

You need to transmit: 2, 4, 6, 8, 10, ..., 100.

• Option A: Send every number: "2, 4, 6, 8, 10, ..., 100" — 50 numbers, lots of bits.
• Option B: Send a short program: "Start at 2. Add 2. Stop at 100." — a few bytes. Your friend runs the program and reconstructs everything.

Option B is a compressed description. It captures the underlying pattern (the model) rather than memorizing every data point. This is what MDL rewards.

Now suppose the data has noisy outliers: 2, 4, 6, 7.9, 8, 10, ..., 100. You'd send:

1. The model ("start at 2, add 2") — cheap.
2. The list of exceptions ("record #4 is 7.9 instead of 8") — extra bits.

MDL chooses the model that minimizes total bits: $$L_{\text{total}}=L(H)+L(D\mid H)$$

where:

• $L(H)$ = length of the hypothesis — bits to encode the model (the tree structure: which attribute at each internal node, what class at each leaf).
• $L(D\mid H)$ = length of the data given the hypothesis — bits to encode the errors (which training records the model gets wrong, and what their correct labels are).

This builds on a fundamental result from information theory (Shannon 1948). From Huffman coding (a data compression algorithm):

• Frequently occurring symbols get shorter codes (fewer bits).
• Rarely occurring symbols get longer codes (more bits).

The mathematical relationship: if an event $X$ happens with probability $P(X)$, the optimal code length in bits is:

$$L(X)=-{\log }_{2}P(X)$$ Why? Think of it backwards. If I assign a code of length $L$ bits to an event, I'm implicitly saying that event happens with probability $2^{-L}$. A 1-bit code means $P=1/2$ (50% chance). A 3-bit code means $P=1/8$ (12.5% chance). The $-{\log }_2$ formula is just this relationship expressed in the forward direction. Concrete example:

• $P=1/2\to L=-{\log }_2(0.5)=1$ bit. A coin flip.
• $P=1/8\to L=-{\log }_2(0.125)=3$ bits. A one-in-eight rare event.
• $P=1\to L=-{\log }_2(1)=0$ bits. Something certain needs no message at all.

The key equivalence: Maximizing probability ≡ minimizing code length. Because $-{\log }_2$ is a monotonically decreasing function, the hypothesis with maximum probability is the same as the hypothesis with minimum description length.

MDL isn't just an ad-hoc idea — it's mathematically equivalent to Bayesian model selection. Here's the proof:

From Bayes' theorem:

$$P(H\mid D)=\frac{P(D\mid H)\times P(H)}{P(D)}$$

where:

• $P(H\mid D)$ = posterior — probability the hypothesis is correct, given the data. This is what we want to maximize.
• $P(D\mid H)$ = likelihood — probability of seeing the data if the hypothesis were true.
• $P(H)$ = prior — how probable the hypothesis was before seeing any data.
• $P(D)$ = evidence — constant for a given dataset (same for all candidate hypotheses).

To find the best hypothesis, maximize the posterior:

$${\text{argmax}}_{H}P(H\mid D)={\text{argmax}}_H\frac{P(D\mid H)P(H)}{P(D)}$$

Since $P(D)$ is constant, this is equivalent to maximizing the numerator $P(D\mid H)\times P(H)$.

Now apply the $-{\log }_2$ equivalence (maximizing probability = minimizing negative log):

$${\text{argmax}}_H[P(D\mid H)P(H)]\equiv {\text{argmin}}_H[-{\log }_{2}P(D\mid H)-{\log }_{2}P(H)]$$

And $-{\log }_{2}P(\cdot )$ is exactly $L(\cdot )$ — code length. So:

$${\text{argmin}}_H[L(D\mid H)+L(H)]$$ This is the MDL formula. Maximizing Bayesian posterior probability is mathematically identical to minimizing total description length. The prior $P(H)$ becomes $L(H)$ (simpler hypotheses get higher prior = shorter code). The likelihood $P(D\mid H)$ becomes $L(D\mid H)$ (better fit = fewer errors to encode). Why this matters: MDL gives a principled, non-arbitrary answer to "how much should we penalize complexity?" The penalty emerges naturally from information theory — it's a bit count, not an arbitrary regularization parameter like $\lambda$.

MDL can be used as a post-pruning criterion. After growing the tree fully:

1. Compute $L_{\text{total}}=L(H)+L(D\mid H)$ for the full tree.
2. For each subtree, compute what the total description length would be if that subtree were pruned (replaced with a leaf).
3. If pruning reduces $L_{\text{total}}$, prune it.

This is more principled than error-rate pruning on a validation set because:

• It doesn't require holding out a separate validation set (all data can be used for training).
• It has a clean theoretical justification via Bayesian inference.
• It automatically balances model complexity against data fit.

In practice today: MDL is less commonly used directly. Modern libraries (scikit-learn, C4.5) use cost-complexity pruning (CCP) or pessimistic error pruning, which are computationally simpler approximations of the same idea. But the principle behind MDL — balancing complexity against fit — underpins every pruning method and every model selection criterion (AIC, BIC, cross-validation).

Decision trees require numerical input — they can't process "Male" or "Female" directly. Two encoding approaches were demonstrated on the COVID dataset:

Label Encoding (sklearn.preprocessing.LabelEncoder):

• Assigns an integer to each category: Male = 0, Female = 1.
• One column per categorical feature.
• Works for binary features (Male/Female) but implies an artificial ordering for multi-category features (e.g., Red=0, Blue=1, Green=2 — the tree might interpret Green > Red, which is meaningless for nominal categories).

One-Hot Encoding (pandas.get_dummies()):

• Creates a separate binary column for each category value.
• "Gender" with values Male/Female becomes two columns: Gender_M and Gender_F, with 1 in the relevant column and 0 in the other.
• No artificial ordering. But can create many columns if a feature has many categories.

from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier()  # no parameters → unlimited growth
clf.fit(X_train, y_train)

clf = DecisionTreeClassifier(max_depth=3)
clf.fit(X_train, y_train)

Scikit-learn implements post-pruning through the cost complexity parameter (ccp_alpha). This is an implementation of minimal cost-complexity pruning (Breiman et al. 1984, from the CART algorithm).

How CCP alpha works: $$R_{\alpha }(T)=R(T)+\alpha \cdot |T|$$

where $R(T)$ is the misclassification rate of tree $T$, $|T|$ is the number of terminal nodes, and $\alpha$ (ccp_alpha) is the complexity penalty.

• Higher $\alpha$ → heavier penalty per leaf → more pruning → simpler (shallower) tree.
• Lower $\alpha$ → lighter penalty → less pruning → more complex (deeper) tree.
• $\alpha =0$ → no penalty → full tree (overfits).

This is directly analogous to the MDL principle: $R(T)$ is the error cost, $\alpha \cdot |T|$ is the model complexity cost. CCP alpha just uses a simpler linear penalty instead of counting bits.

Finding candidate alpha values:

path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas  # list of effective alpha values

Each alpha corresponds to a different pruned version of the tree.

Effect on accuracy (observed on COVID dataset):

• $\alpha =0$: Training accuracy ≈ 99.97%, test accuracy ≈ 68.9% → severe overfitting.
• $\alpha$ increasing: Training accuracy decreases. Test accuracy initially increases as overfitting is reduced.
• Optimal $\alpha \approx 0.012$: Training and test accuracy curves come closest — balanced fit.
• $\alpha$ too large: Both training and test accuracy drop → underfitting.

Choosing the right alpha: There's no single ideal value. Standard approach: plot accuracy vs. alpha for both training and test sets, find where the gap is smallest. Cross-validation is the principled method.

• Generative model: Learns $P(X,Y)$ — how each class generates data. Example: Naive Bayes.
• Discriminative model: Learns $P(Y\mid X)$ — the decision boundary directly. Example: logistic regression.
• Lazy learner: Defers processing until test time. Example: k-NN.
• Eager learner: Builds model as soon as training data arrives. Example: decision trees.
• Hypothesis: A candidate function $h:X\to Y$.
• Bias: Error from overly simple models → underfitting.
• Variance: Error from models being too sensitive to training data → overfitting.
• Regularization: Adds a penalty for large weights. Increases bias slightly, reduces variance significantly.
• Large $\lambda$: Penalty dominates → weights driven near zero → very simple hypothesis → underfitting risk.
• Small $\lambda$: Weights can grow large → model fits training data closely → overfitting risk.
• Why MSE fails for logistic regression: The sigmoid + MSE produces a non-convex cost surface with many local minima. Gradient descent gets stuck. Linear regression + MSE is convex (bowl-shaped) — one global minimum. Logistic regression uses cross-entropy loss, which is convex.