Guided problem set — the whole midterm

Not “how many things are in the world”. The question is: which variables does this particular search problem read? A variable belongs in the state if and only if the goal test, the action set $\text{Actions}(s)$, the transition model $\text{Result}(s,a)$, or the cost function $c(s,a,s')$ consults it — or if it changes in a way that later affects one of those.

So run a four-way relevance test on each of $p$ (position), the $f_i$, $d$ (facing), $\beta$ (battery), once per task.

(a) The full world state keeps everything: $(p, f_1,\dots,f_5, d, \beta)$, size

$$48 \cdot 2^5 \cdot 4 \cdot 21 = 48 \cdot 32 \cdot 4 \cdot 21 = \mathbf{129{,}024}.$$

(b) The goal test reads only $p$. Moves are N/S/E/W regardless of facing, so $\text{Actions}$ does not read $d$. Cost is 1 per move, so $c$ reads nothing. Parcels are never read. Battery is ignored by assumption.

State $= (p)$, size $\mathbf{48}$.

Note how brutal that is: $129{,}024 \to 48$, a factor of 2688, purely by deleting variables nobody reads.

(c) The goal test now reads all five $f_i$ (“are they all delivered?”), and the $f_i$ change as we act, so they stay. $d$ and $\beta$ are still unread.

$$\text{State} = (p, f_1,\dots,f_5), \qquad 48 \cdot 2^5 = \mathbf{1{,}536}.$$

(d) Now “without the battery hitting 0” makes $\beta$ part of the legality of a plan, and $\beta$ changes with every move, so the transition model reads and writes it. It's in.

$$\text{State} = (p, f_1,\dots,f_5, \beta), \qquad 48 \cdot 32 \cdot 21 = \mathbf{32{,}256}.$$

$d$ is still out in every task, because nothing — goal, actions, transitions, costs — ever consults it.

Task	Representation	Size
(a) world state	$(p, f_1..f_5, d, \beta)$	$48\cdot 32\cdot 4\cdot 21 = 129{,}024$
(b) reach dock	$(p)$	$48$
(c) deliver all	$(p, f_1..f_5)$	$48\cdot 32 = 1{,}536$
(d) deliver all, battery	$(p, f_1..f_5, \beta)$	$48\cdot 32\cdot 21 = 32{,}256$

The trap is the facing variable $d$. It is listed prominently in the problem, it is part of the world, and it is irrelevant to every single task — so every product you write that contains a $4$ is wrong. The exam always plants at least one decoy variable, and it usually plants it in a task where a small rule change would make it relevant (if actions were “turn left / go straight”, $d$ would be back in, through $\text{Actions}$, not through the goal test).

Second trap: $2^5$, not $5$ and not $5!$. The state is a snapshot, not a history. Five independent bits give $2^5$ configurations; the order of delivery lives in the plan, not the state.

Three questions in one, and they differ in exactly one line of code: what the frontier is.

• BFS — frontier is a FIFO queue. Pop order is by depth (number of edges), ignoring cost entirely.
• DFS — frontier is a LIFO stack. To pop alphabetically-first, you push successors in reverse alphabetical order.
• UCS — frontier is a priority queue keyed on $g(n)$, the cumulative cost from $S$. Pop order is by cost.

The adjacency lists, alphabetised:
$S\!:\!A,B$  ·  $A\!:\!C,D,S$  ·  $B\!:\!D,E,S$  ·  $C\!:\!A,D,G$  ·  $D\!:\!A,B,C,G$  ·  $E\!:\!B,G$  ·  $G\!:\!C,D,E$.

Pop $S$; enqueue $A,B$. Pop $A$; enqueue $C,D$ ($S$ already expanded). Pop $B$; $D$ is already queued, enqueue $E$. Pop $C$; enqueue $G$. Pop $D$ — nothing new. Pop $E$ — nothing new. Pop $G$: goal.

Pop order: $S, A, B, C, D, E, G$.

Returned path: $S \to A \to C \to G$, found at depth 3. Cost $= 1 + 2 + 8 = \mathbf{11}$.

BFS found a shallow path, not a cheap one.

Push $S$. Pop $S$, push $B,A$ (reverse alphabetical, so $A$ is on top). Pop $A$, push $D,C$ → pop $C$, push $G,D$ → pop $D$ (top of stack), push $G,C,B,A$ → after skipping expanded states, pop $B$, push $E$ → pop $E$, push $G$ → pop $G$: goal.

Pop order: $S, A, C, D, B, E, G$.

Returned path: $S \to A \to C \to D \to B \to E \to G$, cost $= 1+2+1+1+7+2 = \mathbf{14}$.

DFS returned the worst of the three. That is normal, and it is not a bug: DFS promises nothing about quality.

Track $g$ as you go. Pop $S$ ($g{=}0$); frontier $A{:}1$, $B{:}4$. Pop $A$ ($g{=}1$); add $C{:}3$, $D{:}6$ (via $A$). Pop $C$ ($g{=}3$); $D$ via $C$ is $3+1 = 4 < 6$, so replace the frontier entry for $D$ with $g{=}4$; add $G{:}11$ (via $C$). Now the frontier holds $B{:}4$, $D{:}4$, $G{:}11$ — a tie at 4, broken alphabetically, so pop $B$ ($g{=}4$); $D$ via $B$ would be $4+1=5$, worse than 4, discard. Pop $D$ ($g{=}4$); $G$ via $D$ is $4+3 = 7 < 11$, replace. Pop $G$ ($g{=}7$): goal.

Pop order (with $g$): $S(0),\ A(1),\ C(3),\ B(4),\ D(4),\ G(7)$ — note $E$ is never expanded.

Returned path: $S \to A \to C \to D \to G$, cost $= 1+2+1+3 = \mathbf{7}$.

UCS expanded the fewest nodes (6 of 7) and returned the only optimal path.

Trap 1 — “BFS finds the shortest path.” BFS finds the path with the fewest edges. Here that is the 3-edge, cost-11 route; the optimal route has 4 edges and costs 7. BFS is optimal only when every step cost is equal.

Trap 2 — the frontier replacement at $D$. The single most-missed line in UCS: when a cheaper path to a state already on the frontier is found, you replace the entry rather than adding a second one or ignoring it. Miss it and you return $S\to B\to D\to G$ at cost 8.

Trap 3 — goal test on pop, not on generation. $G$ was generated with $g{=}11$ while $C$ was expanded. If you had returned then, you'd answer 11. UCS only commits when $G$ reaches the front of the queue, by which point its $g$ has been improved to 7.

Pin the definitions down before arguing. Complete: if a solution exists, the algorithm is guaranteed to find one in finite time. Optimal: the solution it returns has minimum total cost. These are different properties and a given algorithm can have one without the other — DFS-with-a-visited-set on a finite graph is complete but not optimal.

Note also that “complete” is a property of the algorithm + graph class pair, not of the algorithm alone. That is why (a) has two different answers.

(a) On the Problem 2 graph: yes, complete. The graph is finite (7 states) and we are running graph search with an explored set, so no state is expanded twice; the search must terminate, and it terminates having touched every reachable state, so if $G$ is reachable it is found.

In general: no. Two ways it fails. (i) Tree search on a cyclic graph: with no explored set, DFS can loop $S \to A \to S \to A \to \cdots$ forever. (ii) Infinite state spaces: even acyclic, DFS can march down an infinite branch (“keep adding 1 to the counter”) and never come back, even though the goal sits one step off the root.

(b) No. The counterexample is already in Problem 2: BFS returns $S\to A\to C\to G$ at cost 11, but the optimum is 7. The minimal counterexample is three nodes — $S\to G$ costing 10, and $S\to A$ costing 1 with $A \to G$ costing 1. BFS finds the 1-edge path of cost 10 and stops; the optimum is the 2-edge path of cost 2.

Zero-cost edges. Optimality survives — the proof of UCS optimality only needs $g$ to be non-decreasing along a path, which $c \ge 0$ gives you. What dies is the completeness guarantee in an infinite space: with a positive lower bound $\varepsilon$ on step cost, every cost contour contains finitely many nodes, so UCS eventually pushes past any finite cost. With cost-0 edges you can build an infinite zero-cost chain out of $S$ and UCS will expand it forever, never reaching the cost-1 contour that contains the goal. On a finite graph, zero costs are harmless.

Negative-cost edges. Now optimality dies outright. UCS assumes that once a state is popped, its $g$ can never improve — that is exactly why we are allowed to mark it explored and never reconsider it. A negative edge discovered later can lower the true cost of an already-expanded state, and UCS will never notice. (This is why you need Bellman–Ford, not Dijkstra/UCS, for negative weights. beyond syllabus)

(d) With all costs $1$, $g(n)$ equals the depth of $n$, so the priority queue orders by depth — which is exactly what the FIFO queue does, provided ties are broken in insertion order. So UCS and BFS expand in the same order and both return a minimum-depth path, which is now also a minimum-cost path. This is the precise sense in which BFS is the special case of UCS with unit costs, and the mirror of the fact that UCS is the special case of A* with $h \equiv 0$.

Summary table:

	Complete?	Optimal?
DFS (graph search, finite space)	yes	no
DFS (tree search, cycles / infinite)	no	no
BFS (finite branching)	yes	only if all costs equal
UCS ($c \ge \varepsilon > 0$)	yes	yes

The trap is memorising the table instead of the reason. Every row above has a condition attached, and the exam question is always built by deleting the condition: “DFS is incomplete” (only without an explored set, or in an infinite space), “BFS is optimal” (only for unit costs), “UCS is optimal” (only for non-negative costs). If you can produce the three-node counterexample for BFS in ten seconds, you have actually learned it; if you can only recite the row, you haven't.

Part (c) is the one people lose points on, because zero and negative break different properties — zero breaks completeness in infinite spaces, negative breaks optimality everywhere.

An A* trace is bookkeeping, not cleverness. Keep three columns and never mix them up:

• $g(n)$ — backward cost: what the path you actually took to $n$ has cost so far. A fact.
• $h(n)$ — forward estimate: guessed remaining cost from $n$ to a goal. Given to you, never computed.
• $f(n) = g(n) + h(n)$ — estimated total cost of the cheapest solution through $n$. This is the priority.

“Graph search” means: keep an explored set; never expand a state twice; if a cheaper path to a frontier state appears, replace the entry.

Insert $S$ with $g{=}0$, $h{=}5$, $f{=}5$.

Pop 1: $S$ — $g{=}0, h{=}5, f{=}5$. Generate $A$ ($g{=}2$, $f{=}2{+}4{=}6$) and $B$ ($g{=}1$, $f{=}1{+}4{=}5$).

Frontier: $B(f{=}5)$, $A(f{=}6)$.

Pop 2: $B$ — $g{=}1, h{=}4, f{=}5$. Generate $C$ ($g{=}1{+}2{=}3$, $f{=}3{+}3{=}6$) and $D$ ($g{=}1{+}2{=}3$, $f{=}6$).

Frontier: $A(6)$, $C(6)$, $D(6)$ — a three-way tie.

Alphabetical tie-break: Pop 3: $A$ — $g{=}2, h{=}4, f{=}6$.

$A$ generates $C$ with $g = 2+2 = 4$. But $C$ is already on the frontier with $g = 3$. Since $4 > 3$, discard — do not add a second $C$.

$A$ also generates $D$ with $g = 2+5 = 7$, worse than the existing $g{=}3$. Discard.

So expanding $A$ changed nothing at all. That is A* correctly refusing to be tempted: $A$ looked as promising as $C$ and $D$ on $f$, and turned out to be a dead weight.

Pop 4: $C$ — $g{=}3, h{=}3, f{=}6$. Generates $G$ with $g = 3+4 = 7$, $f = 7+0 = 7$.

Pop 5: $D$ — $g{=}3, h{=}3, f{=}6$. Generates $G$ with $g = 3+4 = 7$ — a tie, so nothing improves.

Pop 6: $G$ — $g{=}7, h{=}0, f{=}7$. Goal test fires.

#	Popped	$g$	$h$	$f$	Path to it
1	S	0	5	5	S
2	B	1	4	5	S→B
3	A	2	4	6	S→A
4	C	3	3	6	S→B→C
5	D	3	3	6	S→B→D
6	G	7	0	7	S→B→C→G

Returned path: $S \to B \to C \to G$, cost $= 1 + 2 + 4 = \mathbf{7}$.

Sanity check: $f$ never decreased along the pop sequence ($5,5,6,6,6,7$). That monotonicity is the fingerprint of a consistent heuristic — and this $h$ is consistent (check every edge: $h(n) - h(n') \le c$ holds for all eight).

The trap is pop 3. $A$ gets expanded even though it contributes nothing to the answer, because its $f$ ties with the useful nodes. Students who “shortcut” by only following the eventual solution path report five pops and miss $A$ and $D$. A* expands every node with $f < f^*$ and some of those with $f = f^*$; it does not magically know which ones matter.

Second trap: the two $g$-values for $C$ (3 via $B$, 4 via $A$). The exam wants to see you keep the smaller one and discard the larger. Writing $C$ twice in your table with two different $g$'s is the classic tree-search-in-graph-search-clothing error.

Third trap: $G$ is generated at pop 4 but not returned until pop 6. Goal test on pop.

Two different tests that students routinely merge into one.

Consistency implies admissibility, never the reverse. So (b) can fail while (a) passes — that is exactly what this problem is built to show.

Compute $h^*$ backwards from the goal:

• $h^*(G) = 0$.
• $h^*(C) = 3$ (only edge $C\to G$).
• $h^*(A) = 1 + h^*(C) = 4$.
• $h^*(S) = \min\{\,1 + h^*(A),\ 3 + h^*(C)\,\} = \min\{5, 6\} = 5$.

$n$	$h(n)$	$h^*(n)$	$h \le h^*$?
S	2	5	yes
A	4	4	yes (tight)
C	1	3	yes
G	0	0	yes

$h$ is admissible.

Test $h(n) - h(n') \le c(n,n')$ on all four edges:

Edge	$c$	$h(n) - h(n')$	OK?
$S \to A$	1	$2 - 4 = -2$	yes
$S \to C$	3	$2 - 1 = 1$	yes
$A \to C$	1	$4 - 1 = 3$	NO
$C \to G$	3	$1 - 0 = 1$	yes

The violating edge is $A \to C$. The failing inequality, written out:

$$h(A) \le c(A,C) + h(C) \quad\Longrightarrow\quad 4 \le 1 + 1 = 2 \quad \text{FALSE}.$$

Intuitively: standing at $A$ the heuristic claims 4 units of work remain; one cheap step later, at $C$, it claims only 1 remains. The heuristic “discovered” 3 units of progress from a step that cost 1. That drop is what consistency forbids.

Insert $S$: $g{=}0,h{=}2,f{=}2$.

Pop $S$ ($f{=}2$). Generate $A$ ($g{=}1$, $f{=}1{+}4{=}5$) and $C$ ($g{=}3$, $f{=}3{+}1{=}4$).

Pop $C$ ($g{=}3, h{=}1, f{=}4$) — it beat $A$ on $f$. Mark $C$ explored. Generate $G$ ($g{=}6$, $f{=}6$).

Pop $A$ ($g{=}1, h{=}4, f{=}5$). $A$ offers $C$ at $g = 1+1 = 2$, which is better than the 3 we used — but $C$ is already in the explored set, so graph search throws it away. There is no frontier entry left to replace.

Pop $G$ ($g{=}6, f{=}6$). Return $S \to C \to G$ at cost $\mathbf{6}$.

The true optimum is $S \to A \to C \to G$ at cost $1 + 1 + 3 = \mathbf{5}$. A* graph search returned a suboptimal path.

(a) Admissible — every $h(n) \le h^*(n)$, tight at $A$.

(b) Not consistent. Violating edge $A \to C$: $h(A) = 4 > c(A,C) + h(C) = 1 + 1 = 2$.

(c) A* graph search returns $S\to C\to G$, cost 6; the optimum is $S\to A\to C\to G$, cost 5. A* tree search on the same graph would still return the optimum (it would regenerate $C$ via $A$ and win), which is exactly the theorem: admissible ⇒ A* tree search optimal; consistent ⇒ A* graph search optimal.

Diagnostic you can use on any trace: with a consistent $h$, the $f$-values of popped nodes are non-decreasing. Here they went $2, 4, 5, 6$ — non-decreasing by luck — but the underlying $f$ along the optimal path $S(2), A(5), C(3), G(5)$ drops from 5 to 3. That drop is the inconsistency made visible.

The trap is believing admissible is enough. It is enough for tree search only. This problem is the smallest possible graph where the distinction bites, and it is the exact structure the lecture used: a node ($C$) reachable two ways, expanded early via the expensive route because its heuristic under-promised, then locked out of correction by the explored set.

The examinable phrase is “exhibit the violating edge”. Saying “it's inconsistent” earns nothing; naming $A\to C$ and writing $4 > 1 + 1$ earns everything. Also note that consistency is checked on edges — there are only four to check here, and checking nodes instead is the standard wrong move.

The recipe the course gives for inventing admissible heuristics is: solve a relaxed problem exactly. A relaxation is the same problem with extra actions allowed (or constraints deleted). Because every legal plan in the original is still legal in the relaxation, the relaxed optimum can only be cheaper — which is precisely $h(n) \le h^*(n)$.

So for each candidate you must name the relaxation it is the exact solution to. If you can't name one, it probably isn't admissible.

It is not just Pacman's position. The goal test reads which dots are eaten, and that changes as he moves, so it's part of the state:

$$\text{State} = (p,\ e_1, e_2, e_3), \quad p \in \{25 \text{ cells}\} \setminus \{3 \text{ walls}\},\ e_i \in \{0,1\}.$$

Size $= 22 \cdot 2^3 = \mathbf{176}$. Tiny, but the same construction with 30 dots is the $2^{30}$ blow-up from Chapter 1.

Manhattan distance from $(1,1)$, ignoring walls:

• to $(3,1)$: $|1-3| + |1-1| = 2$;
• to $(1,4)$: $|1-1| + |1-4| = 3$;
• to $(4,4)$: $|1-4| + |1-4| = 3 + 3 = 6$.

So $h_{\text{count}} = \mathbf{3}$, $h_{\max} = \max(2,3,6) = \mathbf{6}$, $h_{\text{sum}} = 2+3+6 = \mathbf{11}$.

$h_{\text{count}}$ is admissible. Relaxation: allow Pacman to teleport to any cell for free; he still must step onto each remaining dot, and each such step costs 1. The optimal cost of that relaxed problem is exactly the number of dots left. Formally, every real plan that eats $k$ dots contains at least $k$ moves (each dot is eaten by entering its cell), so $h^* \ge k = h_{\text{count}}$. ∎

$h_{\max}$ is admissible. Relaxation: delete the walls (so movement is free Manhattan movement) and require only that the single farthest dot be eaten, ignoring the others. Any real plan must at some point reach that dot, and reaching it costs at least its Manhattan distance (each move changes the Manhattan distance by at most 1, and walls only ever make it worse). So $h^* \ge \max_d \text{Manhattan}(p,d) = h_{\max}$. ∎

$h_{\text{sum}}$ is not admissible. It double-counts shared travel. Counterexample right here: ignore walls for a moment and compute the true cost of the wall-free version of this very problem. The best visiting order is $(1,1) \to (3,1) \to (4,4) \to (1,4)$, costing $2 + 4 + 3 = 9$. All six orders:

Order	Cost
(3,1), (4,4), (1,4)	9
(1,4), (4,4), (3,1)	10
(3,1), (1,4), (4,4)	10
(1,4), (3,1), (4,4)	12
(4,4), (1,4), (3,1)	14
(4,4), (3,1), (1,4)	15

So even with no walls at all, $h^*(\text{start}) \le 9$ in the relaxed world, while $h_{\text{sum}} = 11 > 9$. An overestimate — inadmissible, and A* using it can return a suboptimal plan.

(a) $(p, e_1,e_2,e_3)$, size $22 \cdot 8 = 176$.

(b) $h_{\text{count}} = 3$, $h_{\max} = 6$, $h_{\text{sum}} = 11$.

(c) $h_{\text{count}}$ and $h_{\max}$ admissible (relaxations: free teleportation / no walls and only one dot required). $h_{\text{sum}}$ inadmissible — it reports 11 where the true cost is at most 9.

(d) Use $h_{\max}$, or better, $h(n) = \max\!\big(h_{\text{count}}(n),\, h_{\max}(n)\big)$.

The trap is $h_{\text{sum}}$. It is the most natural thing to write, it is bigger (so it feels better), and it is wrong for a reason that has nothing to do with walls: the three trips share road. Any heuristic that adds up costs of sub-goals that can be achieved on the way to each other overestimates. The exam almost always offers a sum as a distractor next to a max.

Second trap: “prove it admissible” means name the relaxation and show every real plan costs at least this much. “It looks small” is not a proof. Third trap: forgetting that the dot-bits belong in the state — an $h$ that depends only on position cannot be right for a multi-dot problem, because two states with the same position and different dots need different estimates.

Two things, and the second is the one people forget. The minimax value is a number — the utility MAX can guarantee against an optimal opponent. The answer to the game is an action — which child of the root achieves that value.

You evaluate strictly bottom-up: every node's value is determined by its children, so you can never start at the root.

Four MAX nodes, each taking the max of its two leaves:

• $a = \max(5, 2) = 5$
• $b = \max(9, 3) = 9$
• $c = \max(4, 8) = 8$
• $d = \max(6, 1) = 6$

• Left MIN $= \min(a, b) = \min(5, 9) = 5$
• Right MIN $= \min(c, d) = \min(8, 6) = 6$

Root $= \max(5, 6) = 6$.

Minimax value of the root: 6. MAX should play Right.

The full annotated tree: leaves $5,2\,|\,9,3\,|\,4,8\,|\,6,1$ → MAX layer $5, 9, 8, 6$ → MIN layer $5, 6$ → root $6$.

Read the guarantee out loud: “If I play Right, then whatever MIN does, I end up at either $c=8$ or $d=6$; MIN will send me to $d$; from $d$ I take 6.” The 9 down the Left branch is unreachable against a competent opponent — MIN simply steers to $a=5$ instead.

Trap 1 — the biggest leaf is a lie. The largest utility in the tree is 9, sitting under Left. Left is the wrong move. Minimax value is never “the best thing that could happen”; it is the best thing MAX can force.

Trap 2 — answering with a number when an action was asked for. The notes say this explicitly: “the number 4 isn't quite the answer we are looking for at the root… we need to select an action.” Write both: value 6, action Right.

Trap 3 — the layer alternation. With three plies, the layer directly above the leaves is MAX again, not MIN. Mislabel it and you get root $= \max(\min(5,2\,{\to}\,2), \ldots)$ and a confidently wrong answer. Count plies from the root downward before you start.

Write the two rules down before you touch a number.

def max-value(state, α, β):          def min-value(state, α, β):
    v = -∞                               v = +∞
    for each successor:                  for each successor:
        v = max(v, value(succ, α, β))        v = min(v, value(succ, α, β))
        if v ≥ β: return v   # prune        if v ≤ α: return v   # prune
        α = max(α, v)                        β = min(β, v)
    return v                             return v

Read the prune conditions in words. At a MIN node, if the value I can already force is $\le \alpha$, then MAX — who already has an option worth $\alpha$ somewhere above me — will never route the game through me, so my remaining children are irrelevant. At a MAX node, symmetric with $\beta$.

Crucially: $\alpha$ and $\beta$ are passed down, and only $v$ comes back up. A sibling's $\alpha$ update reaches the next sibling through the parent, not sideways.

Root is MAX, called with $\alpha = -\infty$, $\beta = +\infty$. It calls MIN$_1$ with the same $(\alpha,\beta)$.

Step	$v$	$\alpha$	$\beta$	Prune?
MIN$_1$ sees 8	8	$-\infty$	$8$	$8 \le -\infty$? no
MIN$_1$ sees 5	5	$-\infty$	$5$	$5 \le -\infty$? no
MIN$_1$ sees 12	5	$-\infty$	$5$	—

MIN$_1$ returns 5. No pruning here: with $\alpha = -\infty$ nothing can ever satisfy $v \le \alpha$. The first branch is always fully explored.

Back at the root: $v = 5$, so $\alpha \leftarrow \max(-\infty, 5) = \mathbf{5}$.

Root calls MIN$_2$ with $\alpha = 5$, $\beta = +\infty$.

MIN$_2$ sees leaf $3$: $v = 3$. Check $v \le \alpha$: $3 \le 5$ — true. Return immediately.

Pruned: the leaves 10 and 2.

Why this is safe: MIN$_2$'s value is now known to be $\le 3$ (MIN can only go down from here). The root already has an option worth 5. Whatever 10 and 2 turn out to be, this branch can never beat 5, so their exact values cannot change the root.

Back at the root: $v = \max(5, 3) = 5$; $\alpha$ stays $5$.

Root calls MIN$_3$ with $\alpha = 5$, $\beta = +\infty$.

Step	$v$	$\alpha$	$\beta$	Prune?
MIN$_3$ sees 7	7	5	7	$7 \le 5$? no
MIN$_3$ sees 4	4	5	7	$4 \le 5$? yes

Pruned: the leaf 9. MIN$_3$ returns 4.

Root: $v = \max(5, 4) = \mathbf{5}$.

(i) Root minimax value $= \mathbf{5}$; best action $=$ Left.

(ii) α/β in force on entry to each node:

Node	α on entry	β on entry	Value returned
Root (MAX)	$-\infty$	$+\infty$	5
MIN$_1$ (Left)	$-\infty$	$+\infty$	5 (exact)
MIN$_2$ (Centre)	5	$+\infty$	3 (an upper bound, not the true value 2)
MIN$_3$ (Right)	5	$+\infty$	4 (exact, by luck)

(iii) Pruned leaves: 10 and 2 (Centre branch, children 2 and 3) and 9 (Right branch, child 3). Three of nine leaves never evaluated.

Check against full minimax: $\min(8,5,12)=5$, $\min(3,10,2)=2$, $\min(7,4,9)=4$, root $=\max(5,2,4)=5$. Same root value. α-β never changes the root — that is the theorem — even though it reported 3 instead of 2 for the Centre branch.

Trap 1 — “MIN$_2$ returns 2.” No: it returns 3, because it stopped. The values α-β reports for pruned subtrees are bounds, not minimax values. Only the root is guaranteed exact. Exams love asking “what value does node X return?” about a pruned node.

Trap 2 — pruning the first branch. Impossible: $\alpha = -\infty$ on entry. If your answer prunes anything in the leftmost subtree, you have made an arithmetic slip.

Trap 3 — counting one pruned leaf when the condition fires early. When MIN$_2$ returns at its first child, all remaining children are pruned — here two of them, plus their entire subtrees in a deeper tree. Mark them all.

Trap 4 — "order doesn't matter". It does. Had the Centre branch been ordered $2, 10, 3$, MIN$_2$ would still prune after one leaf. Had Left been ordered $12, 8, 5$, nothing changes for Left but α would still end at 5. With perfect ordering, time drops from $O(b^m)$ to $O(b^{m/2})$ — doubling the depth you can search. The root value never changes; only the work does.

Three node types, three rules:

$$V_{\text{MAX}}(s) = \max_{a} V(s'), \qquad V_{\text{MIN}}(s) = \min_{a} V(s'), \qquad V_{\text{CHANCE}}(s) = \sum_{s'} P(s')\,V(s').$$

Every symbol: $s$ is the current state, $s'$ ranges over its children, $P(s')$ is the probability the chance event produces $s'$ (these sum to 1 at each chance node), $V$ is the value from MAX's point of view.

Still strictly bottom-up: MIN layer first, then the expectations, then the root.

• Left, outcome 1: $\min(10, 4) = 4$  ·  Left, outcome 2: $\min(8, 12) = 8$
• Centre, outcome 1: $\min(16, 14) = 14$  ·  Centre, outcome 2: $\min(2, 9) = 2$
• Right, outcome 1: $\min(20, 18) = 18$  ·  Right, outcome 2: $\min(6, 2) = 2$

Left: $0.5 \times 4 + 0.5 \times 8 = 2 + 4 = \mathbf{6.0}$

Centre: $0.25 \times 14 + 0.75 \times 2 = 3.5 + 1.5 = \mathbf{5.0}$

Right: $0.2 \times 18 + 0.8 \times 2 = 3.6 + 1.6 = \mathbf{5.2}$

Check each set of probabilities sums to 1 before you multiply: $0.5{+}0.5$, $0.25{+}0.75$, $0.2{+}0.8$. All good.

Root $= \max(6.0,\ 5.0,\ 5.2) = \mathbf{6.0}$; MAX should play Left.

Action	MIN children	Expectation	Worst case	Best case
Left	4, 8	6.0	4	8
Centre	14, 2	5.0	2	14
Right	18, 2	5.2	2	18

Two things worth staring at. Right contains the leaf $20$, the largest number anywhere in the tree, and Right is not chosen — a 20% chance of a great outcome does not beat a reliable 6. And Left also happens to be the best worst case (4 vs 2 vs 2), so here expectimax and minimax agree on the action — but they agree by coincidence, not by principle.

Trap 1 — treating the chance node like a MIN node. If you replace the expectations with minima you get $\min(4,8)=4$, $\min(14,2)=2$, $\min(18,2)=2$ and root $4$ via Left. Right answer, wrong reasoning, and on a tree with different numbers it would be the wrong action too. The whole point of expectimax is that pessimism about a dice roll is not caution, it's a modelling error.

Trap 2 — forgetting the weights. Averaging $18$ and $2$ to $10$ instead of weighting $0.2/0.8$ to get $5.2$ makes Right the winner. Write $P$ next to every branch before you compute.

Trap 3 — thinking α-β applies. With unbounded leaf values you cannot prune at a chance node: one unseen child can swing the average arbitrarily, so no bound is available from the children seen so far. (If leaf values are bounded, limited pruning becomes possible. beyond syllabus)

Trap 4 — “expectimax value 6 means I'll score 6.” No outcome in the tree equals 6; you get 4 or 8. Expected values are properties of the decision, not of any single play.

A CSP formulation is exactly three lists. Nothing else counts.

The skill being tested: choosing variables so that the constraints come out binary (each touching at most two variables), because every algorithm in this unit — forward checking, arc consistency, AC-3 — is defined on binary constraints and a binary constraint graph.

The natural choice: one variable per seminar, whose value is its slot.

$$\text{Variables: } A, B, C, D \qquad \text{Domains: } D_A = D_B = D_C = D_D = \{1,2,3,4\}.$$

The alternative — one variable per slot, valued by which seminar goes there — is worse here: rule 5 lets two seminars share a slot, so a slot-variable would need a set-valued domain, and the constraints stop being binary.

Note that rule 5 is not a constraint at all. It is the absence of an all-different constraint. Exam papers phrase absences as if they were rules, precisely to see whether you write a constraint for them.

Constraints (all binary):

#	Scope	Constraint
1	$\{A,B\}$	$A < B$
2	$\{B,C\}$	$B < C$
3	$\{C,D\}$	$C \ne D$
4	$\{A,D\}$	$A \ne D$

Constraint graph: nodes are variables, edges are constraints. Four nodes, four edges, forming a cycle $A - B - C - D - A$.

Identification, not planning. In a planning problem (Chapters 1–2) the path is the answer and costs matter. Here nobody cares in what order you assigned the variables; only the final assignment matters, and all complete assignments sit at the same depth ($n = 4$) of the search tree. That is exactly why CSPs get their own specialised algorithms: since the path is worthless, we can throw away everything except the current partial assignment, and we can spend our effort on filtering (killing doomed branches early) and ordering instead of on path cost.

Trap 1 — inventing an all-different constraint. Rule 5 explicitly permits sharing. Most students write “all four slots distinct” out of habit, which changes the answer set completely (and would make $A<B<C$ plus distinctness almost deterministic).

Trap 2 — writing $A \le B$ instead of $A < B$. “Finish before it starts” is strict.

Trap 3 — a non-binary formulation. If you index by slot you get constraints over sets and you cannot run AC-3 as taught. When a formulation question is followed by a filtering question, the formulation is being steered toward binary; take the hint.

In the arc-consistency language of the lecture: forward checking enforces arc consistency on the arcs $Y \to X$ for the newly assigned $X$ only — and deletes from the tail, i.e. from the unassigned neighbour $Y$, never from $X$.

What it does not do: propagate. It never looks at constraints between two unassigned variables. That limitation is the entire point of Problem 12.

$A$'s unassigned neighbours are $B$ and $C$. Delete $R$ from each. $D$ and $E$ are untouched — they are not adjacent to $A$.

$A$	$B$	$C$	$D$	$E$
R	G B	G B	R G B	R G B

$B$'s unassigned neighbours are $C$, $D$, $E$. Delete $G$ from each.

$A$	$B$	$C$	$D$	$E$
R	G	B	R B	R B

$C$ is now a singleton $\{B\}$. Forward checking notices nothing — a domain of size 1 is not a failure. But a human can already see the disaster coming: $D$ and $E$ will both be forced to $R$, and $D \ne E$ is a constraint.

$C = B$: delete $B$ from unassigned neighbours $D$ and $E$.

$A$	$B$	$C$	$D$	$E$
R	G	B	R	R

Still no empty domain, so forward checking allows the search to continue. Assign $D = R$: delete $R$ from unassigned neighbour $E$.

$A$	$B$	$C$	$D$	$E$
R	G	B	R	∅

Failure. $D_E = \varnothing$ after the fourth assignment.

Forward checking needed four assignments to discover a contradiction that was already unavoidable after two. Backtrack: the search now undoes $D=R$, finds no other value for $D$, undoes $C=B$, finds no other value for $C$, undoes $B=G$, and tries $B=B$.

The trap is the singleton domain at step 3. After $B=G$, $C$ has exactly one legal value and $D$, $E$ have the same two values as each other while being constrained unequal. A human sees dead. Forward checking cannot, because it only ever compares an unassigned variable against the just-assigned one. Exams test this by asking “at which assignment is failure detected?” — the answer is later than you'd like, and that lateness is the lesson.

Second trap — deleting from the wrong end. Forward checking deletes from the unassigned neighbour (the tail of the arc $Y \to X$). It never removes the value you just assigned from the assigned variable, and it never touches variables that are not neighbours: $D$ and $E$ survive the $A=R$ step untouched, and writing them as “G B” there is the standard slip.

Third trap — stopping at a size-1 domain. Size 1 is fine. Size 0 is failure.

Each undirected constraint edge gives two arcs. Four constraints here, so eight arcs in the initial queue: $A\!\to\!B$, $B\!\to\!A$, $B\!\to\!C$, $C\!\to\!B$, $C\!\to\!D$, $D\!\to\!C$, $A\!\to\!D$, $D\!\to\!A$.

One preliminary observation that saves half the work: for a $\ne$ constraint, the arc $X \to Y$ can only delete something if $|D_Y| = 1$. With $|D_Y| \ge 2$ every $x$ has a partner. So the $\ne$ arcs ($C\!\to\!D$, $D\!\to\!C$, $A\!\to\!D$, $D\!\to\!A$) will do nothing unless some domain collapses to a singleton.

Process the queue in the order listed.

$A \to B$ (constraint $A < B$): for each $a \in \{1,2,3,4\}$ is there $b \in \{1,2,3,4\}$ with $b > a$? For $a=4$: no. Delete 4.
$D_A = \{1,2,3\}$. Re-enqueue arcs into $A$: $B\!\to\!A$, $D\!\to\!A$.

$B \to A$ (i.e. $a < b$ with $b$ in the tail): for $b=1$, is there $a < 1$? No. Delete 1.
$D_B = \{2,3,4\}$. Re-enqueue arcs into $B$: $A\!\to\!B$, $C\!\to\!B$.

$B \to C$ (constraint $B < C$): for $b=4$, is there $c > 4$? No. Delete 4.
$D_B = \{2,3\}$. Re-enqueue arcs into $B$: $A\!\to\!B$, $C\!\to\!B$.

$C \to B$: for $c=1$, need $b < 1$ — none. For $c=2$, need $b < 2$ from $\{2,3\}$ — none. Delete 1 and 2.
$D_C = \{3,4\}$. Re-enqueue arcs into $C$: $B\!\to\!C$, $D\!\to\!C$.

$A \to B$ again (it was re-enqueued): $D_B$ has shrunk to $\{2,3\}$. For $a=3$, need $b > 3$ — none. Delete 3.
$D_A = \{1,2\}$.

Every remaining arc now passes. The four $\ne$ arcs never fire: no domain ever reached size 1.

Final domains:

$A$	$B$	$C$	$D$
{1, 2}	{2, 3}	{3, 4}	{1, 2, 3, 4}

(b) No, the CSP is not solved — three variables still have two candidate values and $D$ has all four. Enumerating the assignments consistent with these domains and all four constraints gives 8 solutions:

(A,B,C,D) = (1,2,3,2), (1,2,3,4), (1,2,4,2), (1,2,4,3), (1,3,4,2), (1,3,4,3), (2,3,4,1), (2,3,4,3).

This is the lecture's stated limitation: after enforcing arc consistency you may be left with one solution, many solutions, or none at all (and AC-3 will not always tell you which). Arc consistency is a local condition — it checks pairs, never triples — so it cannot see global impossibility. AC-3 still runs inside a backtracking search.

Note $D$ lost nothing. Both of its constraints are $\ne$, and neither neighbour ever became a singleton. Filtering strength is not uniform across variables.

(c) MRV — minimum remaining values, a.k.a. “most constrained variable”, a.k.a. fail-fast ordering: pick the unassigned variable with the fewest legal values left.

Sizes: $|D_A| = 2$, $|D_B| = 2$, $|D_C| = 2$, $|D_D| = 4$. Three-way tie at 2; $D$ is eliminated.

Degree heuristic tie-break — number of constraints to other unassigned variables: $A$ has 2 ($B$, $D$), $B$ has 2 ($A$, $C$), $C$ has 2 ($B$, $D$). Still tied. Alphabetical: choose $A$.

Why min and not max? Because a variable with $k$ values creates $k$ branches. Branching on the smallest $k$ keeps the tree narrow, and if the variable has zero or one options you discover the forced move (or the contradiction) immediately, at the top of the subtree rather than after building a doomed prefix.

(d) LCV — least constraining value: among $A$'s values, try the one that rules out the fewest values in the neighbours' domains. $A$'s unassigned neighbours are $B$ (via $A < B$) and $D$ (via $A \ne D$).

Try	$B$ survivors	removed	$D$ survivors	removed	total
$A = 1$	{2, 3}	0	{2, 3, 4}	1	1
$A = 2$	{3}	1	{1, 3, 4}	1	2

LCV tries $A = 1$ first.

Why least and not most? Because you only need one solution. Values are not branches you must all explore — you stop at the first that works. So order them so the first one is most likely to work, i.e. the one that leaves your neighbours the most room.

(a) $D_A = \{1,2\}$, $D_B = \{2,3\}$, $D_C = \{3,4\}$, $D_D = \{1,2,3,4\}$.

(b) Not solved; 8 complete solutions remain.

(c) MRV selects $A$ (three-way tie at 2 values, broken by degree then alphabetically).

(d) LCV tries $A = 1$ first (rules out 1 value total, vs 2 for $A=2$).

Trap 1 — deleting from the head. “Remember: delete from the tail!” Enforcing $A \to B$ removes values from $D_A$, not from $D_B$. Half of all AC-3 errors are this one, and they show up as suspiciously symmetric final domains.

Trap 2 — forgetting to re-enqueue. The second pass of $A \to B$ is what shrinks $A$ from $\{1,2,3\}$ to $\{1,2\}$. If you process each arc once and stop, you report $D_A = \{1,2,3\}$ and your answer is not arc consistent. Re-enqueue every arc pointing into the variable you just shrank.

Trap 3 — “AC-3 solved it”. It didn't. Eight solutions remain, and a differently-worded CSP could have zero remaining while every domain is non-empty. Arc consistency is necessary, never sufficient.

Trap 4 — comparing AC-3 with forward checking. Problem 11 needed four assignments to detect failure; AC-3 propagates through chains of unassigned variables and so detects failures earlier — at the cost of doing much more work per node. That trade-off ("what's the downside of enforcing arc consistency?") is a standard short-answer question. Answer: time. AC-3 costs $O(n^2 d^3)$ per run and the backtracking search runs it at every node.

Not "which line fits better". Better is not a property of a line; it is a property of a line and a loss. The question is asking you to apply the definition twice:

$$\hat R(h) \;=\; \frac{1}{N}\sum_{i=1}^{N} \ell\big(h(x^{(i)}),\, y^{(i)}\big)$$

with $N = 5$, once with $\ell_{\text{sq}}$ and once with $\ell_{\text{abs}}$. Nothing here involves fitting anything — both hypotheses are handed to you. This is pure evaluation, and ERM then means "pick the one with the smaller $\hat R$".

Get the residuals first, once, and reuse them for both losses. That is the whole trick: $e^{(i)} = h(x^{(i)}) - y^{(i)}$.

$h_A(x) = 2x+2$: predictions $4, 6, 8, 10, 12$.

$i$	$h_A(x^{(i)})$	$y^{(i)}$	$e^{(i)}$	$|e^{(i)}|$	$(e^{(i)})^2$
1	4	4	0	0	0
2	6	6	0	0	0
3	8	8	0	0	0
4	10	10	0	0	0
5	12	17	$-5$	5	25
			sum	5	25

$h_B(x) = 2x+3$: predictions $5, 7, 9, 11, 13$.

$i$	$h_B(x^{(i)})$	$y^{(i)}$	$e^{(i)}$	$|e^{(i)}|$	$(e^{(i)})^2$
1	5	4	$+1$	1	1
2	7	6	$+1$	1	1
3	9	8	$+1$	1	1
4	11	10	$+1$	1	1
5	13	17	$-4$	4	16
			sum	8	20

$$\hat R_{\text{abs}}(h_A) = \tfrac{5}{5} = 1.0, \qquad \hat R_{\text{abs}}(h_B) = \tfrac{8}{5} = 1.6$$ $$\hat R_{\text{sq}}(h_A) = \tfrac{25}{5} = 5.0, \qquad \hat R_{\text{sq}}(h_B) = \tfrac{20}{5} = 4.0$$

Under absolute loss $h_A$ wins ($1.0 < 1.6$). Under squared loss $h_B$ wins ($4.0 < 5.0$). The ranking flips.

Do not divide by $N-1$, and do not forget to divide at all. Dividing by a constant cannot flip a ranking, so the comparison survives either slip — but the reported risk is a specific number and the definition says $\frac1N$.

Squaring is convex and steeply increasing: it converts a residual of 5 into a penalty of 25, while five residuals of 1 cost only 5 in total. So squared loss will happily take on many small errors to shave anything off its one large one. Absolute loss is linear, so one error of 5 and five errors of 1 are priced at exactly the same rate per minute; it has no incentive to move toward the outlier and so keeps the line that nails the straight run.

	$\hat R_{\text{abs}}$	$\hat R_{\text{sq}}$
$h_A = 2x+2$	1.0 ✓ wins	5.0
$h_B = 2x+3$	1.6	4.0 ✓ wins

(b) ERM under absolute loss returns $h_A$; ERM under squared loss returns $h_B$.

(c) The point $(5,17)$ is an outlier. Squared loss prices it at $25$ and will accept four unit errors (total cost 4) to reduce it, so it drags the line upward. Absolute loss prices errors linearly, gains nothing from the trade, and stays with the exact fit on the other four points.

The trap is believing that $\hat R$ ranks hypotheses. It doesn't — $\hat R_\ell$ does. Hand in a sentence like "$h_B$ has lower empirical risk" with no loss named and you have written something that is half wrong whatever the marking scheme, because here it is true of one loss and false of the other. Any time a question says "empirical risk" without naming a loss, that omission is the question.

Second trap — the argument order. These notes write $\ell(\hat y, y)$: guess first, truth second. Squared and absolute loss are symmetric, so it never changes an answer here. It changes everything the moment the loss is asymmetric, which is exactly Problem 15.

Third trap — "the outlier is a data error, delete it". Maybe. But the exam is asking about the loss, not about data cleaning, and you are not told the point is wrong. A 17-minute delivery of 5 items may be perfectly real. The honest answer is to say which loss you would pick and why, not to edit the dataset.

Two independent questions, answered in this order:

1. Are there labels $y^{(i)}$ in the training data? No labels $\Rightarrow$ unsupervised, and you stop there. Labels $\Rightarrow$ supervised, continue.
2. What kind of set is $\mathcal{Y}$? A finite set of categories $\Rightarrow$ classification. A continuum, i.e. $\mathcal{Y} \subseteq \mathbb{R}$ $\Rightarrow$ regression.

Note what is not in the test: the algorithm. "Logistic regression" does not make something regression, and a decision tree can do either. And note that supervision is a property of your data, not of the world — (f) and (g) are the same images.

(a) Classification. $\mathcal{X}$ = X-ray images (pixel arrays), $\mathcal{Y} = \{\text{normal}, \text{pneumonia}, \text{TB}\}$, $|\mathcal{Y}| = 3$ — a finite unordered set. Labels exist (the radiologist's reading). Multi-class classification.

(b) Regression. $\mathcal{X} = \mathbb{R}^3$-ish (area, age, postcode — though postcode is really categorical and wants one-hot encoding), $\mathcal{Y} = \mathbb{R}_{>0}$, dollars. Labels exist. A price is a continuum: between 400,000 dollars and 400,001 dollars there is 400,000.50.

(c) Unsupervised. There is no $y$ at all, and "segments nobody has named in advance" is the giveaway — if the segments were named you would have labels and it would be classification. This is clustering.

(d) Classification. The output is a probability in $[0,1]$, which looks continuous and is the single most common wrong answer here. But $\mathcal{Y} = \{\text{spam}, \text{not spam}\}$: the label you are trying to recover is binary. A probability is a graded answer to a yes/no question, not a real-valued quantity in its own right. This is binary classification, done with logistic regression.

(e) Regression. $\mathcal{Y} = \mathbb{R}_{\ge 0}$, millimetres of rain. Labels exist (tomorrow's actual measurement, known for every historical day). Note that "will it rain tomorrow? yes/no" would be classification on the same inputs — the question determines the type, not the data source.

(f) Classification. $|\mathcal{Y}| = 26$. The classes have no meaningful order or distance: "the answer was R and we said S" is not a near-miss worth half credit, which is exactly why zero-one loss is the natural loss here and squared loss is not.

(g) Unsupervised. Same $\mathcal{X}$ as (f), same images, same pixels — and the labels are gone. Supervised versus unsupervised is a fact about the training set in front of you.

Trap 1 — (d), the continuous output. Logistic regression outputs a number in $[0,1]$ and its name contains "regression", and both facts are decoys. $\mathcal{Y}$ is what you are predicting, not what your model happens to emit on the way there.

Trap 2 — (f) versus (g). The pair exists to force the point that the same raw data supports both a supervised and an unsupervised problem. "Is this dataset supervised?" is a question about whether someone wrote labels down.

Trap 3 — ordinal outputs. A star rating in $\{1,2,3,4,5\}$ is the standard follow-up. It is finite (so classification is defensible) but ordered (so regression is defensible, and treating 1-vs-5 as the same mistake as 4-vs-5 is clearly wrong). The marks are in the justification: name $\mathcal{Y}$, say it is finite but ordered, and say which loss you would use. A question with two defensible answers is testing whether you can say why.

Still just $\hat R(h) = \frac1N\sum_i \ell(h(x^{(i)}), y^{(i)})$ — but now $\ell$ is a table, read as "row = what we guessed, column = the truth". Two of the four cells are zero, so the sum only has two live terms:

$$\hat R(h) \;=\; \frac{1}{N}\Big[\,\underbrace{\#\text{FN}}_{\hat y=0,\,y=1}\cdot 10 \;+\; \underbrace{\#\text{FP}}_{\hat y=1,\,y=0}\cdot 1 \,\Big].$$

Zero-one loss is the special case where both off-diagonal cells are 1, so $\hat R_{0/1} = (\#\text{FN} + \#\text{FP})/N$ — the error rate, and $1 - \hat R_{0/1}$ is the accuracy.

Part (d) is a different kind of question: not "evaluate a classifier" but "given a probability, what is the cost-minimising decision?" Compare two expected losses and find where they cross.

$h_1$: errors $= \text{FN} + \text{FP} = 2 + 1 = 3$. $\ \hat R_{0/1} = 3/20 = 0.15$, accuracy $85\%$.

$h_2$: errors $= 0 + 5 = 5$. $\ \hat R_{0/1} = 5/20 = 0.25$, accuracy $75\%$.

By accuracy, $h_1$ is clearly the better model — ten percentage points better.

$h_1$: $\ \hat R = \dfrac{2 \cdot 10 + 1 \cdot 1}{20} = \dfrac{20 + 1}{20} = \dfrac{21}{20} = \mathbf{1.05}$.

$h_2$: $\ \hat R = \dfrac{0 \cdot 10 + 5 \cdot 1}{20} = \dfrac{5}{20} = \dfrac{1}{4} = \mathbf{0.25}$.

$h_2$ costs the hospital about one quarter of what $h_1$ costs. The ranking has reversed, and not narrowly — by a factor of four.

Sanity check on the units: $h_1$'s risk exceeds 1, which is fine. The risk is an average cost measured in confirmatory-test units, and a single missed case costs ten of those, so averages above 1 are entirely possible. Only zero-one risk is forced into $[0,1]$.

Suppose the model tells you $P(y=1 \mid x) = p$. You have two actions.

Flag ($\hat y = 1$): expected loss $= p \cdot \ell(1,1) + (1-p)\cdot \ell(1,0) = p\cdot 0 + (1-p)\cdot 1 = 1 - p$.

Clear ($\hat y = 0$): expected loss $= p \cdot \ell(0,1) + (1-p)\cdot \ell(0,0) = p \cdot 10 + 0 = 10p$.

Flag when flagging is cheaper:

$$1 - p < 10p \iff 1 < 11p \iff p > \frac{1}{11} \approx 0.0909.$$

So flag any patient with more than a $9.1\%$ chance of disease — nowhere near the default threshold of $0.5$. In general, with false-negative cost $c_{\text{FN}}$ and false-positive cost $c_{\text{FP}}$, the break-even point is

$$p^{*} = \frac{c_{\text{FP}}}{c_{\text{FP}} + c_{\text{FN}}},$$

which gives $1/(1+10) = 1/11$ here, and $1/2$ exactly when the two costs are equal — which is the only reason $0.5$ is ever the right threshold.

	$\hat R_{0/1}$	accuracy	$\hat R_{\text{hospital}}$
$h_1$	0.15 ✓	85%	1.05
$h_2$	0.25	75%	0.25 ✓

(c) Deploy $h_2$. It is the less accurate model and the cheaper one, because the hospital's own loss table says a missed case is worth ten false alarms, and $h_2$ misses none.

(d) Flag whenever $p > 1/11 \approx 0.091$.

The trap is reading accuracy as a measure of quality. Accuracy is $\hat R$ under one specific loss — the one that says every mistake costs the same — and that loss is almost never the one the application has. The exam builds the numbers so that the higher-accuracy model is the worse model, because if you have internalised $\hat R_\ell$ you cannot get this wrong, and if you have memorised "accuracy good" you cannot get it right.

Second trap — transposing the table. Rows are predictions, columns are truth. If you read $\ell(\hat y{=}0, y{=}1) = 10$ as "flagging a healthy patient costs 10", you compute $(1\cdot 10 + 2\cdot 1)/20 = 0.6$ for $h_1$ and $(5\cdot 10+0)/20 = 2.5$ for $h_2$, conclude $h_1$ wins, and have produced a fluent, wrong answer. Write the words "false negative" and "false positive" into the cells before you multiply anything.

Third trap — the threshold of $0.5$. $0.5$ is not a principled threshold; it is the break-even point of a symmetric loss. With a $10{:}1$ cost ratio it moves to $1/11$. Any screening, fraud or safety question is asking you to notice this.

Fourth trap — class imbalance. Here 8 of 20 are positive. Push that to 1 in 1000 and the constant classifier "nobody is ill" scores $99.9\%$ accuracy with risk $10 \cdot 1/1000 = 0.01$ under this table, while catching nothing. Always compute what the trivial classifier scores before claiming a number is good.

The training error of a stump is the empirical risk under zero-one loss, and for a majority-vote leaf that is just the count of the minority class in the leaf. So for every candidate test the recipe is:

1. Split the 8 rows into the two children.
2. In each child, count $(\#y{=}1, \#y{=}0)$.
3. The leaf predicts the majority; its mistakes are the minority count, $\min(\#1, \#0)$.
4. Stump error $= \dfrac{\text{minority of left} + \text{minority of right}}{8}$.

You never need to compute an entropy, a probability or a weighted average here. Count, take minima, add, divide by 8.

Overall label counts first, because (a) needs them: $y=1$ for ids 1,2,3,4,5 — 5 spam; $y=0$ for ids 6,7,8 — 3 not spam.

A single leaf must predict one class for all 8 emails. Majority is spam (5 vs 3), so it predicts spam and is wrong on the 3 non-spam emails:

$$\text{error}(\text{depth-0}) = \tfrac{3}{8} = 0.375.$$

Compute this before the splits, always. It is the number every split has to beat, and it is the number a tie-breaking or stopping rule is compared against.

Test $f_1 = 1$?

$f_1 = 1$: ids 1,2,3,4 — all spam, $(4, 0)$. Predict spam, minority $= 0$ mistakes. Pure leaf.
$f_1 = 0$: ids 5,6,7,8 — $(1, 3)$. Predict not-spam, minority $= 1$ mistake (id 5).

$$\text{error} = \tfrac{0 + 1}{8} = \tfrac{1}{8} = 0.125.$$

Test $f_2 = 1$?

$f_2 = 1$: ids 2,3,4,8 — $(3, 1)$. Predict spam, 1 mistake (id 8).
$f_2 = 0$: ids 1,5,6,7 — $(2, 2)$. Tie; predict either, 2 mistakes.

$$\text{error} = \tfrac{1 + 2}{8} = \tfrac{3}{8} = 0.375.$$

Test $L \ge 4$?

$L \ge 4$: ids 3 ($L{=}5$), 4 ($L{=}7$), 6 ($L{=}4$), 7 ($L{=}6$), 8 ($L{=}9$) — $(2, 3)$. Predict not-spam, 2 mistakes.
$L < 4$: ids 1 ($L{=}2$), 2 ($L{=}0$), 5 ($L{=}1$) — $(3, 0)$. Predict spam, 0 mistakes. Pure leaf.

$$\text{error} = \tfrac{2 + 0}{8} = \tfrac{2}{8} = 0.25.$$

Note that $L \ge 4$ puts five rows on the left and three on the right — children do not have to be the same size, and the $L=4$ row goes with the “$\ge$” side. Decide which way the boundary rounds before you count, and write it down.

Test	left child $(1,0)$	right child $(1,0)$	mistakes	error	reduction vs $3/8$
$f_1 = 1$?	$(4,0)$	$(1,3)$	$0+1$	$1/8 = 0.125$ ✓	$2/8$
$L \ge 4$?	$(2,3)$	$(3,0)$	$2+0$	$2/8 = 0.25$	$1/8$
$f_2 = 1$?	$(3,1)$	$(2,2)$	$1+2$	$3/8 = 0.375$	$0$

(a) $3/8$.   (b) as tabulated.   (c) Training error chooses $f_1$. A “stop unless the split reduces training error” rule rejects $f_2$, whose stump is exactly as wrong as the single leaf it replaced.

Trap 1 — summing errors instead of error rates, or averaging rates instead of summing counts. Both children divide by the same $N = 8$, so you may add raw mistake counts and divide once at the end. What you may not do is average the two children's error rates unweighted: for $f_1$ that would give $\frac12(0) + \frac12(1/4) = 1/8$ by luck (the children are the same size), but for $L \ge 4$ it gives $\frac12(2/5) + \frac12(0) = 1/5 \ne 1/4$. Weight by child size, or just count mistakes.

Trap 2 — the $(2,2)$ tie. A tied leaf is wrong on half its examples no matter which way you break the tie. Predicting "spam" there does not make the error 0.

Trap 3 — the threshold row. Id 6 has exactly $L = 4$, and the test is $L \ge 4$, so it goes left. Exams put a point exactly on the threshold every time.

Trap 4 — thinking a pure child means a good split. Both $f_1$ and $L \ge 4$ produce a pure leaf; their errors differ by a factor of two. And in Problem 17 a split that produces a pure leaf has the worse training error of the two candidates.

Two scores for the same three splits. The counts you need are identical for both, so build the count table once and read both scores off it.

For each test, for each child, you want the pair $(\#y{=}1,\ \#y{=}0)$ and the child size. Then:

$$\text{error} = \frac{\sum_{\text{children}} \min(\#1, \#0)}{N}, \qquad H(Y \mid W) = \sum_{\text{children}} \frac{|S_c|}{N}\,H(Y \mid W = c), \qquad I(Y;W) = H(Y) - H(Y\mid W).$$

$H(Y)$ is the same for all three tests, so whichever test minimises $H(Y \mid W)$ maximises the gain. You can rank by $H(Y\mid W)$ alone and only subtract once.

Overall labels: sold = ids 1,2,3,6 — 4 sold, 6 unsold.

$R = 1$? $\ R{=}1$: ids 1–5, sold 1,2,3 $\Rightarrow (3,2)$, size 5. $\ R{=}0$: ids 6–10, sold 6 only $\Rightarrow (1,4)$, size 5.

$M = 1$? $\ M{=}1$: ids 9,10, neither sold $\Rightarrow (0,2)$, size 2. $\ M{=}0$: ids 1–8, sold 1,2,3,6 $\Rightarrow (4,4)$, size 8.

$d \le 2$? $\ d \le 2$: ids 1 (0.5), 2 (1.0), 4 (1.5), 7 (2.0), 9 (1.2), sold 1,2 $\Rightarrow (2,3)$, size 5. $\ d > 2$: ids 3 (3.0), 5 (4.0), 6 (2.5), 8 (5.0), 10 (3.5), sold 3,6 $\Rightarrow (2,3)$, size 5.

Test	child 1 $(1,0)$	size	child 2 $(1,0)$	size
$R = 1$?	$(3,2)$	5	$(1,4)$	5
$M = 1$?	$(0,2)$	2	$(4,4)$	8
$d \le 2$?	$(2,3)$	5	$(2,3)$	5

Check every row sums to $(4,6)$ and to 10. All three do.

Root as a single leaf: majority is unsold (6 vs 4), so 4 mistakes, error $4/10$.

$R$: $\min(3,2) + \min(1,4) = 2 + 1 = 3$, error $= 3/10 = 0.3$.

$M$: $\min(0,2) + \min(4,4) = 0 + 4 = 4$, error $= 4/10 = 0.4$.

$d \le 2$: $\min(2,3) + \min(2,3) = 2 + 2 = 4$, error $= 4/10 = 0.4$.

So training error says: $R$ is the best test, and $M$ and $d\le 2$ are tied — and both are worthless, since neither beats the $4/10$ of not splitting at all.

Root. 4 sold out of 10, so $H(Y) = H(2/5) = \mathbf{0.971}$ bits.

$R = 1$?

$$H(Y \mid R{=}1) = H(3/5) = 0.971, \qquad H(Y \mid R{=}0) = H(1/5) = 0.722$$ $$H(Y \mid R) = \tfrac{5}{10}(0.971) + \tfrac{5}{10}(0.722) = 0.4855 + 0.3610 = \mathbf{0.846}$$ $$I(Y;R) = 0.971 - 0.846 = \mathbf{0.125}\ \text{bits}$$

$M = 1$?

$$H(Y \mid M{=}1) = H(0) = 0 \quad\text{(pure: both unsold)}, \qquad H(Y \mid M{=}0) = H(1/2) = 1$$ $$H(Y \mid M) = \tfrac{2}{10}(0) + \tfrac{8}{10}(1) = \mathbf{0.800}$$ $$I(Y;M) = 0.971 - 0.800 = \mathbf{0.171}\ \text{bits}$$

$d \le 2$?

$$H(Y \mid d{\le}2) = H(2/5) = 0.971, \qquad H(Y \mid d{>}2) = H(2/5) = 0.971$$ $$H(Y \mid d) = \tfrac{5}{10}(0.971) + \tfrac{5}{10}(0.971) = 0.971 = H(Y), \qquad I(Y;d) = \mathbf{0.000}\ \text{bits}$$

Zero gain, exactly. Both children have the same class proportions as the parent, so knowing $d \le 2$ tells you nothing at all about whether the flat sold. (Exact values, for the record: $I(Y;R) = 0.124511$, $I(Y;M) = 0.170951$, $I(Y;d) = 0$.)

Test	training error	$H(Y\mid W)$	$I(Y;W)$
$R = 1$?	$0.3$ ✓ error's pick	$0.846$	$0.125$
$M = 1$?	$0.4$	$\mathbf{0.800}$	$0.171$ ✓ gain's pick
$d \le 2$?	$0.4$	$0.971$	$0.000$

(c) Training error picks $R$; information gain picks $M$. This is a genuine reversal, not a tie-break.

What gain sees that error cannot. Splitting on $M$ carves out a pure group of two flats — on a main road, neither sold, zero remaining uncertainty, a finished leaf. Training error cannot score that, because those two flats were already being predicted correctly by the root's majority vote, so isolating them changes nothing it measures. Error only ever notices a change that flips a majority; it is a step function of the counts and is flat everywhere else.

What error sees that gain undervalues. $R$ genuinely makes fewer mistakes right now — 3 instead of 4. If you were forced to stop at depth 1 and be graded on accuracy, $R$ is the better stump. Gain is optimising a surrogate (expected number of yes/no questions still needed), not accuracy.

And both agree on $d$. Error says it reduces nothing; gain says $0.000$ bits. When both criteria agree a split is useless, it is useless.

The trap is assuming the two criteria agree, so you compute the cheap one and report it. They are different objectives and they really do disagree. If a question asks for "the best split" without saying by which criterion, that omission is the question — and if it asks for both, expect the answers to differ, because that is the only reason to ask for both.

Second trap — forgetting the size weights in $H(Y\mid W)$. For $M$ the children are sizes 2 and 8, and the unweighted average $\frac12(0) + \frac12(1) = 0.5$ would give a gain of $0.471$ — nearly four times the truth, and it would still have picked $M$, so the answer "looks" right while the method is wrong. Conditional entropy is an expectation over $P(W = \omega) = |S_\omega|/N$.

Third trap — a pure child is not a finished job. $M$ gives one pure leaf of size 2 and leaves a perfectly balanced node of size 8 behind, which still needs work. Purity is per-leaf; the split is scored over all leaves.

Fourth trap — reading $I(Y;d) = 0$ as “$d$ is irrelevant”. It means this threshold is uninformative. A different cut on the same attribute can have positive gain; real-valued attributes are retested at every threshold, which is also why you do not remove an attribute from $A$ in the recursive call once thresholds are allowed.

Three different distributions, so be explicit about which one each entropy is taken over.

• $H(Y)$ uses the row totals: $P(Y{=}1) = 6/8$, $P(Y{=}0) = 2/8$.
• $H(Y \mid W = \omega)$ uses one column, normalised by that column's total — not by 8.
• $H(Y \mid W)$ averages those three numbers, weighted by the column totals over 8.

The single most common error in this whole topic is dividing a cell by $N$ when computing a conditional. Inside column "med" the probabilities are $1/2, 1/2$, not $1/8, 1/8$.

(a) $P(Y{=}1) = 6/8 = 3/4$, $P(Y{=}0) = 1/4$:

$$H(Y) = \tfrac34 \log_2 \tfrac43 + \tfrac14\log_2 4 = \tfrac34(2 - 1.585) + \tfrac14(2) = \tfrac34(0.415) + 0.5 = 0.311 + 0.5 = \mathbf{0.811}$$

(This is $H(1/4) = H(3/4) = 0.811$ from the table; the long form is shown so you can see where it comes from. $\log_2\frac43 = 2 - \log_2 3 = 2 - 1.585 = 0.415$.)

(b) One column at a time.

$W = $ low: column is $(3, 1)$, total 4, so $P(Y{=}1 \mid \text{low}) = 3/4$:

$$H(Y \mid W = \text{low}) = H(3/4) = \mathbf{0.811}$$

$W = $ med: column is $(1,1)$, total 2, so $P = 1/2$ each — maximum uncertainty:

$$H(Y \mid W = \text{med}) = H(1/2) = \mathbf{1.000}$$

$W = $ high: column is $(2,0)$, total 2, so $P(Y{=}1 \mid \text{high}) = 1$ — pure:

$$H(Y \mid W = \text{high}) = H(1) = \mathbf{0.000}$$

Weights are $P(W{=}\omega) = $ column total $/\,8$: low $4/8 = 1/2$, med $2/8 = 1/4$, high $2/8 = 1/4$.

$$H(Y \mid W) = \tfrac12(0.811278) + \tfrac14(1.000000) + \tfrac14(0.000000) = 0.405639 + 0.250000 + 0 = \mathbf{0.656}$$ $$I(Y;W) = H(Y) - H(Y\mid W) = 0.811278 - 0.655639 = \mathbf{0.156}\ \text{bits}$$

Two sanity checks worth doing every time:

• $H(Y \mid W) \le H(Y)$: $0.656 \le 0.811$ ✓. Conditioning never increases entropy on average, so a negative gain is always an arithmetic error.
• $H(Y\mid W)$ lies between the smallest and largest of $\{0, 0.811, 1\}$ ✓. It is an average of them.

Note that $H(Y\mid W=\text{med}) = 1 > H(Y) = 0.811$. That is allowed: conditioning on a particular value can increase uncertainty. Only the average is guaranteed not to.

$H(W)$ from the column totals $4/8, 2/8, 2/8 = \frac12, \frac14, \frac14$:

$$H(W) = \tfrac12\log_2 2 + \tfrac14 \log_2 4 + \tfrac14\log_2 4 = 0.5 + 0.5 + 0.5 = \mathbf{1.500}$$

$H(W \mid Y)$ — now condition the other way, using the rows.

Row $Y{=}1$ is $(3,1,2)$, total 6, so $P(W \mid Y{=}1) = \frac12, \frac16, \frac13$:

$$H(W \mid Y{=}1) = \tfrac12\log_2 2 + \tfrac16\log_2 6 + \tfrac13\log_2 3 = 0.5 + \tfrac{2.585}{6} + \tfrac{1.585}{3} = 0.5 + 0.4308 + 0.5283 = 1.459$$

Row $Y{=}0$ is $(1,1,0)$, total 2, so $P = \frac12, \frac12, 0$:

$$H(W \mid Y{=}0) = H(1/2) = 1.000$$ $$H(W \mid Y) = \tfrac68(1.459148) + \tfrac28(1.000000) = 1.094361 + 0.250000 = \mathbf{1.344}$$ $$H(W) - H(W\mid Y) = 1.500000 - 1.344361 = \mathbf{0.156}\ \text{bits} \quad\checkmark$$

Same number as (c), to six decimals. Mutual information is symmetric — $I(Y;W) = I(W;Y)$ — even though the conditional entropies going each way ($0.656$ and $1.344$) are nothing like each other.

quantity	value (bits)
$H(Y)$	$0.811$
$H(Y \mid W = \text{low})$	$0.811$
$H(Y \mid W = \text{med})$	$1.000$
$H(Y \mid W = \text{high})$	$0.000$
$H(Y \mid W)$	$0.656$
$I(Y;W)$	$\mathbf{0.156}$
$H(W)$  (d)	$1.500$
$H(W \mid Y)$  (d)	$1.344$
$H(W) - H(W\mid Y)$	$\mathbf{0.156}$ ✓

Trap 1 — normalising a conditional by $N$. In column "med" the cells are 1 and 1. If you use $1/8$ and $1/8$ you get $2 \cdot \frac18 \log_2 8 = 0.75$ instead of $1.000$, and the error propagates into both $H(Y\mid W)$ and the gain. A conditional distribution must sum to 1 within the condition. Check that before computing any logarithm.

Trap 2 — the pure column. $W=\text{high}$ has a zero cell. $0\log_2\frac10$ is defined to be 0, so $H = 0$, not undefined and not "skip the column" — the column still carries weight $2/8$ into the average, it just contributes $0$ to the sum.

Trap 3 — forgetting the weights. The unweighted mean of $0.811, 1.000, 0.000$ is $0.604$, which would give a gain of about $0.208$. Plausible-looking and wrong. Weight by $P(W = \omega)$.

Trap 4 — being surprised that $H(Y \mid W = \text{med}) > H(Y)$. That is not an error. "Conditioning reduces entropy" is a statement about the average $H(Y\mid W)$, never about individual values. The medium-practice students are genuinely harder to call than the class as a whole.

A decision tree with real-valued features asks tests of the form “is $x_j \le t$?”. Each such test is a single axis-aligned cut — a line perpendicular to one coordinate axis — so every region a tree can carve out is a box (an axis-aligned rectangle, possibly unbounded), and the decision boundary is always a union of horizontal and vertical segments.

That is the entire content of this problem. Parts (a)–(c) ask what that buys you on this dataset; part (d) asks what it costs you on a boundary that isn't axis-aligned.

Do not assume the drawn tests $x_1 = 3$, $x_2 = 3$ are the only candidates. For (a) you must argue about all single tests.

Take any vertical cut $x_1 \le t$. Scan the possible $t$: the points' $x_1$ values are $1,1,2,2,4,4,5,5$, and at every $x_1$ value there is exactly one positive and one negative. So whatever $t$ you choose, each side receives equal numbers of each class — a side holding $k$ points holds $k/2$ of each. Majority vote in a tied leaf is wrong half the time, so the error is $\frac12$.

By the symmetry of the data under swapping $x_1 \leftrightarrow x_2$, the same holds for every horizontal cut.

$$\text{error of the best depth-1 stump} = \tfrac{4}{8} = \mathbf{0.5}$$

Which is exactly the error of not splitting at all ($4$ positives, $4$ negatives, so a single leaf is wrong 4 times). No single test helps at all — and the information gain of every single test is $0$ bits for the same reason.

Split on $x_1 \le 3$, then on $x_2 \le 3$ in both children:

if x1 <= 3:
    if x2 <= 3:  predict 1     # (1,1), (2,2)
    else:        predict 0     # (1,5), (2,4)
else:
    if x2 <= 3:  predict 0     # (4,2), (5,1)
    else:        predict 1     # (4,4), (5,5)

Every leaf is pure, so training error is $\mathbf{0}$. Depth 2, four leaves.

Any threshold strictly between 2 and 4 works for both cuts, so $x_1 \le 3$ and $x_2 \le 3$ are representative rather than special. And note that $x_2$ is tested again below a node — reusing an attribute is required once thresholds are in play, which is why the greedy algorithm does not delete the chosen attribute from $A$ in its recursive call.

The sting: the first split, $x_1 \le 3$, has zero training error reduction and zero information gain. A greedy algorithm scoring one split at a time has no reason to prefer it over any other, yet it is the first half of a perfect tree. This is exactly what "greedy is suboptimal, but it buys computational efficiency" means in practice.

(c) No. This is XOR. Suppose some line gave zero error. Then the signed value $g(x) = \theta_0 + \theta_1x_1 + \theta_2x_2$ would be positive at $(1,1)$ and $(5,5)$ and negative at $(1,5)$ and $(5,1)$. Add up:

$$g(1,1) + g(5,5) = 2\theta_0 + 6\theta_1 + 6\theta_2, \qquad g(1,5) + g(5,1) = 2\theta_0 + 6\theta_1 + 6\theta_2.$$

The two sums are identical — both pairs have the same midpoint $(3,3)$. But the first must be $> 0$ (sum of two positives) and the second $< 0$ (sum of two negatives). Contradiction, so no such line exists. A depth-2 axis-aligned tree solves what no linear model can.

(d) No — not exactly, ever. The boundary $x_1 + x_2 = 6$ is a diagonal line. A tree's boundary is a union of axis-parallel segments, so it can only approximate a diagonal with a staircase. Adding depth adds steps: each extra level halves the step width, so the error region shrinks toward zero but never reaches it. With a finite tree you always misclassify some sliver next to the diagonal.

Two honest footnotes. On a finite training set you can of course reach zero training error — in the worst case with one leaf per point. The impossibility is about representing the boundary over all of $\mathbb{R}^2$, which is what controls test error. And the fix is the one from Section 9: engineer the feature $x_3 = x_1 + x_2$ and a single test $x_3 \ge 6$ is exact. Axis-aligned is a property of the tree in the coordinates you give it.

(a) $4/8 = 0.5$ — no single threshold test on either feature does better than a single leaf, and every one has zero information gain.

(b) Split $x_1 \le 3$, then $x_2 \le 3$ on both branches: depth 2, 4 leaves, all pure, training error 0.

(c) No. $(1,1),(5,5)$ and $(1,5),(5,1)$ share the midpoint $(3,3)$, so any linear function has the same sum on both pairs; one pair needs a positive sum and the other a negative one.

(d) No. Axis-aligned tests give a staircase boundary; a diagonal needs infinitely many steps. Depth buys a finer staircase and a monotonically smaller error, never an exact fit — unless you add the feature $x_1 + x_2$.

Trap 1 — answering (a) from the figure. The drawn lines are at $3$ and $3$, so it is tempting to evaluate only those. The question says "the best single threshold test", which requires an argument over all thresholds on both features. The argument here is a symmetry argument and takes one sentence; a case-by-case scan of nine thresholds takes a page and earns the same marks.

Trap 2 — "greedy would find the depth-2 tree". It might, by tie-breaking, but nothing in the criterion points at it: every first split scores zero on both training error and information gain. This dataset is the standard counterexample to "greedy top-down induction finds the optimal tree".

Trap 3 — confusing "cannot represent" with "cannot fit the training set". In (d), a deep enough tree gets zero training error on any finite sample with no contradictory labels. The claim being tested is about the boundary over the whole input space.

Trap 4 — forgetting that you may re-test a feature. In (b), $x_2$ is tested in both subtrees. Students who learned "remove the attribute from $A$" from the binary-attribute version of the algorithm conclude that no depth-2 tree exists here.

One parameter, one convex parabola in that parameter, so the minimum is wherever the derivative vanishes. "Derive it" means: write $J(w)$, differentiate with respect to $w$, set to zero, solve. The two sums $\sum x^{(i)}y^{(i)}$ and $\sum (x^{(i)})^2$ will appear by themselves — that is the point of the exercise, and once you have seen them appear you will never again mis-remember which one is on top.

Part (d) is the actual exam content: it offers a plausible-sounding alternative and asks you to show, numerically, that it is worse. "Show it is worse" means compute both objective values.

$$J(w) = \frac{1}{N}\sum_{i}\big(wx^{(i)} - y^{(i)}\big)^2$$

Differentiate term by term, using the chain rule ($\frac{d}{dw}(wx - y)^2 = 2(wx-y)\cdot x$):

$$J'(w) = \frac{2}{N}\sum_{i}\big(wx^{(i)} - y^{(i)}\big)x^{(i)} = \frac{2}{N}\Big(w\sum_i (x^{(i)})^2 - \sum_i x^{(i)}y^{(i)}\Big)$$

Set $J'(w) = 0$. The $\frac2N$ is a nonzero constant, so it drops out:

$$w\sum_i (x^{(i)})^2 = \sum_i x^{(i)}y^{(i)} \qquad\Longrightarrow\qquad \boxed{\;w^{*} = \frac{\sum_i x^{(i)}y^{(i)}}{\sum_i (x^{(i)})^2}\;}$$

It is the minimum, not a maximum or a saddle: $J''(w) = \frac2N\sum_i (x^{(i)})^2 > 0$ whenever some $x^{(i)} \ne 0$, so $J$ is a strictly convex parabola and its one stationary point is the global minimum.

Note where the data enters: only through two numbers, $\sum xy$ and $\sum x^2$. Also note the denominator cannot be $\sum x^{(i)}$ or $(\sum x^{(i)})^2$ — the derivation leaves no room for doubt, which is why deriving beats memorising.

$i$	$x$	$y$	$xy$	$x^2$
1	1	1	1	1
2	2	4	8	4
3	3	5	15	9
4	4	9	36	16
			60	30

$$w^{*} = \frac{60}{30} = \mathbf{2}$$

(c) With $w^{*} = 2$ the predictions are $2, 4, 6, 8$ and the residuals $\hat y - y$ are

$$2-1 = +1,\quad 4-4 = 0,\quad 6-5 = +1,\quad 8-9 = -1$$ $$J(2) = \frac{1^2 + 0^2 + 1^2 + (-1)^2}{4} = \frac{3}{4} = \mathbf{0.75}$$

Note the residuals do not sum to zero here ($+1$): with no intercept there is nothing in the model that can shift the line vertically, so there is no reason for them to. What is zero is $\sum_i x^{(i)}\,(\hat y^{(i)} - y^{(i)}) = 1(1) + 2(0) + 3(1) + 4(-1) = 0$ — exactly the stationarity condition you derived in Step 2, and the fastest possible check that $w^{*}$ is right.

$$\bar x = \frac{1+2+3+4}{4} = \frac{10}{4} = 2.5, \qquad \bar y = \frac{1+4+5+9}{4} = \frac{19}{4} = 4.75$$ $$\frac{\bar y}{\bar x} = \frac{4.75}{2.5} = \frac{19}{10} = 1.9$$

To compare objectives cleanly, expand $J$ once as a quadratic in $w$. With $\sum x^2 = 30$, $\sum xy = 60$ and $\sum y^2 = 1 + 16 + 25 + 81 = 123$:

$$J(w) = \frac{1}{4}\big(30w^2 - 120w + 123\big)$$

Check it at $w^{*}$: $\frac14(120 - 240 + 123) = \frac34$ ✓, and the vertex is at $w = \frac{120}{60} = 2$ ✓.

$$J(1.9) = \tfrac14\big(30(3.61) - 228 + 123\big) = \tfrac14(108.3 - 105) = \tfrac{3.3}{4} = \tfrac{33}{40} = \mathbf{0.825}$$

So $w = 1.9$ costs $0.825$ against the optimum's $0.75$ — worse by $0.075$, about $10\%$. And because $J$ is a parabola centred at $2$, $w = 2.1$ costs exactly the same $0.825$. Equal distance from the optimum, equal penalty: the symmetry is a free check on your algebra.

Why does the "average point" rule fail? It forces the line through $(\bar x, \bar y)$, which is the right instinct for the model with an intercept ($b = \bar y - w\bar x$ does exactly that). With no intercept the line is pinned through the origin instead, and the best such line weights each point by its own $x$ — that is what $\sum xy / \sum x^2$ is: a leverage-weighted slope, in which the point at $x=4$ counts sixteen times as much as the point at $x=1$.

(a) $J'(w) = \frac2N\big(w\sum x^2 - \sum xy\big) = 0 \Rightarrow w^{*} = \sum xy / \sum x^2$, a minimum since $J'' = \frac2N\sum x^2 > 0$.

(b) $w^{*} = 60/30 = 2$.

(c) $J(2) = 3/4 = 0.75$.

(d) $\bar y/\bar x = 1.9$, with $J = 33/40 = 0.825$. The optimum is lower by $0.075$.

Trap 1 — inverting the fraction. $\sum x^2 / \sum xy = 30/60 = 0.5$ is a number you can write down in one slip, and nothing about it looks wrong. Deriving the formula, or sanity-checking that a slope of $0.5$ predicts $\hat y = 2$ when $y = 9$, catches it instantly.

Trap 2 — using the with-intercept formula. $\frac{\sum(x-\bar x)(y - \bar y)}{\sum (x - \bar x)^2}$ is a different model. On this data it gives $\frac{12.5}{5} = 2.5$ with $b = \bar y - w\bar x = 4.75 - 6.25 = -1.5$, and that line reaches $J = 3/8 = 0.375$ — better than the $0.75$ above, because it has a second parameter to spend. But $h(x) = wx$ is the model you were given and it must pass through the origin, so $0.375$ is the answer to a different question. Read which model is being fitted before picking a formula.

Trap 3 — forgetting the $\frac1N$ in the reported risk. $\sum$ of squared residuals is 3; $J$ is $0.75$. Both appear in textbooks as "the objective"; the $\frac1N$ (and sometimes a $\frac1{2N}$, chosen to cancel the 2 from differentiating) never changes $w^{*}$, but it does change the number you write on the line marked $J(w^{*})$.

Trap 4 — "the residuals must sum to zero". True only when the model has an intercept, because the intercept's own stationarity condition is $\sum_i(\hat y - y) = 0$. Here they sum to $+1$. The condition that does hold is $\sum_i x^{(i)}(\hat y^{(i)} - y^{(i)}) = 0$, one equation per parameter.

A mechanical computation with four places to go wrong, so the order matters. Build $X$, then $X^{\top}X$ (a $2\times2$), then its determinant (a scalar — stop and look at it; if it is 0, see Problem 22), then the inverse, then $X^{\top}y$ (a $2$-vector), then multiply.

The intercept is not a special case in the algebra. You handle it by adding a column of ones to $X$, after which $\theta_0$ is just the weight on a feature that is always 1. That is the whole trick, and it is why the vector formula covers the with-intercept case for free.

Know what each object's shape is before you compute it: $X \in \mathbb{R}^{4\times2}$, $X^{\top}X \in \mathbb{R}^{2\times2}$, $X^{\top}y \in \mathbb{R}^{2}$, $\theta^{*} \in \mathbb{R}^{2}$. $X^{\top}X$ is $d \times d$, never $N \times N$ — that is the whole reason this is tractable.

$$X = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{pmatrix} \in \mathbb{R}^{4\times 2}, \qquad y = \begin{pmatrix} 2 \\ 0 \\ 4 \\ 4\end{pmatrix}$$

The first column is all ones; $\theta_0$ is its weight. Rows are examples, columns are features.

Now $X^{\top}X$. Its four entries are exactly the sums you would write by hand:

$$X^{\top}X = \begin{pmatrix} N & \sum x \\ \sum x & \sum x^2 \end{pmatrix} = \begin{pmatrix} 4 & 6 \\ 6 & 14\end{pmatrix}$$

since $\sum x = 0+1+2+3 = 6$ and $\sum x^2 = 0+1+4+9 = 14$. It is symmetric, as $X^{\top}X$ always is.

$$\det(X^{\top}X) = 4\cdot 14 - 6 \cdot 6 = 56 - 36 = \mathbf{20} \ne 0 \ \checkmark$$ $$(X^{\top}X)^{-1} = \frac{1}{20}\begin{pmatrix} 14 & -6 \\ -6 & 4\end{pmatrix} = \begin{pmatrix} 0.7 & -0.3 \\ -0.3 & 0.2 \end{pmatrix}$$

Check the inverse before using it — one multiplication, and it catches every sign slip:

$$\frac{1}{20}\begin{pmatrix} 14 & -6 \\ -6 & 4\end{pmatrix}\begin{pmatrix} 4 & 6 \\ 6 & 14\end{pmatrix} = \frac{1}{20}\begin{pmatrix} 56 - 36 & 84 - 84 \\ -24+24 & -36+56\end{pmatrix} = \frac{1}{20}\begin{pmatrix}20 & 0\\ 0 & 20\end{pmatrix} = I \ \checkmark$$

$$X^{\top}y = \begin{pmatrix} \sum y \\ \sum xy\end{pmatrix} = \begin{pmatrix} 2+0+4+4 \\ 0\cdot2 + 1\cdot 0 + 2\cdot 4 + 3\cdot 4\end{pmatrix} = \begin{pmatrix} 10 \\ 20 \end{pmatrix}$$ $$\theta^{*} = \frac{1}{20}\begin{pmatrix} 14 & -6 \\ -6 & 4\end{pmatrix}\begin{pmatrix}10 \\ 20\end{pmatrix} = \frac{1}{20}\begin{pmatrix} 140 - 120 \\ -60 + 80 \end{pmatrix} = \frac{1}{20}\begin{pmatrix}20\\20\end{pmatrix} = \begin{pmatrix} \mathbf{1} \\ \mathbf{1}\end{pmatrix}$$ $$h(x) = 1 + x$$

Independent cross-check with the scalar with-intercept formulas. $\bar x = 6/4 = 1.5$, $\bar y = 10/4 = 2.5$:

$$\theta_1 = \frac{\sum(x - \bar x)(y - \bar y)}{\sum (x-\bar x)^2} = \frac{(-1.5)(-0.5) + (-0.5)(-2.5) + (0.5)(1.5) + (1.5)(1.5)}{2.25 + 0.25 + 0.25 + 2.25} = \frac{0.75 + 1.25 + 0.75 + 2.25}{5} = \frac{5}{5} = 1$$ $$\theta_0 = \bar y - \theta_1 \bar x = 2.5 - 1(1.5) = 1 \ \checkmark$$

Two completely different routes, same answer. On an exam this is worth the ninety seconds.

Predictions $\hat y = 1 + x$: $\ 1, 2, 3, 4$. Residuals $r^{(i)} = y^{(i)} - \hat y^{(i)}$:

$x$	$y$	$\hat y$	$r = y - \hat y$	$r^2$	$x\,r$
0	2	1	$+1$	1	0
1	0	2	$-2$	4	$-2$
2	4	3	$+1$	1	$+2$
3	4	4	$0$	0	$0$
		sum	0	6	0

$$J(\theta^{*}) = \frac{6}{4} = \frac{3}{2} = \mathbf{1.5}$$

Both stationarity conditions hold, and they are exactly the two rows of $X^{\top}(y - X\theta) = 0$:

• $\sum_i r^{(i)} = 0$ — the ones-column row. This is why the fitted line passes through $(\bar x, \bar y) = (1.5, 2.5)$: indeed $1 + 1.5 = 2.5$ ✓.
• $\sum_i x^{(i)} r^{(i)} = 0$ — the $x$-column row. The residuals are orthogonal to the feature.

This is the geometric content of least squares: $X\theta^{*}$ is the projection of $y$ onto the column space of $X$, so whatever is left over is perpendicular to every column.

(a) $X \in \mathbb{R}^{4\times2}$ with a leading column of ones; $\theta_0$ is the weight on that column.

(b) $X^{\top}X = \begin{pmatrix}4&6\\6&14\end{pmatrix}$, $\det = 20$, $(X^{\top}X)^{-1} = \frac{1}{20}\begin{pmatrix}14&-6\\-6&4\end{pmatrix}$.

(c) $X^{\top}y = (10, 20)^{\top}$ and $\theta^{*} = (1, 1)^{\top}$, i.e. $h(x) = 1 + x$.

(d) Residuals $(+1, -2, +1, 0)$, $J(\theta^{*}) = 6/4 = 1.5$. Both $\sum r = 0$ and $\sum x r = 0$ ✓.

Trap 1 — forgetting the column of ones. Without it you are fitting $h(x) = \theta_1 x$, $X^{\top}X$ becomes the $1\times1$ matrix $(14)$, and you get $\theta_1 = 20/14 = 10/7$ with a much larger risk. If a question says "with an intercept" or writes $\theta_0$, the ones column is mandatory — and if it says "through the origin", it is forbidden.

Trap 2 — the adjugate's signs and positions. $\begin{pmatrix}a&b\\c&d\end{pmatrix}^{-1}$ swaps $a$ and $d$ and negates $b$ and $c$. Swapping $b$ and $c$ as well, or negating $a$ and $d$, are the two standard slips; here the matrix is symmetric so swapping $b,c$ silently does nothing, which makes it a great exam matrix and a terrible one to practise on. Always verify $A^{-1}A = I$.

Trap 3 — multiplying in the wrong order. $\theta^{*} = (X^{\top}X)^{-1}X^{\top}y$, not $X^{\top}y(X^{\top}X)^{-1}$. Shapes rule it out — $(2\times2)(2\times1)$ is the only legal product — so check shapes before you compute.

Trap 4 — residual sign conventions. $y - \hat y$ or $\hat y - y$: squared loss does not care, but the stationarity check $\sum x r = 0$ and anything you say about "over-predicting" do. Fix a convention in writing at the top of your answer.

Three different questions wearing one coat.

• Mechanical: compute a determinant and watch it vanish.
• Conceptual: "not invertible" and "no solution" are different claims. A convex function with a flat valley floor has infinitely many minimisers and no unique one. Distinguish the minimum value (always exists and is unique) from the minimiser (may not be unique).
• Diagnostic: say what causes it, in terms of the columns of $X$, and what to do about it.

Keep the shapes straight: $X \in \mathbb{R}^{3\times2}$, $X^{\top}X \in \mathbb{R}^{2\times2}$.

$$X = \begin{pmatrix} 1 & 2 \\ 2 & 4 \\ 3 & 6\end{pmatrix}, \qquad X^{\top}X = \begin{pmatrix} \sum x_1^2 & \sum x_1x_2 \\ \sum x_1 x_2 & \sum x_2^2 \end{pmatrix}$$ $$\sum x_1^2 = 1 + 4 + 9 = 14, \quad \sum x_1x_2 = 2 + 8 + 18 = 28, \quad \sum x_2^2 = 4 + 16 + 36 = 56$$ $$X^{\top}X = \begin{pmatrix} 14 & 28 \\ 28 & 56\end{pmatrix}, \qquad \det = 14 \cdot 56 - 28 \cdot 28 = 784 - 784 = \mathbf{0}$$

No inverse. Notice the structure: the second column of $X^{\top}X$ is exactly twice the first, inherited from $x_2 = 2x_1$. Also, for later, $X^{\top}y = (1\cdot2 + 2\cdot4 + 3\cdot6,\; 2\cdot2+4\cdot4+6\cdot6)^{\top} = (28, 56)^{\top}$ — itself a multiple of the same direction.

Write the predictions out. For any $\theta$:

$$h(x^{(i)}) = \theta_1 x_1^{(i)} + \theta_2 x_2^{(i)} = \theta_1 x_1^{(i)} + 2\theta_2 x_1^{(i)} = (\theta_1 + 2\theta_2)\,x_1^{(i)}$$

So the model cannot tell $\theta$ apart from $\theta' $ whenever $\theta_1 + 2\theta_2 = \theta_1' + 2\theta_2'$. It only ever sees the single number $k = \theta_1 + 2\theta_2$, and the hypothesis is $h(x) = k\,x_1$. Two parameters, one degree of freedom — this is what rank deficiency is.

Now fit $k$: the data is $y^{(i)} = 2x_1^{(i)}$ exactly $(1\!\to\!2,\ 2\!\to\!4,\ 3\!\to\!6)$, so $k = 2$ gives zero residuals, and the minimum empirical risk is $\mathbf{0}$.

$$\text{argmin} = \{(\theta_1, \theta_2) : \theta_1 + 2\theta_2 = 2\}$$

— an entire line in parameter space. For example $(2, 0)$, $(0, 1)$, $(4, -1)$ and $(\tfrac23, \tfrac23)$ all achieve risk exactly 0 (check $(4,-1)$: $4 - 2 = 2$ ✓). So a minimiser certainly exists; what fails is uniqueness, and with it the inversion step, since $(X^{\top}X)^{-1}$ would have had to name one particular point on that line.

Geometrically: $J$ is a convex paraboloid in $(\theta_1, \theta_2)$ that is a parabola in the direction $(1,2)$ and perfectly flat in the direction $(2,-1)$. A flat valley floor, not a bowl, so no unique bottom.

The practical reading: $\theta_1 = 4,\ \theta_2 = -1$ fits the data perfectly and says "area helps a lot, half-area hurts". That sentence is meaningless, and any interpretation of individual weights under collinearity is meaningless in exactly this way.

$X^{\top}X$ is invertible $\iff$ $\operatorname{rank}(X) = d$ $\iff$ the columns of $X$ are linearly independent.

Here $\operatorname{rank}(X) = 1$: the two columns are parallel, so one direction in feature space is simply absent from the data. $N = 3 \ge d = 2$ is necessary but nowhere near sufficient — $N \ge d$ counts rows, and rank is about columns. The two ways to fail:

• Exact collinearity (this problem): one feature is a linear combination of the others. Duplicated features, unit conversions, a one-hot encoding that keeps all $k$ categories and an intercept (the dummy-variable trap — the $k$ indicator columns sum to the ones column), or an engineered feature like $x_3 = x_1 + x_2$.
• $N < d$: fewer examples than parameters. Then $\operatorname{rank}(X) \le N < d$ and $X^{\top}X$ is singular automatically, with a whole subspace of perfect fits. This is the high-dimensional regime, and it is why a degree-12 polynomial fitted to 10 points has no unique solution.

Near-singular is the case you actually meet: $\det$ tiny rather than exactly 0, so the inverse exists but has huge entries, and $\theta^{*}$ swings wildly on a rounding error in $y$. That instability, not the literal failure to invert, is what collinearity costs you in practice.

$$X^{\top}X + 2I = \begin{pmatrix} 14 + 2 & 28 \\ 28 & 56 + 2\end{pmatrix} = \begin{pmatrix} 16 & 28 \\ 28 & 58\end{pmatrix}$$ $$\det = 16\cdot 58 - 28 \cdot 28 = 928 - 784 = \mathbf{144} \ne 0$$

Invertible. $\ (X^{\top}X + 2I)^{-1} = \dfrac{1}{144}\begin{pmatrix} 58 & -28 \\ -28 & 16\end{pmatrix}$, and with $X^{\top}y = (28,56)^{\top}$:

$$\theta_{\text{ridge}} = \frac{1}{144}\begin{pmatrix}58 & -28\\ -28 & 16\end{pmatrix}\begin{pmatrix}28\\56\end{pmatrix} = \frac{1}{144}\begin{pmatrix} 1624 - 1568 \\ -784 + 896\end{pmatrix} = \frac{1}{144}\begin{pmatrix}56 \\ 112\end{pmatrix} = \begin{pmatrix} 7/18 \\ 7/9 \end{pmatrix}$$

$\theta_{\text{ridge}} \approx (0.389,\ 0.778)$ — a single, unique answer. Three things to read off it:

• $\theta_1 + 2\theta_2 = \frac{7}{18} + \frac{14}{9} = \frac{7 + 28}{18} = \frac{35}{18} \approx 1.944$, slightly less than the unpenalised $2$. Ridge shrinks: it no longer fits the data perfectly, trading a little risk for a unique, small-norm solution.
• Of all the points on the line $\theta_1 + 2\theta_2 = k$, ridge picks the one nearest the origin, which is why the collinear pair ends up sharing the weight ($\theta_2 = 2\theta_1$ here) instead of one taking $+4$ and the other $-1$.
• Adding $\lambda I$ raises every eigenvalue by $\lambda > 0$. Since $X^{\top}X$ is always positive semi-definite, its eigenvalues are $\ge 0$, so they all become $\ge \lambda > 0$ and the matrix is invertible for any dataset at all. This is a guarantee, not a trick that happened to work on these numbers.

(a) $X^{\top}X = \begin{pmatrix}14&28\\28&56\end{pmatrix}$, $\det = 0$.

(b) Minimisers exist but are not unique: every $\theta$ with $\theta_1 + 2\theta_2 = 2$ attains the minimum empirical risk of $0$ — a line in parameter space, e.g. $(2,0)$, $(0,1)$, $(4,-1)$.

(c) Because $\operatorname{rank}(X) = 1 < d = 2$: the columns are linearly dependent ($x_2 = 2x_1$). The condition is that $X^{\top}X$ is invertible iff the columns of $X$ are linearly independent; $N \ge d$ is necessary, not sufficient.

(d) $X^{\top}X + 2I = \begin{pmatrix}16&28\\28&58\end{pmatrix}$ with $\det = 144$, giving the unique $\theta_{\text{ridge}} = (7/18,\ 7/9)^{\top} \approx (0.389, 0.778)$.

Trap 1 — "singular means no solution". It means no unique solution. The empirical risk here is minimised exactly, at infinitely many places. Writing "the problem is infeasible" loses the marks; writing "the minimiser is not unique; the set of minimisers is the line $\theta_1 + 2\theta_2 = 2$" gets all of them.

Trap 2 — "just add more data". Does nothing. Every new row obeys $x_2 = 2x_1$ too, so rank stays 1 no matter how many rows you have. Collinearity is a property of the feature definitions, and the fixes are to drop a feature, combine them, or regularize.

Trap 3 — $N \ge d$ as the invertibility test. It is the condition people remember and it is not the condition. Here $N > d$ and the matrix is still singular. Rank is about columns.

Trap 4 — interpreting weights under collinearity. $(4, -1)$ and $(0,1)$ are equally optimal and tell opposite stories about whether area matters. If two features are nearly collinear, the sign of either weight is noise; that is the honest thing to say about it.

Part (a) is arithmetic; parts (b)–(d) are the reason the problem exists. For a quadratic the update is linear, so it can be solved in closed form and the stability condition read off exactly — no hand-waving about "too big a step".

First, the gradient. $J(w) = 2w^2 \Rightarrow J'(w) = 4w$. So the update is

$$w^{(t)} = w^{(t-1)} - \alpha \cdot 4w^{(t-1)} = (1 - 4\alpha)\,w^{(t-1)}.$$

Everything in this problem follows from that one bracket. Call it the multiplier $\rho = 1 - 4\alpha$. Each step multiplies $w$ by $\rho$ — so convergence is a question about $|\rho|$, and nothing else.

Note it is $4w$, not $2w$: the constant $2$ in $2w^2$ doubles the gradient and therefore halves the usable step sizes. The general rule for $J = cw^2$ is $\rho = 1 - 2\alpha c$, and here $c = 2$.

$\rho = 1 - 4\cdot\tfrac18 = 1 - \tfrac12 = \tfrac12$. Each step halves $w$.

$t$	$w^{(t)}$	$J'(w^{(t)}) = 4w$	$J(w^{(t)}) = 2w^2$
0	$8$	$32$	$128$
1	$8 - \tfrac18(32) = \mathbf{4}$	$16$	$32$
2	$4 - \tfrac18(16) = \mathbf{2}$	$8$	$8$
3	$2 - \tfrac18(8) = \mathbf{1}$	$4$	$2$

Two things to notice, both examinable. The steps get smaller ($4, 2, 1$) even though $\alpha$ never changes, because the gradient itself shrinks as you approach the minimum — gradient descent slows down automatically near a flat region. And $J$ falls by a factor of $\rho^2 = \tfrac14$ per step, not $\rho$: $128 \to 32 \to 8 \to 2$.

(b) Apply the multiplier $t$ times:

$$w^{(t)} = \rho\,w^{(t-1)} = \rho^2 w^{(t-2)} = \dots = (1-4\alpha)^{t}\,w^{(0)}.$$

Check against (a): $(\tfrac12)^3 \cdot 8 = 1$ ✓.

(c) The minimiser is $w^{*} = 0$. So $w^{(t)} \to 0$ for every starting point exactly when $|\rho|^t \to 0$, i.e. when

$$|1 - 4\alpha| < 1 \iff -1 < 1 - 4\alpha < 1 \iff -2 < -4\alpha < 0 \iff \boxed{\;0 < \alpha < \tfrac12\;}$$

Solve both inequalities, not just the right-hand one: $1 - 4\alpha < 1$ gives $\alpha > 0$ and $1 - 4\alpha > -1$ gives $\alpha < \tfrac12$. The upper limit is $1/c$ with $c = 2$, matching the general rule $0 < \alpha < 1/c$ for $J = cw^2$.

The endpoints are excluded, and both are instructive: $\alpha = 0$ never moves, $\alpha = \tfrac12$ oscillates forever at constant $|w|$. Strict inequalities, both ends.

$\alpha$	$\rho = 1-4\alpha$	$w^{(0..3)}$	$J^{(0..3)}$	behaviour
$\tfrac18$	$+\tfrac12$	$8, 4, 2, 1$	$128, 32, 8, 2$	monotone convergence, one side
$\tfrac14$	$0$	$8, 0, 0, 0$	$128, 0, 0, 0$	exact minimum in one step
$\tfrac12$	$-1$	$8, -8, 8, -8$	$128, 128, 128, 128$	oscillates forever, no progress
$\tfrac34$	$-2$	$8, -16, 32, -64$	$128, 512, 2048, 8192$	diverges, alternating sign

$\alpha = \tfrac14$ gives $\rho = 0$: one step lands exactly on $w^{*} = 0$. For a one-dimensional quadratic the perfect step size is $\alpha = \frac{1}{2c} = \frac{1}{J''}$ — which is Newton's method, and the reason second-order methods exist.

$\alpha = \tfrac12$ sits exactly on the boundary. $|\rho| = 1$, so $|w|$ is preserved exactly: it ping-pongs between $8$ and $-8$ with $J = 128$ every single iteration. Not divergence, but no convergence either — which is why the range is open at $\tfrac12$.

$\alpha = \tfrac34$ overshoots past the minimum by more than it started: each step doubles $|w|$ and flips its sign. $J$ quadruples per iteration. This is the failure mode you see in practice as a loss curve that climbs to infinity or NaN within a few steps, and the fix is always the same: lower $\alpha$.

(a) $w^{(1)} = 4$, $w^{(2)} = 2$, $w^{(3)} = 1$, with $J = 32, 8, 2$ (from $J(8) = 128$).

(b) $w^{(t)} = (1 - 4\alpha)^t\,w^{(0)}$.

(c) $|1-4\alpha| < 1 \iff 0 < \alpha < \tfrac12$.

(d) $\alpha = \tfrac14$: lands on $w^{*} = 0$ in one step. $\alpha = \tfrac12$: oscillates $8, -8, 8, -8$ with $J$ stuck at 128. $\alpha = \tfrac34$: diverges as $8, -16, 32, -64$, with $J$ quadrupling each step.

Trap 1 — differentiating $2w^2$ as $2w$. Then $\rho = 1 - 2\alpha$, you get $w^{(1)} = 6$ at $\alpha = \tfrac18$, and the convergence range comes out as $0 < \alpha < 1$ — double the truth. The leading constant on the quadratic is there precisely to catch this, and it is the single most common error in the topic.

Trap 2 — solving only one half of $|1-4\alpha| < 1$. Dropping the absolute value gives $\alpha < 0$ or some other nonsense. Expand it into the two-sided inequality and solve both ends.

Trap 3 — "a bigger $\alpha$ is always faster". False in both directions: $\alpha = \tfrac14$ beats $\alpha = \tfrac18$ (one step versus infinitely many), and $\alpha = \tfrac12$ is worse than both while being bigger still. Speed is governed by $|\rho|$, which is $0$ in the middle of the range and rises toward $1$ at both ends.

Trap 4 — expecting to reach $w^{*}$ exactly. At $\alpha = \tfrac18$ the iterates are $8, 4, 2, 1, \tfrac12, \dots$ — they halve forever and never equal 0. Gradient descent converges in the limit; you stop on a tolerance or an iteration budget. Writing "$w^{(3)} = 0$" because "it converges" is answering a different question.

Mostly: can you keep the shapes straight, and do you know why the identity has $A + A^{\top}$ in it rather than $2A$?

Shapes first. $\theta \in \mathbb{R}^2$, $A \in \mathbb{R}^{2\times2}$, so $\theta^{\top}A\theta$ is $(1\times2)(2\times2)(2\times1) = 1\times1$ — a scalar. Its gradient has the same shape as $\theta$, so $\nabla_\theta J \in \mathbb{R}^2$ — a column vector, in the denominator-layout convention these notes use. If you produce a matrix, you have made an error of kind, not of arithmetic.

And compute $A\theta$ once; (a), (b) and (d) all reuse it.

$$A\theta = \begin{pmatrix}2 & 4\\0&3\end{pmatrix}\begin{pmatrix}1\\2\end{pmatrix} = \begin{pmatrix}2(1) + 4(2) \\ 0(1) + 3(2)\end{pmatrix} = \begin{pmatrix}10 \\ 6\end{pmatrix}$$ $$J(\theta) = \theta^{\top}(A\theta) = (1)(10) + (2)(6) = 10 + 12 = \mathbf{22}$$

(b) Build $A^{\top}$ by reflecting across the diagonal, then add:

$$A^{\top} = \begin{pmatrix}2 & 0\\4&3\end{pmatrix}, \qquad A + A^{\top} = \begin{pmatrix}4 & 4\\4&6\end{pmatrix}$$

($A + A^{\top}$ is always symmetric — a useful check before you multiply.)

$$\nabla_\theta J = (A+A^{\top})\theta = \begin{pmatrix}4&4\\4&6\end{pmatrix}\begin{pmatrix}1\\2\end{pmatrix} = \begin{pmatrix}4 + 8 \\ 4 + 12\end{pmatrix} = \begin{pmatrix}\mathbf{12} \\ \mathbf{16}\end{pmatrix}$$

Expand the quadratic form symbolically. In general $\theta^{\top}A\theta = \sum_{i}\sum_{j} A_{ij}\theta_i\theta_j$, so here

$$J = A_{11}\theta_1^2 + A_{12}\theta_1\theta_2 + A_{21}\theta_2\theta_1 + A_{22}\theta_2^2 = 2\theta_1^2 + 4\theta_1\theta_2 + 0 + 3\theta_2^2$$

Sanity check at $\theta = (1,2)$: $2(1) + 4(2) + 3(4) = 2 + 8 + 12 = 22$ ✓ — matches (a).

$$\frac{\partial J}{\partial \theta_1} = 4\theta_1 + 4\theta_2 = 4(1) + 4(2) = 12 \ \checkmark$$ $$\frac{\partial J}{\partial \theta_2} = 4\theta_1 + 6\theta_2 = 4(1) + 6(2) = 16 \ \checkmark$$

And now you can see where $A + A^{\top}$ comes from. The cross terms $A_{12}\theta_1\theta_2$ and $A_{21}\theta_2\theta_1$ are the same monomial, so only the sum $A_{12} + A_{21} = 4 + 0 = 4$ ever appears in $J$. The function cannot distinguish $A$ from its symmetric part $\frac12(A + A^{\top})$, so the derivative can only depend on $A + A^{\top}$.

(d) $2A\theta = 2\begin{pmatrix}10\\6\end{pmatrix} = \begin{pmatrix}20\\12\end{pmatrix}$ — not $(12, 16)^{\top}$. Both components are wrong, and the first is wrong by a lot.

$2A\theta$ is correct exactly when $A = A^{\top}$, because then $A + A^{\top} = 2A$. Our $A$ has $A_{12} = 4$ and $A_{21} = 0$, so it is not symmetric and the shortcut fails. It is a safe shortcut in the one place it is used most — $X^{\top}X$ in the normal equations is symmetric by construction, giving $\nabla_\theta(\theta^{\top}X^{\top}X\theta) = 2X^{\top}X\theta$ — and that is precisely why people reach for it when it does not apply.

(e) One step with $\alpha = \tfrac14$:

$$\theta^{(1)} = \theta - \alpha\nabla_\theta J = \begin{pmatrix}1\\2\end{pmatrix} - \tfrac14\begin{pmatrix}12\\16\end{pmatrix} = \begin{pmatrix}1 - 3\\ 2 - 4\end{pmatrix} = \begin{pmatrix}\mathbf{-2}\\ \mathbf{-2}\end{pmatrix}$$

Both coordinates update simultaneously, from the same old $\theta$. Do not feed the new $\theta_1$ into the computation of $\theta_2$ — that is a different algorithm (coordinate descent).

Worth noticing: $J(-2,-2) = 2(4) + 4(4) + 3(4) = 8 + 16 + 12 = 36 > 22$. The step made things worse, because $\alpha = \tfrac14$ is too large here and because this $J$ is not even bounded below — $A$'s symmetric part $\begin{pmatrix}2&2\\2&3\end{pmatrix}$ happens to be positive definite ($\det = 2 > 0$, trace $> 0$), so $J \ge 0$ with its minimum at the origin, and $\theta = (-2,-2)$ overshot straight past it. A step can increase the objective; that is information about $\alpha$, not a mistake in the gradient.

(a) $J(\theta) = 22$.   (b) $\nabla_\theta J = (A+A^{\top})\theta = \begin{pmatrix}4&4\\4&6\end{pmatrix}\begin{pmatrix}1\\2\end{pmatrix} = (12, 16)^{\top}$.

(c) $J = 2\theta_1^2 + 4\theta_1\theta_2 + 3\theta_2^2$, so $\partial J/\partial\theta_1 = 4\theta_1 + 4\theta_2 = 12$ and $\partial J/\partial\theta_2 = 4\theta_1 + 6\theta_2 = 16$ ✓.

(d) $2A\theta = (20, 12)^{\top}$, which is wrong. It is valid only for symmetric $A$.

(e) $\theta^{(1)} = (-2, -2)^{\top}$, at which $J = 36$ — an increase, because $\alpha = \tfrac14$ overshoots.

The trap is the non-symmetric $A$. Every quadratic form you meet in linear regression is built from $X^{\top}X$, which is symmetric, so $2A\theta$ works every time you have practised it. The exam hands you an $A$ with a zero in one off-diagonal slot, which is a deliberate flag: $A_{12} \ne A_{21}$ means you must use $A + A^{\top}$.

Second trap — transposing wrongly, or forgetting the $\theta$. $A + A^{\top}$ is a matrix, not the gradient. The gradient is that matrix times $\theta$. Reporting $\begin{pmatrix}4&4\\4&6\end{pmatrix}$ as "the gradient" is a shape error.

Third trap — updating coordinates sequentially. Gradient descent evaluates the whole gradient at $\theta^{(t-1)}$ and then moves. Using the freshly-updated $\theta_1$ when computing $\theta_2$ gives $(-2, -3)$ here, which is Gauss–Seidel-style coordinate descent, not gradient descent.

Fourth trap — assuming $J$ must decrease. Descent is only guaranteed for small enough $\alpha$. Seeing $J$ rise from 22 to 36 is the diagnostic from Problem 23 appearing in two dimensions.

The distinction is exactly one thing — how many examples contribute to each step:

$$\textbf{batch: } \ w \leftarrow w - \alpha\,\nabla J(w) = w - \alpha\cdot\frac{2}{N}\sum_{i=1}^{N}(wx^{(i)} - y^{(i)})x^{(i)}$$ $$\textbf{SGD: } \ w \leftarrow w - \alpha\,\ell_j'(w) = w - \alpha\cdot 2(wx^{(j)} - y^{(j)})x^{(j)} \quad \text{for one } j$$

Note the $\frac1N$: the batch gradient is an average of per-example gradients, which is why a batch step is not the same size as a typical SGD step even with the same $\alpha$. Four SGD steps are one epoch, not one step — the fair comparison in (b)–(d) is one batch step against one epoch of SGD, which costs the same arithmetic.

Compute the per-example gradients fresh at each SGD step, because $w$ has already moved.

$$\sum x y = 1(2) + 1(0) + 2(2) + 2(6) = 2 + 0 + 4 + 12 = 18, \qquad \sum x^2 = 1 + 1 + 4 + 4 = 10$$ $$w^{*} = \frac{18}{10} = \mathbf{1.8}$$

$J(1.8)$: predictions $1.8, 1.8, 3.6, 3.6$, residuals $-0.2, +1.8, +1.6, -2.4$, squares $0.04, 3.24, 2.56, 5.76$, total $11.6$:

$$J(w^{*}) = \tfrac{11.6}{4} = \mathbf{2.9}$$

$J(0)$: residuals are just $-y$, giving $4 + 0 + 4 + 36 = 44$, so $J(0) = \tfrac{44}{4} = \mathbf{11}$.

Note that the best achievable risk is $2.9$, not $0$ — the two points at $x = 2$ have $y = 2$ and $y = 6$, so no function of $x$ alone can fit both. Keep $2.9$ in mind as the floor; it is what makes the later numbers interpretable.

$$\nabla J(0) = \frac{2}{4}\sum_i (0\cdot x^{(i)} - y^{(i)})x^{(i)} = \frac12\Big[(-2)(1) + (0)(1) + (-2)(2) + (-6)(2)\Big] = \frac12(-2 - 0 - 4 - 12) = \frac{-18}{2} = -9$$ $$w^{(1)} = 0 - \tfrac14(-9) = \mathbf{2.25}$$

$J(2.25)$: predictions $2.25, 2.25, 4.5, 4.5$, residuals $0.25, 2.25, 2.5, -1.5$, squares $0.0625 + 5.0625 + 6.25 + 2.25 = 13.625$:

$$J(2.25) = \tfrac{13.625}{4} = \mathbf{3.40625}$$

One step took $J$ from $11$ down to $3.41$, against a floor of $2.9$. It slightly overshot $w^{*} = 1.8$ (landing at $2.25$) but the direction was unambiguous: a batch gradient is the average over all four examples, so no single point can hijack it.

Order $1,2,3,4$. Each step uses $\ell_j'(w) = 2(wx_j - y_j)x_j$ and $\alpha = \tfrac14$, so $w \leftarrow w - \tfrac12(wx_j - y_j)x_j$.

step	$(x_j, y_j)$	$w$ before	$\ell_j'$	$w$ after
1	$(1,2)$	$0$	$2(0-2)(1) = -4$	$0 + 1 = 1$
2	$(1,0)$	$1$	$2(1-0)(1) = +2$	$1 - 0.5 = 0.5$
3	$(2,2)$	$0.5$	$2(1-2)(2) = -4$	$0.5 + 1 = 1.5$
4	$(2,6)$	$1.5$	$2(3-6)(2) = -12$	$1.5 + 3 = \mathbf{4.5}$

$J(4.5)$: predictions $4.5, 4.5, 9, 9$, residuals $2.5, 4.5, 7, 3$, squares $6.25 + 20.25 + 49 + 9 = 84.5$, so $J = \mathbf{21.125}$ — worse than where it started ($J(0) = 11$). After three sensible steps that hovered near $w^{*}$, the fourth example ($x=2, y=6$, the one no line can fit) produced a gradient of $-12$ and threw $w$ to $4.5$.

Order $4,1,2,3$. Same four examples, same $\alpha$, same start.

step	$(x_j, y_j)$	$w$ before	$\ell_j'$	$w$ after
1	$(2,6)$	$0$	$2(0-6)(2) = -24$	$0 + 6 = 6$
2	$(1,2)$	$6$	$2(6-2)(1) = +8$	$6 - 2 = 4$
3	$(1,0)$	$4$	$2(4-0)(1) = +8$	$4 - 2 = 2$
4	$(2,2)$	$2$	$2(4-2)(2) = +8$	$2 - 2 = \mathbf{0}$

It ends at $w = 0$, exactly back at the start, with $J = \mathbf{11}$.

run	final $w$	final $J$
batch, 1 step	$2.25$	$3.40625$
SGD, order $1,2,3,4$	$4.5$	$21.125$
SGD, order $4,1,2,3$	$0$	$11$
optimum	$1.8$	$2.9$

Identical data, identical $\alpha$, identical arithmetic cost — and three completely different answers. SGD's iterates depend on the order of the examples; batch's do not. That is the variance the "S" refers to, and it is why SGD needs a smaller $\alpha$ than batch (or a decaying one, e.g. $\alpha_t = 1/\sqrt{t}$), and why you quote the average of recent iterates rather than the last one.

One per-example gradient $(\hat y^{(i)} - y^{(i)})\,x^{(i)}$ costs $O(d)$ — here about $50$ multiply-adds. A batch gradient averages $N$ of them: $O(Nd) = 10^6 \times 50 = 5\times10^{7}$ operations per single update to $\theta$.

$$\frac{\text{cost of one batch step}}{\text{cost of one SGD step}} = \frac{Nd}{d} = N = \mathbf{10^6}$$

So in the time batch takes to move $\theta$ once, SGD moves it a million times. Even if each of those steps is in a mildly wrong direction, a million mediocre steps beat one perfect one by a wide margin, and that — not any statistical subtlety — is why large-scale learning uses SGD.

	Batch GD	SGD
cost per update	$O(Nd)$	$O(d)$
gradient direction	exact $\nabla J$; descent guaranteed for small $\alpha$	unbiased estimate of $\nabla J$; individual steps may increase $J$
trajectory	deterministic, smooth	noisy; depends on the ordering (see (c) vs (d))
usable $\alpha$	larger	smaller, usually decayed
memory	needs the whole dataset per step	one example at a time — works on a stream
near the optimum	settles	keeps rattling in a noise ball of radius $\propto \alpha$

"Unbiased" is the precise statement that rescues SGD: picking $j$ uniformly gives $\mathbb{E}_j[\ell_j'(w)] = \frac1N\sum_i \ell_i'(w) \propto \nabla J(w)$. On average SGD moves downhill, which is why it works at all despite runs like (c). Mini-batching (say 32 examples per step) averages 32 per-example gradients instead of $10^6$, buying most of the noise reduction at $32/N$ of the cost of a full batch step — which is what everyone actually does.

(a) $w^{*} = 18/10 = 1.8$, $J(w^{*}) = 2.9$, $J(0) = 11$.

(b) $\nabla J(0) = -9$, so $w^{(1)} = 2.25$ with $J = 3.40625$.

(c) $w$ goes $0 \to 1 \to 0.5 \to 1.5 \to 4.5$; final $J = 21.125$, worse than the start.

(d) In the order $4,1,2,3$: $0 \to 6 \to 4 \to 2 \to 0$; final $J = 11$. Same cost, same data, different answer — SGD is order-dependent and batch is not.

(e) $Nd/d = N = 10^6$ SGD updates per batch update. Batch gives exact directions at $O(Nd)$ per step; SGD gives noisy directions at $O(d)$ per step and wins on wall-clock whenever $N$ is large, at the price of needing a smaller, usually decaying $\alpha$.

Trap 1 — the missing $\frac1N$. $J$ here is defined with $\frac14$, so the batch gradient carries $\frac{2}{4}$ and comes out as $-9$, not $-36$. Forget it and your batch step is four times too big ($w^{(1)} = 9$), which makes batch look wildly unstable and inverts the entire conclusion. Read the definition of $J$ in the question, every time.

Trap 2 — comparing one batch step to one SGD step. That comparison is rigged, because a batch step costs $N$ times more. Compare per unit of arithmetic: one batch step versus one epoch of $N$ SGD steps — which is exactly what (b) versus (c) does.

Trap 3 — reusing a stale $w$ inside the epoch. SGD updates $w$ after every single example. Computing all four per-example gradients at $w = 0$ and applying them one after another is just a batch step with the wrong scaling; the four gradients at $w=0$ are $-4, 0, -8, -24$, so you would land at $w = 0 + 1 + 0 + 2 + 6 = 9$ — a different algorithm with a very different answer. Recompute the residual from the current $w$ at every step.

Trap 4 — "SGD is worse because $J$ went up". SGD's noise is not purely a cost: on a non-convex objective it can jump out of a poor local minimum, which batch cannot. On a convex objective like this one there is nothing to escape, so the noise is pure cost and smaller steps are pure gain. Say which regime you are in before judging it.

$\phi : \mathbb{R}^{K} \to \mathbb{R}^{M}$ takes the $K$ original features of one example and returns the $M$ features you actually regress on. The rule for reading it off a hypothesis is mechanical:

Each $\theta_j$ in the hypothesis multiplies exactly one entry of $\phi(x)$ — so list the things the $\theta$s multiply, in order. A bare $\theta_0$ with nothing attached multiplies the constant $1$, so $\phi$ starts with a $1$; that is where the bias column comes from.

Then $\Phi \in \mathbb{R}^{N \times M}$, with row $i$ equal to $\phi(x^{(i)})^{\top}$ — one row per example, one column per produced feature. $N$ never changes under feature engineering; $M$ does.

(a) The four $\theta$s multiply $1$, $x$, $x^3$ and $\sin x$:

$$\phi(x) = \begin{pmatrix} 1 \\ x \\ x^3 \\ \sin x\end{pmatrix} \in \mathbb{R}^{4}, \qquad M = 4, \qquad \Phi \in \mathbb{R}^{12 \times 4}$$

There is no $x^2$ term, so there is no $x^2$ entry. $\phi$ is read off the hypothesis you were given, not off a template for "the degree-3 polynomial".

(b) The monomials in $x_1, x_2$ of total degree $\le 2$ are $1$; $x_1, x_2$; $x_1^2, x_1x_2, x_2^2$:

$$\phi(x_1,x_2) = \begin{pmatrix} 1 \\ x_1 \\ x_2 \\ x_1^2 \\ x_1x_2 \\ x_2^2\end{pmatrix} \in \mathbb{R}^{6}, \qquad M = \mathbf{6}, \qquad \Phi \in \mathbb{R}^{50\times 6}$$ $$h(x) = \theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_1^2 + \theta_4x_1x_2 + \theta_5x_2^2$$

The cross term $x_1x_2$ is the one people drop, and it is the only one that lets the model represent an interaction — the whole reason to go to degree 2 with more than one feature.

(c) With $x_1 = 2$, $x_2 = 3$: $\ x_1^2 = 4$, $x_1x_2 = 6$, $x_2^2 = 9$.

$$\phi(2,3)^{\top} = \begin{pmatrix} 1 & 2 & 3 & 4 & 6 & 9\end{pmatrix}$$

Six numbers in one row of $\Phi$, from an example that arrived as two numbers.

(d) Identical to the normal equations with $X$ replaced by $\Phi$:

$$\theta^{*} = (\Phi^{\top}\Phi)^{-1}\Phi^{\top}y, \qquad \Phi^{\top}\Phi \in \mathbb{R}^{6\times6}$$

And yes, the model is still linear — linear in $\theta$, which is the only linearity least squares ever required. $h$ is a curved, quadratic surface in $x$; it is a flat, linear function of the parameters. Every result from Section 7 carries over unchanged: the same closed form, the same convexity, the same singularity condition (now on the columns of $\Phi$).

That last point matters: engineered features collide easily. Add $x_3 = x_1 + x_2$ to $\phi$ and $\Phi$ is instantly rank-deficient, exactly as in Problem 22.

The monomials of degree $\le D$ in $K$ variables number $\binom{D + K}{K}$. With $K = 2$:

$$M = \binom{D+2}{2} = \frac{(D+1)(D+2)}{2}$$

Check at $D = 2$: $\frac{3 \cdot 4}{2} = 6$ ✓ — matches the six entries we listed. At $D = 3$:

$$M = \frac{4 \cdot 5}{2} = \mathbf{10}$$

namely $1$; $x_1, x_2$; $x_1^2, x_1x_2, x_2^2$; $x_1^3, x_1^2x_2, x_1x_2^2, x_2^3$. Count them: $1 + 2 + 3 + 4 = 10$ ✓.

This growth is the whole problem with polynomial features. At $K = 10$ original features, degree 2 already gives $\binom{12}{2} = 66$ features and degree 3 gives $\binom{13}{3} = 286$. More features means a richer hypothesis class, which means a better training fit and, past some point, worse generalization — which is Problem 27.

(a) $\phi(x) = (1,\ x,\ x^3,\ \sin x)^{\top}$, $M = 4$, $\Phi \in \mathbb{R}^{12\times4}$.

(b) $\phi(x) = (1,\ x_1,\ x_2,\ x_1^2,\ x_1x_2,\ x_2^2)^{\top}$, $M = 6$, $\Phi \in \mathbb{R}^{50\times6}$.

(c) $(1,\ 2,\ 3,\ 4,\ 6,\ 9)$.

(d) $\theta^{*} = (\Phi^{\top}\Phi)^{-1}\Phi^{\top}y$. The model is linear in $\theta$ (not in $x$), which is all least squares needs.

(e) $\binom{D+2}{2} = \frac{(D+1)(D+2)}{2}$; at $D=3$ that is $10$.

Trap 1 — dropping the leading 1. Then $M = 3$ in (a) and the model is forced through the origin. The bias is a feature that is constantly 1; it has to be in $\phi$ or there is nothing for $\theta_0$ to multiply.

Trap 2 — dropping the cross term. "Degree 2 in two variables" is six terms, not five and not four. If the question says "full" or "including interactions", the cross term is being checked explicitly.

Trap 3 — writing $\Phi \in \mathbb{R}^{M \times N}$. Rows are examples. $\Phi$ is tall and thin when $N > M$, which is the regime you want. Get this backwards and every subsequent matrix product is ill-shaped.

Trap 4 — "this is nonlinear regression". It is linear regression on nonlinear features. The distinction is not pedantry: it is exactly why you still get a closed form and a convex objective, and it is a one-line short-answer question that appears on these exams verbatim.

Two numbers per model, and they answer two different questions. Read them in this order, every time:

1. Is the training error high? If yes, the model cannot even fit what it has seen — underfitting (high bias). Nothing about test error is needed to diagnose this.
2. Is the gap (test $-$ train) large? If yes, it fitted the training set in ways that do not generalise — overfitting (high variance).

"High" and "large" are relative to the other rows and to the noise floor you believe is in the data; here the columns span $0.00$ to $1.84$, so the comparisons are not close.

The two failures are independent. A model can be both (high train error and a big gap) and the best model is the one that is neither.

Model	train	test	gap	diagnosis
$A$	$0.42$	$0.45$	$0.03$	underfitting. Train error is the highest of all five and the gap is tiny — it is equally bad everywhere, which is the signature of a class too small to contain the truth.
$B$	$0.08$	$0.11$	$0.03$	good fit. Low train error and a small gap. This is what you are aiming for.
$C$	$0.01$	$0.63$	$0.62$	overfitting. Train error improved from $B$ by $0.07$ and test error got worse by $0.52$.
$D$	$0.00$	$1.84$	$1.84$	overfitting, severely. Perfect on the training set, four times worse than $A$ on test — $A$ being the model that could barely fit anything.

$A$ and $B$ have the same gap, $0.03$. The gap alone cannot distinguish them; it is the train level that says $A$ is underfitting. You genuinely need both numbers.

(b) Ship $B$ — the lowest test error, $0.11$.

The lowest training error belongs to $D$, at $0.00$, which is the worst model in the table by the only measure that matters. They are different questions because training error measures how well you fitted data you have already seen, and no amount of it is evidence about data you have not. Training error is monotonically non-increasing in model capacity, so "minimise training error over model classes" always selects the largest class — it is not a model selection criterion at all.

One caveat that is itself examinable: once you have used this test set to pick $B$, it is no longer an unbiased estimate of $B$'s risk. Hyperparameters are supposed to be chosen on a validation set, which is Problem 30.

(c) $0.00$ means the degree-15 polynomial interpolated the training data — it passed through every point exactly, noise included. It is not good news, it is the definition of the failure: the model had enough free parameters to memorise, so it memorised, including the part of each $y$ that was random and will not repeat. A model whose training error is exactly zero should always be treated as a suspect rather than an achievement.

And note what training error could not tell you: across $A \to D$ it falls monotonically $0.42 \to 0.08 \to 0.01 \to 0.00$ and never once hints that anything went wrong. Overfitting is invisible without held-out data. That is the entire argument for having a test set.

(d) $E$ is degree 3 — the same hypothesis class as $B$, which was fine — but trained on 20 examples instead of 200. Train $0.03$, test $0.37$: a gap of $0.34$. That is overfitting caused by data scarcity, not by model capacity. With 20 points a degree-3 polynomial has plenty of freedom to chase noise.

The fix that does not change the model: get more training data. Going back to the full 200 examples is model $B$, with test error $0.11$. More data shrinks the gap without touching the hypothesis class, which is the one lever that costs you nothing in bias.

This is why "overfitting" is not a property of a model. It is a property of a model and a sample size. The same degree-3 polynomial overfits at $N=20$ and fits well at $N=200$.

(e)

	Underfitting (like $A$)	Overfitting (like $C$, $D$, $E$)
symptom	train error high, gap small	train error low, gap large
cause	hypothesis class too small	class too large for the data available
do this	add capacity: raise the degree, add features or interactions, grow the tree	remove capacity or add data: lower the degree, regularize (raise $\lambda$), prune the tree, or collect more examples
do NOT do this	add more data — it will not help; the class cannot represent the truth at any $N$	add more features — it makes the gap worse

The "do NOT" row is the useful half. More data is the standard reflex and it is useless against underfitting: model $A$ with 20,000 examples still has train error near $0.42$, because a line fitted to a curve is wrong no matter how much of the curve you show it.

(a) $A$ underfits (highest train error, tiny gap); $B$ is a good fit (low train, small gap); $C$ overfits (gap $0.62$); $D$ overfits severely (gap $1.84$).

(b) Ship $B$, test MSE $0.11$. $D$ has the lowest training error ($0.00$) and the worst test error — training error is non-increasing in capacity and therefore cannot select a model.

(c) It interpolated the training set, fitting the noise. Bad news, and invisible to training error alone.

(d) Overfitting from too few examples, not too much capacity. Fix: more training data — at $N = 200$ this same model is $B$.

(e) Underfitting $\to$ add capacity (more features, higher degree, less regularization). Overfitting $\to$ reduce capacity or add data (lower degree, larger $\lambda$, more examples).

Trap 1 — diagnosing from the gap alone. $A$ and $B$ both have a gap of $0.03$ and are opposite diagnoses. Always report the train level and the gap.

Trap 2 — "high test error means overfitting". No: $A$ has the second-highest test error in the table and is underfitting. High test error with equally high training error is underfitting, and the prescriptions are opposite — so this misdiagnosis sends you to add regularization to a model that needed more capacity.

Trap 3 — model $E$. It is in the table to break the reflex "overfitting $\Rightarrow$ reduce the degree". Reducing $E$'s degree would make it underfit as well. The variable that changed was $N$.

Trap 4 — picking by training error. $D$ wins on training error and loses on everything else. Any question of the form "which model would you deploy" is checking whether you look at the held-out column.

Three stages, strictly in order, because each feeds the next: a score $z = \theta^{\top}x$ (any real number), a probability $h = \sigma(z) \in (0,1)$, and a loss built from that probability. Then one gradient step.

The gradient formula is given, and it is worth staring at: $\nabla_\theta J = \frac1N\sum_i (h^{(i)} - y^{(i)})x^{(i)}$. The bracket is the residual — predicted probability minus actual label — and it is exactly the same shape as linear regression's gradient. No $\sigma'$ appears anywhere, because the derivative of the sigmoid and the derivative of the logarithm cancel. That cancellation is the reason cross-entropy is the loss of choice here.

Shapes: $z$ is a scalar per example, $h$ is a scalar per example, $\nabla_\theta J \in \mathbb{R}^3$ — same shape as $\theta$, because each term is a scalar times $x^{(i)} \in \mathbb{R}^3$.

$$z^{(1)} = \theta^{\top}x^{(1)} = (0)(1) + (1)(2) + (-1)(1) = 0 + 2 - 1 = \mathbf{1}$$ $$z^{(2)} = \theta^{\top}x^{(2)} = (0)(1) + (1)(1) + (-1)(2) = 0 + 1 - 2 = \mathbf{-1}$$ $$h^{(1)} = \sigma(1) = \mathbf{0.731}, \qquad h^{(2)} = \sigma(-1) = \mathbf{0.269}$$

Consistency check: $0.731 + 0.269 = 1.000$ ✓, as $\sigma(-z) = 1 - \sigma(z)$ demands.

Only one of the two terms survives per example, because $y$ is 0 or 1.

Example 1, $y = 1$: the loss is $-\ln h$:

$$\ell^{(1)} = -\ln(0.731) = \mathbf{0.313}$$

Example 2, $y = 0$: the loss is $-\ln(1 - h)$, and $1 - 0.269 = 0.731$:

$$\ell^{(2)} = -\ln(1 - 0.269) = -\ln(0.731) = \mathbf{0.313}$$ $$J(\theta) = \frac{0.313 + 0.313}{2} = \mathbf{0.313}$$

Both examples cost the same, which the figure explains: each is the same distance on the correct side of the boundary. For scale, a model that said $0.5$ for everything would score $-\ln(0.5) = \ln 2 = 0.693$, so $0.313$ is genuinely better than knowing nothing — a comparison always worth making, since cross-entropy has no natural units.

Note which probability goes inside the log: for $y = 0$ it is $1 - h$, the probability the model assigns to the true class. In both cases the loss is $-\ln P(\text{correct class})$, which is the whole content of cross-entropy and much easier to remember than the two-term formula.

Residuals first:

$$h^{(1)} - y^{(1)} = 0.731 - 1 = -0.269, \qquad h^{(2)} - y^{(2)} = 0.269 - 0 = +0.269$$

Equal and opposite — again the symmetry. Now weight each $x^{(i)}$ by its residual and average:

$$\nabla_\theta J = \frac12\left[(-0.269)\begin{pmatrix}1\\2\\1\end{pmatrix} + (0.269)\begin{pmatrix}1\\1\\2\end{pmatrix}\right] = \frac{0.269}{2}\left[\begin{pmatrix}-1\\-2\\-1\end{pmatrix} + \begin{pmatrix}1\\1\\2\end{pmatrix}\right] = \frac{0.269}{2}\begin{pmatrix}0\\-1\\1\end{pmatrix}$$ $$\nabla_\theta J = \begin{pmatrix}\mathbf{0} \\ \mathbf{-0.1345} \\ \mathbf{+0.1345}\end{pmatrix}$$

The bias component is exactly zero, and that is not a coincidence: the bias feature is $1$ for every example, so its gradient component is the plain average of the residuals, $\frac12(-0.269 + 0.269) = 0$. One example is under-predicted by as much as the other is over-predicted, so there is no pressure to shift the whole boundary — only to rotate it.

(d) With $\alpha = 1$:

$$\theta^{(1)} = \theta - 1\cdot\nabla_\theta J = \begin{pmatrix}0\\1\\-1\end{pmatrix} - \begin{pmatrix}0\\-0.1345\\0.1345\end{pmatrix} = \begin{pmatrix}\mathbf{0}\\ \mathbf{1.1345}\\ \mathbf{-1.1345}\end{pmatrix}$$ $$z^{(1)}_{\text{new}} = 0 + 2(1.1345) - 1.1345 = \mathbf{+1.1345}, \qquad z^{(2)}_{\text{new}} = 0 + 1.1345 - 2(1.1345) = \mathbf{-1.1345}$$

$J$ went down, and you can say so without evaluating a single logarithm. Example 1 is a positive whose score rose from $1$ to $1.1345$, so $h^{(1)}$ rose and $-\ln h^{(1)}$ fell. Example 2 is a negative whose score fell from $-1$ to $-1.1345$, so $h^{(2)}$ fell and $-\ln(1-h^{(2)})$ fell too. Both terms decreased, so the average decreased. (For the record: $J$ goes from $0.313262$ to $0.278837$.)

Each example moved further onto its own correct side. That is what the gradient step did: it steepened the boundary rather than moving it, exactly as the zero bias component predicted.

(e) Threshold $0.5$ on $h$ is the same as threshold $0$ on $z$, since $\sigma$ is increasing and $\sigma(0) = 0.5$. So:

• Example 1: $h = 0.731 > 0.5 \Rightarrow \hat y = 1$, and $y = 1$ ✓ correct.
• Example 2: $h = 0.269 < 0.5 \Rightarrow \hat y = 0$, and $y = 0$ ✓ correct.

Both correct — zero-one loss is $0/2 = 0$ — while cross-entropy is still $0.313$. Cross-entropy keeps pushing after the classification is already right, because it scores confidence, not correctness; that is precisely why it is differentiable and usable, and why zero-one loss is not.

Odds. Logistic regression is linear in the log-odds:

$$\ln\frac{h}{1-h} = \theta^{\top}x = z \qquad\Longrightarrow\qquad \frac{h^{(1)}}{1 - h^{(1)}} = e^{z^{(1)}} = e^{1} \approx 2.718$$

Check it directly: $0.731/0.269 = 2.717$, matching $e \approx 2.718$ up to the rounding in the given $\sigma$ values ✓. Example 1 is about $2.7$ times more likely positive than negative.

$i$	$z$	$h = \sigma(z)$	$y$	$\ell$	$h - y$
1	$+1$	$0.731$	1	$0.313$	$-0.269$
2	$-1$	$0.269$	0	$0.313$	$+0.269$

(b) $J(\theta) = 0.313$.   (c) $\nabla_\theta J = (0,\ -0.1345,\ +0.1345)^{\top}$.

(d) $\theta^{(1)} = (0,\ 1.1345,\ -1.1345)^{\top}$; new scores $+1.1345$ and $-1.1345$; $J$ decreased (to $0.2788$) because each example moved further onto its correct side.

(e) Both predicted correctly at threshold $0.5$; the odds for example 1 are $e^{1} \approx 2.718$ to 1.

Trap 1 — inserting a $\sigma'$ into the gradient. The chain rule looks like it should leave a factor $\sigma(z)(1-\sigma(z))$ behind. It cancels against the $1/h$ from differentiating $\ln h$. If your gradient contains $h(1-h)$, you have differentiated squared loss through a sigmoid instead — a different (and non-convex) objective.

Trap 2 — using $h$ instead of $1-h$ for a negative example. For $y = 0$ the loss is $-\ln(1 - h)$. Plugging in $-\ln(0.269) = 1.313$ gives $J = 0.813$ instead of $0.313$, and the number even looks plausible. Say out loud "probability of the true class" before you take the log.

Trap 3 — forgetting the bias feature. $\theta \in \mathbb{R}^3$ and $x \in \mathbb{R}^3$ with a leading 1. Drop it and $z^{(1)} = 1$ by coincidence here, but the gradient loses a component and the shapes stop matching.

Trap 4 — "both examples are classified correctly, so the loss is 0". That is zero-one loss. Cross-entropy is $0.313$ and still has a nonzero gradient, which is the only reason the step in (d) exists. Confusing "correct" with "zero loss" is the single most common conceptual error in this chapter.

Trap 5 — $\ln$ versus $\log_2$. Entropy problems in Section 6 used $\log_2$; cross-entropy here uses $\ln$. The two differ by a factor $\ln 2$, which never changes an $\arg\min$ but always changes the number. Use whichever the question writes.

The objective is a sum of two competing terms: fit, which wants large weights that chase the data, and penalty, which wants small weights. $\lambda$ sets the exchange rate between them.

This problem rigs $\hat R$ to be identical for the two candidates, so the fit term cancels out of the comparison and you are looking at the penalty alone. That is artificial on purpose: it isolates the question "what shape of solution does each penalty prefer, all else equal?", which is the thing you are actually being tested on.

Then parts (c)–(e) are short-answer, and each has a specific right answer, not a vibe.

	$\sum_j \theta_j^2$ (Ridge)	$\sum_j|\theta_j|$ (LASSO)
$\theta_A = (3,0)$	$9 + 0 = 9$	$3 + 0 = \mathbf{3}$
$\theta_B = (2,2)$	$4 + 4 = \mathbf{8}$	$2 + 2 = 4$

Full objectives with $\hat R = 0.5$ and $\lambda = 1$:

	Ridge objective	LASSO objective
$\theta_A = (3,0)$	$0.5 + 9 = 9.5$	$0.5 + 3 = \mathbf{3.5}$ ✓
$\theta_B = (2,2)$	$0.5 + 8 = \mathbf{8.5}$ ✓	$0.5 + 4 = 4.5$

Note that both vectors have the same total "size" in a loose sense — $3 + 0$ versus $2+2$ is only off by one — yet squaring swings the comparison the other way, because $3^2 = 9$ punishes concentration while $2^2 + 2^2 = 8$ rewards spreading.

(b) Ridge chooses $\theta_B = (2,2)$; LASSO chooses $\theta_A = (3,0)$.

In one sentence: squaring penalises a single large weight more than two medium ones, so Ridge spreads weight across correlated features; the absolute value prices every unit of weight the same wherever it sits, so what LASSO can save is the number of features used — and LASSO drops one entirely.

(c) Look at how each penalty behaves for one weight near zero, with everything else fixed.

• Ridge: $\frac{d}{d\theta_j}\lambda\theta_j^2 = 2\lambda\theta_j \to 0$ as $\theta_j \to 0$. The penalty's pull toward zero vanishes right where you would need it most, so any tiny nonzero gradient from the fit term holds $\theta_j$ at a small nonzero value. Shrinkage, never elimination.
• LASSO: $\frac{d}{d\theta_j}\lambda|\theta_j| = \pm\lambda$, a constant pull of size $\lambda$ that does not vanish near zero. If the fit term's pull on $\theta_j$ is weaker than $\lambda$, the two cannot balance anywhere except exactly at $\theta_j = 0$, where the kink lets the subgradient absorb the difference. Hence exact zeros.

Geometrically: the LASSO constraint region $\sum|\theta_j| \le c$ is a diamond, with corners on the axes, and a corner is where a coordinate is exactly 0. The Ridge region $\sum\theta_j^2 \le c$ is a circle, which touches a generic objective contour at a point with every coordinate nonzero. That is why LASSO performs feature selection and Ridge does not.

Both sums start at $j = 1$: $\theta_0$ is never penalised. Three reasons, in increasing order of how likely they are to be the expected answer.

1. $\theta_0$ is not a feature weight. Regularization encodes the prior belief "features probably do not matter much, so keep their weights small". The bias is not a feature; it is the model's baseline level, and shrinking it expresses the belief that $y$ is probably near zero — a belief about your units, not about the data.

2. Concrete consequence: you lose shift-equivariance. Suppose every $y^{(i)}$ is in dollars and you switch to cents, multiplying all $y$ by 100 — or simply add 1000 dollars to every house price. The correct response is for $\theta_0$ to grow accordingly, with the feature weights unchanged. A penalty $\lambda\theta_0^2$ fights this: at $\lambda$ large enough, the fitted intercept is dragged toward 0 and every prediction is biased low for the whole dataset, uniformly. Penalising $\theta_0$ makes your model's answers depend on where you happened to put the origin of $y$.

3. At $\lambda \to \infty$ the model should be the best constant, not zero. With the bias exempt, infinite $\lambda$ drives $\theta_{1..M} \to 0$ and leaves $\theta_0 = \bar y$, i.e. "always predict the training mean" — the sensible maximally-underfit model. With the bias penalised, infinite $\lambda$ gives $h \equiv 0$, which is not a model of anything.

$\lambda \to 0$: the penalty disappears and you recover ordinary least squares, $\theta^{\star} \to (\Phi^{\top}\Phi)^{-1}\Phi^{\top}y$. Maximum variance, minimum bias — and if $\Phi^{\top}\Phi$ is singular (Problem 22), no unique answer at all.

$\lambda \to \infty$: all penalised weights are crushed to 0 and the prediction becomes the constant $\theta_0 = \bar y$. Maximum bias, zero variance — guaranteed underfitting. Between the extremes, training error increases monotonically with $\lambda$ while test error is U-shaped, which is why $\lambda$ is chosen on held-out data (Problem 30) and never on the training set — on the training set the answer is always $\lambda = 0$.

Standardization. Both penalties are stated in the units of the weights, and a weight's units are the inverse of its feature's. Measure a distance feature in kilometres instead of metres and its values shrink by 1000, so the fitted weight must grow by 1000 to make the same prediction — and its Ridge penalty grows by $10^6$. The same model, the same data, a thousand-fold different penalty, purely because of a unit choice. So subtract the mean and divide by the standard deviation of each feature first (using the training statistics, applied unchanged to test data); then one unit of weight means the same thing in every coordinate and $\lambda$ is a meaningful single knob.

(a) Ridge: $9$ for $\theta_A$, $8$ for $\theta_B$ (objectives $9.5$ and $8.5$). LASSO: $3$ for $\theta_A$, $4$ for $\theta_B$ (objectives $3.5$ and $4.5$).

(b) Ridge picks $\theta_B = (2,2)$; LASSO picks $\theta_A = (3,0)$. Squaring penalises one big weight more than two medium ones, so Ridge spreads; the absolute value prices weight uniformly, so LASSO zeroes a coordinate out.

(c) LASSO's derivative is $\pm\lambda$ and does not vanish at $0$, so a weight whose fit-gradient is smaller than $\lambda$ can only balance exactly at zero (the diamond's corners lie on the axes). Ridge's derivative $2\lambda\theta_j \to 0$ at the origin, so it never finishes the job (the circle has no corners).

(d) $\theta_0$ is a baseline, not a feature weight. Penalising it destroys shift-equivariance — add a constant to every $y$ and the fitted intercept is pulled back toward 0, biasing every prediction low — and it makes $\lambda \to \infty$ give $h \equiv 0$ instead of $h \equiv \bar y$.

(e) $\lambda \to 0$ gives OLS; $\lambda \to \infty$ gives the constant predictor $\bar y$. Features must be standardized because the penalty depends on the units of each feature, so without it $\lambda$ means something different in every coordinate.

Trap 1 — assuming the two regularizers always agree. They are different objectives. These numbers are chosen so that each picks the vector the other rejects, which is the cleanest possible demonstration that "regularization shrinks weights" is not a complete description.

Trap 2 — "LASSO gives smaller weights". Not pointwise: $\theta_A$'s largest weight is $3$, bigger than either of $\theta_B$'s. LASSO gives sparser weights, i.e. fewer nonzero ones. Sparse and small are different properties.

Trap 3 — squaring the sum instead of summing the squares. $(3+0)^2 = 9$ agrees with $3^2 + 0^2 = 9$ by luck on $\theta_A$, but for $\theta_B$ it gives $(2+2)^2 = 16$ instead of $8$ — and reverses the conclusion. $\|\theta\|_2^2 = \sum_j\theta_j^2$.

Trap 4 — forgetting that $\lambda$ cannot be fitted. $\lambda$ is a hyperparameter. Minimising the training objective over $\theta$ and $\lambda$ jointly always returns $\lambda = 0$, since the penalty only ever adds to the objective. Hyperparameters live on held-out data by necessity, not by convention.

Cross-validation is a procedure for estimating a model's risk without touching the test set, used here as the scoring function in a search over 5 candidate values of a hyperparameter. So separate the three roles cleanly, because every confusion in this topic is a collapse of two of them:

• Training set — fits $\theta$ (the parameters), by ERM.
• Validation set(s) — scores $\lambda$ (the hyperparameter). Used repeatedly, therefore no longer unbiased for the final model.
• Test set — estimates the risk of the one finished model. Used once, at the end, or not at all.

In $k$-fold, the 1000 examples take turns playing training and validation: for each fold, train on the other $k-1$ folds (800 examples) and score on the held-out one (200). Each example is validated on exactly once and trained on $k-1$ times.

Arithmetic note: every row has 5 numbers, so comparing row sums ranks them exactly as comparing means does. Add first, divide once.

$\lambda$	sum of 5 folds	mean
$0.01$	$0.42+0.50+0.46+0.38+0.44 = 2.20$	$0.44$
$0.1$	$0.20+0.34+0.26+0.32+0.38 = 1.50$	$0.30$
$1$	$0.22+0.28+0.20+0.26+0.24 = 1.20$	$\mathbf{0.24}$ ✓
$10$	$0.30+0.36+0.34+0.32+0.38 = 1.70$	$0.34$
$100$	$0.52+0.56+0.48+0.54+0.50 = 2.60$	$0.52$

5-fold CV selects $\lambda = 1$, with an estimated risk of $0.24$.

The column of means is U-shaped in $\lambda$ — $0.44, 0.30, \mathbf{0.24}, 0.34, 0.52$ — exactly the bias–variance story of Problem 29(e): too little regularization overfits, too much underfits, and the minimum is in the middle. A monotone column would be a warning that the best $\lambda$ lies outside the range you searched, and you should extend the grid.

Read down the fold-1 column alone: $0.42,\ \mathbf{0.20},\ 0.22,\ 0.30,\ 0.52$. The minimum is at $\lambda = \mathbf{0.1}$, not $\lambda = 1$.

A single 80:20 holdout would have selected $\lambda = 0.1$ — the wrong value, as judged by the far more reliable 5-fold estimate. And nothing in that one column would have warned you: $0.20$ versus $0.22$ looks like a clear winner if you have only one number each.

What it demonstrates is variance in the estimate. A single 200-example validation set gives a noisy estimate of risk, and the noise ($\pm 0.06$ or so across folds here) is comparable to the real differences between neighbouring $\lambda$ values ($0.30$ vs $0.24$). Averaging $k$ folds cuts that noise down without needing any more data, and that is the entire reason $k$-fold exists.

Look at the $\lambda = 0.1$ row to see it directly: its folds run $0.20, 0.34, 0.26, 0.32, 0.38$ — a spread of $0.18$, which is three times the gap between the best and second-best mean. Any conclusion drawn from one of those five numbers is a coin flip. The $\lambda = 1$ row, by contrast, is $0.20$–$0.28$ and wins on four of the five folds.

Holdout: one fit per candidate, plus one final refit on all the data.

$$C + 1 = 5 + 1 = \mathbf{6}\ \text{fits}$$

$k$-fold: $k$ fits per candidate, plus the final refit.

$$Ck + 1 = 5 \times 5 + 1 = \mathbf{26}\ \text{fits}$$

So $k$-fold costs about $k$ times more compute and buys you a $k$-times-averaged estimate. The extreme is LOOCV, $k = N$: here that would be $5 \times 1000 + 1 = 5001$ fits, each on 999 examples. Nearly unbiased, almost always too expensive, and with high variance of its own because the $N$ training sets are nearly identical. $k = 5$ or $10$ is the standard compromise.

If you were tuning two hyperparameters on a grid — say 5 values of $\lambda$ and 4 polynomial degrees — then $C = 20$ and 5-fold costs $101$ fits. The cost is multiplicative in the number of hyperparameters, which is why grid search gets abandoned quickly.

(d) You are choosing $\lambda$, a hyperparameter — a knob that controls the hypothesis class itself (here, how strongly weights are penalised, and so how much effective capacity the model has). The parameters $\theta$ are not being chosen here; they are refitted from scratch inside every one of the 25 fits.

Why not minimise training error over $\lambda$? Because the training objective is $\hat R(\theta) + \lambda r(\theta)$, and the training error $\hat R$ alone is minimised by whichever $\lambda$ constrains $\theta$ least — i.e. $\lambda = 0$, always, for every dataset. The answer would be a foregone conclusion and would have nothing to do with the data. The same argument applies to every capacity hyperparameter: more capacity always fits the training set at least as well, so training error ranks capacity monotonically and cannot find an optimum. A quantity that controls capacity cannot be tuned on the data used to fit the parameters.

(e) Having chosen $\lambda = 1$, refit on all 1000 examples with $\lambda = 1$. That is the shipped model, and it is the "$+1$" in the fit counts above. Each CV fit used only 800 examples, so none of those 25 models is the one you want — they existed only to score $\lambda$.

The separate test set — data that took part in neither the fitting nor the selection — exists to estimate the final model's risk. You need it because $0.24$ is optimistically biased: it is the minimum of five noisy estimates, and taking a minimum over noise systematically understates the truth. Report $0.24$ as "the CV score that selected $\lambda$", and whatever the untouched test set says as "the estimated risk". Peek at the test set repeatedly and it quietly becomes a validation set, after which you no longer have an honest estimate of anything.

(a) Means $0.44,\ 0.30,\ \mathbf{0.24},\ 0.34,\ 0.52$; 5-fold CV selects $\lambda = 1$.

(b) A holdout equal to fold 1 would select $\lambda = 0.1$ (its $0.20$ beats $\lambda=1$'s $0.22$) — the wrong value. It demonstrates that a single split gives a high-variance risk estimate, with fold-to-fold noise as large as the real differences between candidates; averaging $k$ folds removes it without extra data.

(c) Holdout $C + 1 = 6$ fits; $k$-fold $Ck + 1 = 26$ fits; LOOCV would be $CN + 1 = 5001$.

(d) The hyperparameter $\lambda$. Training error cannot choose it because training error is minimised at $\lambda = 0$ for any dataset — capacity-controlling quantities are monotone in training error and so have no interior optimum there.

(e) Refit on all 1000 examples at $\lambda = 1$. A separate, never-selected-on test set gives the honest risk estimate, because the winning CV score $0.24$ is biased low by being the minimum over five noisy numbers.

Trap 1 — picking per-fold winners and voting. CV selects on the mean across folds, one number per candidate. Choosing a different $\lambda$ for each fold produces five models and no decision.

Trap 2 — forgetting the final refit. People answer "25 fits" and ship one of the 800-example fold models. The procedure is: score with CV, then retrain on everything with the chosen hyperparameter. $Ck + 1$, and the $+1$ is the model you actually deploy.

Trap 3 — reporting the CV score as the test error. $0.24$ is the minimum over five candidates of noisy estimates, which is biased low by construction. This is the same selection bias as in Problem 27(b), where picking a model on the test set stopped that test set from being honest.

Trap 4 — confusing $k$ with the number of candidates. $k$ is the number of folds (how the data is cut), $C$ is the number of hyperparameter values (what you are searching). Here both are 5, which is exactly the sort of coincidence an exam uses to see whether you know which is which. If the question changes to 10-fold over 5 candidates, the answer is $51$ fits, not $26$ or $101$.

Trap 5 — "$k$-fold gives more data". It gives better use of the data you have. Every fit still sees only $\frac{k-1}{k}N = 800$ examples; what improves is the precision of the estimate, by averaging, not the size of any training set.