Ch.

19 — Learning from Examples

Chapter 19 — Learning from Examples

Detailed Study Notes • Sections 19.1 – 19.4
Russell & Norvig — Artificial Intelligence: A Modern Approach (Global Edition)

Contents
TOC \h \o "1-2"

Page 1
 Ch. 19 — Learning from Examples

19.1 Forms of Learning

An agent is learning if it improves its performance after making observations about the world. When the
agent is a computer, this is machine learning: the computer observes data, builds a model, and uses that
model both as a hypothesis about the world and as software that solves problems.

Why have a machine learn instead of programming it directly?

1. Unanticipated situations: designers can’t foresee every future case (a maze robot must learn each
new maze; a stock predictor must adapt from boom to bust).
2. No known solution: sometimes nobody knows how to write the program (e.g. face recognition is
done subconsciously — only ML can capture it).
ML is now standard software engineering: e.g. gravitational-lensing analysis sped up 10 million×; data-
center cooling energy cut 40%. Patterson & Dean called it a “Golden Age” for computer architecture.
Three factors determine what kind of learning happens:
• Which component of the agent is to be improved.
• What prior knowledge the agent has (this influences the model it builds).
• What data and feedback on that data is available.
Any agent component can be learned — e.g. a self-driving car can learn condition–action braking rules,
recognize buses from labeled images, learn the effects of actions (braking on wet roads), and learn part
of its utility function from passenger complaints.

Induction vs deduction
Induction: going from specific observations to a general rule (the sun rose every day → it will rise
tomorrow). Inductive conclusions MAY be wrong.
Deduction: conclusions are guaranteed correct if the premises are correct (Chapter 7).
This chapter assumes little prior knowledge — the agent starts from scratch. Input is usually a factored
representation (a vector of attribute values).

Classification vs regression
Classification: output is one of a finite set of values (sunny/cloudy/rainy, true/false).
Regression: output is a number (a temperature). A better name would be “function approximation”;
“regression” comes from Galton’s 1886 “regression to the mean.”
Three types of feedback → three main types of learning:
• Supervised learning: observe input–output pairs and learn a function mapping input to output.
Each output is a label (e.g. “bus” / “pedestrian”). The environment acts as teacher.
• Unsupervised learning: learn patterns with NO explicit feedback. The most common task is
clustering (e.g. discovering a cluster of “cat” images).
• Reinforcement learning: learn from rewards and punishments (e.g. win/lose at the end of a chess
game); the agent must decide which prior actions deserve credit/blame.

Page 2
 Ch. 19 — Learning from Examples

19.2 Supervised Learning

Formal task
Given a training set of N input–output pairs (x₁,y₁),…,(xₙ,yₙ), each generated by an unknown function y =
f(x), discover a function h that approximates the true f.
Hypothesis h: drawn from a hypothesis space H (= model class / function class), e.g. degree-3
polynomials, JavaScript functions, 3-SAT formulas.
Ground truth: the true answer yᵢ we want the model to predict.
Choosing a hypothesis space:
• Use prior knowledge about how the data was generated, OR
• Do exploratory data analysis — histograms, scatter plots, box plots, statistical tests — to get a feel
for the data, OR
• Just try multiple hypothesis spaces and see which works best.

Choosing a good hypothesis WITHIN the space

Consistent hypothesis: h(xᵢ) = yᵢ for every training example. With continuous outputs we can’t expect
an exact match, so we seek a best-fit function where each h(xᵢ) is close to yᵢ.
Generalization: the TRUE measure of h is how it handles UNSEEN inputs — evaluated on a separate
test set. h generalizes well if it accurately predicts the test set.
Four hypothesis spaces on the same data (Figure 19.1):
• Straight lines h(x)=w₁x+w₀ — no line is consistent with the points.
• Sinusoids h(x)=w₁x+sin(w₀x) — not quite consistent but fits both data sets very well.
• Piecewise-linear (connect the dots) — ALWAYS consistent.
• Degree-12 polynomials — consistent (a degree-12 polynomial can perfectly fit 13 points), but
consistency ≠ a good guess.

Bias and variance — the core trade-off

Bias: tendency of a hypothesis to deviate from the expected value, averaged over different training
sets; usually caused by restrictions of the hypothesis space. High bias → underfitting (fails to find a
pattern). Linear functions have HIGH bias; piecewise-linear has LOW bias.
Variance: amount the hypothesis changes due to fluctuations in the training data. High variance →
overfitting (pays too much attention to the specific data, performs poorly on unseen data). Degree-
12 polynomials have HIGH variance.
Bias–variance trade-off: complex low-bias models fit training data well; simple low-variance models
generalize better.
Ockham’s razor / Einstein: prefer the simplest hypothesis that adequately fits the data. But defining
“simple” is hard — deep nets have billions of parameters yet generalize well, so parameter count alone
isn’t fitness; aim for “appropriateness.”
Bayesian view of model choice:
h* = argmax over h∈H P(h | data) = argmax over h∈H P(data | h)
P(h) (Bayes’ rule)

Page 3
 Ch. 19 — Learning from Examples

Give smooth low-degree polynomials a HIGH prior P(h) and spiky degree-12 ones a LOW prior — allow
unusual functions only when the data really demand them.

Expressiveness vs complexity trade-off

Why not let H = all programs / Turing machines? Because more expressive H makes FINDING a good
hypothesis harder: fitting a line is easy, high-degree polynomials harder, Turing machines undecidable.
Also we want h(x) to be fast to compute afterwards.
So most work uses simple representations. But the trade-off isn’t simple — an expressive language can let
a SIMPLE hypothesis fit, whereas a restricted language may force any consistent hypothesis to be
complex. Deep learning uses complex representations but keeps h(x) computation bounded.

19.2.1 Example problem: Restaurant waiting

Output y = WillWait (Boolean). Input x = vector of 10 discrete attributes used throughout the chapter:
• Alternate, Bar, Fri/Sat, Hungry, Patrons (None/Some/Full), Price ($/$$/$$$), Raining, Reservation,
Type (French/Italian/Thai/burger), WaitEstimate (0–10/10–30/30–60/>60).
There are 2⁶ × 3² × 4² = 9,216 possible input combinations, but only 12 examples are given — the other
9,204 outputs are unknown. Guessing those missing outputs from just 12 examples is the essence of
induction.

Page 4
 Ch. 19 — Learning from Examples

19.3 Learning Decision Trees

A decision tree maps a vector of attribute values to a single output “decision.” It tests attributes from
the root down: each internal node tests one attribute, branches are labeled with attribute values, and
leaves give the output. For now we consider discrete inputs and Boolean output (positive/negative
example) — Boolean classification.

19.3.1 Expressiveness of decision trees

Logical equivalence
A Boolean decision tree equals a statement Output ⇔ (Path₁ ∨ Path₂ ∨ …), where each Path is a
conjunction of attribute-value tests from root to a true leaf. This is disjunctive normal form → ANY
propositional-logic function can be written as a decision tree.
Concise for many problems (many “How-To” manuals are decision trees), but some functions need
EXPONENTIALLY large trees: the majority function and the parity function. Real-valued diagonal
boundaries (y > A₁+A₂) are hard because tree tests give only axis-aligned rectangular boxes.
No representation is efficient for ALL functions. With n Boolean attributes the truth table has 2ⁿ rows, so
there are 2^(2ⁿ) distinct Boolean functions. With 20 attributes → 2^1,048,576 ≈ 10^300,000 functions —
a million-bit representation can’t capture them all.

19.3.2 Learning decision trees from examples

We want the SMALLEST tree consistent with the examples, but finding the guaranteed-smallest is
intractable. LEARN-DECISION-TREE uses a greedy divide-and-conquer heuristic: test the MOST
IMPORTANT attribute first (the one that makes the most difference), then recurse on the subproblems
→ short paths, shallow tree.
Type is a POOR first attribute (its four values each leave equal positives/negatives). Patrons is GOOD:
None→all No, Some→all Yes, Full→mixed (then Hungry is a good second test).

Four recursive cases

1. All remaining examples positive (or all negative) → answer Yes (or No).
2. Mixed positives and negatives → choose the best attribute to split on.
3. No examples left → return PLURALITY-VALUE (most common output) of the PARENT’s examples.
4. No attributes left but mixed examples → same description, different labels (noise,
nondeterminism, or an unobservable attribute) → return the most common output of the remaining
examples.
LEARN-DECISION-TREE algorithm (Figure 19.5):
1. If examples empty → return PLURALITY-VALUE(parent_examples).
2. Else if all examples same classification → return that classification.
3. Else if attributes empty → return PLURALITY-VALUE(examples).
4. Else A ← argmax IMPORTANCE(a, examples); make a root test on A; for each value v of A, recurse
on the matching subset and attach the subtree.

What the learned tree tells us

Page 5
 Ch. 19 — Learning from Examples

Examples don’t appear in the tree — only attribute tests (internal nodes), values (branches), and outputs
(leaves). The induced tree (Figure 19.6) differs from the “true” tree but is consistent AND simpler.
It dropped Raining and Reservation (not needed to classify the examples) and found an unexpected
pattern (SR waits for Thai on weekends). It WILL err on unseen cases (e.g. Full + wait 0–10 when not
hungry) until given more data.
Learning curve (“happy graph”): plot test accuracy vs training-set size, averaging many random
splits. On the restaurant problem it climbs to ~95% — accuracy rises as the training set grows.

19.3.3 Choosing attribute tests (entropy & information gain)

IMPORTANCE is measured by information gain, defined via entropy — the fundamental quantity of
information theory (Shannon & Weaver, 1949). Entropy measures the uncertainty of a random variable:
more information → less entropy.
H(V) = Σₖ P(vₖ) log₂ (1/P(vₖ)) = − Σₖ P(vₖ) log₂ P(vₖ)

Entropy intuition (worked values)

Always-heads coin → 0 bits. Fair coin → 1 bit: −(0.5 log₂0.5 + 0.5 log₂0.5) = 1.
Fair 4-sided die → 2 bits. Loaded 99%-heads coin → −(0.99 log₂0.99 + 0.01 log₂0.01) ≈ 0.08 bits.
Boolean entropy helper: B(q) = −(q log₂ q + (1−q) log₂(1−q)), so H(Loaded) = B(0.99)
≈ 0.08.
For a set with p positive and n negative examples, the output entropy is B(p/(p+n)). The restaurant set
has p=n=6 → B(0.5) = 1 bit.
An attribute A with d values splits E into E₁…E_d (Eₖ has pₖ positives, n ₖ negatives). Expected
remaining entropy:
Remainder(A) = Σ (k=1..d) ((pₖ+nₖ)/(p+n)) · B(pₖ/(pₖ+nₖ))
Information gain = expected entropy reduction (this IS the IMPORTANCE function):
Gain(A) = B(p/(p+n)) − Remainder(A)

Restaurant gains
Gain(Patrons) = 1 − [ (2/12)B(0/2) + (4/12)B(4/4) + (6/12)B(2/6) ] ≈
0.541 bits
Gain(Type) = 1 − [ (2/12)B(1/2)×2 + (4/12)B(2/4)×2 ] = 0 bits
Patrons has the maximum gain of any attribute → chosen as the root. Confirms the earlier intuition.

19.3.4 Generalization and overfitting

We want a tree that fits training data AND generalizes. Overfitting becomes MORE likely as attributes
grow and LESS likely as training examples grow. Larger hypothesis spaces (more nodes / higher degree)
can both fit and overfit more.

Decision tree pruning

Combat overfitting by eliminating nodes that aren’t clearly relevant. Start with the full tree; find a test
node whose descendants are all leaves; if it looks irrelevant (detecting only noise), replace it with a leaf.

Page 6
 Ch. 19 — Learning from Examples

Repeat.
An irrelevant attribute splits examples into subsets each with roughly the whole-set proportion p/(p+n) →
information gain near zero. So low gain hints at irrelevance — but how low?

χ² (chi-squared) pruning — significance test

Null hypothesis: the attribute is irrelevant (true info gain = 0). Compute expected counts assuming
irrelevance:
p̂ₖ = p · (pₖ+nₖ)/(p+n) , n̂ₖ = n · (pₖ+nₖ)/(p+n)
Total deviation: Δ = Σ (k=1..d) [ (pₖ−p̂ₖ)²/p̂ₖ + (nₖ−n̂ₖ)²/n̂ₖ ]
Δ follows the χ² distribution with d−1 degrees of freedom. E.g. Type (4 values → 3 dof): Δ≥7.82 rejects
irrelevance at 5%; Δ≥11.35 at 1%. Below that → prune the branch.
Benefits: tolerates noise (pruned trees beat unpruned on noisy data), and are smaller / easier to
understand / faster.

Why NOT early stopping?

Early stopping = stop growing when no single attribute looks good (instead of grow-then-prune). Problem:
it misses cases where no SINGLE attribute is informative but a COMBINATION is — e.g. XOR of two
attributes (neither alone helps, but splitting then splitting again is very informative). Grow-then-prune
handles this correctly.

19.3.5 Broadening the applicability of decision trees

• Missing data: how to classify an example missing a test attribute, and how to adjust the gain
formula when values are unknown (Exercise [Link]).
• Continuous / multivalued inputs: use a split-point test (an inequality like Weight > 160). Find good
split points by sorting values and considering only boundaries between examples with different
classifications. Splitting is the most expensive part of real-world decision-tree learning.
• Many-valued attributes (Zipcode, CreditCardNumber): use the information gain ratio to avoid
splitting into single-example subtrees, or an equality test A=vₖ.
• Continuous output → regression tree: each leaf holds a linear function of some numerical
attributes rather than a single value. CART (Classification And Regression Trees) covers both.

Decision trees: pros & cons

Pros: easy to understand, scalable to large data, handle discrete AND continuous inputs, do
classification AND regression. Often the FIRST method tried for extracting a classifier.
Cons: suboptimal accuracy (greedy search); deep trees are slow to evaluate; UNSTABLE — one new
example can change the root and the whole tree. Random forests (§19.8.2) fix some of these.

Page 7
 Ch. 19 — Learning from Examples

19.4 Model Selection and Optimization

Goal: pick a hypothesis that optimally fits FUTURE examples. Two ingredients to define: “future
example” and “optimal fit.”

Stationarity & i.i.d. assumption

Assume future examples are like the past. Each example Eⱼ has the SAME prior distribution (stationarity)
and is INDEPENDENT of previous ones:
P(Eⱼ) = P(Eⱼ₊₁) = … and P(Eⱼ) = P(Eⱼ | Eⱼ₋₁, Eⱼ₋₂, …)
Examples satisfying both are independent and identically distributed (i.i.d.).
“Optimal fit” = (initially) minimizing error rate — the proportion of times h(x) ≠ y. Estimate it on a test
set; never let the hypothesis peek at the test answers.

Why THREE data sets

One hypothesis → train/test split suffices. But tuning multiple hypotheses (comparing models, adjusting
“knobs” = hyperparameters — parameters of the model CLASS, not the individual model) lets the
RESEARCHER peek at the test set across trials.
1. Training set — train candidate models.
2. Validation set (dev set) — evaluate candidates and pick the best.
3. Test set — locked away for ONE final unbiased evaluation.

k-fold cross-validation
When data is scarce, each example does double duty (train + validate, not simultaneously). Split into k
equal subsets; do k rounds, each holding out 1/k as validation and training on the rest; average the k
scores.
Popular k = 5 or 10 (5–10× the compute). Extreme k = n is leave-one-out cross-validation (LOOCV). Even
so, you still need a separate test set.

Model selection vs optimization

Model selection: choose a good hypothesis SPACE (better named “model-class selection”). Partly
qualitative (polynomials vs trees) and partly quantitative (which Degree).
Optimization (= training): find the best hypothesis WITHIN that space.
MODEL-SELECTION (Figure 19.8): try increasing size (tree nodes / polynomial degree), run CROSS-
VALIDATION at each, pick the size with the lowest validation error, retrain on all training data, then report
error on the held-out test set.

19.4.1 Model selection

Two validation-curve patterns (Figure 19.9)
Training error decreases monotonically as complexity grows (often reaching zero).
(a) U-shaped validation curve: error falls, then rises as the model overfits. MODEL-SELECTION picks
the bottom of the U (e.g. a 7-node tree). Best balance of under/overfitting.
(b) Keeps decreasing: after an initial dip the validation error keeps falling (e.g. CNN on MNIST best at
1,000,000 parameters).

Page 8
 Ch. 19 — Learning from Examples

Interpolation: a model that exactly fits all training data has interpolated it. Classes often overfit as
capacity nears interpolation; but deep nets, kernel machines, random forests, and boosted
ensembles tend to KEEP improving (pattern b) — more capacity → more candidate functions
matching the true f.

19.4.2 From error rates to loss

Minimizing error rate isn’t the full story: different errors cost differently (classifying non-spam as spam is
worse than the reverse). Decision makers maximize expected utility; in ML we equivalently MINIMIZE a
loss function.
L(x, y, ŷ) = Utility(use y given x) − Utility(use ŷ given x)
Usually simplified to L(y, ŷ) (independent of x). E.g. L(spam, nospam)=1 but L(nospam, spam)=10 (10×
worse). L(y, y)=0 always.

Three standard loss functions

Absolute-value (L₁): L₁(y,ŷ) = |y − ŷ|
Squared-error (L₂): L₂(y,ŷ) = (y − ŷ)²
0/1 loss: L₀₁(y,ŷ) = 0 if y=ŷ else 1
Generalization vs empirical loss:
GenLoss_L(h) = Σ over (x,y)∈E L(y, h(x)) P(x, y)
h* = argmin over h∈H GenLoss_L(h)
P(x,y) is usually unknown, so estimate with empirical loss over N examples:
EmpLoss_{L,E}(h) = (1/N) Σ over (x,y)∈E L(y, h(x))
ĥ* = argmin over h∈H EmpLoss_{L,E}(h)

Four reasons ĥ* differs from the true f

1. Unrealizability: H doesn’t contain f (the problem is realizable if H DOES contain f).
2. Variance: different example sets → different hypotheses (→ 0 as examples grow, if realizable).
3. Noise: f is nondeterministic / noisy — noise can’t be predicted, only characterized.
4. Computational complexity: searching a large H is intractable, so we settle for a good-enough
hypothesis.
Small-scale learning (dozens–thousands of examples): loss is mostly approximation + estimation error.
Large-scale learning (millions): loss is dominated by computation limits.

19.4.3 Regularization
Instead of cross-validation, directly minimize a weighted sum of empirical loss and hypothesis
complexity (the total cost):
Cost(h) = EmpLoss(h) + λ · Complexity(h) ĥ* = argmin over h∈H Cost(h)

Regularization details
λ is a hyperparameter — a conversion rate between loss and complexity. Good λ balances a simple
function’s loss against a complex one’s tendency to overfit. Penalizing complexity = regularization (seeking

Page 9
 Ch. 19 — Learning from Examples

more “regular” functions).

Two choices: the loss function (L₁/L₂) and the regularization function (complexity measure). For
polynomials, a good one is the sum of squared coefficients (discourages the wiggly degree-12 fit).
Feature selection: discard irrelevant attributes to simplify — χ² pruning is a kind of feature selection.
MDL (minimum description length): measure loss AND complexity in BITS — encode the hypothesis
as a program plus encode the data (correct predictions cost 0 bits); minimize total bits.

19.4.4 Hyperparameter tuning

