A First Taste of Algorithms · Problem Set 9

Diamond

4.1 The matched pair, derived. Prove the deep water’s claim: for softmax probabilities p over scores s₁, …, s_V with true class t and loss L = −log(p_t), ∂L/∂sᵢ = pᵢ − [i = t]. (a) Write p_t = e^{s_t} / Σⱼ e^{sⱼ} and L = −s_t + log(Σⱼ e^{sⱼ}). (b) Differentiate the two terms of L with respect to a general score sᵢ, carefully handling the case i = t versus i ≠ t in the first term, and using the chain rule on the log-sum in the second. (The derivative of the log-sum is where pᵢ is born — show it.) (c) Combine to get pᵢ − [i = t], and interpret the result as a sentence about blame: confident-and-wrong versus nearly-right. (d) The verification that closes the loop: explain why your hand-derived gradient must match what the Value engine computes when you build this same loss out of exp, log, and division — and what it would mean about your algebra (or the engine) if they disagreed. This is the chapter’s deepest point: the engine and the calculus are the same thing, one done by machine and one by hand.

4.2 (Alternative Diamond — attention.) For a single attention head, derive the gradient of the loss with respect to the query matrix W_Q, at least through the first link of the chain. (a) Write the output context vector for position t as a weighted sum of value vectors with weights A_{t,s}, and A as the softmax of scaled scores Q Kᵀ/√d_k. (b) Using the softmax gradient you derived in 4.1 (the same p − [i=t] structure, now per attention row), express ∂(loss)/∂(scores) in terms of the incoming gradient on the context. (c) Push one more link: ∂(scores)/∂Q is linear in K, so assemble ∂(loss)/∂W_Q via the chain rule and X. You need not simplify fully — the point is to see that attention’s gradient is the same softmax-and-chain machinery as the classifier’s, which is why your Value engine trains it without knowing it is “attention.” (d) State, in one sentence, what this shared machinery says about the unity of everything in this chapter.

Computational Lab

5.1 Lab 9 in full. The engine is not real until (a) it matches finite-difference gradients on a messy expression, (b) it trains a tiny model end-to-end by your own backward sweep, and (c) the numpy model generates novel names and shows you the train/test gap opening. Export your parameter count (Problem 2.5) and your two loss curves (Problem 2.2).

Teach It

6.1 Explain backpropagation to someone using the word “blame” and no calculus: a final mistake is blamed on the things that caused it, each cause blamed in proportion to how much it mattered, blame flowing backward through the steps until every knob knows its share. Use a concrete chain (the bowl, or a two-step calculation). Then show them the actual backward method and point to where “blame flows backward” is the reversed loop. Report which half — the metaphor or the code — made it click.

6.2 Show someone the model generating names, then tell them the honest two-part truth this book ends its technical arc on: we built exactly this, and we understand exactly this; the trillion-knob version is built exactly too, and understood by no one exactly. Discuss the gap between building and understanding. Report their reaction to the idea that the most powerful technology of their era is, at bottom, this — counted steps, downhill walks, blame flowing backward — scaled twelve orders of magnitude past where anyone can fully follow it.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses