# COMP3308 — Artificial Intelligence: Search, Reasoning & Learning
> Leon | Original study notes
[English](COMP3308.md) · [中文](COMP3308.zh.md)
## Guided extensions
Read the linked lesson first. Then follow the story, predict the output, run the complete program and check the explanation. Each case adds one practical challenge.
1. [Reopen a state when A* finds a better route](#lab-astar-heuristics-astar-reopen-states) — Distinguish admissibility, consistency and reopening.
2. [Keep long-text likelihoods in log space](#lab-naive-bayes-log-space-word-counts) — Connect smoothing, repeated words and stable normalization.
3. [See which class disappears inside an average](#lab-classification-metrics-macro-micro-report) — Calculate class reports before comparing averages.
Explore how intelligent systems search for actions, reason under uncertainty and learn predictive patterns. Original analogies and worked examples connect the mathematics to implementation choices and the limits of each method.
An independently written guide to search, optimization, games, supervised learning, neural networks, probabilistic reasoning and clustering. Each topic includes original worked reasoning and teaching notes. Reinforcement and association learning receive orientation only.
## Connected knowledge framework
### Search and strategic decisions
- [Model a problem, then choose a frontier](#search-models)
- [A* and trustworthy lower bounds](#astar-heuristics)
- [Hill climbing, restarts and beam search](#local-search)
- [Simulated annealing and genetic search](#stochastic-optimization)
- [Minimax and alpha–beta bounds](#minimax-pruning)
- [Cutoffs, chance nodes and multiple players](#bounded-stochastic-games)
### Learning from labeled examples
- [Learning tasks and nearest neighbors](#learning-neighbors)
- [1R: a useful one-feature baseline](#one-rule)
- [Naive Bayes and smoothed likelihoods](#naive-bayes)
- [Validation, cross-validation and comparisons](#evaluation-design)
- [Confusion matrices and error costs](#classification-metrics)
- [Decision trees, entropy and information gain](#decision-tree-information)
- [Grow useful trees without memorizing noise](#tree-generalization)
### Neural representations and model families
- [Perceptrons and linear decision boundaries](#perceptron)
- [Multilayer networks and backpropagation](#backpropagation)
- [Optimization, initialization and regularization](#neural-training)
- [Autoencoders and learned representations](#autoencoders)
- [Convolutions, pooling and shared features](#convolutional-networks)
- [Margins, soft constraints and kernels](#support-vector-machines)
- [Bagging, boosting and random forests](#ensemble-learning)
### Uncertainty and unsupervised structure
- [Joint distributions, conditioning and Bayes](#probability-reasoning)
- [Bayesian networks and inference](#bayesian-networks)
- [K-means, representatives and vector quantization](#kmeans)
- [Hierarchies, thresholds and cluster quality](#clustering-comparisons)
## Model a problem, then choose a frontier
### 01 / The story
Imagine a delivery robot inside a museum. A state might record only its room, but that description fails if some doors require a key: two visits to the same room can have different futures. Recording the room and key status repairs the model. The robot then keeps a tray of unfinished routes.
A queue explores nearby rooms first; a stack follows one corridor deeply; a priority tray follows the cheapest journey so far. The analogy separates two decisions: describe enough of the world to predict legal moves, then choose which unfinished route deserves attention.
### 02 / The principle
A search problem specifies an initial state, actions, a transition model, a goal test and path costs. Search nodes also store parent links and accumulated cost; multiple nodes may represent the same state. Breadth-first search uses a FIFO frontier and finds a shallowest goal with finite branching, giving minimum cost when steps have equal cost.
Depth-first search uses a stack, needs little frontier memory, but can follow an infinite branch and is not generally optimal. Depth-limited search can miss deeper goals.
Iterative deepening repeats increasing limits, retaining depth-first memory with shallowest-goal completeness under finite branching. Uniform-cost search removes the smallest accumulated cost and tests goals on removal; on infinite spaces its usual completeness guarantee needs costs bounded below by a positive number.
### 03 / The formula, unpacked
```text
g(n) = Σ edge costs along the route to n
BFS: minimum depth; DFS: maximum current depth; UCS: minimum g(n)
BFS tree frontier: O(bᵈ); DFS tree frontier: O(bm); IDS: O(bd)
```
The symbol g(n) is the cost already paid to reach search node n. The summation adds every edge on that route, not just the last edge. Here b is the finite branching factor, d the shallowest solution depth, and m the maximum search depth.
The memory bounds describe conventional tree-search frontiers; a graph-search visited set adds storage. Frontier order describes which node is expanded next, not the final path itself.
### 04 / A first worked example
A robot has routes S→A costing 1, A→G costing 9, S→B costing 4 and B→G costing 2. Both goals lie two edges away. If A is generated first, breadth-first search can return S→A→G, costing 10.
Uniform-cost search removes S, then A with cost 1, then B with cost 4. Its goal candidates have costs 10 and 6, so it removes the cost-6 candidate and returns S→B→G. Parent links reconstruct that route. The expansion list S,A,B,G is not itself a legal route.
### Words to know
- **State:** Information sufficient to determine legal future actions.
- **Frontier:** Generated routes waiting to be explored.
- **Path cost:** The sum of step costs on one route.
### Let us work through it
**Why include a key in the state?**
It changes which doors can be opened.
**Why test UCS goals on removal?**
An earlier generated goal may be more expensive than another unfinished route.
**Is an expansion list a path?**
Usually not; use parent links to reconstruct one connected route.
### Two equal-depth routes
Directed edges are S→A:2,A→G:8,S→B:3,B→G:2. No other edges exist. A is generated before B. Compare BFS and UCS.
**Choose the method**
Separate the number of edges from the sum of their costs.
1. Both routes have two edges, so BFS can select A’s route by the stated order.
2. Add costs: S-A-G costs 2+8=10; S-B-G costs 3+2=5.
3. UCS removes A at 2, B at 3, then the goal at 5 before the goal at 10.
**Interpret the answer**
BFS can return cost 10; UCS returns S-B-G with cost 5.
**Check the reasoning**
The graph has only these two complete routes, and 5 is the smaller total.
### A depth limit misses a solution
A chain S→A→B→G has unit costs. Root depth is zero. Try depth limit 2, then iterative deepening limits 0,1,2,3.
**Choose the method**
Label depths before deciding which nodes are reachable within a limit.
1. S,A,B,G have depths 0,1,2,3 respectively.
2. Limit 2 reaches B but cannot generate a permitted goal at depth 3.
3. Limits 0,1,2 fail; limit 3 reaches G and reconstructs all three edges.
**Interpret the answer**
The depth-2 search terminates without a solution; iterative deepening finds cost 3 at limit 3.
**Check the reasoning**
Three edges are unavoidable because the graph is a single chain.
### Leon's further thinking
**Cost changes the algorithm choice**
Counting edges solves cheapest travel only when every edge has equal cost. With differing costs, compare accumulated sums.
**State merging needs justification**
Merging two room visits is safe only if their future legal actions and costs match. A remaining battery budget can matter just as a key does.
**Watch out:** Calling depth-limited search complete merely because it terminates confuses termination with finding an existing goal. Its limit must reach a solution, and cycle handling must match the chosen state representation.
Check your understanding
When does breadth-first search behave like uniform-cost search?
When every step has the same positive cost and tie handling is aligned: accumulated cost is a constant times depth, so both expand layers in the same order.
## A* and trustworthy lower bounds
### 01 / The story
Suppose a courier chooses between partly completed journeys. Looking only at money already spent rewards cheap starts that may have expensive endings. Looking only at a map estimate rewards routes that appear close to the destination despite costly detours already taken. A* writes both numbers on each route card.
Its remaining-cost estimate must behave like a defensible lower quote, not an optimistic marketing promise with arbitrary values. A relaxed map, where some obstacles disappear, supplies such a quote. Better lower quotes save exploration, although calculating them can itself be expensive.
### 02 / The principle
A* expands the frontier node minimizing accumulated cost plus estimated remaining cost. Admissibility means the estimate never exceeds the true cheapest remaining cost. Consistency additionally bounds each estimate by one step plus the successor estimate; with zero goal estimates it implies admissibility and nondecreasing f along paths. Tree-search A* is optimal with an admissible heuristic under the usual termination assumptions.
Graph search can safely close nodes permanently with a consistent heuristic; an admissible but inconsistent heuristic can require reopening a state when a cheaper route appears. Test the goal when selected for expansion. Finite branching and a positive lower step-cost bound support completeness in infinite spaces. Memory is often the practical bottleneck; IDA* trades repeated work for bounded depth-first storage.
### 03 / The formula, unpacked
```text
f(n) = g(n) + h(n)
Admissible: 0 ≤ h(n) ≤ h*(n)
Consistent: h(n) ≤ c(n,n′) + h(n′)
hmax(n) = max(h₁(n), …, hₖ(n))
```
Here h(n) estimates the remaining cost and h*(n) is the true minimum remaining cost. The edge from n to n′ costs c(n,n′). Thus f is a lower bound on a solution through n when h is admissible.
Taking the maximum of several admissible heuristics preserves admissibility; summing them generally does not. A dominating heuristic is at least as large everywhere, but total runtime also depends on its computation cost and tie handling.
### 04 / A first worked example
Consider S→A of cost 2, A→G of cost 3, S→B of cost 1 and B→G of cost 8. Set h(A)=3, h(B)=1, h(S)=2 and h(G)=0. After expanding S, A has f=5 while B has f=2. Expanding B generates a goal with g=9, but A remains at f=5.
A is expanded next and creates a better goal with g=5. Only when this goal is removed does search finish. All heuristic values are admissible and consistent; stopping at the first generated goal would return the wrong answer.
### Words to know
- **Heuristic:** An estimate of remaining cost used to order exploration.
- **Admissible:** Never larger than the true cheapest remaining cost.
- **Consistent:** No estimate drops by more than the cost of one transition.
### Let us work through it
**What is f when g=4,h=3?**
Seven: add paid and estimated remaining cost.
**Is zero heuristic admissible for nonnegative costs?**
Yes; A* then orders nodes like UCS.
**May two lower bounds be added?**
Not generally; they may count the same necessary work twice.
**Why is “admissible” alone not enough for a permanent closed set?**
A state can be expanded before its best g is discovered when the heuristic is inconsistent. The example expands A twice to recover the better path.
### Choose the next frontier node
Frontier entries A:(g=3,h=4), B:(5,1), C:(2,6). Assume these are admissible estimates and expand smallest f.
**Choose the method**
Compute each total before comparing.
1. A has f=3+4=7.
2. B has f=5+1=6, while C has f=2+6=8.
3. The minimum is 6 at B, despite B having the greatest cost already paid.
**Interpret the answer**
Expand B first. The ordering is B,A,C if no new nodes appear.
**Check the reasoning**
Choosing only the smallest g would pick C, confirming that A* uses both terms.
### Admissible but inconsistent
Edges are A→B:1,B→G:4,A→G:7. Let h(A)=5,h(B)=2,h(G)=0. Check admissibility and consistency.
**Choose the method**
First find true cheapest remaining distances, then test every edge inequality.
1. True distances are h*(B)=4 and h*(A)=min(7,1+4)=5.
2. Estimates 5≤5, 2≤4 and 0≤0 are nonnegative and admissible.
3. On A→B, consistency needs 5≤1+2=3, which is false. The other two edge tests pass.
**Interpret the answer**
The heuristic is admissible but inconsistent, so permanent closing needs additional care.
**Check the reasoning**
Along A→B, g rises by 1 but h falls by 3, so f falls by 2, exposing inconsistency.
### Repair a too-early closed state
Use the graph and heuristic in the program. Calculate the first cost to G, the improved cost to A and the final cost to G.
**Choose the method**
Order frontier entries by f, but calculate route improvements using g.
1. S->A has g=2 and f=2. S->B has g=1 and f=3.5, so A expands first.
2. A->G gives g(G)=2+2=4. B still has smaller f and expands next.
3. B->A gives g(A)=1+0.5=1.5. Reopen A, then reach G with 1.5+2=3.5.
**Interpret the answer**
The optimal path is S,B,A,G with cost 3.5. Keeping A permanently closed would retain cost 4 in this graph.
**Check the reasoning**
Compare with uniform-cost search using h=0, or enumerate the three simple S-to-G paths: costs 4, 3.5 and 101.
### Reopen a state when A* finds a better route
Mina builds a route planner with a lower-bound estimate for the remaining cost. Every estimate is optimistic, but neighbouring estimates do not change smoothly. The planner first reaches A with cost 2 and later discovers a route costing 1.5. A permanent closed list discards the improvement. Mina keeps the best known cost and allows a state to return to the frontier when that cost improves.
```python
from heapq import heappop, heappush
from math import inf
def astar(graph, heuristic, start, goal):
best = {start: 0.0}
parent = {}
frontier = [(heuristic[start], 0.0, start)]
expanded = []
while frontier:
_, cost, node = heappop(frontier)
if cost != best[node]:
continue
expanded.append(node)
if node == goal:
path = [goal]
while path[-1] != start:
path.append(parent[path[-1]])
return cost, list(reversed(path)), expanded
for nxt, step in graph[node]:
if step < 0:
raise ValueError("nonnegative edges required")
candidate = cost + step
if candidate < best.get(nxt, inf):
best[nxt] = candidate
parent[nxt] = node
heappush(frontier, (candidate + heuristic[nxt], candidate, nxt))
return inf, [], expanded
graph = {"S": [("A", 2), ("B", 1)], "A": [("G", 2)],
"B": [("A", 0.5), ("G", 100)], "G": []}
h = {"S": 3.5, "A": 0, "B": 2.5, "G": 0}
cost, path, expanded = astar(graph, h, "S", "G")
assert cost == 3.5 and path == ["S", "B", "A", "G"]
assert expanded == ["S", "A", "B", "A", "G"]
assert astar(graph, {node: 0 for node in graph}, "S", "G")[0] == cost
print("expanded:", expanded)
print("path:", path)
print(f"cost: {cost:.1f}")
```
**Run it locally**
```sh
python astar-heuristics-astar-reopen-states.py
```
**Expected output**
```text
expanded: ['S', 'A', 'B', 'A', 'G']
path: ['S', 'B', 'A', 'G']
cost: 3.5
```
**Follow the execution**
1. Store f=g+h in the heap and also keep g. The best dictionary records the cheapest discovered path to each state.
2. A better g inserts a fresh heap entry, even if the state was expanded before.
3. Skip entries whose g no longer matches best. They describe obsolete routes.
4. Stop when the goal is popped with its current best g. Merely generating a goal is too early.
**Read the code step by step**
Admissibility means h(v) <= the true remaining cost. Consistency is the stronger edge condition h(u) <= w(u,v)+h(v). Here h(B)=2.5 is admissible, because B->A->G costs 2.5. It is inconsistent on B->A because 2.5 > 0.5+0.
After S, A has f=2 and B has f=3.5. Expanding A discovers G at cost 4. Expanding B then improves A to g=1.5. Reopening A improves G to 3.5. Under the stated finite graph, nonnegative edges, admissible finite heuristic and h(goal)=0, reopening preserves the route needed for optimal A* termination. The function assumes the caller supplies these heuristic conditions; it does not verify admissibility.
With an inconsistent heuristic, states can be expanded many times. Do not claim the usual one-expansion-per-state complexity. In the special case h=0, this search becomes uniform-cost search. In practice, choose a heuristic whose assumptions you can justify and record both solution quality and expansion count.
### Leon's further thinking
**Check edges as well as goals**
A table can underestimate every true remaining distance and still violate consistency on an edge. Reopening addresses that distinction.
**A better estimate has a price**
If computing h takes longer than expanding the nodes it saves, a tighter bound can slow the whole search. Count both costs.
**Watch out:** Admissibility alone does not justify discarding every later route to a closed state. Use consistency or implement cheaper-path reopening correctly.
Check your understanding
For a sliding-tile puzzle, why is Manhattan distance admissible when the blank is excluded?
Each move shifts one numbered tile by one grid step. Every tile must cover at least its Manhattan displacement, so the sum cannot exceed the number of required moves. Counting the blank as well can double-count progress.
## Hill climbing, restarts and beam search
### 01 / The story
A venue planner adjusts a seating arrangement to reduce awkward pairings. The route taken through previous arrangements is irrelevant; only the final arrangement matters. Hill climbing resembles keeping one layout on the desk and accepting the best nearby improvement.
A local beam keeps several candidate layouts, but if they all look almost identical, the extra desks provide little exploration. Random restarts resemble beginning with a fresh seating plan rather than endlessly rearranging a stubborn one. This analogy fits optimization of complete configurations, but it does not establish that nearby layouts reveal the quality of distant arrangements.
### 02 / The principle
Local search evaluates complete candidate states with an objective and a neighborhood relation. For minimization, steepest descent chooses the neighbor with smallest objective, moving only when improvement is allowed.
It can stop at a local minimum, stall on a plateau or struggle on a ridge whose useful direction is absent from the allowed moves. Sideways moves, richer neighborhoods, limited lookahead and random restarts alter this behavior. Local beam search expands successors of k current states and retains the best k globally; it is not simply k independent hill climbers.
A levelwise beam search similarly discards candidates outside its beam. Permanent pruning saves memory but can remove every route to a goal, so neither ordinary beam search nor ordinary hill climbing is generally complete or optimal.
### 03 / The formula, unpacked
```text
snext ∈ argmin{V(u) : u ∈ N(s)}
Restart success probability after r independent runs = 1 − (1 − p)ʳ
```
V(s) is the objective value of configuration s, with smaller values preferred here. N(s) is the set of allowed neighboring configurations. The argmin notation means a state attaining the lowest score, with a separate tie rule.
In the restart expression, p is one run’s probability of reaching a desired solution and r counts independent runs with the same success probability. The expression does not apply unchanged to correlated restarts or changing budgets.
### 04 / A first worked example
A current timetable scores 12 conflicts. Its neighbors score 9, 10 and 14, so steepest descent chooses the score-9 timetable. Its next neighbors score 11, 12 and 9. A strict-improvement rule stops, although another distant timetable scores 0.
A beam of width 2 would initially retain scores 9 and 10, potentially exploring an escape through the second candidate. Suppose independent random restarts each find a zero-conflict timetable with probability 0.2. Five runs succeed with probability 1−0.8⁵=0.67232, about 67.2%. This quantifies improvement in chances without claiming certainty after five runs.
### Words to know
- **Neighborhood:** The candidate configurations reachable by one allowed change.
- **Local minimum:** No allowed neighbor has a smaller objective.
- **Beam width:** The number of candidates retained after global selection.
### Let us work through it
**Does a local minimum prove global optimality?**
No; better states may lie beyond a worse intermediate step.
**What does a strict descent rule do on ties?**
It does not move to an equal-score neighbor.
**Why can beams lose diversity?**
Several retained candidates may come from the same region.
### Select a beam globally
Beam width is 2. Candidate X has successor scores 4,8; Y has scores 3,5. Scores are minimized, and all successors are distinct.
**Choose the method**
Pool successors before selecting.
1. The pooled scores are 4,8,3,5.
2. Sort ascending to obtain 3,4,5,8.
3. Keep the first two: score 3 from Y and score 4 from X.
**Interpret the answer**
The next beam has scores 3 and 4, exactly two states.
**Check the reasoning**
Keeping one best child per parent happens to agree here, but with X:(1,2),Y:(3,4), global selection would keep both from X.
### Three independent restarts
A run succeeds with probability 1/4. Assume three independent runs with identical budgets. Find the probability of at least one success.
**Choose the method**
It is easier to count the complementary event: all fail.
1. One run fails with probability 1−1/4=3/4.
2. Independence makes all-fail probability (3/4)³=27/64.
3. Subtract from one: 1−27/64=37/64=0.578125.
**Interpret the answer**
Success probability is 57.8125%, greater than 25% but below certainty.
**Check the reasoning**
The two complementary probabilities 37/64 and 27/64 sum to 1.
### Leon's further thinking
**Change the neighborhood**
A swap of two items may be necessary even when moving either item alone makes the objective worse. A richer move set can remove a local trap.
**State the independence assumption**
Repeatedly restarting from the same seed can reproduce the same failure. The formula 1−(1−p)^r assumes independent chances.
**Watch out:** Keeping the best k successors of each beam member creates up to k² candidates and describes a different algorithm from retaining the best k across the combined successor pool.
Check your understanding
Why can allowing unlimited equal-score moves make hill climbing worse?
It can cycle indefinitely across a plateau. Bound sideways moves, track repeated states or use a deliberate stochastic exploration policy.
## Simulated annealing and genetic search
### 01 / The story
A landscape photographer wants a high viewpoint but must sometimes walk downhill to reach a better ridge. Early in the day, exploration is affordable; near sunset, risky detours become less attractive. Annealing captures that changing willingness to accept a worse step.
Genetic search instead resembles maintaining many candidate itineraries, combining promising segments and occasionally making a surprising change. The biological language is only a design metaphor: crossing two good itineraries can create an impossible trip, and a fitness score can reward the wrong thing. Both methods depend on how candidates, neighborhoods and objectives are encoded.
### 02 / The principle
Simulated annealing samples a neighbor and always accepts an improving move; a worsening move is accepted with a probability controlled by its loss and the current temperature. Cooling reduces exploratory moves. Asymptotic convergence results require restrictive cooling and connectivity assumptions and do not guarantee an optimum for an ordinary finite run.
A genetic algorithm maintains a population, selects parents according to fitness, recombines their encodings and applies mutation. Selection intensifies exploitation; mutation and population diversity support exploration.
Constraints may require a representation that always remains valid or an explicit repair or penalty method. Elitism can retain the best candidate but does not prove global optimality. Always report the best objective found and the computational budget, rather than presenting one stochastic run as a proof.
### 03 / The formula, unpacked
```text
Δ = V(candidate) − V(current)
P(accept) = min(1, exp(−Δ/T)), T > 0
Fitness-proportional selection: P(i) = Fᵢ / Σⱼ Fⱼ
```
V is an objective to minimize, so a positive Δ means deterioration. T is the positive temperature on the same scale as the objective difference. The exponential gives a number between zero and one for worsening moves.
Fᵢ is a nonnegative fitness to maximize for individual i; the selection denominator must be positive. Objective values and fitness are different conventions, so a cost may need a justified transformation before fitness-proportional selection.
### 04 / A first worked example
A routing candidate costs 40 and a proposed neighbor costs 44, so Δ=4. At temperature 8, acceptance probability is exp(−0.5)≈0.6065; at temperature 2 it is exp(−2)≈0.1353. A uniform random draw of 0.3 accepts the first proposal but rejects the second.
Separately, three genetic candidates have fitnesses 2, 3 and 5, giving selection probabilities 0.2, 0.3 and 0.5. Crossing bit strings 1100 and 0011 after the second position produces 1111 and 0000. Their fitness must be evaluated afresh: parent quality does not determine child quality.
### Words to know
- **Temperature:** A positive control of willingness to accept worse moves.
- **Mutation:** A random change to a candidate encoding.
- **Fitness:** A score used to favor candidates during selection.
### Let us work through it
**What if Δ is negative?**
The move improves a minimized objective and is accepted with probability 1.
**What does cooling change?**
It lowers acceptance probability for a fixed positive deterioration.
**Does crossover ensure valid children?**
No; representation and constraint handling must ensure validity.
### A cooling decision
Minimize cost. Current cost 20, proposed 22. Use temperatures 4 and 1, with the same uniform draw 0.4; accept when draw is below probability.
**Choose the method**
Compute deterioration once, then substitute each temperature.
1. Δ=22−20=2, a worsening move.
2. At T=4, exp(−2/4)≈0.606531, above 0.4, so accept.
3. At T=1, exp(−2)≈0.135335, below 0.4, so reject.
**Interpret the answer**
The warmer run accepts and the cooler run rejects this same worse proposal.
**Check the reasoning**
Both probabilities lie between 0 and 1 and decrease when temperature falls.
### Select and recombine
Three fitnesses are 1,2,5. Parents 101010 and 010101 cross after position 3, counting from 1. Compute selection probabilities and children.
**Choose the method**
Normalize scores, then exchange suffixes at the stated cut.
1. Total fitness is 1+2+5=8.
2. Probabilities are 1/8,2/8,5/8, or 0.125,0.25,0.625.
3. Split 101|010 and 010|101; exchanging suffixes gives 101101 and 010010.
**Interpret the answer**
The probabilities favor fitness 5, while the children are 101101 and 010010; their quality still needs evaluation.
**Check the reasoning**
Probabilities sum to 1 and both children retain length 6.
### Leon's further thinking
**Scale temperature with the objective**
Multiplying all objective values and T by the same positive number leaves Δ/T and acceptance probabilities unchanged.
**Zero fitness is allowed, zero total is not**
An individual with fitness 0 receives probability 0. If all are 0, division fails and a fallback selection rule must be specified.
**Watch out:** Do not state that annealing is always complete and optimal because a slow-cooling theorem exists. Its limiting assumptions and infinite-time statement differ from a practical schedule.
Check your understanding
What happens if a fitness-proportional scheme is given negative fitness values?
They cannot define selection probabilities. Use an appropriate nonnegative transformation, rank selection or another explicitly defined selection scheme, and examine how the transformation changes selection pressure.
## Minimax and alpha–beta bounds
### 01 / The story
Two players alternately choose which corridor a token follows through a maze. At the exit, one receives the number printed there and the other loses the same amount. A tempting corridor may contain a wonderful exit that the opponent will never permit. Minimax evaluates what each player can enforce, working backward from exits.
Alpha–beta pruning is like closing a corridor after proving that an earlier choice already guarantees something better. It is a proof that further inspection cannot change the present decision, not a guess that an unexplored corridor probably looks uninteresting.
### 02 / The principle
For a finite deterministic two-player zero-sum game with perfect information, minimax backs up maximum values at MAX nodes and minimum values at MIN nodes. Exact terminal utilities yield an optimal strategy against optimal opposition; a weaker opponent cannot force a worse value if MAX continues to follow a minimax strategy.
Alpha–beta performs the same depth-first backup while carrying bounds from ancestors. Alpha is a lower bound already available to MAX, and beta an upper bound available to MIN. Once alpha is at least beta, remaining siblings cannot improve the relevant ancestor’s decision.
The root value equals full minimax, although tied move selection can differ. Move ordering changes pruning efficiency; worst-case work remains exponential, while ideal ordering can roughly double reachable depth for a fixed budget.
### 03 / The formula, unpacked
```text
V(s) = U(s) at terminal states
V(s) = max V(child) at MAX; min V(child) at MIN
Prune when α ≥ β
Full-tree time O(bᵐ); depth-first space O(bm)
```
U(s) is a terminal payoff measured from MAX’s perspective. V(s) is the backed-up value, and child ranges over legal successors. Alpha and beta describe bounds relevant to the current search path, not independent global scores for all nodes.
Here b is branching factor and m the searched depth. The storage expression assumes depth-first traversal with successor lists; storing the whole game tree would have a much larger memory cost.
### 04 / A first worked example
MAX has three moves leading to MIN nodes. Their leaves, visited left to right, are A:[5,7], B:[3,100], and C:[6,4]. A returns 5, so root alpha becomes 5. At B, seeing its first leaf 3 sets beta to 3.
Since beta≤alpha, leaf 100 can be skipped: MIN can already limit B to at most 3. At C, the first leaf 6 does not permit pruning, so inspect 4 and return 4. MAX chooses A, guaranteeing 5. The pruned leaf could be enormous without changing the choice.
### Words to know
- **Utility:** A numerical outcome value from a fixed player’s perspective.
- **Minimax:** Choose the best outcome that optimal opposition allows.
- **Pruning:** Skip a branch after proving it cannot change the needed decision.
### Let us work through it
**Why does MIN take the smaller number?**
Numbers measure MAX’s utility, which the opponent seeks to reduce.
**Does a huge hidden leaf prevent pruning?**
Not if another MIN child already gives a low upper bound.
**Does move order change exact root value?**
No, but it changes how much work can be skipped.
### Back up a small tree
MAX chooses between MIN nodes L with leaves 8,3 and R with leaves 4,6. All are terminal MAX utilities.
**Choose the method**
Evaluate opponents’ responses before choosing at the root.
1. MIN at L takes min(8,3)=3.
2. MIN at R takes min(4,6)=4.
3. MAX then takes max(3,4)=4.
**Interpret the answer**
Choose R, guaranteeing 4 against optimal opposition.
**Check the reasoning**
Choosing the largest leaf 8 would fail because MIN can instead choose 3.
### Prove a cutoff
Root MAX already has a completed move worth 6. Its next MIN child has leaves 4,9,100 in that order. Show what may be skipped.
**Choose the method**
Carry the root lower bound into the MIN node.
1. The earlier move establishes α=6.
2. Seeing the first leaf 4 gives this MIN node β≤4.
3. Since β≤4<6≤α, the remaining leaves cannot make MIN’s value exceed the root’s available 6.
**Interpret the answer**
Skip 9 and 100; retain the earlier root move.
**Check the reasoning**
Full evaluation gives min(4,9,100)=4, confirming the bound and decision.
### Leon's further thinking
**A bound is not necessarily an exact value**
After cutting a MIN node on a low child, its true value might be even lower. The ancestor only needs proof that this move cannot beat its alternative.
**Model assumptions matter**
Hidden cards require information-state reasoning. A minimax tree that secretly uses an opponent’s unseen cards solves a different problem.
**Watch out:** Use the same utility perspective throughout the tree. Alternating the sign informally while also applying MIN can reverse the decision twice.
Check your understanding
Does alpha–beta make a shallow heuristic evaluation more accurate?
No. It preserves the minimax result for the same searched tree and leaf values. Saved work can fund a deeper search, but pruning itself does not improve the evaluation function.
## Cutoffs, chance nodes and multiple players
### 01 / The story
A board-game program has ten seconds to move. It cannot inspect every ending, so it stops at a horizon and estimates the unfinished positions. A position that looks profitable immediately before a forced loss illustrates the danger of a horizon.
Dice add a different complication: the player cannot choose which number appears, so outcomes must be averaged according to their probabilities. Adding a third player changes the incentives again, because two opponents need not want the same outcome. Time limits, randomness and multiple interests require separate changes to the model rather than one universal game-search shortcut.
### 02 / The principle
A depth cutoff substitutes a heuristic evaluation for terminal utility, sacrificing exact-game optimality. Iterative deepening retains the last completed search when time expires. Quiescence search extends tactically unstable positions using selected forcing moves, but still needs termination controls.
A linear evaluation combines features and may miss interactions. Expectiminimax adds chance nodes whose values are probability-weighted expectations, while MAX and MIN backups remain unchanged. Expected-utility decisions require cardinal utility: a positive affine transformation preserves preferences, but an arbitrary increasing transformation need not.
Ordinary alpha–beta reasoning cannot simply ignore chance outcomes; valid pruning needs bounds on unseen values and probability mass. For more than two players, a Max-n backup carries a utility vector and each player selects its own component, without the two-player zero-sum guarantee.
### 03 / The formula, unpacked
```text
E(s) = Σᵢ wᵢ φᵢ(s)
V(chance) = Σⱼ pⱼ V(sⱼ), Σⱼ pⱼ = 1
Utility-preserving affine change: U′ = aU + b, a > 0
```
E(s) estimates the value of an unfinished state using features φᵢ and weights wᵢ. At a chance node, pⱼ is the probability of successor sⱼ and the probabilities cover all outcomes.
The constants a and b rescale and shift utility; using the same transformation everywhere preserves expected-utility comparisons. A probability is not an opponent’s adversarial choice. A utility vector needs one component per player and a stated tie-breaking convention.
### 04 / A first worked example
A player chooses a safe action worth 3 or a gamble worth 10 with probability 0.4 and 0 otherwise. The gamble’s expected utility is 0.4×10+0.6×0=4, so a player maximizing these utilities chooses it. Adding 2 and multiplying all utilities by 3 gives safe utility 11 and expected gamble utility 14, preserving the choice.
Squaring the original nonnegative utilities instead gives 9 versus 40; that still agrees here, but need not for other lotteries. At a three-player node, vectors (5,1,0) and (2,4,3) make player two choose the latter because 4>1.
### Words to know
- **Cutoff:** A point where search stops and estimates unfinished outcomes.
- **Chance node:** A node whose successor is chosen according to probabilities.
- **Expected utility:** The probability-weighted average of outcome utilities.
### Let us work through it
**Should a chance node choose its worst child?**
No; average using outcome probabilities unless the model specifies an adversary.
**What must probabilities sum to?**
One, after including all mutually exclusive outcomes.
**What does iterative deepening keep?**
The result of the last fully completed search depth.
### Compare a chance action
Safe utility is 2. A gamble gives 8 with probability 1/4 and 0 otherwise. The agent maximizes expected utility and breaks ties toward safe.
**Choose the method**
Weight each outcome, then apply the stated tie rule.
1. The high outcome contributes(1/4)×8=2.
2. The low outcome contributes(3/4)×0=0, so total expectation is 2.
3. Safe also equals 2, so expected utility alone ties; the specified rule selects safe.
**Interpret the answer**
Choose safe by tie-breaking; neither option has a larger expectation.
**Check the reasoning**
The mean 2 lies between the gamble’s outcomes 0 and 8.
### Bound unseen chance outcomes
A chance branch has a known outcome 10 with probability 0.3. Remaining probability 0.7 has utilities between 0 and 4. Another action guarantees 6. Can MAX discard the chance branch?
**Choose the method**
Use the best possible unseen outcome to form an upper bound.
1. Known contribution is 0.3×10=3.
2. Unseen contribution is at most 0.7×4=2.8.
3. Total expectation is at most 5.8, below the already available 6.
**Interpret the answer**
Yes. Even its best permitted expectation cannot beat 6.
**Check the reasoning**
The lower bound is 3+0.7×0=3, so the complete permitted interval [3,5.8] lies below 6.
### Leon's further thinking
**Expected value is not a promised outcome**
A lottery with outcomes 0 and 8 can have mean 2 even though 2 never occurs. The mean summarizes repeated draws under the model.
**Nonlinear utility can be appropriate if explicit**
Risk aversion may be modeled with a concave utility of points. Apply the utility before taking expectation; this intentionally changes the decision criterion.
**Watch out:** A large estimated reward just beyond a cutoff is not a proven win, and a high raw neural output is not automatically a calibrated probability.
Check your understanding
A lottery pays 0 or 4 equally; a sure option pays 1.5. Does taking square roots preserve the preferred option?
No. Original expected utilities are 2 and 1.5, favoring the lottery. After square roots they are 1 and about 1.225, favoring the sure option. The nonlinear transformation changes risk preferences.
## Learning tasks and nearest neighbors
### 01 / The story
A repair workshop estimates a new bicycle’s service time by finding similar past jobs. If past records include actual repair times, averaging nearby records is supervised regression; if they include repair categories, voting is classification. Grouping unlabeled jobs into types is clustering.
Learning which repair action earns a later reward is reinforcement learning, and discovering which replacement parts co-occur is association learning. The workshop’s similarity ruler matters: measuring price in cents can overwhelm frame size in centimeters. Nearest-neighbor learning makes this choice visible because prediction is built directly from the selected examples.
### 02 / The principle
A supervised learner uses input–target pairs to predict unseen targets. K-nearest neighbors stores training examples and delays most computation until prediction, making it a lazy learner. Classification uses a vote among k closest examples; regression typically averages their targets, optionally with distance weights. Euclidean, Manhattan and general Minkowski distances encode different geometry.
Fit scaling on training data only and apply it unchanged to validation and test data. Nominal features need a meaningful mismatch or encoding rule; arbitrary integer labels introduce false distances. Missing values require an explicit policy rather than an assumed universal penalty. Small k can follow noise, large k can blur real boundaries. Irrelevant dimensions can weaken useful neighborhoods, so feature selection and validation are important.
### 03 / The formula, unpacked
```text
dq(x,z) = (Σⱼ |xⱼ − zⱼ|ᑫ)^(1/q), q ≥ 1
xscaled = (x − mintrain)/(maxtrain − mintrain)
Regression: ŷ = (Σᵢ wᵢ yᵢ)/(Σᵢ wᵢ)
```
Vectors x and z contain corresponding features; j indexes features. Setting q to 1 gives Manhattan distance and q to 2 gives Euclidean distance. Training minima and maxima define min–max scaling; a constant feature needs a separate convention because its denominator is zero.
In the regression average, i indexes selected neighbors, yᵢ is their target and wᵢ a positive weight. For inverse-distance weighting, explicitly handle an exact zero-distance match.
### 04 / A first worked example
A one-dimensional archive contains jobs at complexity scores 1, 3, 6 and 9 with service times 10, 18, 30 and 50 minutes. A new job scores 5. Distances are 4, 2, 1 and 4, so k=2 selects scores 6 and 3. Their unweighted prediction is (30+18)/2=24 minutes.
Inverse-distance weights 1 and 1/2 give (30+9)/1.5=26 minutes. These are predictions rather than guaranteed durations. With n stored jobs and d features, a brute-force query computes n distances, costing O(nd) before neighbor selection; storing the archive costs O(nd).
### Words to know
- **Feature:** A measured input property, such as length.
- **Regression:** Predicting a numerical target.
- **Distance weighting:** Giving selected examples different influence based on distance.
### Let us work through it
**Why scale features?**
Units can otherwise dominate the distance without reflecting importance.
**What does k count?**
The selected nearest training examples.
**May a new scaled value exceed 1?**
Yes, if it exceeds the training maximum.
### Predict from two neighbors
Training pairs (x,y) are(0,2),(4,10),(7,16). Query x=5 with k=2 and ordinary absolute distance.
**Choose the method**
Find distances first, then average only selected targets.
1. Distances are 5,1,2 respectively.
2. The closest two are x=4 and 7, with targets 10 and 16.
3. Their unweighted average is(10+16)/2=13.
**Interpret the answer**
Predict 13, an estimate between the two selected targets.
**Check the reasoning**
The distant target 2 is excluded because k=2, not 3.
### Compare two distance rulers
Points are x=(1,2),z=(4,6). Compute Manhattan and Euclidean distance with equally scaled coordinates.
**Choose the method**
Subtract matching coordinates, then use the chosen aggregation.
1. Absolute coordinate differences are|1−4|=3 and|2−6|=4.
2. Manhattan adds them:3+4=7.
3. Euclidean squares, adds and takes a square root: √(9+16)=5.
**Interpret the answer**
Distances are 7 and 5; they describe different allowed geometry.
**Check the reasoning**
A direct diagonal length 5 cannot exceed the axis-by-axis route length 7.
### Find and average two neighbors
Reproduce the first worked problem with a sorted distance table.
```python
records = [(0, 2), (4, 10), (7, 16)]
query = 5
ranked = []
for x, target in records:
distance = abs(x - query)
ranked.append((distance, x, target))
ranked.sort()
selected = ranked[:2]
total = 0
for distance, x, target in selected:
total += target
prediction = total / len(selected)
print("Neighbors:", selected)
print("Prediction:", prediction)
assert prediction == 13
```
**Run it locally**
```sh
python learning-neighbors-nearest-two-trace.py
```
**Expected output**
```text
Neighbors: [(1, 4, 10), (2, 7, 16)]
Prediction: 13.0
```
**Follow the execution**
1. Distances are 5,1,2 before sorting.
2. Sorting puts inputs 4 and 7 first, with targets 10 and 16.
3. The mean is 26/2=13; changing k would change the selected set.
**Read the code step by step**
Each record is a pair of input and target. The for statement unpacks that pair into names. abs returns absolute distance. append adds a three-number tuple to the growing ranked list.
sort orders tuples by their first number, then later numbers to break ties. The slice [:2] keeps the first two entries. A second loop adds their targets; += means add to the existing total. len counts the selected entries. Dividing total by that count gives the mean. assert verifies the worked answer. This demonstration does no feature scaling because there is only one input coordinate.
### Leon's further thinking
**Squared distance can rank neighbors**
For Euclidean ranking, omit the square root because it preserves order for nonnegative values. Use the actual distance if the weighting formula needs it.
**Handle exact matches explicitly**
Using 1/d at d=0 divides by zero. One defensible policy averages targets of exact matches before considering more distant examples.
**Watch out:** Fitting normalization on the entire dataset leaks information into validation. Refit all preprocessing within each training fold.
Check your understanding
Why can converting colors red, green and blue to 1, 2 and 3 harm k-NN?
It invents an ordering and makes red twice as far from blue as from green. Use a categorical distance or justified encoding consistent with the intended notion of similarity.
## 1R: a useful one-feature baseline
### 01 / The story
A librarian wants a quick rule for predicting whether a returned item needs repair. They could inspect dozens of attributes, but first try a single one, such as binding type. For each binding type, they write the most common outcome observed in past records.
They then repeat with age group and cover material, keeping the attribute that makes the fewest mistakes. This is a deliberately modest benchmark: if a complicated system cannot beat it on new records, complexity needs justification. One feature can generate several branches, so “one rule” does not mean one literal sentence or one outcome.
### 02 / The principle
For each candidate attribute, 1R partitions the training data by attribute value and predicts the majority class in each group. It selects the attribute whose complete rule has the smallest training error. Ties need a deterministic convention. A missing value can be treated as a distinct category, provided that policy makes sense for the data-generating process.
Numeric attributes require intervals: sort values, propose boundaries and avoid tiny intervals that memorize individual labels. Minimum bucket sizes and merging adjacent same-label intervals can constrain complexity. A 1R model is interpretable and supplies a strong sanity-check baseline, but interactions between attributes are invisible to it. Attribute and discretization selection are training decisions, and final performance must be assessed on held-out observations.
### 03 / The formula, unpacked
```text
prediction(v) = argmax꜀ count(attribute=v, class=c)
Errors(attribute) = Σᵥ [count(v) − max꜀ count(v,c)]
```
The value v ranges over one attribute’s categories or numeric intervals, and c ranges over classes. Count(v,c) counts training records with both that value and that class; count(v) counts all records in the group.
Subtracting its majority count gives the unavoidable training mistakes for a constant prediction in that group. Sum those mistakes across groups and compare attributes. The rule for a previously unseen category must also be specified, such as a training-set majority fallback.
### 04 / A first worked example
Eight devices have a target label repair or keep. For cover type, metal contains three repair and one keep, while plastic contains one repair and three keep. Predicting repair for metal and keep for plastic makes one error in each group, two total.
For age band, young contains two repair and one keep; old contains two repair and three keep. The best age rule makes one plus two errors, three total. The chosen 1R model therefore uses cover type, achieving 6/8=75% training accuracy. A new plastic device is predicted keep regardless of its age, exposing the model’s deliberate limitation.
### Words to know
- **Baseline:** A simple reference method used for comparison.
- **Majority class:** The most frequent label in a group.
- **Discretization:** Replacing numerical values with interval categories.
### Let us work through it
**Does 1R use exactly one branch?**
No, one attribute can have several values and branches.
**How many errors in a group with 4A,1B?**
One, when predicting the majority A.
**Can zero training error prove a good model?**
No, the rule may merely memorize unique identifiers.
### Choose the better attribute
Attribute A splits labels into(4 yes,1 no) and(1 yes,4 no). Attribute B gives(3 yes,2 no) and(2 yes,3 no). Use majority predictions.
**Choose the method**
Compute minority counts in each group and sum.
1. A makes 1+1=2 errors out of 10.
2. B makes 2+2=4 errors out of 10.
3. Since 2<4, select A; its training accuracy is(10−2)/10=0.8.
**Interpret the answer**
A wins with 80% training accuracy; held-out accuracy remains unknown.
**Check the reasoning**
Both attributes describe the same totals of 5 yes and 5 no.
### Why one feature misses XOR
Records are(0,0)→0,(0,1)→1,(1,0)→1,(1,1)→0. Use 1R with ties predicted 0.
**Choose the method**
Group by one input and inspect labels; repeat for the other.
1. For the first input 0, labels are 0 and 1; predict 0 and make one error.
2. For first input 1, labels again are 1 and 0; another error gives 2 total.
3. Grouping by the second input gives the same two balanced groups and 2 errors.
**Interpret the answer**
Either 1R choice has 50% accuracy. The target depends on the pair, not either coordinate alone.
**Check the reasoning**
A two-level tree testing both inputs can distinguish all four rows.
### Leon's further thinking
**State unseen-category behavior**
A rule has no learned majority for an unseen value. Choose a training-only fallback before evaluating new observations.
**Numeric boundaries are learned choices**
Trying many intervals against the test labels is test-set tuning even if the final model uses only one feature.
**Watch out:** Choosing an attribute with one unique value per record can create zero training errors and useless predictions. Treat identifiers and overly fine numeric intervals with particular care.
Check your understanding
Can 1R express a rule that predicts true exactly when two binary inputs differ?
Not with either input alone on the complete balanced XOR table. Each single-feature group contains both labels equally, so interactions require a richer model.
## Naive Bayes and smoothed likelihoods
### 01 / The story
An inbox filter combines clues such as a special offer word and an unfamiliar sender. First it asks how frequent spam is before reading either clue. Then it asks how expected each clue would be if the message were spam or ordinary mail.
Combining those answers reverses the direction of reasoning from “what spam tends to contain” to “what this message probably is.” The naive step treats the clues as independent once the class is known. Repeating the same clue in several correlated forms can therefore make the filter more confident without supplying much genuinely new evidence.
### 02 / The principle
Naive Bayes models a class prior and one conditional feature distribution per class, then multiplies them using conditional independence given the class. This is not an assumption that every feature is equally informative: different likelihood ratios can have very different influence.
For categorical data, frequency estimates need smoothing so an unseen value does not force a whole class score to zero. Numeric features can use a Gaussian density with class-specific mean and variance, or another suitable distribution. Evaluate products in log space to avoid numerical underflow.
Missing observed features can be marginalized away under the model, but the winning class can change and informative missingness needs extra modeling. Normalize class scores when probabilities are required, while recognizing that a misspecified independence model may produce poorly calibrated probabilities.
### 03 / The formula, unpacked
```text
P(c|x) ∝ P(c) Πⱼ P(xⱼ|c)
P(xⱼ=v|c) = (N꜀ᵥ + 1)/(N꜀ + kⱼ)
Gaussian density: exp(−(x−μ)²/(2σ²))/(σ√(2π))
```
Here c is a class, xⱼ the jth observed feature, and the proportionality omits a denominator shared by all classes. N꜀ᵥ counts class-c records with value v; N꜀ is the number with observed values for that feature, and kⱼ is its possible category count.
Laplace smoothing adds one to every category. The Gaussian expression is a density, not the probability of one exact real number; μ and positive σ are class-specific parameters.
### 04 / A first worked example
Suppose P(spam)=0.25 and P(ordinary)=0.75. Given spam, an offer word occurs with probability 0.8 and an unfamiliar sender with probability 0.6. Given ordinary mail, the corresponding probabilities are 0.1 and 0.2. For a message with both clues, the naive scores are 0.25×0.8×0.6=0.12 and 0.75×0.1×0.2=0.015.
Dividing by their sum 0.135 gives a spam posterior of 8/9≈0.8889. Separately, an unseen value among four possible categories in six class records receives smoothed probability (0+1)/(6+4)=0.1, rather than zero. Both class scores use the same evidence, so their normalization denominator is shared. A prediction compares those scores before normalization as well.
### Words to know
- **Prior:** A class probability before the current evidence.
- **Likelihood:** How expected the observed evidence is under a proposed class.
- **Smoothing:** Adding specified pseudo-counts to avoid unsupported zero estimates.
### Let us work through it
**Independent before or after knowing the class?**
The model assumes independence after conditioning on the class.
**Do scores already sum to 1?**
Usually not; divide each by the sum when posterior probabilities are needed.
**Why use logarithms?**
Products of tiny probabilities can underflow; logs turn products into sums.
**Why is taking log after multiplying all probabilities too late?**
The product may already have rounded to zero. log(0) cannot recover information lost during multiplication. Add the logarithms before that happens.
### Normalize two class scores
P(A)=P(B)=0.5. For observed binary clues x=y=1, class A likelihoods are 0.8,0.5; class B likelihoods 0.2,0.5. Assume conditional independence.
**Choose the method**
Multiply prior and class-specific likelihoods, then normalize.
1. A score is 0.5×0.8×0.5=0.2.
2. B score is 0.5×0.2×0.5=0.05; total is 0.25.
3. Posteriors are 0.2/0.25=0.8 and 0.05/0.25=0.2.
**Interpret the answer**
Predict A, with model posterior 0.8. Equal second-clue likelihoods do not change the odds.
**Check the reasoning**
Posterior odds 4:1 equal the first-clue likelihood ratio 0.8:0.2 because prior odds are 1:1.
### Smooth an unseen category
One class has counts red 3,green 1,blue 0. These are the only three possible categories. Apply add-one smoothing.
**Choose the method**
Add one to each count and add three to the original total.
1. Original total is 3+1+0=4.
2. Smoothed counts are 4,2,1 and denominator 4+3=7.
3. Probabilities are 4/7,2/7,1/7; blue now has positive support.
**Interpret the answer**
The unseen blue estimate is 1/7≈0.142857, avoiding a zero product.
**Check the reasoning**
The numerators 4+2+1=7 match the denominator, so probabilities sum to 1.
### Normalize two smoothed document scores
V=3, alpha=1 and class priors are 1/2. Class A counts are red=3, round=1, blue=0; class B counts are red=0, round=1, blue=3. Classify red,red,round.
**Choose the method**
Compute class token totals and smoothed word probabilities before applying the repeated-word counts.
1. Each class has four tokens, so the denominator is 4+3=7. A gives red=4/7 and round=2/7.
2. A score is (1/2)(4/7)^2(2/7)=16/343. B score is (1/2)(1/7)^2(2/7)=1/343.
3. Divide by their sum 17/343: posterior A=16/17 and B=1/17.
**Interpret the answer**
The model predicts A with approximate probability 0.941176 under its assumptions.
**Check the reasoning**
The posterior odds are 16:1. Only the two red occurrences distinguish the classes, each contributing a likelihood ratio of 4.
### Keep long-text likelihoods in log space
A club sorts messages into two topics. Mina multiplies word probabilities and obtains reasonable scores for a short note. For a much longer note, both class scores become zero in floating-point arithmetic. The message did not become impossible; the representation ran out of range. She stores log scores, adds contributions, and normalizes only after subtracting the largest score.
```python
from math import exp, log, isclose
vocabulary = ["red", "round", "blue"]
counts = {"A": {"red": 3, "round": 1, "blue": 0},
"B": {"red": 0, "round": 1, "blue": 3}}
def log_scores(document):
result = {}
for label, words in counts.items():
denominator = sum(words.values()) + len(vocabulary)
score = log(0.5)
for word in vocabulary:
probability = (words[word] + 1) / denominator
score += document.get(word, 0) * log(probability)
result[label] = score
return result
def posterior(scores):
largest = max(scores.values())
weights = {label: exp(value - largest) for label, value in scores.items()}
total = sum(weights.values())
return {label: value / total for label, value in weights.items()}
short = {"red": 2, "round": 1}
scores = log_scores(short)
probabilities = posterior(scores)
assert isclose(probabilities["A"], 16 / 17)
print(f"short P(A|text): {probabilities['A']:.6f}")
long = {word: count * 1000 for word, count in short.items()}
long_scores = log_scores(long)
print("raw scores underflow:", [exp(x) == 0 for x in long_scores.values()])
print("log-space winner:", max(long_scores, key=long_scores.get))
assert isclose(sum(posterior(long_scores).values()), 1.0)
```
**Run it locally**
```sh
python naive-bayes-log-space-word-counts.py
```
**Expected output**
```text
short P(A|text): 0.941176
raw scores underflow: [True, True]
log-space winner: A
```
**Follow the execution**
1. Add one to every class-word count. Add the vocabulary size to each class token total.
2. Compute log prior plus count*log likelihood for each word. Repeated words contribute repeatedly.
3. Subtract the largest log score before exponentiating. This preserves ratios and keeps the largest weight equal to one.
4. Compare the short document to 16/17 and show why raw long-document scores collapse.
**Read the code step by step**
For class c, score(c)=log P(c)+sum over words w of n_w*log((N_cw+alpha)/(N_c+alpha*V)). n_w counts occurrences in the new document. N_cw is the training count for word w in class c. N_c is the total training token count for the class, V is vocabulary size, and alpha=1 here. A word-order-independent multinomial factor is omitted because it is the same for both classes and cancels in normalization.
For a document with two red tokens and one round token, the unnormalized scores are 16/343 and 1/343, including the equal priors. Normalizing gives P(A|text)=16/17. A fixed vocabulary is used; unseen words are ignored in this small demo. A real pipeline needs a documented unknown-token policy fitted from training data.
Stable arithmetic prevents numerical underflow from erasing the comparison. It does not fix the conditional-independence approximation or calibrate the probabilities. Repeating highly dependent words can still make this model overconfident. Keep numerical correctness separate from modeling correctness.
### Leon's further thinking
**Duplicate evidence is dangerous**
Copying a binary feature creates perfectly dependent columns. Naive multiplication counts its likelihood ratio twice and may exaggerate confidence.
**A density may exceed one**
For a narrow continuous distribution, density height can exceed 1 while total area stays 1. Do not clip a Gaussian density as if it were an event probability.
**Watch out:** Dropping a missing feature does not guarantee the class ranking stays unchanged. Its likelihood ratio may have been the deciding evidence.
Check your understanding
Why is multiplying P(feature) values different from naive Bayes?
Naive Bayes uses P(feature|class), so the evidence changes each class score differently. Unconditional feature probabilities would be identical factors across classes and would not provide class-specific evidence.
## Validation, cross-validation and comparisons
### 01 / The story
A chef tunes a recipe with one group of tasters and reserves another group for the final tasting. Asking the reserved group after every adjustment turns them into tuning tasters, even if nobody changes their name. Machine-learning evaluation has the same problem: repeatedly inspecting a test score makes it part of development.
Cross-validation rotates the tasting role so limited data contributes to several training runs, but recipes trained on overlapping ingredients are not statistically independent experiments. Good evaluation begins by defining which future customers the result is intended to represent, then separating development choices from the final estimate.
### 02 / The principle
Training estimates model parameters; validation selects hyperparameters, features, preprocessing and stopping rules; a test set estimates performance after those choices are fixed. Holdout uses one split, repeated holdout explores split variability, and k-fold cross-validation rotates the held-out fold.
Stratification approximately preserves class proportions but does not solve leakage from repeated people, time order or related records; those need group-aware or chronological splitting. Fit every learned preprocessing operation within each training fold. Leave-one-out trains n models and can be expensive. Compare models on identical splits using paired differences.
A classical paired t interval assumes approximately independent differences with an appropriate distribution; ordinary cross-validation folds overlap in training data, so its naive interval can be overconfident. Retraining for deployment changes the fitted model and does not create a fresh test estimate.
### 03 / The formula, unpacked
```text
CV score = (1/k) Σᵢ scoreᵢ for equally sized folds
d̄ = (1/k)Σᵢ dᵢ
sd² = Σᵢ(dᵢ − d̄)²/(k−1)
Classical paired interval: d̄ ± t* sd/√k
```
k is the number of paired evaluations and dᵢ is model A’s score minus model B’s score on the same evaluation data. The bar denotes a mean and sd the sample standard deviation of differences.
The critical value t* depends on the confidence level and k−1 degrees of freedom. This interval is a statistical model with assumptions, not an automatic certificate of superiority. Unequal fold sizes can require weighting when estimating pooled per-example performance.
### 04 / A first worked example
A dataset has 120 independent observations. In six-fold cross-validation, each run trains on 100 and evaluates on 20. Every observation is evaluated once, although training sets overlap. Suppose two models’ paired score differences across five separate, suitably independent experiments are 0.02, 0.04, 0.03, 0.01 and 0.05.
Their mean is 0.03 and sample standard deviation is about 0.01581. With t*=2.776, the classical 95% interval is 0.03±0.01963, or roughly [0.0104,0.0496]. Applying that calculation uncritically to five ordinary CV folds would ignore their dependence and overstate the evidence.
### Words to know
- **Validation:** Development data used to choose model settings.
- **Leakage:** Information unavailable at prediction time enters model development.
- **Paired comparison:** Compare two models using the same evaluation observations.
### Let us work through it
**Does stratification remove time leakage?**
No; it balances class proportions, not chronological order.
**Where should scaling be fitted in CV?**
Inside each fold’s training portion.
**Is the test set for tuning?**
No; using it for choices turns it into development data.
### Count a five-fold split
There are 100 independent examples split into five equal folds. One fold validates each run. Count train size, validation size and total validation appearances.
**Choose the method**
Divide the dataset once, then follow the rotation.
1. Each fold contains 100/5=20 examples.
2. Each run trains on 100−20=80 and validates on 20.
3. Five runs yield 5×20=100 validation appearances, one per example.
**Interpret the answer**
Train 80 and validate 20 per run; every example is held out once.
**Check the reasoning**
Training appearances total 5×80=400, so training sets overlap despite distinct validation folds.
### Equal-fold mean versus pooled accuracy
Two validation folds have 10 and 30 examples. A model gets 9 and 15 correct respectively. Compute both unweighted fold mean and pooled accuracy.
**Choose the method**
Keep denominators attached to each count.
1. Fold accuracies are 9/10=0.9 and 15/30=0.5.
2. Equal-fold mean is(0.9+0.5)/2=0.7.
3. Pooled accuracy is(9+15)/(10+30)=24/40=0.6.
**Interpret the answer**
Equal-fold mean is 70%; per-observation pooled accuracy is 60%.
**Check the reasoning**
Size weighting gives(10/40)0.9+(30/40)0.5=0.6, matching pooled counting.
### Leon's further thinking
**Keep related records together**
Photos of the same object in train and test can reward remembering that object. Group by the unit that will be new at deployment.
**Weight by the intended estimand**
A mean of fold accuracies weights folds equally. A pooled accuracy weights observations equally; unequal folds can make them differ.
**Watch out:** Test data must not decide the winning hyperparameter. Use nested evaluation or a separate final test set when model selection itself is part of the procedure being assessed.
Check your understanding
Why might random stratified splits be misleading for next-month demand prediction?
They can train on records later than the validation records, giving access to future patterns. Use a time-ordered evaluation matching the intended forecasting setting.
## Confusion matrices and error costs
### 01 / The story
A parcel scanner flags damaged packages for inspection. Catching nearly every damaged parcel sounds excellent, but if it also flags almost every intact parcel, inspectors drown in unnecessary work. Conversely, a very cautious scanner may make few false accusations while missing most damage.
A confusion matrix keeps both stories visible by counting correct and incorrect decisions separately for each true condition. The practical decision also depends on consequences: an unnecessary inspection and a missed damaged package need not cost the same. A single headline percentage cannot express all of these operational tradeoffs.
### 02 / The principle
For a chosen positive class, a confusion matrix records true positives, false positives, false negatives and true negatives. Accuracy counts all correct decisions, precision asks how trustworthy positive predictions are, and recall asks how many actual positives are recovered.
F1 is their harmonic mean and does not use true negatives. Class imbalance can make accuracy high for a useless majority predictor. Define what to do when a metric denominator is zero, and choose macro, micro or weighted averaging deliberately in multiclass tasks.
Changing a decision threshold often trades precision against recall, although it is not a universal algebraic opposition across different models. A cost matrix weights the consequences of errors. Choose a threshold on validation data and assess it on held-out data under the relevant class prevalence.
### 03 / The formula, unpacked
```text
Accuracy = (TP+TN)/N
Precision = TP/(TP+FP); Recall = TP/(TP+FN)
F1 = 2TP/(2TP+FP+FN)
Total error cost = cFP·FP + cFN·FN
```
TP counts true positives; FP false positives; FN missed positives; TN true negatives; N is their sum. The positive class must be named before computing the metrics. cFP and cFN are application-specific costs per corresponding mistake, assumed constant in this simplified expression.
F1 ranges from zero to one when defined and gives neither a probability nor a cost estimate. If no positive predictions exist, precision needs an explicit reporting convention.
### 04 / A first worked example
Among 200 packages, 40 are truly damaged. The scanner flags 50, including 30 damaged ones. Thus TP=30, FP=20, FN=10 and TN=140. Accuracy is 170/200=85%; precision is 30/50=60%; recall is 30/40=75%; F1 is 60/(60+20+10)=2/3≈66.7%. If unnecessary inspection costs 2 units and missing damage costs 15 units, total error cost is 20×2+10×15=190.
A scanner that never flags anything has 80% accuracy but costs 40×15=600, showing why the operational objective matters more than a small difference in accuracy alone. The cost comparison keeps the same package population and counts both kinds of mistake explicitly.
### Words to know
- **Precision:** The fraction of positive predictions that are truly positive.
- **Recall:** The fraction of actual positives successfully found.
- **False negative:** A truly positive example incorrectly predicted negative.
### Let us work through it
**Which denominator measures recall?**
All actual positives: TP+FN.
**Does F1 use TN?**
No; adding true negatives alone does not change F1.
**Why name the positive class?**
Swapping class roles changes precision and recall.
**Can 90% accuracy prove that every class is recognised?**
No. The flower recall is zero here. Inspect class counts and choose aggregate metrics that reflect the task priorities.
### Build all four counts
Of 100 items,20 are truly positive. The system predicts 30 positives, of which 15 are correct. Find accuracy, precision, recall and F1.
**Choose the method**
Complete the confusion matrix before substituting ratios.
1. TP=15 and FP=30−15=15.
2. FN=20−15=5; TN=100−15−15−5=65.
3. Accuracy 80/100=0.8; precision 15/30=0.5; recall 15/20=0.75; F1=30/(30+15+5)=0.6.
**Interpret the answer**
Accuracy 80%, precision 50%, recall 75%, F1=60%; the headline accuracy hides half the flags being false.
**Check the reasoning**
Counts 15+15+5+65=100 and actual positives 15+5=20 match the givens.
### Compare error costs
On the same set, model A has FP=8,FN=4; B has FP=14,FN=1. Each false positive costs 1 unit and each false negative 10. Ignore correct-decision costs.
**Choose the method**
Weight both kinds of error before comparing totals.
1. A costs 8×1+4×10=48.
2. B costs 14×1+1×10=24.
3. B saves 48−24=24 units despite six extra false positives.
**Interpret the answer**
Choose B under these stated costs; another cost ratio could change the decision.
**Check the reasoning**
Three fewer misses save 30 units; six extra false flags cost 6, net saving 24.
### Compute macro F1 from three classes
Eight leaves and one seed are correct. The single flower is called a leaf. Compute all class F1 scores and macro F1.
**Choose the method**
Create one-vs-rest counts for each class, then average the F1 values rather than averaging precision and recall first.
1. Leaf: TP=8, FP=1, FN=0, so F1=16/17.
2. Flower: TP=0, FP=0, FN=1, so F1=0. Seed has F1=1.
3. Macro F1=(16/17+0+1)/3=11/17, approximately 0.647059.
**Interpret the answer**
Macro F1 is about 0.6471 despite accuracy 0.9.
**Check the reasoning**
Pooling gives TP=9, FP=1, FN=1, so micro F1=18/20=0.9, which matches 9/10 accuracy.
### See which class disappears inside an average
A classifier recognises ten pictures: eight leaves, one flower and one seed. Mina sees 90% accuracy and thinks every category works well. The report tells a different story: the only flower was called a leaf. She calculates a score for each class before taking an average, so the small class can no longer disappear inside the large one.
```python
from math import isclose
labels = ["leaf", "flower", "seed"]
truth = ["leaf"] * 8 + ["flower", "seed"]
predicted = ["leaf"] * 9 + ["seed"]
def report(truth, predicted, labels):
if len(truth) != len(predicted) or not truth:
raise ValueError("nonempty aligned observations required")
if set(truth + predicted) - set(labels):
raise ValueError("unknown label")
per_class = []
total_tp = total_fp = total_fn = 0
for label in labels:
tp = sum(t == label and p == label for t, p in zip(truth, predicted))
fp = sum(t != label and p == label for t, p in zip(truth, predicted))
fn = sum(t == label and p != label for t, p in zip(truth, predicted))
denominator = 2 * tp + fp + fn
f1 = 2 * tp / denominator if denominator else 0.0
per_class.append((label, tp, fp, fn, f1))
total_tp += tp; total_fp += fp; total_fn += fn
macro = sum(row[4] for row in per_class) / len(labels)
micro = 2 * total_tp / (2 * total_tp + total_fp + total_fn)
return per_class, macro, micro
rows, macro, micro = report(truth, predicted, labels)
for label, tp, fp, fn, f1 in rows:
print(f"{label}: TP={tp} FP={fp} FN={fn} F1={f1:.4f}")
accuracy = sum(t == p for t, p in zip(truth, predicted)) / len(truth)
assert isclose(macro, (16/17 + 0 + 1)/3) and isclose(micro, accuracy)
print(f"macro F1={macro:.4f}; micro F1={micro:.4f}; accuracy={accuracy:.4f}")
```
**Run it locally**
```sh
python classification-metrics-macro-micro-report.py
```
**Expected output**
```text
leaf: TP=8 FP=1 FN=0 F1=0.9412
flower: TP=0 FP=0 FN=1 F1=0.0000
seed: TP=1 FP=0 FN=0 F1=1.0000
macro F1=0.6471; micro F1=0.9000; accuracy=0.9000
```
**Follow the execution**
1. Treat one class as positive at a time. The mistaken flower creates a false positive for leaf and a false negative for flower.
2. Compute F1_c=2TP_c/(2TP_c+FP_c+FN_c). State a convention for a zero denominator.
3. Macro averages class F1 values equally. Micro first combines counts and then computes one score.
4. Check micro F1 against accuracy for this single-label, exhaustive-class setting.
**Read the code step by step**
Macro F1=(1/K) sum over K class-specific F1 values. Every included class receives weight 1/K. Micro F1=2 sum(TP)/(2 sum(TP)+sum(FP)+sum(FN)). In exhaustive single-label classification, each incorrect prediction contributes one FP and one FN, so micro F1 equals accuracy. This identity does not extend automatically to multilabel evaluation or a selected subset of classes.
Leaf has F1=16/17, flower has F1=0, and seed has F1=1. Macro F1 is about 0.6471, while micro F1 and accuracy are 0.9. Neither average replaces the class-level counts. Ten examples are far too few for a reliable deployment estimate.
The code uses zero for a zero-denominator class and includes the explicitly listed labels. Other reporting conventions can exclude undefined classes. State the rule before comparing reports; otherwise two honest tools can return different macro values from the same data.
### Leon's further thinking
**Cost units must be consistent**
Adding minutes for one error to currency for another is meaningless without a conversion rule. Use a common stated unit.
**Threshold choice is a learned choice**
Trying thresholds on the final test labels leaks test information even when the model weights stay fixed.
**Watch out:** Calling all items negative does not yield perfect precision. It yields no positive predictions, so the precision denominator is zero.
Check your understanding
A model has 90% recall but only 10% precision. What does that imply for its positive predictions?
It catches nine out of ten actual positives, but only one in ten flagged cases is truly positive. Most flags are false positives, so the resulting workload may be substantial.
## Decision trees, entropy and information gain
### 01 / The story
A museum guide identifies an artifact by asking a sequence of questions. A helpful first question divides the collection into groups that are much easier to identify. A question that almost always receives the same answer teaches little; a question that identifies every item by its catalogue number memorizes the collection without helping with new arrivals.
Decision-tree learning formalizes this choice by measuring uncertainty before and after a question. Each branch then asks its own follow-up question using only the artifacts that reached it. This local process creates a readable decision procedure, although locally useful questions need not produce the globally smallest tree.
### 02 / The principle
A classification tree tests an attribute or threshold at each internal node and predicts a class at a leaf. ID3 greedily chooses high information gain, partitions the data and recurses on each subset. Entropy measures uncertainty in the class distribution; information gain subtracts the size-weighted child entropy from parent entropy.
Pure nodes have entropy zero. If no informative split remains, predict a majority class rather than continuing forever; empty branches need a fallback based on available parent data. Numeric threshold tests produce axis-aligned boundaries, whereas categorical tests branch on values.
A tree can represent complex finite mappings, but conflicting labels for identical features cannot be perfectly classified by a deterministic function. Learning a compact generalizable tree requires more than reducing training entropy.
### 03 / The formula, unpacked
```text
H(Y) = −Σ꜀ p꜀ log₂ p꜀, with 0 log₂ 0 defined as 0
IG(S,A) = H(S) − Σᵥ (|Sᵥ|/|S|)H(Sᵥ)
```
p꜀ is the fraction of observations in class c. The logarithm base two measures entropy in bits; the zero-probability term is defined by its limit, not by claiming log₂0 equals zero.
S is the current training subset, A a candidate attribute and Sᵥ a child subset. Its weight |Sᵥ|/|S| is the fraction routed to that branch. Information gain therefore averages uncertainty over examples, not equally over differently sized branches.
### 04 / A first worked example
A node contains eight artifacts: four class A and four class B, so entropy is 1 bit. A proposed question creates one child with three A and one B and another with one A and three B. Each child has entropy −0.75log₂0.75−0.25log₂0.25≈0.8113 bits.
The weighted child entropy is also 0.8113, giving gain 0.1887 bits. A second question creates two pure four-item children, giving child entropy 0 and gain 1. On this training data, the greedy rule selects the second question. Whether it generalizes depends on how the question was obtained and validated.
### Words to know
- **Entropy:** A measure of uncertainty in a label distribution.
- **Information gain:** Parent uncertainty minus expected uncertainty after a split.
- **Pure node:** A node containing only one observed class.
### Let us work through it
**Entropy of one certain class?**
Zero, since there is no class uncertainty.
**Why weight child entropies?**
Larger children contain more observations and should contribute more.
**Does greedy mean globally best tree?**
No, the best immediate split may not give the best complete tree.
### A completely informative split
A node has 4 red and 4 blue labels. A split sends all red left and all blue right. Compute parent entropy and gain in bits.
**Choose the method**
Calculate class proportions and then the weighted child uncertainty.
1. Parent proportions are 1/2,1/2, so H=−2(1/2)log₂(1/2)=1.
2. Both children are pure, so each entropy is 0.
3. Weighted child entropy=(4/8)0+(4/8)0=0; gain=1−0=1.
**Interpret the answer**
The split gains 1 bit, removing all training-label uncertainty.
**Check the reasoning**
Gain equals parent entropy and cannot remove more uncertainty than was present.
### Weight child uncertainty
A node has 3A and 1B. Split into a pure 2A child and a mixed 1A1B child. Use log₂3≈1.584963.
**Choose the method**
Compute parent entropy, then weight each child by its two records.
1. Parent entropy=−0.75log₂0.75−0.25log₂0.25≈0.811278.
2. Pure child entropy is 0; balanced mixed child entropy is 1.
3. Each child has weight 2/4, so expected entropy=0.5; gain≈0.311278.
**Interpret the answer**
The split gains about 0.3113 bits; uncertainty remains in the mixed child.
**Check the reasoning**
Gain is nonnegative and smaller than the initial 0.811278 bits.
### Leon's further thinking
**Entropy units depend on log base**
Base 2 gives bits; the natural logarithm gives nats. Keep one base when comparing gains.
**A unique ID can look perfect**
Splitting every training item into its own pure leaf removes entropy but may have no rule for future IDs. Purity alone is insufficient.
**Watch out:** Do not average child entropies without weighting by child size. A tiny pure branch should not outweigh a large mixed branch.
Check your understanding
What is the entropy of four equally likely classes, and why?
It is −4×(1/4)×log₂(1/4)=2 bits. There are four equally plausible labels, so two binary bits are needed on average in the ideal coding interpretation.
## Grow useful trees without memorizing noise
### 01 / The story
A gardener can let every twig grow or trim branches that consume space without producing useful fruit. A learned tree has a similar tension: extra branches can explain unusual training records while making future decisions less reliable. Trimming must be judged on evidence beyond the records that created the branches.
Numeric questions also need restraint; carving a tiny interval around every unusual value produces a tidy training story and a brittle classifier. The gardening analogy helps explain complexity control, but a statistically useful pruning decision depends on validation evidence and the cost of mistakes, not on visual symmetry.
### 02 / The principle
Pre-pruning limits growth through depth, minimum leaf size or minimum improvement. Post-pruning grows a tree and then compares simpler alternatives, such as replacing a subtree with a majority-class leaf, raising a subtree or pruning extracted rules.
Reduced-error pruning accepts changes that do not harm validation performance, subject to a chosen tie policy. Numeric splits usually test thresholds between distinct sorted values; evaluate their resulting weighted impurities. Information gain favors many-valued attributes, including identifiers.
Gain ratio divides by the entropy of the branch distribution to mitigate that bias, but very small denominators create another problem, so practical selection uses safeguards. Acquisition costs may also influence which tests are worthwhile. None of these devices guarantees the best tree, and the final test set must remain outside pruning decisions.
### 03 / The formula, unpacked
```text
SplitInfo(A) = −Σᵥ qᵥ log₂ qᵥ, qᵥ = |Sᵥ|/|S|
GainRatio(A) = IG(S,A)/SplitInfo(A)
Candidate threshold between a < b: θ = (a+b)/2
```
qᵥ is the fraction of current examples sent to branch v, regardless of their class. SplitInfo measures the uncertainty of branch membership, whereas IG measures reduction in class uncertainty.
Gain ratio is defined only when SplitInfo is positive and should not be used without selection safeguards. The threshold θ divides distinct ordered numeric values a and b; actual implementations can choose an equivalent safe representable boundary and must handle tied values consistently.
### 04 / A first worked example
Eight training records have a balanced binary target. A unique identifier splits them into eight pure singleton branches, so its information gain is 1 bit. Its split information is −8×(1/8)log₂(1/8)=3 bits, giving gain ratio 1/3. A meaningful two-valued attribute that also perfectly separates the target has split information 1 and gain ratio 1.
Later, a subtree gets 15 of 20 validation records correct; replacing it with a majority leaf gets 16 correct. Reduced-error pruning accepts the leaf. The validation comparison supports simplification, but the reported final performance still needs untouched evaluation data.
### Words to know
- **Pre-pruning:** Stop growth before a branch is fully built.
- **Post-pruning:** Simplify an already grown tree using a stated criterion.
- **Gain ratio:** Information gain divided by branch-distribution entropy.
### Let us work through it
**Can the test set choose pruning?**
No; use validation evidence and preserve final testing.
**Why consider thresholds between distinct values?**
They change which examples fall on each side; splitting equal values inconsistently is invalid.
**What if SplitInfo=0?**
The ratio is undefined; the split sends all examples to one branch.
### Prune using validation counts
A subtree correctly labels 17 of 25 validation items. Replacing it with its training-majority leaf correctly labels 19. Accept non-worsening accuracy.
**Choose the method**
Compare the two candidates on identical validation items.
1. Subtree accuracy is 17/25=0.68.
2. Leaf accuracy is 19/25=0.76.
3. The improvement is 2/25=0.08, so the simpler replacement passes the rule.
**Interpret the answer**
Prune the subtree; validation accuracy rises by 8 percentage points.
**Check the reasoning**
Errors fall from 8 to 6, agreeing with two more correct predictions.
### Compare gain ratios
Four records have balanced binary labels. Attribute ID has four singleton branches; attribute A has two pure branches of size 2. Both gains are 1 bit.
**Choose the method**
Measure branch entropy separately from class gain.
1. ID branch probabilities are 1/4 each, so SplitInfo=2 bits.
2. A branch probabilities are 1/2 each, so SplitInfo=1 bit.
3. Ratios are 1/2=0.5 for ID and 1/1=1 for A.
**Interpret the answer**
A has the higher ratio; it achieves equal training separation with fewer branches.
**Check the reasoning**
The original information gains tie; only normalization distinguishes these choices.
### Leon's further thinking
**A tie policy changes the final size**
When validation scores tie, preferring the smaller tree is a defensible simplicity policy, but state it before inspecting outcomes.
**Pure leaves are not always useful**
A one-example leaf has no within-leaf disagreement, yet little evidence about future cases. Minimum leaf size trades fit for stability.
**Watch out:** Gain ratio reduces some many-value bias; it does not automatically remove identifier leakage or guarantee a smaller, more accurate tree.
Check your understanding
Why might pre-pruning stop too early on XOR?
Each individual input gives zero information gain at the balanced root, even though two successive splits solve the problem. A rule requiring immediate positive gain can miss a useful interaction.
## Perceptrons and linear decision boundaries
### 01 / The story
An automated gate awards points for several badge features, adds a baseline adjustment, and opens when the total reaches a threshold. Each feature’s weight determines how strongly it pushes the decision. When a known valid badge is rejected, a perceptron update nudges the scoring rule toward that badge; when an invalid badge is accepted, it nudges the other way.
Geometrically, this rotates or shifts a separating boundary. A single boundary cannot isolate every possible pattern: accepting two opposite corners of a square while rejecting the other two demands more than one straight dividing line.
### 02 / The principle
An artificial neuron computes a weighted input sum plus a bias, then applies an activation function. A perceptron uses a hard threshold and therefore forms a linear decision boundary. With binary targets 0 and 1, its error is target minus prediction; each mistaken example changes weights in proportion to its input and updates the bias.
An epoch is one pass through the training data. For a finite linearly separable dataset, standard perceptron learning converges after finitely many mistakes under its usual update conditions. Nonseparable data need a stopping budget or another objective.
The algorithm finds a separator, not necessarily the largest-margin separator. A multi-neuron hidden layer can combine linear tests to represent nonlinear patterns such as XOR, but the original single-perceptron update does not directly solve multilayer credit assignment.
### 03 / The formula, unpacked
```text
z = w·x + b; a = 1 if z ≥ 0, otherwise 0
e = t − a
w ← w + ηex; b ← b + ηe
Boundary: w·x + b = 0
```
x is the input vector, w a matching weight vector, b the bias, z the pre-activation and a the binary output. The target t uses the same 0/1 convention. Eta, written η, is a positive learning rate.
The dot denotes a dot product. Weight updates must use the prediction made before the update. The normal vector w is perpendicular to the decision boundary, while b moves that boundary without changing its orientation.
### 04 / A first worked example
Take x=(2,−1), target t=1, initial weights w=(0.2,0.4), bias b=−0.3 and learning rate η=0.5. The score is 0.2×2+0.4×(−1)−0.3=−0.3, so prediction a=0 and error e=1. Update weights to (0.2,0.4)+0.5×(2,−1)=(1.2,−0.1), and bias to 0.2. Re-evaluating this example gives 1.2×2+(−0.1)×(−1)+0.2=2.7, hence output 1.
This example is now correct, but previously correct examples may have changed sides. Check the full training set before claiming an epoch has achieved separation. The update changed both orientation and offset of the boundary. Keeping the bias fixed would describe a different algorithm with a different sequence of future classifications.
### Words to know
- **Dot product:** Multiply matching entries, then add all products.
- **Bias:** An adjustable constant added to the weighted input sum.
- **Linearly separable:** One straight boundary can place all labels on their required sides.
### Let us work through it
**What happens on a correct prediction?**
e=0, so this perceptron rule changes neither weights nor bias.
**Must learning find the widest margin?**
No, ordinary perceptron only seeks a separator.
**What does a score of zero predict here?**
Class 1 because the threshold is z≥0.
### Correct a false positive
x=(1,2), target 0, w=(1,0), b=0, η=0.2. Predict 1 when z≥0. Perform one update.
**Choose the method**
Find the old prediction and its signed error before changing parameters.
1. Old score=1×1+0×2+0=1, so a=1 and e=0−1=−1.
2. Weight change=0.2(−1)(1,2)=(−0.2,−0.4); new w=(0.8,−0.4).
3. New b=−0.2 and score=0.8−0.8−0.2=−0.2, so output 0.
**Interpret the answer**
This example becomes correct after one update.
**Check the reasoning**
The score decreased by 1.2=η(||x||²+1), consistent with e=−1.
### Use an offset boundary
One-dimensional data: x=1 has label 0 and x=3 has label 1. Use threshold z≥0. Find w=1 and a suitable b, then check why b=0 cannot work with any w.
**Choose the method**
Place the boundary between the two points and test signs.
1. Choose b=−2 so z=x−2 and boundary x=2.
2. At x=1, z=−1 gives 0; at x=3, z=1 gives 1.
3. If b=0, both positive inputs have the sign of w; w=0 gives 1 for both. They cannot receive different labels.
**Interpret the answer**
w=1,b=−2 separates the data; the bias is essential in this example.
**Check the reasoning**
The midpoint 2 lies strictly between 1 and 3, so neither example sits on the threshold.
### Leon's further thinking
**Freeze the old prediction**
Compute e once from the old parameters. Recomputing e halfway through updating coordinates mixes two different rules.
**Scaling changes the update path**
Multiplying one input coordinate by 100 multiplies its weight update by 100 for the same error. Scale features before interpreting learning-rate behavior.
**Watch out:** A zero score needs an explicit threshold convention. Switching between greater-than and greater-than-or-equal during a trace changes updates.
Check your understanding
Why can a perceptron without a bias fail on data separable by an ordinary straight line?
Its boundary is constrained to pass through the origin. A bias supplies the offset needed for separators that do not pass through the origin.
## Multilayer networks and backpropagation
### 01 / The story
Imagine a workshop with several processing stations. The final product is wrong, but blaming only the last station misses how earlier stations shaped its input. Backpropagation traces how a small change at each station would influence the final error. Each station receives downstream sensitivity and multiplies it by its own local sensitivity.
This is a chain-rule calculation, not an instruction to send the original target unchanged to every hidden unit. The forward pass saves intermediate values; the backward pass reuses them. All gradients describe the same current workshop configuration before the optimizer changes any of its settings.
### 02 / The principle
A multilayer perceptron composes affine transformations with nonlinear activations. Without nonlinearities, stacked affine layers collapse to one affine map. Categorical inputs often use one-hot encodings or learned embeddings; output choices depend on the task, with one sigmoid common for binary classification and softmax common for exclusive multiclass classification.
Backpropagation efficiently differentiates a chosen loss through the computation graph. For sigmoid units and half squared error, output sensitivities combine prediction error with the sigmoid derivative; hidden sensitivities combine downstream sensitivities through outgoing weights.
Compute all gradients using the forward-pass parameter values, then update. A universal approximation theorem concerns the existence of sufficiently large networks under stated function and domain conditions; it does not guarantee that a particular architecture or training run finds suitable parameters.
### 03 / The formula, unpacked
```text
σ(z) = 1/(1+exp(−z)); σ′(z) = σ(z)(1−σ(z))
L = ½Σᵢ(aᵢ−tᵢ)²
δᵢ = (aᵢ−tᵢ)aᵢ(1−aᵢ) at output
δⱼ = aⱼ(1−aⱼ)Σᵢ wᵢⱼδᵢ at hidden unit
∂L/∂wᵢⱼ = δᵢaⱼ; w ← w − η∇L
```
a denotes a unit’s activation and t its target. Delta, δ, is the derivative of loss with respect to a unit’s pre-activation. The weight wᵢⱼ connects source j to destination i. A hidden unit has no direct target, so its sensitivity sums downstream contributions.
The gradient symbol ∇ collects partial derivatives of the loss. These delta expressions specifically assume sigmoid activation and half squared error; another activation or loss changes the local derivative.
### 04 / A first worked example
A tiny network has input x=1, one sigmoid hidden unit with input weight 0 and bias 0, and one sigmoid output with weight 2 and bias −1. The hidden activation is 0.5; the output score is 2×0.5−1=0, so output a=0.5. With target 1, loss is 0.125.
Output delta is (0.5−1)×0.25=−0.125. The output-weight gradient is −0.0625. Hidden delta is 0.25×2×(−0.125)=−0.0625, which is also the input-weight gradient. At learning rate 0.1, both weights increase by 0.00625; the output bias increases by 0.0125 and hidden bias by 0.00625.
### Words to know
- **Derivative:** The local rate at which one quantity changes when another changes slightly.
- **Chain rule:** Multiply local rates along a dependency path, adding contributions from multiple paths.
- **Gradient:** A list of loss derivatives, one for each adjustable parameter.
### Let us work through it
**Why save the forward activations?**
Local derivative formulas use them during the backward pass.
**Does a hidden unit have the original label as its target?**
Usually no; it receives sensitivity through downstream connections.
**Why add nonlinear activations?**
Otherwise stacked affine layers still describe one affine transformation.
### One sigmoid gradient
Input x=2, weight w=0, bias b=0, target t=1. Use sigmoid output, L=(a−t)²/2 and learning rate 0.1. Compute one simultaneous update.
**Choose the method**
Move forward for a, then backward through loss and activation.
1. z=0×2+0=0, so a=σ(0)=0.5 and L=0.125.
2. Sigmoid slope is 0.5(1−0.5)=0.25; δ=(0.5−1)0.25=−0.125.
3. Weight gradient=δx=−0.25 and bias gradient=δ=−0.125. New w=0.025,b=0.0125.
**Interpret the answer**
The score rises to 0.0625, moving the sigmoid output toward target 1.
**Check the reasoning**
Both gradients are negative, so subtracting them increases both parameters as needed.
### Backpropagate a simple chain
Let u=3w, prediction a=u+1, target t=4, loss L=(a−t)²/2. At w=2 compute dL/dw. Use slope of L with respect to a equal to a−t.
**Choose the method**
Compute intermediate values, then multiply local slopes backward.
1. At w=2, u=6,a=7 and L=(7−4)²/2=4.5.
2. Local slopes are dL/da=3, da/du=1, du/dw=3.
3. Chain rule gives dL/dw=3×1×3=9.
**Interpret the answer**
The gradient is 9; a small decrease in w decreases the loss locally.
**Check the reasoning**
Directly L=(3w−3)²/2; its slope at w=2 is 3(3w−3)=9, agreeing with the chain.
### Check one sigmoid update
Follow the first worked problem using only the standard math module.
```python
import math
x, target = 2.0, 1.0
weight, bias = 0.0, 0.0
rate = 0.1
score = weight * x + bias
activation = 1 / (1 + math.exp(-score))
delta = (activation - target) * activation * (1 - activation)
weight_gradient = delta * x
bias_gradient = delta
weight = weight - rate * weight_gradient
bias = bias - rate * bias_gradient
print(f"Old output: {activation:.6f}")
print(f"New weight: {weight:.6f}")
print(f"New bias: {bias:.6f}")
print(f"New score: {weight * x + bias:.6f}")
assert abs(weight - 0.025) < 1e-12
```
**Run it locally**
```sh
python backpropagation-sigmoid-one-update.py
```
**Expected output**
```text
Old output: 0.500000
New weight: 0.025000
New bias: 0.012500
New score: 0.062500
```
**Follow the execution**
1. The old score 0 gives activation 0.5 and delta −0.125.
2. The input 2 makes the weight gradient −0.25; bias gradient remains −0.125.
3. Subtracting the negative updates raises the score to 0.0625.
**Read the code step by step**
import math makes the exponential function available as math.exp. Comma-separated assignment stores two numbers in two names. The sigmoid turns the old score into an output between 0 and 1.
The expression for delta multiplies the loss slope by the sigmoid slope. Both gradients are saved before either parameter changes. Subtracting rate times gradient performs descent. An f-string inserts a computed value; :.6f displays six decimal places. abs and a small tolerance check the expected floating-point result. This is one hand-designed neuron and one training step, not a trained general classifier.
### Leon's further thinking
**Start with a scalar chain**
For u=2w and L=u²/2, changing w slightly changes u twice as much. Multiply that rate 2 by the local loss slope u to get 2u.
**Check gradients numerically**
For a smooth loss compare the derivative with [L(w+ε)−L(w−ε)]/(2ε). Small finite ε gives an approximation, useful for detecting sign mistakes.
**Watch out:** Do not update an outgoing weight before using it to compute the hidden gradient for the same example. That mixes parameter versions and is no longer the intended gradient.
Check your understanding
Why are independent sigmoid output scores not automatically a probability distribution over mutually exclusive classes?
They need not sum to one. Softmax explicitly normalizes scores across classes; even normalized scores still require empirical calibration checks before strong probabilistic claims.
## Optimization, initialization and regularization
### 01 / The story
A hiker descending a valley chooses a direction from the local slope and a step length from a training policy. Tiny steps take a long time; large steps can jump across the valley and climb the opposite side. Momentum gives the hiker some persistence, smoothing alternating directions but sometimes carrying them too far.
Training and validation losses act like two maps: one shows fit to the familiar terrain, while the other checks whether the route helps on unseen terrain. Neither a flat slope nor a low training loss proves the hiker has reached the best destination.
### 02 / The principle
Gradient descent updates parameters opposite the loss gradient. Full-batch updates average all training examples; stochastic updates use one example; minibatches trade gradient noise against efficient computation. Learning rate controls step size and can determine whether training converges or diverges.
Momentum accumulates past update directions, while adaptive methods rescale updates using gradient history. Random, appropriately scaled initialization breaks symmetry between hidden units. Input scaling helps optimization, but must be learned without leakage. Deep sigmoid networks can suffer vanishing gradients because many small derivatives multiply.
Monitor validation loss, retain the best checkpoint and stop after a defined patience period. Weight decay and dropout constrain fitting, though none guarantees generalization. A stationary point can be a minimum, maximum or saddle, and neural losses can have multiple equivalent minima.
### 03 / The formula, unpacked
```text
vₜ = μvₜ₋₁ − η∇L(θₜ); θₜ₊₁ = θₜ + vₜ
Lregularized = Ldata + λ||w||²/2
Inverted dropout: ã = ma/q, m ~ Bernoulli(q)
```
Theta, θ, denotes parameters and v their update velocity. Eta is learning rate and μ the momentum coefficient, usually between zero and one. Lambda, λ, controls an L2 penalty on selected weights.
For dropout, q is retention probability, m is a random zero-or-one mask and a is an activation. Dividing retained activations by q keeps their expected value unchanged during training. In this inverted-dropout convention, prediction uses unmasked activations without another scaling step.
### 04 / A first worked example
For the scalar loss L(w)=w²/2, the gradient is w. Starting at w=4 with learning rate 0.5 gives w=2, then 1, then 0.5; losses fall from 8 to 2, 0.5 and 0.125. With learning rate 3, the first update gives w=−8 and loss 32, so a gradient step has increased the loss.
For an activation a=6 and dropout retention q=0.75, the training output is 8 with probability 0.75 or 0 with probability 0.25. Its expectation remains 6. This does not mean any individual training forward pass equals inference.
### Words to know
- **Learning rate:** The multiplier controlling the size of a gradient update.
- **Momentum:** A stored update direction that mixes past motion with the current gradient.
- **Regularization:** A restriction or penalty intended to discourage overly specific fitting.
### Let us work through it
**Does every gradient step reduce loss?**
No, too large a learning rate can overshoot.
**What does dropout preserve in expectation?**
The activation value under the inverted scaling convention.
**Which checkpoint should early stopping retain?**
The best according to the declared validation criterion.
### Two descent steps
L(w)=w²/2, gradient w, initial w=6, learning rate 1/2. Use plain gradient descent without momentum.
**Choose the method**
At each step subtract half the current weight.
1. Initial loss=6²/2=18.
2. First update w=6−(1/2)6=3, loss=9/2=4.5.
3. Second update w=3−(1/2)3=1.5, loss=2.25/2=1.125.
**Interpret the answer**
After two steps w=1.5 and loss 1.125; each step quarters this loss.
**Check the reasoning**
Halving w squares into a factor 1/4 in w²/2, explaining the loss ratio.
### Dropout expectation
Activation a=10, independent retention mask with q=0.4. Use inverted dropout ã=ma/q. Find outputs and expectation.
**Choose the method**
List the two mask outcomes and weight their outputs.
1. When m=1, output=10/0.4=25, with probability 0.4.
2. When m=0, output=0, with probability 0.6.
3. Expectation=0.4×25+0.6×0=10.
**Interpret the answer**
Training outputs 0 or 25 but averages 10; inference uses 10 without another scaling.
**Check the reasoning**
The expected value equals a, although neither individual output equals a.
### Leon's further thinking
**A derivative is local information**
The gradient predicts a small-step change near current parameters. It does not certify a large jump or a global optimum.
**Penalty and update need matching conventions**
For λw²/2, the added slope is λw. Omitting the half changes the derivative to 2λw; compare definitions before comparing settings.
**Watch out:** Decreasing training loss while validation loss worsens is a reason to revisit complexity or stopping. Continuing until training error vanishes is not a general learning objective.
Check your understanding
If two hidden units have identical incoming and outgoing weights, why can zero initialization be a problem?
Under symmetric computation they receive identical gradients and remain identical, failing to learn distinct features. Random initialization breaks this symmetry.
## Autoencoders and learned representations
### 01 / The story
An archivist compresses sketches into a short description and asks another archivist to reconstruct them. If the description can simply copy every pixel, little structure must be learned. A tight description forces it to preserve recurring features, such as shape and stroke direction.
An autoencoder creates this exercise from the data itself, using the input as the reconstruction target. However, a compact description is not encryption: anyone with enough access or an alternative decoder might recover information. Reconstruction quality also reflects what the model has learned to retain, rather than a universal measure of what humans consider important.
### 02 / The principle
An autoencoder combines an encoder that maps an input to a latent representation with a decoder that reconstructs it. Training minimizes a reconstruction loss without external class labels. An undercomplete bottleneck limits representation dimension; sparse penalties and denoising objectives impose other constraints even when a hidden layer is wide.
A denoising autoencoder receives a corrupted input but targets the clean input. Stacked autoencoders can pretrain successive representations, followed by a supervised head and optional end-to-end fine-tuning. Such pretraining is one historical and practical option, not a required step for every deep network.
Latent features can support compression, visualization or downstream prediction. High reconstruction error may suggest novelty, but anomaly detection needs separate validation because unfamiliar inputs can sometimes reconstruct well and harmless changes can reconstruct poorly.
### 03 / The formula, unpacked
```text
h = fencoder(x); x̂ = fdecoder(h)
Lreconstruction = (1/n)Σᵢ ||xᵢ − x̂ᵢ||²
Denoising: minimize ||x − fdecoder(fencoder(xcorrupted))||²
```
x is an input vector, h its latent code and x̂ the reconstruction. The encoder and decoder are learned functions, often neural networks. The sum averages over n training examples; the squared norm adds featurewise reconstruction errors, so feature scaling affects the objective.
In denoising, xcorrupted is a deliberately perturbed input while the target remains the clean x. A small latent dimension limits coordinate count but does not itself define a bitrate, security property or interpretable factor.
### 04 / A first worked example
Suppose training inputs have the form (u,2u), such as (1,2), (3,6) and (4,8). An encoder h=x₁ and decoder x̂=(h,2h) reconstruct all three perfectly using one coordinate instead of two. For input (3,7), the same system reconstructs (3,6), giving squared error (3−3)²+(7−6)²=1.
The example demonstrates learned structure: the data approximately follow a line. It does not show that the representation is secret or that error 1 is necessarily anomalous. A practical threshold would be chosen using an appropriate held-out distribution and the consequences of false alarms.
### Words to know
- **Encoder:** A function turning input into an internal representation.
- **Decoder:** A function reconstructing the input from the representation.
- **Reconstruction error:** A specified measure of difference between input and reconstruction.
### Let us work through it
**Are class labels required?**
No; ordinary reconstruction uses the input as its target.
**Does one latent number define a fixed bitrate?**
No; storage precision and encoding must also be specified.
**Does large error prove anomaly?**
No; the threshold and task require validation.
### Reconstruct a line-shaped pattern
Use h=x₁ and decoder(h,3h). For x=(2,7), compute reconstruction and sum of squared errors. No averaging over coordinates.
**Choose the method**
Encode first, decode next, then compare each coordinate.
1. The encoder keeps h=2.
2. Decoder outputs(2,6).
3. Errors are 2−2=0 and 7−6=1; squared sum=0²+1²=1.
**Interpret the answer**
Reconstruction is(2,6), with error 1; the decoder forces the relation x₂=3x₁.
**Check the reasoning**
An input(2,6) would reconstruct exactly, giving zero error.
### Clean versus corrupted target
Clean input is(1,1), corrupted input(1,0). Compare outputs A=(1,0) and B=(0.8,0.8) using squared error to the clean target.
**Choose the method**
Use the clean vector in both comparisons.
1. A copies the corrupted input; error=(1−1)²+(1−0)²=1.
2. B has two errors 0.2, giving 0.2²+0.2²=0.08.
3. Since 0.08<1, the denoising objective prefers B.
**Interpret the answer**
B better recovers the clean pattern despite not copying either input coordinate exactly.
**Check the reasoning**
If incorrectly compared to the corrupted target, A would score 0, illustrating why target choice matters.
### Leon's further thinking
**Feature units matter**
Converting length values from meters to centimeters multiplies each difference by 100 and its squared error by 10000. Choose feature scaling to match the intended importance.
**A wide bottleneck needs other constraints**
If a model can copy inputs perfectly, reconstruction alone may teach little. Denoising or sparsity changes what information is useful to retain.
**Watch out:** Compression and reconstruction do not establish cryptographic confidentiality. Treat autoencoder security claims separately from representation learning.
Check your understanding
Why does a denoising autoencoder compare its output with the clean input?
Otherwise it could learn to reproduce the corruption. The clean target encourages recovering structure that remains predictable despite the perturbation.
## Convolutions, pooling and shared features
### 01 / The story
A quality inspector slides a small stencil across a cloth. The same stencil checks each area for a local pattern. It may find an edge in one place and a corner in another. Reusing the stencil is the key idea behind a convolutional filter.
### 02 / The principle
Convolutional networks use local receptive fields and shared filter weights to exploit spatial structure. A filter spans all input channels and produces one output feature map; multiple filters learn multiple maps. Deep-learning libraries usually implement cross-correlation without flipping the filter, despite calling it convolution.
Stride controls sampling positions, padding controls border treatment and dilation spreads filter entries. Nonlinear activation follows filtering; pooling downsamples through a local maximum or average. Weight sharing greatly reduces parameters relative to dense connections and yields translation equivariance under suitable boundary assumptions.
Pooling may provide limited shift tolerance, not guaranteed global invariance. Multiple layers enlarge the effective receptive field. Local contrast normalization is an optional historical component; modern architectures vary. Train these operations through backpropagation and validate robustness rather than inferring it from architecture alone.
### 03 / The formula, unpacked
```text
yᵢⱼₖ = bₖ + Σᵤᵥ꜀ Wᵤᵥ꜀ₖ xᵢ₊ᵤ,ⱼ₊ᵥ,꜀
Output width = floor((W + 2P − K)/S) + 1
Parameters = Kheight·Kwidth·Cin·Cout + Cout
```
x is the input tensor and y the feature map before activation. The indices u and v locate a filter entry, c an input channel and k an output channel. The first expression shows stride-one cross-correlation.
In the shape expression, W is input width, P padding per side, K filter width and S stride, with dilation one. Cin and Cout count channels; one bias per output channel is included. Spatial image size does not multiply the number of shared parameters.
### 04 / A first worked example
Apply a 2×2 filter [[1,0],[0,−1]] to the 3×3 input [[1,2,3],[4,5,6],[7,8,9]], with stride one, no padding and zero bias. The four outputs are 1−5=−4, 2−6=−4, 4−8=−4 and 5−9=−4, forming a 2×2 map. ReLU would set all four to zero; max pooling before ReLU would produce −4.
For a separate RGB layer using eight 3×3 filters, parameter count is 3×3×3×8+8=224, regardless of whether the input image is 32×32 or 64×64. Output dimensions and computation cost still depend on image size. Weight sharing saves parameters without eliminating the work of visiting image positions.
### Words to know
- **Channel:** One value plane, such as red intensity or a learned feature map.
- **Stride:** The number of positions the filter moves between evaluations.
- **Weight sharing:** Reuse the same filter numbers at many spatial positions.
### Let us work through it
**Does a filter see all input channels?**
In an ordinary dense convolution, yes; it sums their contributions into one output channel.
**Does doubling image width double parameters?**
No; the same filter is reused, though computation increases.
**What does ReLU do to −3?**
It outputs max(0,−3)=0.
### Slide a one-dimensional filter
Input [2,5,4,8], filter [1,−1], stride 1, no padding, bias 0. Use cross-correlation, then ReLU.
**Choose the method**
Use each adjacent pair without flipping the filter.
1. First window [2,5] gives 2×1+5×(−1)=−3.
2. Next windows [5,4] and [4,8] give 1 and −4.
3. ReLU replaces negatives by 0, producing [0,1,0].
**Interpret the answer**
Raw map [−3,1,−4], activated map [0,1,0].
**Check the reasoning**
Output length=(4−2)/1+1=3, matching three windows.
### Count shape and parameters
Input is 8×8 with 3 channels. Use 4 ordinary 3×3 filters, stride 1, padding 0, one bias per output channel, dilation 1.
**Choose the method**
Compute spatial size separately from learned parameter count.
1. Output width and height are(8−3)/1+1=6.
2. Four filters create 4 output channels, so shape is 6×6×4.
3. Each filter has 3×3×3=27 weights and 1 bias; total 4×28=112.
**Interpret the answer**
Output shape 6×6×4;112 trainable parameters.
**Check the reasoning**
There are 144 output values but only 112 parameters, because each filter is reused at 36 positions.
### Leon's further thinking
**Name correlation versus convolution**
A mathematical convolution flips the kernel, while the usual network operation does not. State the convention before a hand calculation.
**Boundary rules qualify equivariance**
Padding and stride can make shifted outputs differ near borders or sampling positions. Shared weights alone do not guarantee arbitrary-shift invariance.
**Watch out:** Equivariance means a shifted input shifts the feature map. Invariance means the output stays unchanged. Convolution alone usually supplies the former, not the latter.
Check your understanding
With width 10, filter width 3, padding 1 and stride 2, what is the output width?
floor((10+2−3)/2)+1=floor(4.5)+1=5. Counting filter placements avoids rounding the fractional result upward.
## Margins, soft constraints and kernels
### 01 / The story
A surveyor places a fence between two kinds of plants. Many fences separate the observed plants, but a fence with a wide clear corridor on both sides is less sensitive to small movements. A hard-margin support vector machine seeks that widest corridor.
One mislabeled plant can make strict separation impossible, so a soft margin allows some violations at a cost. A kernel changes the geometry in which the fence is straight, making a curved boundary possible in the original garden. This is a mathematical preference for a margin, not a promise that every unseen plant will be classified correctly.
### 02 / The principle
A linear SVM predicts from the sign of a weighted feature sum. Under canonical scaling, hard-margin constraints place all training examples at signed functional margin at least one and minimize half the squared weight norm. Soft-margin training adds nonnegative slack variables, penalized by C, to allow points inside the margin or misclassified.
Larger C penalizes violations more strongly relative to the norm term. In the dual, predictions depend on inner products with training examples whose multipliers are nonzero. A kernel supplies an inner product in a feature space without explicitly constructing its coordinates.
Valid kernels require positive-semidefinite Gram matrices for finite point sets; arbitrary similarity functions need not qualify. Scaling, C and kernel parameters require validation. Soft-margin support vectors can lie inside the margin, so they are not always simply the nearest correctly classified points.
### 03 / The formula, unpacked
```text
minimize ½||w||² + CΣᵢ ξᵢ
subject to yᵢ(w·xᵢ+b) ≥ 1−ξᵢ, ξᵢ ≥ 0
Margin width = 2/||w||
f(x) = Σᵢ αᵢyᵢK(xᵢ,x)+b
```
xᵢ is a training vector and yᵢ is either −1 or +1. The weight vector w and bias b define the separator; ξᵢ measures a margin shortfall. C is a positive penalty parameter. Alpha, αᵢ, is a learned dual multiplier.
K computes a feature-space inner product, and the sign of f predicts the class. The margin-width expression uses canonical scaling and a nonzero w; it is not the distance from every training point to the boundary.
### 04 / A first worked example
In one dimension, negative examples lie at −3 and −1 and positive examples at 1 and 4. The hard-margin solution is w=1 and b=0: the closest examples −1 and 1 satisfy y(wx+b)=1. The two margin boundaries are x=−1 and x=1, so their separation is 2/|w|=2.
For a soft-margin illustration, if a positive example at x=0.2 is evaluated under this same boundary, its functional margin is 0.2, requiring slack at least 0.8. For a degree-two kernel K(u,v)=(uv+1)², inputs u=2 and v=3 give K=49 without explicitly constructing the mapped vectors.
### Words to know
- **Margin:** The separation measured around a decision boundary under a stated scaling.
- **Slack:** The nonnegative shortfall from the required signed margin of 1.
- **Kernel:** A function acting as an inner product in a feature representation.
### Let us work through it
**What labels does this SVM formula use?**
−1 and+1, unlike the earlier 0/1 perceptron convention.
**What does increasing C favor?**
Fewer margin violations relative to keeping the weight norm small.
**Is every similarity a valid kernel?**
No; the required inner-product structure must hold.
### Find two slack values
Keep a fixed classifier. A positive example has score 0.3; a negative example has score 0.4. Find the minimum slack for each under y f(x)≥1−ξ.
**Choose the method**
Multiply each score by its label before measuring shortfall.
1. Positive signed margin=(+1)0.3=0.3, so ξ≥1−0.3=0.7.
2. Negative signed margin=(−1)0.4=−0.4, so ξ≥1−(−0.4)=1.4.
3. Both bounds are positive; nonnegativity adds no further change.
**Interpret the answer**
Minimum slacks 0.7 and 1.4; the first point is correctly signed but inside the margin, the second misclassified.
**Check the reasoning**
Substituting gives 0.3=1−0.7 and −0.4=1−1.4, exactly meeting constraints.
### Compute a polynomial kernel explicitly
For scalar inputs u=1,v=2, use K(u,v)=(uv+1)². Verify with feature map φ(x)=(x²,√2x,1).
**Choose the method**
Compute the compact formula and the feature dot product separately.
1. Kernel formula gives(1×2+1)²=9.
2. Mapped vectors are(1,√2,1) and(4,2√2,1).
3. Dot product=1×4+√2×2√2+1×1=4+4+1=9.
**Interpret the answer**
Both give 9, demonstrating an implicit three-coordinate inner product.
**Check the reasoning**
Expanding generally gives u²v²+2uv+1=(uv+1)², so agreement is not accidental.
### Leon's further thinking
**Functional and geometric margins differ**
Multiplying w and b by the same positive constant leaves the boundary unchanged but scales its raw scores. Canonical constraints fix the scale for the width formula.
**Explain the kernel requirement gently**
For any finite points and real coefficients c, a valid Gram matrix K must satisfy cᵀKc≥0. This is the squared-length property expected of inner products.
**Watch out:** A kernel trick avoids explicit feature coordinates; it does not remove training costs, overfitting risk or the need to choose a valid kernel.
Check your understanding
If a positive example has score w·x+b=−0.4, what minimum slack satisfies its soft-margin constraint?
Its signed functional margin is −0.4, so −0.4≥1−ξ requires ξ≥1.4. Slack greater than one indicates misclassification under this convention.
## Bagging, boosting and random forests
### 01 / The story
Three weather spotters may outperform one if they make different mistakes. If they all read the same broken thermometer, their unanimous vote adds little. Ensembles depend on this distinction between multiple models and useful diversity. Bagging gives learners different resampled histories.
A random forest also limits which features each split may inspect. Boosting instead builds a sequence in which later learners focus on what the current collection handles poorly. The committee analogy is useful, but models are not independent witnesses: shared training data, shared features and shared biases can make their errors strongly correlated.
### 02 / The principle
Bagging trains base learners on bootstrap samples drawn with replacement and aggregates votes or numeric predictions. It often reduces variance for unstable learners such as deep trees. A random forest adds random feature subsets at individual splits, aiming to decorrelate trees while keeping them useful.
AdaBoost maintains a distribution over training examples, fits a weak classifier and increases relative emphasis on mistakes before the next round. Its final vote weights learners using their weighted error, rather than raw unweighted accuracy alone.
Gradient boosting instead fits successive learners to a loss-related correction such as a negative gradient. Diversity and adequate accuracy can help ensembles, but neither independence nor improvement is guaranteed in practice. Extra models cost training time, storage and prediction work; noisy labels can attract harmful boosting attention.
### 03 / The formula, unpacked
```text
Bootstrap inclusion probability = 1−(1−1/n)ⁿ ≈ 0.632
AdaBoost: εₜ = Σᵢ Dₜ(i)·1[hₜ(xᵢ)≠yᵢ]
αₜ = ½ln((1−εₜ)/εₜ)
Dₜ₊₁(i) ∝ Dₜ(i)exp(−αₜyᵢhₜ(xᵢ))
```
n is training-set size and each bootstrap sample makes n draws. Dₜ is the normalized example-weight distribution at round t. The indicator is one for a mistake and zero otherwise. Predictions hₜ and labels yᵢ use −1/+1 values.
Epsilon is weighted error and alpha the learner’s vote weight. The shown AdaBoost formula assumes 0<εₜ<0.5; zero error and non-improving learners require explicit special handling. Renormalize the next distribution to sum to one.
### 04 / A first worked example
Three independent binary classifiers each err with probability 0.2. Majority vote is wrong when exactly two or all three err: 3×0.2²×0.8+0.2³=0.104. If their errors were identical, ensemble error would remain 0.2 instead. In an AdaBoost round with four equally weighted examples and one mistake, ε=0.25 and α=0.5ln3≈0.5493.
After exponential reweighting and normalization, the mistaken example has weight 1/2, while each correct example has weight 1/6. The next learner is trained against that changed distribution. This arithmetic explains the mechanism without assuming its future test error will decrease.
### Words to know
- **Bootstrap:** Sample training records with replacement, allowing repeats.
- **Correlated errors:** Models tend to fail on the same examples.
- **Weighted vote:** Combine predictions with specified unequal vote strengths.
### Let us work through it
**Does more models guarantee improvement?**
No, identical or poor errors may persist.
**What error does AdaBoost use?**
The current example-weighted error, not necessarily ordinary error rate.
**Why normalize example weights?**
They must form a distribution summing to 1 for the stated weighted-error formula.
### Three independent votes
Three binary classifiers independently err with probability 0.1 on a randomly drawn example. Find majority-vote error.
**Choose the method**
Separate exactly two mistakes from all three.
1. For one specified pair to err and the third succeed, probability=0.1²×0.9=0.009.
2. There are three possible wrong pairs, contributing 3×0.009=0.027.
3. All three wrong contributes 0.1³=0.001; total=0.028.
**Interpret the answer**
Majority error is 2.8% under independence, below 10% for each voter.
**Check the reasoning**
If all errors were identical, the answer would be 10%, showing why the assumption matters.
### A tiny bootstrap
There are 3 records. Draw 3 times independently with replacement. Find the probability a specified record appears at least once and expected distinct count.
**Choose the method**
Count complete absence, then use symmetry for the expectation.
1. Each draw misses the record with probability 2/3.
2. All three miss with probability(2/3)³=8/27; inclusion=19/27.
3. Sum the inclusion indicators of three records: expected distinct count=3×19/27=19/9.
**Interpret the answer**
Inclusion probability≈70.37%; expected distinct count≈2.111, not 3.
**Check the reasoning**
The expectation lies between 1 and 3, the possible distinct counts for three draws.
### Leon's further thinking
**Finite bootstrap differs from the limit**
The 63.2% figure is a large-n limit. For n=2 the exact inclusion chance is 75%; use the finite formula for small examples.
**Label noise can attract emphasis**
A persistently mislabeled item may gain large boosting weight. Inspect data quality rather than assuming every hard example is informative.
**Watch out:** Random forests normally sample candidate features at each split, not merely once for each whole tree. State the actual variant being implemented.
Check your understanding
Why is a bootstrap sample of size n not expected to contain n distinct training records?
Draws use replacement. A given record is absent with probability (1−1/n)ⁿ, approaching e⁻¹, so only about 63.2% of distinct records appear on average for large n.
## Joint distributions, conditioning and Bayes
### 01 / The story
A warehouse alarm sounds more often during equipment faults, but it also sounds occasionally during routine vibration. Hearing it changes belief about a fault; it does not prove a fault occurred. A useful calculation keeps a ledger of every combination: fault and alarm, fault without alarm, no fault with alarm, and neither.
Summing rows gives overall frequencies; restricting attention to alarm rows and renormalizing answers the question after an alarm. This bookkeeping explains why a reliable alarm can still generate many false alerts when faults are rare. Conditional reasoning depends on both the evidence and the prior situation.
### 02 / The principle
A joint probability distribution assigns nonnegative mass summing to one across complete assignments of discrete variables. Marginalization sums over variables that are not part of a query. Conditioning restricts to compatible assignments and divides by the probability of the evidence, which must be positive.
The product rule yields the chain rule, decomposing a joint into conditional factors. Bayes’ rule reverses conditioning by combining likelihood with prior probability. Independence means a joint factorizes without conditioning; conditional independence means it factorizes after a specified variable is known.
Neither type generally implies the other. Normalize unnormalized class scores only after summing all relevant hidden possibilities. Probability is a formal model of uncertainty; a frequency estimate is one way to obtain it, not the only interpretation.
### 03 / The formula, unpacked
```text
P(A|B) = P(A,B)/P(B), P(B)>0
P(A|B) = P(B|A)P(A)/P(B)
P(A) = Σᵦ P(A,b)
A ⟂ B | C: P(A,B|C) = P(A|C)P(B|C)
```
A and B denote events or variable assignments; the comma means both occur and the vertical bar means given. The sum ranges over a complete set of mutually exclusive values b. C is the variable or evidence that makes A and B conditionally independent in the last expression.
The independence symbol applies to the stated conditioning set only. All formulas use a consistent probability model and require conditioning events to have positive probability.
### 04 / A first worked example
Suppose a machine fault occurs with probability 0.02. The alarm sounds with probability 0.9 during a fault and 0.05 without one. The joint fault-and-alarm mass is 0.02×0.9=0.018. The no-fault-and-alarm mass is 0.98×0.05=0.049. Thus P(alarm)=0.067 and P(fault|alarm)=0.018/0.067≈0.2687.
In a hypothetical 10,000 operating periods, expected counts are 180 true alarms and 490 false alarms. The alarm raises fault probability substantially above 2%, yet most alarm periods still have no fault. These are illustrative model probabilities, not an empirical reliability claim. The two joint alarm cases are mutually exclusive and exhaust all ways the alarm can sound.
### Words to know
- **Joint probability:** Probability that specified events occur together.
- **Marginalization:** Sum over unwanted alternatives to obtain a smaller query.
- **Conditional probability:** Probability after restricting to cases compatible with observed evidence.
### Let us work through it
**Why divide by evidence probability?**
It rescales the retained cases so their probabilities sum to 1.
**Can we condition on zero-probability evidence using this formula?**
No; the denominator is zero.
**Does a strong likelihood remove the prior?**
No; posterior reasoning still multiplies by the prior.
### A rare signal
An event occurs with probability 0.1. A signal is positive with probability 0.8 when the event occurs and 0.2 otherwise. Find event probability after a positive signal.
**Choose the method**
Compute both mutually exclusive ways a positive signal can occur.
1. Event-and-positive mass=0.1×0.8=0.08.
2. No-event-and-positive mass=0.9×0.2=0.18; total positive mass 0.26.
3. Posterior=0.08/0.26=4/13≈0.307692.
**Interpret the answer**
The signal raises event probability from 10% to about 30.77%, still below one half.
**Check the reasoning**
Out of 1000 modeled cases,80 true and 180 false positives give 80/260, the same fraction.
### Read a joint table
Binary A,B have joint probabilities P(1,1)=0.3,P(1,0)=0.2,P(0,1)=0.1,P(0,0)=0.4. Find P(A=1),P(A=1|B=1), and independence.
**Choose the method**
Sum relevant cells, then compare joint mass with the product of marginals.
1. P(A=1)=0.3+0.2=0.5; P(B=1)=0.3+0.1=0.4.
2. P(A=1|B=1)=0.3/0.4=0.75.
3. If independent, P(1,1) would equal 0.5×0.4=0.2, but actual mass is 0.3.
**Interpret the answer**
The marginal is 0.5, conditional 0.75, and A,B are dependent.
**Check the reasoning**
All four masses are nonnegative and sum to 1, so the table is a valid distribution.
### Leon's further thinking
**Natural frequencies can help**
Replace probabilities with expected counts out of 1000 or 10000, then restrict to evidence cases. The same ratios often become easier to see.
**Conditioning is not intervention**
Learning that a switch is on can provide evidence about its causes. Forcing it on changes the process; a probability table alone need not answer that causal question.
**Watch out:** Do not swap P(alarm|fault) with P(fault|alarm). They answer different questions and are equal only in special cases.
Check your understanding
If two variables become independent after a common cause is observed, must they also be independent before it is observed?
No. Mixing over the unobserved common cause can create dependence. Learning one effect can then change belief about the cause and consequently about the other effect.
## Bayesian networks and inference
### 01 / The story
A building dashboard connects rain, a sprinkler and a wet courtyard. Drawing dependencies lets the engineer store local conditional tables instead of an enormous ledger of all combinations. The arrows tell the probability model how to factorize, but their direction alone does not certify causation.
To answer whether it rained after observing wet ground, the engineer must consider the unobserved sprinkler states, not silently choose the most convenient one. Variable elimination reuses intermediate calculations, much as an accountant totals repeated subtables once. Sampling offers another route, approximating answers from many simulated assignments when exact calculation becomes expensive.
### 02 / The principle
A Bayesian network is a directed acyclic graph with one conditional probability table per variable given its parents. Its local Markov property makes each variable independent of its non-descendants conditional on its parents, producing a product factorization of the joint. Absence of a direct edge does not mean unconditional independence.
A node’s Markov blanket comprises its parents, children and the other parents of its children. Exact enumeration sums over hidden assignments; variable elimination multiplies relevant factors and sums out one variable at a time, with complexity strongly affected by elimination order and intermediate factor size.
Approximate methods include prior sampling, rejection sampling, likelihood weighting and Gibbs sampling. Rare evidence harms rejection efficiency; weighted or dependent samples introduce their own variance and convergence issues. Network structure and tables can come from data, expertise or both.
### 03 / The formula, unpacked
```text
P(x₁,…,xₙ) = Πᵢ P(xᵢ | parents(Xᵢ))
P(Q|e) = α Σhidden Πᵢ P(xᵢ | parents(Xᵢ))
Binary-node parameter count = Σᵢ 2ᵏⁱ
```
Q is the queried variable, e the observed evidence and alpha the normalization constant making the resulting distribution sum to one. The sum covers every hidden-variable assignment consistent with the evidence. kᵢ is the number of binary parents of binary node i; each parent configuration needs one independent probability for that node.
The parameter-count expression assumes all variables are binary. Compact representation does not guarantee cheap inference, because products of factors can become large.
### 04 / A first worked example
Let R denote rain with P(R)=0.2 and S a sprinkler with P(S)=0.3, independent roots. Wet-ground probabilities for (R,S)=(1,1),(1,0),(0,1),(0,0) are 0.99, 0.8, 0.7 and 0.05. Sum over S to obtain P(wet|R)=0.3×0.99+0.7×0.8=0.857, and P(wet|not R)=0.3×0.7+0.7×0.05=0.245. The unnormalized rain scores are 0.1714 and 0.196, so P(R|wet)=0.1714/0.3674≈0.4665.
The network stores 1+1+4=6 independent parameters, compared with 2³−1=7 for an unrestricted joint distribution. The summation is essential because sprinkler status was not observed. Choosing just one sprinkler setting would answer a different conditional query. Observing wet ground makes the initially independent causes statistically coupled in general.
### Words to know
- **Directed acyclic graph:** Arrows connect nodes without a directed path returning to its start.
- **Conditional table:** A distribution for a node for every allowed parent assignment.
- **Variable elimination:** Multiply relevant factors and sum out hidden variables in stages.
### Let us work through it
**Does no edge mean independence?**
No; indirect paths and conditioning can create dependence.
**How many parameters for a binary root?**
One; the other probability is one minus it.
**Why sum hidden values?**
All unobserved alternatives can contribute to the observed evidence.
### Infer through a hidden cause
Network A→B has P(A=1)=0.4, P(B=1|A=1)=0.75, P(B=1|A=0)=0.25. Observe B=1.
**Choose the method**
Form two joint masses then normalize over A.
1. A=1 and B=1 has probability 0.4×0.75=0.3.
2. A=0 and B=1 has probability 0.6×0.25=0.15; evidence mass 0.45.
3. P(A=1|B=1)=0.3/0.45=2/3.
**Interpret the answer**
Posterior is 2/3, larger than prior 0.4 because B=1 favors A=1.
**Check the reasoning**
The complementary posterior is 0.15/0.45=1/3, so both sum to 1.
### Count a four-node network
All variables are binary. Graph has independent roots A,B; C has parent A; D has parents B,C. Count independent probability parameters versus an unrestricted joint.
**Choose the method**
Count parent assignments per node; one free probability per binary row.
1. Roots A and B each need 2⁰=1 parameter.
2. C has one binary parent and needs 2; D has two and needs 4.
3. Total 1+1+2+4=8; an unrestricted four-binary joint has 2⁴−1=15.
**Interpret the answer**
The network uses 8 parameters instead of 15 because it encodes independence restrictions.
**Check the reasoning**
Each conditional-table row sums to 1; counting both entries as independent would double-count.
### Leon's further thinking
**A collider can connect causes after observation**
For independent causes A→C←B, observing C can make evidence for A reduce the need for B to explain C. The dependence depends on the tables.
**Parameter savings use normalization**
For a binary node, each parent row has two probabilities but only one independent choice, because the second is 1 minus the first.
**Watch out:** An arrow is a dependency in a probability factorization. Interpreting it as an intervention-ready causal relationship requires additional assumptions and evidence.
Check your understanding
Why can elimination order change runtime without changing the exact answer?
The distributive law permits different summation orders, but the orders create intermediate factors of different sizes. Correct exact arithmetic gives the same marginal while memory and multiplication costs differ.
## K-means, representatives and vector quantization
### 01 / The story
A ceramics studio wants a small set of standard glaze colors to approximate thousands of observed samples. It assigns each sample to its nearest current standard, then moves each standard to the mean of its assigned samples. Repeating this can reduce approximation error. A standard need not equal an existing sample, just as a centroid need not be a data point.
If the studio must choose only available physical samples, a medoid is a different representative. The chosen distance also matters: numerical closeness in a color encoding need not perfectly match human perception, so a tidy mathematical cluster can still be unhelpful in practice.
### 02 / The principle
Lloyd’s k-means alternates assignment to the nearest centroid with updating each nonempty centroid to its cluster mean. Under squared Euclidean loss, each step cannot increase the objective, and standard finite-data implementations terminate at a locally stable partition subject to tie conventions.
Global optimality is not guaranteed; multiple starts and k-means++ initialization can help. Arithmetic means specifically minimize squared Euclidean distances: changing the distance generally requires changing the representative update. Scale features appropriately, handle empty clusters explicitly and examine sensitivity to outliers.
The number of clusters is a modeling choice, not necessarily a discovered natural truth. Centroids can form a codebook for vector quantization, replacing each input block with a centroid index. Storage savings require counting both indices and the codebook, and reconstruction becomes lossy.
### 03 / The formula, unpacked
```text
J = Σᵣ Σx∈Cᵣ ||x−μᵣ||²
μᵣ = (1/|Cᵣ|) Σx∈Cᵣ x
Naive iteration cost: O(nkd)
Fixed-length index bits per item = ceil(log₂k)
```
Cᵣ is cluster r and μᵣ its centroid, the coordinatewise mean of its members. J is within-cluster sum of squared errors, with smaller values preferred for a fixed k and dataset. Here n is number of points, k number of clusters and d feature dimension.
The centroid formula requires a nonempty cluster. A fixed-length code for k representatives needs the stated number of bits; total compressed size also includes representative values and any format overhead.
### 04 / A first worked example
For points 0, 2, 8 and 10, choose k=2 with initial centroids 0 and 8. Nearest-centroid assignment forms {0,2} and {8,10}; the updated means are 1 and 9. Assignments then stay unchanged. The objective is (0−1)²+(2−1)²+(8−9)²+(10−9)²=4. As a separate compression calculation, 100 four-byte blocks originally occupy 400 bytes.
A four-entry codebook occupies 16 bytes, and 100 two-bit indices occupy 25 bytes, totaling 41 bytes before headers. The result saves storage by restricting reconstruction to four representative blocks, so exact original recovery is generally impossible.
### Words to know
- **Centroid:** The coordinate-by-coordinate mean of a cluster.
- **SSE:** Sum of squared distances from points to their assigned representatives.
- **Codebook:** The stored collection of representatives indexed during reconstruction.
### Let us work through it
**Must a centroid be an observed point?**
No; a mean may lie between points.
**Does every run find the global optimum?**
No, initialization and ties can lead to different local results.
**What is needed for an empty cluster?**
An explicit policy, since its mean has denominator zero.
### One Lloyd iteration
Points 1,3,9,11; k=2; initial centers 1 and 9. Use squared Euclidean distance and assign to the nearer center.
**Choose the method**
Assign first, then compute means and the new objective.
1. Points 1,3 are nearer 1; points 9,11 are nearer 9.
2. New centers are(1+3)/2=2 and(9+11)/2=10.
3. New SSE=(1−2)²+(3−2)²+(9−10)²+(11−10)²=4.
**Interpret the answer**
Centers 2 and 10 give SSE 4 and unchanged assignments on the next pass.
**Check the reasoning**
Initial SSE=0+4+0+4=8, so the update decreases the objective.
### Count compressed storage
Encode 64 blocks, each originally 4 bytes, using 8 representative blocks of 4 bytes each. Use fixed-length indices and ignore headers.
**Choose the method**
Count original bytes, codebook bytes and packed index bits separately.
1. Original size=64×4=256 bytes.
2. Codebook=8×4=32 bytes; each index needs log₂8=3 bits.
3. Indices=64×3=192 bits=24 bytes; total=32+24=56 bytes.
**Interpret the answer**
Stored size 56 bytes, saving 200 bytes before headers, with generally lossy reconstruction.
**Check the reasoning**
32 bytes of representatives alone already exceed the 24-byte index stream, so omitting the codebook would seriously undercount.
### Trace two Lloyd steps
Check assignment, means and squared error on four one-dimensional points.
```python
points = [1, 3, 9, 11]
centers = [1, 9]
for step in range(2):
groups = [[], []]
for point in points:
distances = [abs(point - centers[0]), abs(point - centers[1])]
group_id = 0 if distances[0] <= distances[1] else 1
groups[group_id].append(point)
centers = [sum(group) / len(group) for group in groups]
error = 0
for group_id, group in enumerate(groups):
for point in group:
error += (point - centers[group_id]) ** 2
print(f"Step {step + 1}: centers={centers}, SSE={error:.1f}")
assert centers == [2.0, 10.0]
```
**Run it locally**
```sh
python kmeans-lloyd-two-clusters.py
```
**Expected output**
```text
Step 1: centers=[2.0, 10.0], SSE=4.0
Step 2: centers=[2.0, 10.0], SSE=4.0
```
**Follow the execution**
1. First assignment creates [1,3] and [9,11].
2. Their means 2 and 10 give four squared errors of 1, totaling 4.
3. The second assignment is unchanged, so both means and SSE stay fixed.
**Read the code step by step**
range(2) runs the outer loop twice, with step values 0 and 1. groups contains two empty lists. Index 0 means the first center and 1 the second. The conditional expression chooses the closer center; <= gives ties to the first. Absolute distance and squared distance give the same nearest ordering here. append places a point into its selected list.
The list comprehension computes one mean per group using sum divided by len. Both groups are nonempty in this example; a general implementation needs an empty-group rule. enumerate supplies both a list index and its group. The inner loop adds squared errors, with **2 meaning square. The printed second pass confirms stability on these data only; it does not certify a global optimum for arbitrary datasets.
### Leon's further thinking
**The mean matches squared loss**
For absolute distance in one dimension, a median minimizes the total instead. Do not change the distance while blindly keeping the mean update.
**Report codebook overhead**
For a very small dataset, storing representatives may cost more than the saved index bits. Count all parts before claiming compression.
**Watch out:** A decreasing k-means objective does not prove that the clusters correspond to meaningful real-world categories. Interpretation and stability need separate investigation.
Check your understanding
Why does comparing raw SSE across different k tend to favor larger k?
Adding centroids cannot worsen the best achievable SSE and can eventually give one centroid per point. Choose k using additional criteria, stability and the intended use, not SSE alone.
## Hierarchies, thresholds and cluster quality
### 01 / The story
A mapmaker groups villages first into neighboring pairs, then districts, then regions. A hierarchy preserves several levels of resolution, so the user chooses where to cut the tree. But “nearby groups” has several meanings. One short bridge can connect two long chains under single linkage; complete linkage instead checks their most distant cross-group pair.
A streaming grouping rule has another choice: a new village may join the cluster of its nearest already seen village if it lies within a threshold. That rule can depend on arrival order. Different algorithms answer different grouping questions, even when they use the same distance table.
### 02 / The principle
Agglomerative clustering starts with singleton clusters and repeatedly merges the closest pair under a linkage rule; divisive methods start together and split. A dendrogram records merge structure and heights, while a cut supplies an actual partition. Single linkage uses the smallest cross-cluster distance and can chain through bridge points.
Complete linkage uses the largest distance; average linkage averages all cross pairs. Centroid and medoid distances provide other definitions. An online nearest-neighbor threshold method assigns a point using previously seen neighbors or creates a new cluster; specify whether clusters can later merge and how ties are handled.
Evaluate cohesion and separation with measures such as silhouette or Davies–Bouldin, but internal scores favor particular geometries. Classical dense implementations store O(n²) distances; runtime depends on linkage and data structures rather than one universal bound.
### 03 / The formula, unpacked
```text
dsingle(A,B) = min{d(a,b): a∈A,b∈B}
dcomplete(A,B) = max{d(a,b): a∈A,b∈B}
s(i) = (b(i)−a(i))/max(a(i),b(i))
DB = (1/k)Σᵣ maxₛ≠ᵣ [(Sᵣ+Sₛ)/Mᵣₛ]
```
A and B are clusters. For silhouette, a(i) is point i’s mean distance to other members of its cluster and b(i) the smallest mean distance to another cluster; larger silhouette is usually better, with conventions for singletons.
In Davies–Bouldin, Sᵣ is within-cluster scatter and Mᵣₛ the distance between representatives; smaller DB is usually better. Specify scatter, representative and distance consistently, and handle coincident representatives because a zero denominator can make the score undefined.
### 04 / A first worked example
Consider one-dimensional clusters A={0,2} and B={5,9}. Their cross distances are 5, 9, 3 and 7. Single linkage gives 3, complete linkage 9 and average linkage 24/4=6. A threshold of 4 therefore permits their merge under single linkage but not complete linkage.
For point 2 in partition {0,2},{5,9}, within-cluster distance a=2 and mean distance to the other cluster b=(3+7)/2=5, so silhouette is (5−2)/5=0.6. With centroids 1 and 7, average absolute scatters are 1 and 2; for these two clusters DB=(1+2)/6=0.5. Every quantity uses the same one-dimensional Euclidean distance.
### Words to know
- **Linkage:** A rule converting point distances into a distance between clusters.
- **Dendrogram:** A tree recording cluster merges and their heights.
- **Silhouette:** A comparison of within-cluster distance with distance to the nearest other cluster.
### Let us work through it
**Which linkage uses the farthest pair?**
Complete linkage.
**What does negative silhouette suggest?**
The point is on average closer to another cluster than to its own.
**Does a hierarchy specify one unique partition?**
No; choose a cut height or cluster count.
### Three linkage answers
One-dimensional clusters A={1,3},B={6,8}. Use absolute distance. Compute single, complete and average linkage.
**Choose the method**
Enumerate every cross-cluster pair once.
1. Distances are|1−6|=5,|1−8|=7,|3−6|=3,|3−8|=5.
2. Minimum is 3 and maximum 7, giving single and complete linkage.
3. Average=(5+7+3+5)/4=20/4=5.
**Interpret the answer**
Single 3, complete 7, average 5; a threshold 4 merges only under single linkage.
**Check the reasoning**
The average 5 lies between minimum 3 and maximum 7.
### Compute one silhouette
Partition is A={0,2},B={8,10}. For point 2 use absolute distance and the standard non-singleton silhouette definition.
**Choose the method**
Average within and across groups before forming the ratio.
1. Only other own-cluster point is 0, so a=|2−0|=2.
2. Distances to B are 6 and 8, giving b=(6+8)/2=7.
3. s=(7−2)/max(2,7)=5/7≈0.714286.
**Interpret the answer**
The positive silhouette about 0.714 indicates this point is closer to its own cluster on average.
**Check the reasoning**
The result lies in [−1,1], and b>a explains the positive sign.
### Leon's further thinking
**Single linkage can connect by chains**
With points 0,2,4 and threshold 2, successive short links join all three although the endpoint distance is 4.
**Internal quality is conditional on the ruler**
Changing feature scale changes distances and can reverse score comparisons. Choose a meaningful representation before optimizing a score.
**Watch out:** Neither a dendrogram nor a self-organizing map automatically supplies one uniquely correct cluster count. A cut, threshold or interpretation is still needed.
Check your understanding
Why can a single outlying bridge point dramatically change single-link clustering?
Only the nearest cross-cluster pair controls each merge. A chain of individually short links can join groups whose endpoints are far apart.
## Continue exploring
- [Russell and Norvig — Artificial Intelligence: A Modern Approach](https://aima.cs.berkeley.edu/)
- [Berkeley AI textbook — Informed search](https://inst.eecs.berkeley.edu/~cs188/textbook/search/informed.html)
- [Berkeley AI textbook — Naive Bayes](https://inst.eecs.berkeley.edu/~cs188/textbook/ml/naive-bayes.html)
- [Berkeley AI textbook — Bayesian network representation](https://inst.eecs.berkeley.edu/~cs188/textbook/bayes-nets/representation.html)
- [Stanford CS231n — Backpropagation](https://cs231n.github.io/optimization-2/)
- [Stanford CS231n — Convolutional networks](https://cs231n.github.io/convolutional-networks/)
- [Goodfellow, Bengio and Courville — Autoencoders](https://www.deeplearningbook.org/contents/autoencoders.html)
- [scikit-learn official guide — Support vector machines](https://scikit-learn.org/stable/modules/svm.html)
- [scikit-learn official guide — Clustering](https://scikit-learn.org/stable/modules/clustering.html)
- [scikit-learn: Model evaluation and averaging classification metrics](https://scikit-learn.org/stable/modules/model_evaluation.html)
---
Leon