• Hand-tuning: guess values from experience, train, measure on validation, use intuition, repeat.
• Grid search: try all combinations of a few discrete hyperparameters (parallelizable across
machines).
• Random search: sample uniformly from all settings — good when there are too many
combinations and for continuous values.
• Bayesian optimization: treat hyperparameter choice as an ML problem — model loss y =
f(hyperparameters x), update beliefs each run, trade off exploitation vs exploration (upper
confidence bounds, like MCTS); assumes f is a Gaussian process. Can beat expert hand-tuning.
• Population-based training (PBT): start with random search over a population; later generations
inherit successful values plus random mutation (like genetic algorithms) — parallel AND informed
by earlier runs.

Page 10
 Ch. 19 — Learning from Examples

Exam Cheatsheet
Condensed, high-yield summary of Chapter 19 (19.1–19.4).

Core concepts at a glance

Term One-line meaning
Machine learning Observe data → build a model used as both hypothesis and software.
Induction Specific examples → general rule; may be wrong (vs deduction =
guaranteed).
Classification / regression Output is a finite category / a number.
Supervised / unsupervised / Input-output pairs / patterns with no feedback (clustering) / rewards &
RL punishments.
Hypothesis space H Set of candidate functions (= model class). h is a hypothesis/model from H.
Consistent / best-fit h(xᵢ)=yᵢ exactly / h(xᵢ) close to yᵢ (continuous).
Generalization Performance on UNSEEN test data — the true measure of h.
Bias / underfitting Deviation from expected value due to H restrictions; fails to find the
pattern.
Variance / overfitting Change due to data fluctuation; fits the specific data, fails on new data.
Ockham’s razor Prefer the simplest hypothesis that adequately fits the data.
Decision tree Tests attributes root→leaf; equals DNF → any propositional function.
Entropy H(V) Uncertainty in bits; fair coin=1, 4-die=2, 99% coin≈0.08.
Information gain Entropy reduction from a split = IMPORTANCE; pick max-gain attribute.
Pruning / χ² pruning Remove irrelevant nodes; significance test on deviation Δ (d−1 dof).
Early stopping (avoid) Misses informative attribute COMBINATIONS (e.g. XOR); grow-then-prune
instead.
CART / regression tree Leaves hold linear functions for numeric output.
i.i.d. / stationarity Examples independent + identically distributed; future like past.
Train / validation / test Fit / pick model & tune hyperparameters / one final unbiased score.
k-fold CV / LOOCV k rounds, each holds out 1/k for validation; k=n = leave-one-out.
Loss L(y,ŷ) Utility lost by predicting ŷ; L₀₁, L₁ (abs), L₂ (squared).
Regularization Minimize EmpLoss + λ·Complexity; penalize complex hypotheses.
Hyperparameter tuning Hand / grid / random search; Bayesian optimization; PBT.

Things examiners love to test

• Compute entropy and information gain for an attribute split (know B(q) and Remainder).

Page 11
 Ch. 19 — Learning from Examples

• Explain bias vs variance and map them to underfitting vs overfitting with the Figure 19.1 example.
• Why Patrons (gain ≈ 0.541) beats Type (gain = 0) as the root.
• Why grow-then-prune beats early stopping (XOR-style attribute combinations).
• Distinguish training / validation / test sets and why the test set must stay locked away.
• State the four reasons ĥ* differs from f: unrealizability, variance, noise, computational complexity.
• Give the loss functions (L₀₁, L₁, L₂) and explain asymmetric costs (spam example).

Page 12
 Ch. 19 — Learning from Examples

Formula Sheet
Name Formula
Bayesian model choice h* = argmax_h P(h | data) = argmax_h P(data | h)
P(h)

Entropy H(V) = − Σₖ P(vₖ) log₂ P(vₖ)

Boolean entropy B(q) = −(q log₂ q + (1−q) log₂(1−q))

Set output entropy H(Output) = B(p / (p+n))

Remainder after split Remainder(A) = Σₖ ((pₖ+nₖ)/(p+n)) B(pₖ/(pₖ+nₖ))

Information gain Gain(A) = B(p/(p+n)) − Remainder(A)

