LWLeon.
Home/Learning/ COMP3308
LEON / COMP3308

Artificial Intelligence: Search, Reasoning & Learning

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.

24 TOPICS · EN + ZH · 6 RUNNABLE PROGRAMS · 51 WORKED PROBLEMS

Connected knowledge framework ↓Download English notes ↓Read the reference in this language ↗
LEON / LEARNING MAP

See the learning route first

Follow the arrows. Choose a stage to open its first lesson. The full framework lists every topic.

  1. 01

    Search and strategic decisions

    Define a state, compare exploration rules, then reason about competing or random moves.

    6 topics ↗
  2. 02

    Learning from labeled examples

    Start with understandable predictors and learn how to measure their performance honestly.

    7 topics ↗
  3. 03

    Neural representations and model families

    Build from one weighted decision to trainable networks, margins and combinations of models.

    7 topics ↗
  4. 04

    Uncertainty and unsupervised structure

    Keep probability accounting explicit, then explore structure when labels are absent.

    4 topics ↗
LEON / FROM IDEAS TO IMPLEMENTATION

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. 01

    Reopen a state when A* finds a better route

    Distinguish admissibility, consistency and reopening.

    Story · Code · Reasoning    Read the lesson: A* and trustworthy lower bounds
  2. 02

    Keep long-text likelihoods in log space

    Connect smoothing, repeated words and stable normalization.

    Story · Code · Reasoning    Read the lesson: Naive Bayes and smoothed likelihoods
  3. 03

    See which class disappears inside an average

    Calculate class reports before comparing averages.

    Story · Code · Reasoning    Read the lesson: Confusion matrices and error costs
Text size
New to Python or the maths? Start here ↗Download all Python examples ↓
Running Python for the first time? Follow four steps
  1. Install Python 3.12 or newer. Official Python downloads ↗
  2. Choose “Download Python” beside an example. The .py file contains the program as text.
  3. Open a terminal in the download folder. Run python filename.py, using the actual file name. Some systems use python3 instead. A terminal is a window where you type commands and read text results.
  4. Compare each result with “Expected output” on this page. Change one input and observe the difference.

Some examples use NumPy, a package for numbers and arrays. If the code contains import numpy as np, install NumPy once with the same Python: python -m pip install numpy. The import line loads NumPy and gives it the short name np. Official NumPy installation guide ↗

No dataset or model-weight downloads are needed. Examples run offline after Python and any required package are installed. You can copy the code from the page; its output appears in your terminal.

Prepare for the journey

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.

Before you start

  • Read simple Python or equivalent code
  • Basic algebra; key vector and logarithm notation is explained in context
  • A willingness to follow probability and local-rate calculations, with rules and values supplied in examples

What you will learn

  • Choose search strategies using their assumptions and resource costs
  • Trace game search and explain valid pruning
  • Train and assess baseline classifiers without data leakage
  • Compute neural and probabilistic updates
  • Compare clustering objectives and interpret their limitations

Connected knowledge framework

The stages show the learning order. Select any topic to read its story, method and examples.

01 / Search and strategic decisions

Model a problem, then choose a frontierA* and trustworthy lower boundsHill climbing, restarts and beam searchSimulated annealing and genetic searchMinimax and alpha–beta boundsCutoffs, chance nodes and multiple players

02 / Learning from labeled examples

Learning tasks and nearest neighbors1R: a useful one-feature baselineNaive Bayes and smoothed likelihoodsValidation, cross-validation and comparisonsConfusion matrices and error costsDecision trees, entropy and information gainGrow useful trees without memorizing noise

03 / Neural representations and model families

Perceptrons and linear decision boundariesMultilayer networks and backpropagationOptimization, initialization and regularizationAutoencoders and learned representationsConvolutions, pooling and shared featuresMargins, soft constraints and kernelsBagging, boosting and random forests

04 / Uncertainty and unsupervised structure

