Rung 35
Graphs, DAGs, tensors
The structures a modern model is actually made of.
Best attempted after 26. Trees and heaps and 29. Matrices as transformations. Nothing stops you trying this now — the gate will tell you if you were right.
The gate
Represent an arithmetic expression as a directed acyclic graph, topologically sort it, and evaluate it by walking that order. Then add an edge that creates a cycle and show your sort detects it rather than looping. Separately, predict the output shape of three broadcast operations before running them.
Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.
Rung 26's trees had one path from the root to any node. Lift that restriction and you get a graph: nodes and edges, any shape. Require the edges to have direction and forbid cycles, and you get a directed acyclic graph — a DAG.
Separately: a tensor is what you get when a list of numbers is not enough. A vector is one-dimensional, a matrix two, and a tensor is the general case. A batch of colour images is four-dimensional: image, height, width, colour channel.
Two ideas in one rung because they meet in the same place — the object that represents a computation.
Why this is on the ladder
Because a computation graph is a DAG. Every value your model computes is a node whose edges point to the values it was computed from. Evaluating the model is a walk forward through that graph; rung 45's backpropagation is a walk backward through the same graph, applying rung 22's chain rule at each node.
The acyclic part is what makes it possible. No cycles means there is an order in which every node's inputs are ready before the node is reached — a topological sort — and without that guarantee neither pass would terminate.
Do this
Take (a + b) * (b - c). Draw it as a DAG. Note that b is a single node with
two outgoing edges; it is not duplicated, and that sharing is exactly why the
structure is a graph rather than a tree.
Implement it: nodes, edges, a topological sort, and an evaluation that walks the sorted order. Check it against Python's own arithmetic.
Then add an edge that makes a cycle and run the sort again. It must report the cycle rather than spin. Detecting that condition is the whole reason the "acyclic" in DAG is load-bearing.
For tensors, practise shapes. Given arrays of shape (3, 1) and (1, 4), predict
the broadcast result before running it. Then (2, 3, 4) with (4,). Then a pair
that cannot broadcast, and predict the error. Shape errors are the most common
failure at rung 44, and predicting shapes is the skill that prevents them.
Where people get stuck
Broadcasting silently doing something plausible but wrong. Shapes (3,) and
(3, 1) combine into (3, 3) — no error, no complaint, and a bug that surfaces
much later as a loss that will not fall. Print shapes; do not assume them.
With the DAG, the usual mistake is evaluating in the order the nodes were created rather than the order the sort produced. It works on small examples by luck and fails on anything branched.