χ² expected counts p̂ₖ = p·(pₖ+nₖ)/(p+n) ; n̂ₖ = n·(pₖ+nₖ)/(p+n)

χ² deviation Δ = Σₖ [ (pₖ−p̂ₖ)²/p̂ₖ + (nₖ−n̂ₖ)²/n̂ₖ ] (d−1 dof)

i.i.d. assumption P(Eⱼ)=P(Eⱼ₊₁)=… ; P(Eⱼ)=P(Eⱼ | Eⱼ₋₁,…)

Absolute-value loss (L₁) L₁(y,ŷ) = |y − ŷ|

Squared-error loss (L₂) L₂(y,ŷ) = (y − ŷ)²

0/1 loss L₀₁(y,ŷ) = 0 if y=ŷ else 1

General loss L(x,y,ŷ) = Utility(y|x) − Utility(ŷ|x)

Generalization loss GenLoss_L(h) = Σ L(y,h(x)) P(x,y)

Best hypothesis (gen) h* = argmin_h GenLoss_L(h)

Empirical loss EmpLoss_{L,E}(h) = (1/N) Σ L(y,h(x))

Best hypothesis (emp) ĥ* = argmin_h EmpLoss_{L,E}(h)

Regularized cost Cost(h) = EmpLoss(h) + λ · Complexity(h)

Number of Boolean functions with n attributes: 2^(2ⁿ)

Key numbers worth memorizing

Fair coin = 1 bit, fair 4-sided die = 2 bits, 99% loaded coin ≈ 0.08 bits.
Restaurant set: p=n=6 → H = B(0.5) = 1 bit. Gain(Patrons) ≈ 0.541; Gain(Type) = 0.
χ² with 3 dof: reject at 5% if Δ ≥ 7.82; at 1% if Δ ≥ 11.35.
Restaurant inputs: 2⁶×3²×4² = 9,216 combinations; only 12 examples given. Spam: L(nospam,spam)=10 vs
L(spam,nospam)=1.

Page 13
 Ch. 19 — Learning from Examples

Practice Questions with Solutions

Use the restaurant dataset (Figure 19.2, p=n=6) where referenced.

Q1. Entropy of a biased coin

Compute the entropy of a coin that lands heads with probability 0.75. Is it more or less than a fair coin?
Solution:
H = B(0.75) = −(0.75 log₂ 0.75 + 0.25 log₂ 0.25).
log₂ 0.75 ≈ −0.415, log₂ 0.25 = −2. So H ≈ −(0.75×(−0.415) + 0.25×(−2)) = −(−0.311 − 0.5) = 0.811 bits.
Less than the fair coin’s 1 bit — a biased coin has lower uncertainty.

Q2. Information gain of a split

An attribute A is Boolean and splits 12 examples (6+, 6−) into: branch A=true with (4+, 2−) and branch
A=false with (2+, 4−). Compute Gain(A).
Solution:
Whole-set entropy = B(6/12) = B(0.5) = 1 bit.
B(4/6) = B(0.667): −(0.667 log₂ 0.667 + 0.333 log₂ 0.333) ≈ −(0.667×(−0.585)+0.333×(−1.585)) ≈ 0.918. By
symmetry B(2/6)=B(0.333)≈0.918.
Remainder = (6/12)(0.918) + (6/12)(0.918) = 0.918.
Gain(A) = 1 − 0.918 ≈ 0.082 bits. A weak but nonzero split.

Q3. Verify Gain(Type) = 0

Type splits the restaurant data into French (1+,1−), Italian (1+,1−), Thai (2+,2−), burger (2+,2−). Show its
information gain is 0 and explain why.
Solution:
Each branch has equal positives and negatives → each B = B(0.5) = 1 bit.
Remainder = (2/12)(1) + (2/12)(1) + (4/12)(1) + (4/12)(1) = 1 bit.
Gain(Type) = 1 − 1 = 0 bits. Type tells us nothing because every branch is as uncertain as the whole set
— hence a poor root choice.

Q4. Bias vs variance