Joint distributions, conditioning and BayesBayesian networks and inferenceK-means, representatives and vector quantizationHierarchies, thresholds and cluster quality
COMP3308 / 01Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Why include a key in the state?

    It changes which doors can be opened.

  2. Why test UCS goals on removal?

    An earlier generated goal may be more expensive than another unfinished route.

  3. Is an expansion list a path?

    Usually not; use parent links to reconstruct one connected route.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 02Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. What is f when g=4,h=3?

    Seven: add paid and estimated remaining cost.

  2. Is zero heuristic admissible for nonnegative costs?

    Yes; A* then orders nodes like UCS.

  3. May two lower bounds be added?

    Not generally; they may count the same necessary work twice.

  4. 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.

Work through a problem · 01

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.

Work through a problem · 02

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.

Work through a problem · 03

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.

Run a complete example · 01

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 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python astar-heuristics-astar-reopen-states.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 04Leon

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.

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.

03 / The formula, unpacked

Δ = 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.

Let us work through it

  1. What if Δ is negative?

    The move improves a minimized objective and is accepted with probability 1.

  2. What does cooling change?

    It lowers acceptance probability for a fixed positive deterioration.

  3. Does crossover ensure valid children?

    No; representation and constraint handling must ensure validity.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 05Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Why does MIN take the smaller number?

    Numbers measure MAX’s utility, which the opponent seeks to reduce.

  2. Does a huge hidden leaf prevent pruning?

    Not if another MIN child already gives a low upper bound.

  3. Does move order change exact root value?

    No, but it changes how much work can be skipped.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 06Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Should a chance node choose its worst child?

    No; average using outcome probabilities unless the model specifies an adversary.

  2. What must probabilities sum to?

    One, after including all mutually exclusive outcomes.

  3. What does iterative deepening keep?

    The result of the last fully completed search depth.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 07Leon

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.

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.

03 / The formula, unpacked

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).

Let us work through it

  1. Why scale features?

    Units can otherwise dominate the distance without reflecting importance.

  2. What does k count?

    The selected nearest training examples.

  3. May a new scaled value exceed 1?

    Yes, if it exceeds the training maximum.

Work through a problem · 01

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.

Work through a problem · 02

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.

Run a complete example · 01

Find and average two neighbors

Reproduce the first worked problem with a sorted distance table.

Python 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python learning-neighbors-nearest-two-trace.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 08Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does 1R use exactly one branch?

    No, one attribute can have several values and branches.

  2. How many errors in a group with 4A,1B?

    One, when predicting the majority A.

  3. Can zero training error prove a good model?

    No, the rule may merely memorize unique identifiers.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 09Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Independent before or after knowing the class?

    The model assumes independence after conditioning on the class.

  2. Do scores already sum to 1?

    Usually not; divide each by the sum when posterior probabilities are needed.

  3. Why use logarithms?

    Products of tiny probabilities can underflow; logs turn products into sums.

  4. 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.

Work through a problem · 01

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.

Work through a problem · 02

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.

Work through a problem · 03

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.

Run a complete example · 01

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 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python naive-bayes-log-space-word-counts.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 10Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does stratification remove time leakage?

    No; it balances class proportions, not chronological order.

  2. Where should scaling be fitted in CV?

    Inside each fold’s training portion.

  3. Is the test set for tuning?

    No; using it for choices turns it into development data.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 11Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Which denominator measures recall?

    All actual positives: TP+FN.

  2. Does F1 use TN?

    No; adding true negatives alone does not change F1.

  3. Why name the positive class?

    Swapping class roles changes precision and recall.

  4. 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.

Work through a problem · 01

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.

Work through a problem · 02

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.

Work through a problem · 03

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.

Run a complete example · 01

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 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python classification-metrics-macro-micro-report.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 12Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Entropy of one certain class?

    Zero, since there is no class uncertainty.

  2. Why weight child entropies?

    Larger children contain more observations and should contribute more.

  3. Does greedy mean globally best tree?

    No, the best immediate split may not give the best complete tree.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 13Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Can the test set choose pruning?

    No; use validation evidence and preserve final testing.

  2. Why consider thresholds between distinct values?

    They change which examples fall on each side; splitting equal values inconsistently is invalid.

  3. What if SplitInfo=0?

    The ratio is undefined; the split sends all examples to one branch.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 14Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. What happens on a correct prediction?

    e=0, so this perceptron rule changes neither weights nor bias.

  2. Must learning find the widest margin?

    No, ordinary perceptron only seeks a separator.

  3. What does a score of zero predict here?

    Class 1 because the threshold is z≥0.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 15Leon

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.

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.

03 / The formula, unpacked

σ(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.

Let us work through it

  1. Why save the forward activations?

    Local derivative formulas use them during the backward pass.

  2. Does a hidden unit have the original label as its target?

    Usually no; it receives sensitivity through downstream connections.

  3. Why add nonlinear activations?

    Otherwise stacked affine layers still describe one affine transformation.

Work through a problem · 01

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.

Work through a problem · 02

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.

Run a complete example · 01

Check one sigmoid update

Follow the first worked problem using only the standard math module.

Python 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python backpropagation-sigmoid-one-update.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 16Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does every gradient step reduce loss?

    No, too large a learning rate can overshoot.

  2. What does dropout preserve in expectation?

    The activation value under the inverted scaling convention.

  3. Which checkpoint should early stopping retain?

    The best according to the declared validation criterion.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 17Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Are class labels required?

    No; ordinary reconstruction uses the input as its target.

  2. Does one latent number define a fixed bitrate?

    No; storage precision and encoding must also be specified.

  3. Does large error prove anomaly?

    No; the threshold and task require validation.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 18Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does a filter see all input channels?

    In an ordinary dense convolution, yes; it sums their contributions into one output channel.

  2. Does doubling image width double parameters?

    No; the same filter is reused, though computation increases.

  3. What does ReLU do to −3?

    It outputs max(0,−3)=0.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 19Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. What labels does this SVM formula use?

    −1 and+1, unlike the earlier 0/1 perceptron convention.

  2. What does increasing C favor?

    Fewer margin violations relative to keeping the weight norm small.

  3. Is every similarity a valid kernel?

    No; the required inner-product structure must hold.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 20Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does more models guarantee improvement?

    No, identical or poor errors may persist.

  2. What error does AdaBoost use?

    The current example-weighted error, not necessarily ordinary error rate.

  3. Why normalize example weights?

    They must form a distribution summing to 1 for the stated weighted-error formula.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 21Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Why divide by evidence probability?

    It rescales the retained cases so their probabilities sum to 1.

  2. Can we condition on zero-probability evidence using this formula?

    No; the denominator is zero.

  3. Does a strong likelihood remove the prior?

    No; posterior reasoning still multiplies by the prior.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 22Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Does no edge mean independence?

    No; indirect paths and conditioning can create dependence.

  2. How many parameters for a binary root?

    One; the other probability is one minus it.

  3. Why sum hidden values?

    All unobserved alternatives can contribute to the observed evidence.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework
COMP3308 / 23Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Must a centroid be an observed point?

    No; a mean may lie between points.

  2. Does every run find the global optimum?

    No, initialization and ties can lead to different local results.

  3. What is needed for an empty cluster?

    An explicit policy, since its mean has denominator zero.

Work through a problem · 01

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.

Work through a problem · 02

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.

Run a complete example · 01

Trace two Lloyd steps

Check assignment, means and squared error on four one-dimensional points.

Python 3Download source ↓

Scroll sideways for long lines. Copy or download keeps the original code.

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
python kmeans-lloyd-two-clusters.py

Expected output

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.

↑ Back to the knowledge framework
COMP3308 / 24Leon

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.

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.

03 / The formula, unpacked

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.

Let us work through it

  1. Which linkage uses the farthest pair?

    Complete linkage.

  2. What does negative silhouette suggest?

    The point is on average closer to another cluster than to its own.

  3. Does a hierarchy specify one unique partition?

    No; choose a cut height or cluster count.

Work through a problem · 01

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.

Work through a problem · 02

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.

↑ Back to the knowledge framework

Continue exploring

Original stories, explanations and worked problems by Leon. Course codes identify independent study paths. The linked references belong to their authors.