Match each to underfitting/overfitting and give the Figure 19.1 example: (a) high bias, (b) high variance.
Solution:
(a) High bias → underfitting. The straight-line fit can only represent slope, missing other patterns. Small
data changes barely move it (low variance).
(b) High variance → overfitting. The degree-12 polynomial fits all 13 points but swings wildly at the
ends; a slightly different data set gives a very different curve.

Q5. Why three data sets?

Page 14
 Ch. 19 — Learning from Examples

A researcher tries 20 settings of the χ² pruning threshold, each time measuring error on the same test
set, and reports the best. What is wrong, and what is the fix?
Solution:
No single hypothesis peeked at the test set, but the RESEARCHER did — selecting the best of 20 test
scores biases the estimate optimistically (the test set effectively became a validation set).
Fix: use a separate validation/dev set to choose among the 20 settings, and lock the test set away for
ONE final unbiased evaluation. With scarce data, use k-fold cross-validation for the validation step
(but still keep a separate test set).

Q6. Loss and expected utility

A spam filter has L(nospam, spam)=10 and L(spam, nospam)=1. For a borderline email, the model
estimates P(spam)=0.6. Which label minimizes expected loss?
Solution:
Predict “spam”: risk = loss when it’s actually nospam = P(nospam)×L(nospam,spam) = 0.4×10 = 4.0.
Predict “nospam”: risk = P(spam)×L(spam,nospam) = 0.6×1 = 0.6.
Predict NOSPAM (expected loss 0.6 < 4.0) — even though spam is more likely, mislabeling real mail is
10× costlier, so the threshold to call something spam is high.

Q7. Cross-validation arithmetic

You have 100 examples and use 5-fold cross-validation. (a) How many examples are in each validation
fold? (b) How many training/validation rounds run? (c) What does LOOCV mean here?
Solution:
(a) 100/5 = 20 examples held out per fold.
(b) 5 rounds, each training on 80 and validating on the other 20; average the 5 scores.
(c) LOOCV = leave-one-out = k = n = 100 rounds, each holding out a single example.

Q8. Conceptual short answers

(a) Why does grow-then-prune beat early stopping? (b) Name the four reasons the learned ĥ* can differ
from the true f.
Solution:
(a) Early stopping halts when no single attribute is informative, but some functions (e.g. XOR) have no
single useful attribute while a COMBINATION is highly informative. Growing fully then pruning discovers
these; early stopping misses them.
(b) Unrealizability (f not in H), variance, noise, and computational complexity.

Page 15
 Ch. 19 — Learning from Examples

More Practice — University Problem Sets

Free resources from major universities on decision trees, bias/variance, model selection, and ML theory
(with solutions where available). Links open in your browser.

UC Berkeley — CS188 (uses this exact textbook)

• CS188 course site (exams + sections with solutions) — Decision trees, entropy/information gain, and
overfitting problems; midterms/finals have full keys.
• CS189 Introduction to Machine Learning — Bias–variance, cross-validation, regularization, and loss
functions with problem sets and exams.

MIT OpenCourseWare
• 6.034 Artificial Intelligence — Decision-tree and ID3/entropy lectures, quizzes, and exams with
solutions.
• 6.036 Introduction to Machine Learning — Full ML course: loss functions, regularization, model
selection — with auto-graded exercises.

Stanford
• CS229 Machine Learning — Bias–variance, regularization, model selection notes plus problem sets
with solutions.
• CS221 Artificial Intelligence — Learning, loss minimization, and generalization assignments with exam
practice.

Other high-quality sources

• AIMA companion site (Russell & Norvig) — Official Chapter 19 exercises for this textbook.
• Google Machine Learning Crash Course — Interactive lessons on training/validation/test splits,
overfitting, and regularization.

Study tip
The two highest-yield skills: (1) compute entropy + information gain for a split by hand (memorize B(q)
and the Remainder formula), and (2) explain the bias–variance / underfitting–overfitting picture using
Figure 19.1. Most decision-tree and model-selection exam questions reduce to these two.

Page 16