Big ideas

Up close, every smooth curve is a straight line. The error of pretending shrinks like the square of how far you look. So we can study the easy, straight version and trust the answer nearby.

A vector is not a mysterious arrow. It is a list of numbers you are allowed to add and scale. Houses, photos, words and shopping slips all follow the same two rules, so one set of tools works on all of them. That is why linear algebra powers machine learning.

Everything fancy in this unit (matrices, Gaussian elimination, echelon form) is just these two moves, done by a machine at scale: remove an unknown by subtracting rules, then substitute back.

One more thing: four rules for three unknowns usually have no answer at all. This one does because the rules happen to agree. When real data disagrees, which is the everyday case in machine learning, linear regression finds the best almost-answer instead.

A linear system never has exactly two answers. Suppose $\mathbf{u}$ and $\mathbf{v}$ are both answers. Then the point halfway between them is an answer too, and so is every point on the line through them. Two answers always grow into infinitely many. So the only possible counts are zero, one, or infinity.

A matrix is a function, and multiplying matrices means doing one function after another. "Blur, then darken" is one combined filter, and that filter is $AB$ (read right to left: $B$ acts first). The strange row-times-column rule is exactly the arithmetic that makes $(AB)\mathbf{x}=A(B\mathbf{x})$ true.

That is also why order matters. Socks then shoes is not shoes then socks. In general $AB\neq BA$.

$$A\mathbf{x}=x_1\mathbf{a}_1+x_2\mathbf{a}_2+\cdots+x_n\mathbf{a}_n$$

Rows give you rules to obey. Columns give you ingredients to mix. The machine view asks which input made this output. Three pictures, one equation. And the big questions (is there an answer? just one?) belong to the machine $A$ itself, not to the particular $\mathbf{b}$ you happen to be holding.

The columns of a matrix are where î and ĵ land. Once you know those two landing spots, you know where every point goes: $A\mathbf{x}=x_1(A\hat\imath)+x_2(A\hat\jmath)$. And $\det A$ is the area of the tile those two arrows make: how much the machine grows or shrinks area, with a minus sign if it flips space over.

The inverse exists exactly when $\det A\neq0$, because you cannot un-squash something that was squashed flat. And even when it exists, a determinant close to zero makes the inverse huge and the answer shaky. In practice we solve with elimination and never build $A^{-1}$.

all solutions = one solution + every "invisible" direction

The invisible directions are the arrows the matrix sends to zero: solutions of $A\mathbf{x}=\mathbf{0}$. Together they are called the null space of $A$. You will meet "one answer plus the null space" again in regression, in optimization, and inside neural networks.

solutions of $A\mathbf{x}=\mathbf{b}$ = $\mathbf{x}_p$ + all of $N(A)$

One anchor, plus the whole blind spot. If the blind spot is only $\{\mathbf{0}\}$, there are no look-alikes, and a solution (when there is one) is unique. You already know that case by its other names: $\det\neq0$, invertible.

Elimination rewrites the same problem until the answer is obvious. Every move can be undone, so the solutions never change. At the end, the staircase tells you everything: pivot columns are pinned-down unknowns, columns without a pivot are free, and a row that says $0=$ something non-zero means no solution. In the big example the last row became "$0=a+1$", so there is a solution only when $a=-1$.

In RREF, every pivot column is a clean "1 and zeros" column, so the answer can be read straight off the bar. Every column without a pivot is a free variable, and each one gives exactly one invisible direction. So the size of the null space is

$\dim N(A) = n - \operatorname{rank}(A)$

unknowns minus pivots: freedom left over = unknowns minus the rules that really pin something down. (This is the rank–nullity theorem.)

Rank answers "how many solutions?" completely. Compare $\operatorname{rank}(A)$ with $\operatorname{rank}([A|\mathbf{b}])$ and with $n$, the number of unknowns:

① At least one solution $\iff\operatorname{rank}(A)=\operatorname{rank}([A|\mathbf{b}])$. Adding $\mathbf{b}$ brought no new direction, so $\mathbf{b}$ is in the column space.

② Exactly one $\iff$ ① holds and $\operatorname{rank}(A)=n$: no free variables.

③ Infinitely many $\iff$ ① holds and $\operatorname{rank}(A)<n$: free variables exist, and the null space is alive.

One picture: a matrix is a machine that moves space; solving $A\mathbf{x}=\mathbf{b}$ asks which input the machine turned into that output. One method: elimination on $[A|\mathbf{b}]$ until the staircase appears. One number: rank, which counts the dimensions that survive and decides all three fates.

A group is a set with a trustworthy undo button. You can combine any two members and stay inside, brackets never matter, there is a do-nothing member $e$, and every $x$ has a partner that brings you back to $e$.

When a set fails, it is nearly always the last promise. The counting numbers have no $-5$. The whole numbers under multiplication have no $\tfrac12$.

$$\lambda(\mathbf{u}+\mathbf{v})=\lambda\mathbf{u}+\lambda\mathbf{v}$$

Adding and scaling can be done in either order, and you never leave the world. Anything you can add and scale by these rules counts as a vector. Every "linear" idea in this course, from gradients to averages, is this route-swapping trick.

In $\mathbb{R}^n$, the subspaces are exactly the flat things through the origin: the origin alone, lines through $\mathbf{0}$, planes through $\mathbf{0}$, and so on up to the whole space. A set that is shifted, curved or fenced in always lets something escape.

This is a theorem, not just a pattern. Sections 10 and 11 show why: every subspace is the span of a few independent arrows, and such a span is always a flat through $\mathbf{0}$.

$$\begin{aligned}A(\mathbf{x}+\mathbf{y})&=A\mathbf{x}+A\mathbf{y}=\mathbf{0}+\mathbf{0}=\mathbf{0}\\ A(\lambda\mathbf{x})&=\lambda A\mathbf{x}=\mathbf{0}\end{aligned}$$

Zero in, zero out. Invisible plus invisible is invisible, and a stretched invisible change is still invisible. So the null space $N(A)$ is always a subspace. The same two rules make the column space $C(A)=\{A\mathbf{x}\}$, all the outputs the machine can produce, a subspace too.

But the solutions of $A\mathbf{x}=\mathbf{b}$ with $\mathbf{b}\neq\mathbf{0}$ are never a subspace: two of them add up to $2\mathbf{b}$, not $\mathbf{b}$.

The span is every mix $\lambda_1\mathbf{v}_1+\cdots+\lambda_k\mathbf{v}_k$. It is always a flat through the origin, so it is always a subspace: a point, a line, a plane, or more.

Its size depends on how many different directions the arrows point in. A new arrow that lies inside the current span adds nothing. An arrow that points out of it adds a whole new direction.

Vectors are independent when the only way to make $\lambda_1\mathbf{x}_1+\cdots+\lambda_k\mathbf{x}_k=\mathbf{0}$ is with every $\lambda_i=0$. You can only get home by never leaving.

If some other weights bring you home, the set is dependent, and at least one vector is a mix of the rest: extra baggage.

Stack the vectors as columns and eliminate. A pivot column brings a new direction. A column without a pivot is a mix of earlier columns, and in the reduced form its numbers are the exact recipe.

The number of pivots, the rank, is the number of truly different directions. If every column has a pivot, the vectors are independent.

If the ingredients $\mathbf{b}_i$ are independent, then the dishes $\mathbf{x}_j=B\boldsymbol{\lambda}_j$ are independent exactly when their recipe cards $\boldsymbol{\lambda}_j$ are. So you can always do the check on the small, simple cards instead of the big dishes.

And more cards than ingredients ($m>k$) always means dependent.

A basis reaches everything with nothing extra. Because of that, every vector has exactly one address:

$$\mathbf{x}=\lambda_1\mathbf{b}_1+\cdots+\lambda_k\mathbf{b}_k$$

The $\lambda_i$ are the coordinates. Change the basis and the address changes, but the point itself stays put. A dependent pair cannot be a basis: the graph paper collapses to a line.

Every basis of a space has the same number of vectors. That number is the dimension: the count of independent directions, the number of knobs you really have.

Components count the room you are written in. Dimension counts the room you actually use. And more vectors than the dimension always means redundancy.

To find a basis of a span: stack, reduce, and keep the original vectors in the pivot columns. The number you keep is the dimension.

For the slide example: a basis of $U$ is $\{\mathbf{x}_1,\mathbf{x}_2,\mathbf{x}_4\}$, and $\dim(U)=3$. Four vectors walked in, one was a mix, and three genuine directions remain.

A norm is just a rule for measuring length. Different rules give different shapes of "all points at distance 1": a circle for the crow, a diamond for the taxi. When a machine-learning model measures error or closeness, it has quietly picked one of these rules, and the pick changes the answer.

$$\mathbf{x}^T\mathbf{y}=\sum_i x_iy_i$$

The dot product is an agreement score. Every "people like you also watched…" system is built on this one line of arithmetic.

Any score with these three ingredients is called an inner product. The dot product is just the most famous one. Every inner product gives you its own length, its own distance and its own angle, and they all behave sensibly. The natural next question: how do we cook up new ones? (Next section.)

The matrix $A$ reshapes the unit ball. The identity gives a round ball. A diagonal $A$ squashes it into an egg along the axes. Off-diagonal numbers tilt the egg. A matrix that is not positive-definite tears the ball open, because some arrows would get a negative length squared.

$$|\langle\mathbf{x},\mathbf{y}\rangle|\le\|\mathbf{x}\|\,\|\mathbf{y}\|\qquad\text{and}\qquad\|\mathbf{x}+\mathbf{y}\|\le\|\mathbf{x}\|+\|\mathbf{y}\|$$

A shadow never beats the stick, and a detour never beats the straight road. The first fact makes angles possible (next section). The second fact makes sure every inner product gives a proper length.

$\cos\omega$ is the shadow of a length-1 arrow. Shrink both arrows to length 1, then drop the shadow of one onto the other: its length is $\cos\omega$. Full shadow: same direction. No shadow: right angle. Negative shadow: opposite. Length never enters. Only direction does.

In 2D, two random arrows can point any which way. In 1000D, two random arrows are almost always at almost exactly 90°. The spread of the cosine shrinks like $1/\sqrt{n}$: about 0.03 when $n=1000$.

Why this matters: a 1000-number embedding space has room for millions of ideas that barely get in each other's way. It also means a cosine of 0.3 between two real embeddings is huge. Random chance would give about 0.

"At a right angle" is not a fact about two arrows alone. It is a fact about two arrows and a ruler. Measuring with $A=\operatorname{diag}(2,1)$ is exactly the same as stretching the page sideways by $\sqrt2$ and then measuring normally. Choosing the ruler to fit the problem is what feature weighting and the Mahalanobis distance do in machine learning. (Section 5's lens shows the same thing: press diag(2, 1).)

$$A^TA=I$$

This one line is the test for an honest motion. Pass it, and every length, distance and angle is safe. The shear keeps the area (its determinant is 1), but it fails this test, and you can see its arrows slide off the measuring rings.

Any arrow = its shadow along a direction + a leftover at a right angle. The shadow amount is $\alpha=\langle\mathbf{a},\mathbf{b}\rangle/\langle\mathbf{b},\mathbf{b}\rangle$. If the stick leans backwards (angle past 90°), $\alpha$ turns negative and the shadow falls behind you. This single split is the heart of least squares, attention scores and PCA.

Gram–Schmidt = cut off the shadows, then resize to 1. Each new direction loses the parts that point along the clean ones, so what is left must be at a right angle to them. Any basis at all can be cleaned this way.

$\det A$ is the area of the tile that the unit square becomes. Its size says how much every area grows. A minus sign means the tile was flipped over. Zero means it was squashed flat, and then nothing can undo $A$.

A big determinant is a sum of small ones: entry × sign × minor, along any row or column. Pick the line with the most zeros. For big matrices, eliminate down to a triangle and multiply the diagonal. Every road gives the same number.

$\operatorname{tr}A$ is the sum of the diagonal. It ignores everything off the diagonal, and $\operatorname{tr}(AB)=\operatorname{tr}(BA)$ always. Soon you will see it is also the sum of the eigenvalues.

An eigenvector is an arrow that $A$ only stretches: $A\mathbf{x}=\lambda\mathbf{x}$. The stretch number $\lambda$ is its eigenvalue. To test a guess, multiply once and check if the answer is a multiple of the arrow.

$$\det(A-\lambda I)=0$$

An eigenvalue is a setting of the dial $\lambda$ where $A-\lambda I$ squashes space flat. Solve this equation for the eigenvalues, then solve $(A-\lambda I)\mathbf{x}=\mathbf{0}$ for the directions. Check: sum = trace, product = determinant.

$$A=Q\Lambda Q^{\top}$$

A symmetric matrix is: turn into the grain, stretch each grain direction by its $\lambda$, turn back. Its eigenvalues are real, its eigen-directions are at right angles, and undoing $Q$ is just flipping it.

A symmetric 3×3 matrix turns the round ball into an egg. The egg's axes are the eigen-directions, their lengths are the $|\lambda|$'s, and the volume grows by $|\lambda_1\lambda_2\lambda_3|=|\det A|$.

A pure turn has no real eigen-directions. Its eigenvalues are the twins $\cos\theta\pm i\sin\theta$, which sit on the unit circle. The angle of $\lambda$ is the turn, and the size of $\lambda$ is the stretch.

$$A=LL^{\top}$$

Fill in $L$ from the top-left corner, one entry at a time. It only works when $A$ is positive-definite, so it doubles as a test. And $\mathbf{x}=L\mathbf{z}$ bends a round random cloud into one with covariance $\Sigma$.

Different eigenvalues, or a symmetric matrix, guarantee a full set of eigen-directions. A repeated eigenvalue in a non-symmetric matrix can come up short ($\operatorname{gm}<\operatorname{am}$). And the data matrix $A^{\top}A$ is always in the safe, symmetric, positive-definite club.

A matrix looks like a block of numbers. Underneath, it is a short list of simple moves. Writing $A=(\text{turn})\,(\text{resize})\,(\text{turn})$ does not change $A$ at all. It only lets you see what $A$ does.

A diagonal matrix is a resize tool: one handle per axis. Repeating, undoing and measuring area all work one number at a time: $D^k=\operatorname{diag}(d_1^k,\dots,d_n^k)$. The only danger is a handle set to 0 — that axis is flattened for good.

$A=PDP^{-1}$ says: in its own favourite directions, $A$ is just a resize tool. The columns of $P$ are those directions (the eigenvectors). The diagonal of $D$ says how much each is stretched (the eigenvalues).

A symmetric matrix is an equalizer. It splits the input along directions at right angles, turns each part up by its own $\lambda$, and adds them back: $A=\sum_i\lambda_i\,\mathbf q_i\mathbf q_i^{\top}=Q\Lambda Q^{\top}$. Undoing the split is free, because $Q^{-1}=Q^{\top}$.

$A=PDP^{-1}$ is a translator: into the matrix's own directions, resize, and back. Its best trick is repetition: $A^k=PD^kP^{-1}$. Powers of a matrix become powers of plain numbers.

An eigenvector is a direction the matrix does not turn. Eigendecomposition needs $n$ independent ones for an $n\times n$ matrix. The shear has one, the rotation has none, and a rectangular matrix cannot even ask the question.

Every matrix is turn · resize · turn: $A=U\Sigma V^{\top}$. There are two frames at right angles — $V$ for inputs, $U$ for outputs — and a list of stretches $\sigma_1\ge\sigma_2\ge\dots\ge0$. No exceptions: not rotations, not shears, not rectangles.

To find the SVD, take the round trip. The eigenvectors of $A^{\top}A$ are the input frame $V$, and $\sigma_i=\sqrt{\lambda_i}$. The output frame comes free: $\mathbf u_i=A\mathbf v_i/\sigma_i$. $\Sigma$ always has the same shape as $A$, padded with zeros.

A rectangular matrix maps one world into another. A $3\times2$ matrix can only fill a flat sheet inside 3-D space. The SVD's $\mathbf u_1,\mathbf u_2$ span that sheet, and $\mathbf u_3$ is the direction it can never reach.

Sort the layers biggest first and keep the top $k$: $\hat A(k)=\sum_{i\le k}\sigma_i\mathbf u_i\mathbf v_i^{\top}$. No rank-$k$ matrix does better, and the error is $\sigma_{k+1}$. Each layer costs only $m+n+1$ numbers — so this is compression, for photos and for tables of ratings alike.

$\sigma_1$ is the biggest boost a matrix can give: $\|A\|_2=\sigma_1$. The ratio $\sigma_1/\sigma_2$ says how uneven the boosts are. When it is huge, undoing the matrix blows up tiny errors.

Every matrix is turn · resize · turn. Sort the stretches biggest first and keep the top few, and you have the best short summary a matrix can have. Photo compression, noise removal, PCA and recommenders are all that one move.

The slope tells you which way is up. So you step the other way. Slope positive? Step left. Slope negative? Step right.

$$w_{\text{new}} = w - \eta\,L'(w)$$

Here $L'(w)$ (read it: "L-prime of w") is the slope where you stand. $\eta$ (read it: "eta") is a small number that sets your step size. The minus sign is the "go the other way" part.

$$\frac{df}{dx}=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}$$

The derivative is rise ÷ run between two points, as the two points squeeze into one. It never divides by zero. It only asks what the ratio gets close to.

$$\frac{d}{dx}\,g\big(f(x)\big)=g'\big(f(x)\big)\cdot f'(x)$$

Machines in a row: their rates multiply. Work out the outer rate at the inner value, then multiply by the inner rate. A deep network is a long row of machines, so this one rule runs all of machine learning.

$$T_n(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+\cdots$$

Each term copies one more derivative at the anchor: first the value, then the slope, then the bend. Near the anchor the copy is excellent. Far away it can fail, so Taylor is a local promise.

$$\frac{\partial f}{\partial x}=\text{the slope when only } x \text{ moves}$$

Freeze every other input, then differentiate as usual. Each partial derivative is the slope of one slice through the landscape.

$$\mathbf{w}_{\text{new}}=\mathbf{w}_{\text{old}}-\eta\,\nabla L(\mathbf{w})$$

The gradient points steepest uphill, and its length says how steep. So minus the gradient is steepest downhill. This one line, repeated, is how almost every model in machine learning is trained.

$$\text{shape of the derivative}=(\text{number of outputs})\times(\text{number of inputs})$$

Two rows of the table do almost all the work in machine learning. The gradient: the loss is one number and the weights are a list, so the derivative is a list shaped like the weights. That is why you can subtract it from them. The Jacobian: a layer turns a list into a list, so its derivative is a matrix.

$$J_{ij}=\frac{\partial f_i}{\partial x_j}$$

Row $i$, column $j$: how much output $i$ moves when input $j$ is nudged. Zoom in on any smooth map and it becomes this matrix.

$$\text{area after}\approx|\det\mathbf J|\times\text{area before}$$

$\det\mathbf J$ is the local area factor. Not zero means you can undo the map near that point. But being undoable near every point still allows the map to wrap around and repeat.

$$\frac{\partial L}{\partial \mathbf x}=\underbrace{\frac{\partial L}{\partial \mathbf a}}_{\text{row}}\;\mathbf J_{\tanh}\;\mathbf J_{W}$$

The chain rule for lists is matrix multiplication, later layer on the left. Backpropagation just multiplies from the loss end, so it only ever carries a thin row.

$$\mathbf w\leftarrow\mathbf w-\eta\,\nabla L(\mathbf w)$$

The gradient says which way. The learning rate $\eta$ says how far to trust it. Too small and you crawl. Too big and you overshoot, again and again.

$$\text{slope from the left}=\text{slope from the right}\ \Longleftrightarrow\ \text{a derivative exists}$$

At a corner the two sides disagree, so there is no derivative. Software just picks a value in between. Rows versus columns is only a habit, but the order of matrix factors is a rule.

If you keep one habit from this unit, make it counting shapes before computing anything. Outputs give rows, inputs give columns. A gradient has the same shape as the thing you differentiate by. In a product, the inner sizes must match. Most matrix-calculus mistakes are shape mistakes, and counting catches them before any algebra.

Training needs one slope per knob, at every step. So the real question is not "what is the slope?" but "how do we get a million slopes cheaply?"

Backpropagation is the answer: tiny steps, and blame sent backwards.

Any function, however scary, is a chain of easy steps. Forward, each step computes a value. Backward, each step receives a blame $\bar v=\partial f/\partial v$, starting from $\bar f=1$.

The blame that reaches $x$ at the far left is the answer $df/dx$.

$$\frac{\partial f}{\partial x}=\sum_{\text{routes}}\ \prod_{\text{arrows on the route}}\big(\text{small slope}\big)$$

Multiply along each route. Add the routes. Backprop does exactly this, and shares the work so that no route is walked twice.

A derivative is a promise: "near here, the function is a straight line plus a leftover that fades fast". Chain two promises, and the slopes multiply. Let several routes run side by side, and their products add.

And one entry of a matrix product, $\sum_k (J_G)_{ik}(J_F)_{kj}$, is both rules written at once.

Set $\bar f=1$. Walk from right to left. At each value, add up (child's blame × child's small slope) over all its children.

One sweep, and every value in the graph — every input, every weight — holds its slope.

$\delta=(a-y)(1-a^2)$: the miss, times how steep the squash is. Every knob that feeds $z$ then gets $\delta$ times one number: $x$ for the weight, $1$ for the bias.

Step each knob against its slope, repeat, and the loss really falls. That is training, complete.

Through the squash, scale each neuron's blame by its own slope. Then weights get $\boldsymbol\delta^{(Z)}\mathbf x^\top$, biases get $\boldsymbol\delta^{(Z)}$, and the layer below gets $A^\top\boldsymbol\delta^{(Z)}$.

Repeat, layer after layer. That is the inner loop of all of deep learning.

Dot product → the other vector. $\mathbf a^\top X\mathbf b$ → the outer product $\mathbf a\mathbf b^\top$. $\mathbf x^\top B\mathbf x$ → $\mathbf x^\top(B+B^\top)$, because $\mathbf x$ appears twice.

When in doubt, count where the variable appears, and add one term for each appearance.

Every layer's slope is the same shared start, times one new factor. Carry that start — the blame $\boldsymbol\delta$ — from the loss backwards, and each factor is used once.

So one backward sweep costs about as much as one forward pass, however many knobs there are.

$f(\mathbf x_0)+\nabla f(\mathbf x_0)^{\top}(\mathbf x-\mathbf x_0)$ is the "flat Earth" version of $f$ near $\mathbf x_0$.

Its error grows like the square of the distance: twice as far, about four times the error. Every gradient-descent step leans on this promise.

The nudge estimate's error is (curve error, shrinking like $h^2$) + (rounding noise, growing like $1/h$). So there is a best $h$ — about $10^{-6}$ here — and even there the answer is off by about $10^{-10}$.

Autodiff has neither problem. Nudging survives only as a gradient checker: a quick test that a hand-written backward pass is right.

Blame flows backwards through the same graph that computed the value. Multiply along paths, add at forks, and reuse every shared piece. Then a million slopes cost one sweep.

A Taylor polynomial is a copy built from a few facts at one spot: height, slope, bend, and so on. Each extra fact keeps the copy close for longer. What we still need is a promise about how close.

If a smooth trail starts and ends at the same height, it has a level spot in between: $f'(c)=0$. All it needs is no gaps and no sharp corners. This one small fact will build the whole unit.

Somewhere, the slope equals the average slope: $f'(c)=\dfrac{f(b)-f(a)}{b-a}$. Rearranged, $f(b)=f(a)+f'(c)(b-a)$. That is the straight-line copy, made exact by one secret point.

Each Rolle step turns two zeros into one new zero, one derivative lower. If $F$ is zero at $b$ and flat to order $n-1$ at $a$, the zeros pass all the way down: $F^{(n)}(c)=0$ for some $c$ in between.

Every smooth function is its copy plus one leftover term: $f(x)=P_{n-1}(x)+\dfrac{f^{(n)}(c)}{n!}(x-a)^n$, exactly. The leftover looks like the next term, measured at a secret point. And the whole proof is Rolle, used again and again.

You never need the secret point. If $|f^{(n)}|\le M$ on the stretch, then $|R_n|\le\dfrac{M}{n!}|x-a|^n$. A worst case turns the exact leftover into a guarantee you can compute.

Each new term is the previous one times $\dfrac{|x|}{n+1}$. Once $n+1$ is bigger than $|x|$, every step shrinks the term. So the series for $e^x$, $\sin x$ and $\cos x$ can be trusted at every $x$. For $\ln(1+x)$ there is no factorial, and past $x=1$ it fails.

Walk in a straight line and a landscape becomes a one-variable curve $F(t)$. Its bend is $h^2f_{xx}+2hk\,f_{xy}+k^2f_{yy}$. Those three second slopes are the landscape's curvature, and they are where the Hessian is born.

At a level spot, the height change after a small step is $\tfrac12Q$. If $Q$ is always positive, it's a valley; always negative, a peak; both, a pass. The three second slopes at the spot decide which.

$f(\mathbf x_0+\mathbf h)\approx f(\mathbf x_0)+\nabla f^{\top}\mathbf h+\tfrac12\mathbf h^{\top}H\mathbf h$. It is the one-variable formula with each piece moved up a level: number, list, table. The step goes in once for the list and twice, like bread, for the table.

The Hessian is the judge. Work out $D=f_{xx}f_{yy}-f_{xy}^2$: positive with $f_{xx}>0$ is a bowl, positive with $f_{xx}<0$ is an upside-down bowl, negative is a saddle. The eigenvalues say the same thing: they are the strongest and weakest bends, and $D=\lambda_1\lambda_2$.

Find every level spot. Work out the Hessian at each one, because it changes from place to place. Read $D$, then $f_{xx}$. And when $D=0$, the bends have run out of evidence, so look further.

Near its bottom, a loss is its own quadratic clone. The Hessian's eigenvalues say how narrow the valley is, and so how hard plain descent will be. Its inverse turns the clone into Newton's one jump, $-H^{-1}\nabla f$, which is powerful but costly for millions of weights.

Every smooth function is, up close, a polynomial, and Taylor's theorem tells you exactly how far "up close" reaches. The leftover $f^{(n)}(c)(x-a)^n/n!$ came from a ladder of level spots. In two variables, the bend part is a table, the Hessian, whose signs say whether a level spot is the bottom of a bowl. When a training run says it has found a minimum, this unit is how you can check.

$$\text{new}=\text{old}-\gamma\,\nabla f(\text{old})$$

Read it: new position equals old position, minus the stride times the uphill arrow at the old position. Take the arrow, turn it around, shrink it to your stride, and step. This one line is the picture you just played with, written in symbols.

Wrongness is the sum of squared misses, $L=\sum_i\big(y_i-(ax_i+b)\big)^2$. Its slope, $\nabla L=\big(-2\sum x_ir_i,\,-2\sum r_i\big)$, just says "move the line toward the points". If the misses are mostly positive, push the line up.

The walk stops where the slope is zero, $f'(x)=0$. The bend decides what kind of stop it is: $f''>0$ is a valley, $f''<0$ is a hilltop. And the valley you reach is the one below your start, not always the deepest.

The rule is $\mathbf x_{\text{new}}=\mathbf x-\gamma\nabla f(\mathbf x)$. On a bowl the slope is a spring, $\nabla f=A\mathbf x+\mathbf b$, and the bottom is $\mathbf x^*=-A^{-1}\mathbf b$. A trench has one stiff spring and one soft one, so a single stride bounces across it while crawling along it.

Each step multiplies the distance to the bottom by $1-\gamma\lambda$. Keep that between $-1$ and $1$, which means $\gamma<2/\lambda$. With many directions, the stiffest one ($\lambda_{\max}$) sets the limit for all, and the softest one sets how slowly you crawl.

Line search fixes the direction $-\mathbf g$, then slides to the bottom of $h(\gamma)=f(\mathbf x-\gamma\mathbf g)$. At the best stride, the new slope is at a right angle to the step. On a bowl, that stride is $\gamma^*=\mathbf g^{\top}\mathbf g/\mathbf g^{\top}A\mathbf g$.

Trap the bottom in a bracket and squeeze. Halving leaves width $(b-a)/2^k$ after $k$ rounds; golden cuts shrink it by $0.618$ per round and reuse a probe. Or skip the hunt: Armijo accepts any stride with $h(\alpha)\le h(0)+c\,\alpha\,h'(0)$.

Start bold, finish careful. On a clock: $\alpha_0e^{-kt}$, $\alpha_0/(1+kt)$, or divide by a constant every few epochs. By feel: the bold driver multiplies the rate by $1.05$ after a good step, and undoes and halves after a bad one.

To audit a slope, nudge and divide. Forward, $\dfrac{J(w+\Delta)-J(w)}{\Delta}$, is off by about $\tfrac12J''\Delta$. Central, $\dfrac{J(w+\Delta)-J(w-\Delta)}{2\Delta}$, is off by about $\tfrac16J'''\Delta^2$. So use central, with a small but not tiny $\Delta$.

The loss is a sum over examples, so its slope is too. A random handful gives $\nabla J(S)=\sum_{i\in S}\nabla L_i$; scaled by $N/|S|$, it is right on average, and its noise shrinks like $1/\sqrt{|S|}$. Step on it: $\mathbf w\leftarrow\mathbf w-\alpha\,\nabla J(S)$. That is minibatch gradient descent; $|S|=1$ is stochastic, and $|S|=N$ is batch.

With a noisy slope and a fixed stride, the walker ends in a cloud around the bottom whose size grows with the stride: its variance is about $\gamma\sigma^2/2\lambda$, where $\sigma$ is the size of the noise. A shrinking stride with $\sum\gamma_t=\infty$ and $\sum\gamma_t^2<\infty$ closes the cloud. The same shake can lift a walker out of a shallow dip.

The bill is the total area of the patches: $J=\sum_i\text{miss}_i^2$. Its slope is every row's push, added up: $\nabla J=2\sum_i\text{miss}_i\,\mathbf X_i$.

A row that guessed too high pushes the knobs down along itself. A row that guessed too low pushes them up. A bigger miss pushes harder.

Start small, centred and random: small so the first step stays on the map, random so no two knobs are clones.

And when the numbers explode anyway, look at the factor $1-2\eta x^2$. It is the size of the data, not your start, that needs fixing.

More knobs than facts means a zero training bill is free, so a zero training bill means nothing. Judge a model on rows it has never seen.

Later units add a small charge for big knobs (a regulariser). Then "fits the data with small knobs" beats "fits the data with any knobs", and the learner wins.

A knob's sensitivity is its feature's size, squared: $\partial y/\partial w_j=x_j^2$. One stride moves knob $j$ by $\eta\,x_j^2\times|\text{miss}|$.

So features of different sizes make one knob overshoot while another crawls. No stride can serve both. Rescaling the features is the fix.

Rescaling changes the units, not the meaning. After standardising, every column has average $0$ and $\sum_i z_i^2=n$, so every column is the same size and one stride can serve every knob.

What rescaling does not fix: two columns that rise and fall together. That leftover comes back in Section 10.

Descent finds the valley downhill from where it starts, and the watershed decides which one. Restarts give $k$ chances: all fail with probability $(1-p)^k$.

With $d$ knobs of $k$ dips each, the dips multiply to $k^d$, and the chance of being right on every knob shrinks to $p^d$.

Step length is stride × tilt: $\gamma\,|\nabla f|$. Small tilt means small steps, whether or not you are near a valley. A flat of width $W$ and tilt $g$ costs about $W/(\gamma g)$ steps.

The cure comes next unit: momentum, which keeps rolling across the flat instead of deciding every footstep afresh.

Each direction shrinks by its own factor, $1-\eta\lambda$. The steepest direction sets the speed limit, $\eta<2/\lambda_{\max}$. At that limit the gentlest direction crawls, and $\kappa=\lambda_{\max}/\lambda_{\min}$ measures how badly.

Steepest descent is the best direction for this one step, never the best direction for the whole trip.

Along a contour the height does not change, so $\nabla F\cdot\delta\mathbf x=0$: the gradient is at right angles to every contour.

It points at the bottom only when the contours are circles. On ovals, the angle between "steepest" and "towards the bottom" is the zig-zag.

The bill's steepness in knob $j$ is $2\sum_ix_{ij}^2$: the column's size, squared. The full table of steepnesses is $H=2X^{\top}X$. Standardising makes every diagonal entry $2n$, so the walls level out: here $\kappa$ falls from $1487$ to $10.2$.

The part that survives is the off-diagonal, from columns moving together. Removing it takes a rotation, not a rescaling.

Every failure has a signature on the loss curve: blow-up, the train–test scissors, a growing zig-zag, fast-then-crawl, flat from the start, a different answer every run.

Every fix either reshapes the landscape or teaches the walker.

$$\begin{gathered}w_1\leftarrow(1-\eta)\,w_1\\ w_2\leftarrow(1-10\eta)\,w_2\end{gathered}$$

Each step multiplies every direction by its own number, and all those numbers share one $\eta$. Pick $\eta$ for the steep direction and the gentle one crawls. Pick it for the gentle one and the steep one blows up. No single stride serves both.

$$\begin{gathered}\mathbf v\leftarrow\beta\,\mathbf v-\alpha\nabla J\\ \mathbf w\leftarrow\mathbf w+\mathbf v,\qquad \mathbf v_0=\mathbf 0\end{gathered}$$

Each move is a faded copy of the last move plus a fresh push. Pushes that agree pile up to $1/(1-\beta)$ times one push — ten times at $\beta=0.9$. Pushes that flip cancel. You pay for the speed with overshoot.

$$\begin{gathered}A\leftarrow A+\nabla J\odot\nabla J\\ \mathbf w\leftarrow\mathbf w-\frac{\alpha}{\sqrt A}\odot\nabla J\end{gathered}$$

($\odot$ means "multiply entry by entry".) Each knob divides its step by the root of its own total. On step one this leaves exactly $\alpha$ for every knob, whatever its slope. But the total never shrinks, so the steps only ever get smaller.

$$\begin{gathered}A\leftarrow \rho\,A+(1-\rho)\,\nabla J\odot\nabla J\\ \mathbf w\leftarrow\mathbf w-\frac{\alpha}{\sqrt A}\odot\nabla J\end{gathered}$$

Swap the running total for a fading average, and the stride settles at a healthy size instead of dying. On a steady slope it settles at exactly $\alpha$. The price is a first step that is $1/\sqrt{1-\rho}$ times too big.

$$\begin{aligned}F&\leftarrow \rho_f F+(1-\rho_f)\nabla J\\ A&\leftarrow \rho A+(1-\rho)\nabla J\odot\nabla J\\ \mathbf w&\leftarrow\mathbf w-\alpha_t\,\frac{F}{\sqrt A}\\ \alpha_t&=\alpha\,\frac{\sqrt{1-\rho^{\,t}}}{1-\rho_f^{\,t}}\end{aligned}$$

Step = average direction ÷ root of average loudness, times a warm-up rate $\alpha_t$. Pushes that disagree cancel, loudness divides out, and the very first step is exactly $\alpha$.

$$\begin{gathered}\text{safe stride: }\ \alpha<\frac{2}{\lambda_{\max}}\\[4pt] \text{steps needed}\ \sim\ \kappa=\frac{\lambda_{\max}}{\lambda_{\min}}\end{gathered}$$

The steepest direction sets the safe stride. The gentlest direction sets how many steps you need. Their ratio $\kappa$ (read "kappa", the condition number) is the tax plain descent pays. The adaptive methods divide each slope by its own size, so they never see $\kappa$ at all.

$$\begin{gathered}\min_{\mathbf x}\ f(\mathbf x)\\ \text{subject to}\quad e(\mathbf x)=0,\quad g_i(\mathbf x)\le0\end{gathered}$$

Three roles, three pictures. $f$ is the score: you want it small. $e=0$ is the path: you must stay exactly on it. Each $g_i\le0$ is a fence: you must stay behind it. So $x\ge2$ becomes $g=2-x\le0$, whose slope is $\nabla g=-1$. Watch that minus sign — it is where most marks are lost.

$$\nabla f(\mathbf x^\star)=-\mu\,\nabla g(\mathbf x^\star),\qquad \mu\ge0$$

At the answer, nothing is left to slide along the fence. So the score's arrow and the fence's arrow lie on one line. They are parallel, not equal, and $\mu$ is the stretch between them. Soon $\mu$ will turn out to be a price.

$$\max_{\mu\ge0}\ \mu\,g \;=\; \begin{cases}0,& g\le0\\ +\infty,& g>0\end{cases}$$

$$\begin{aligned}L(\mathbf x,\lambda,\boldsymbol\mu)&=f(\mathbf x)+\lambda\,e(\mathbf x)\\ &\quad+\sum_i\mu_i\,g_i(\mathbf x),\qquad \mu_i\ge0\end{aligned}$$

Obey the fence and the guard's best fine is $\mu=0$: you pay nothing. Break it and the guard raises $\mu$ without limit. So the Lagrangian $L$ — score, plus a fine for leaving the path, plus a fine for each fence — is not a rough copy of the problem. It is the problem, with rules turned into prices.

$$\begin{gathered}g_i(\mathbf x)+t_i^{\,2}=0\\ \Longrightarrow\quad \boxed{\ \mu_i\,g_i(\mathbf x^\star)=0\ }\end{gathered}$$

Write the room left as a square and differentiate. Out comes $\mu_ig_i=0$: either you have room and the fine is zero, or you are touching and the fine may be positive. Never room and a fine at once.

$$\begin{gathered}\text{each fence: }\ \mu_i=0\ \ \text{or}\ \ g_i=0\\ \Longrightarrow\quad 2^m\ \text{cases}\end{gathered}$$

KKT is "set every derivative to zero" on the Lagrangian, plus the sign rule. To use it by hand, guess for each fence whether it is touching, solve, and throw out any guess that gives a negative fine or breaks a rule.

$$\begin{aligned}f\big(\theta\mathbf x+(1-\theta)\mathbf y\big)&\le\theta f(\mathbf x)\\ &\quad+(1-\theta)f(\mathbf y)\\[3pt] &\text{is the same as}\\[3pt] f(\mathbf y)&\ge f(\mathbf x)\\ &\quad+\nabla f(\mathbf x)^{\!\top}(\mathbf y-\mathbf x)\end{aligned}$$

The curve stays under every string, or, the same thing, above every tangent. The tangent form means one slope reading is a promise about the whole function. On a convex problem, a point that passes the five conditions is the answer.

$$\begin{aligned}p^\star&=\min_{\mathbf x}\ \max_{\mu\ge0}\ L(\mathbf x,\mu)\\ &\ge\ \max_{\mu\ge0}\ \min_{\mathbf x}\ L(\mathbf x,\mu)=d^\star\end{aligned}$$

Left, you move first: the primal. Right, the guard moves first: the dual. Moving second is an advantage, so the dual is always a lower bound. And the dual is the lowest of many straight lines, so it is always a hill.

$$\begin{gathered}q(\alpha)=2\alpha-2\alpha^2\\ \alpha^\star=\tfrac12,\qquad d^\star=\tfrac12=p^\star\end{gathered}$$

The boundary is built from the fines: in general $w=\sum_i\alpha_iy_ix_i$, with $\sum_i\alpha_iy_i=0$. Points far from the boundary get $\alpha_i=0$ and could be deleted. Only the touching points — the support vectors — matter.

Look at the cloud from every direction. For each one, drop the points onto the line and measure how spread out they land. Keep the direction with the biggest spread.

That is principal component analysis (PCA). Everything else in this unit is the machinery that does this search quickly, and the reason it works. On the 90 points, line A has spread $5.45$ and line B only $0.41$. You have just done PCA by eye.

A model can only explain change in $y$ using change in $\mathbf x$. So a direction along which the data barely changes carries almost no information, whatever the target is.

That is why PCA ranks directions by their spread — and why it can do so without ever looking at $y$.

$$C=\frac1N X^\top X$$

After centring, one small $D\times D$ table says how much each column moves (the diagonal) and which columns move together (the rest). From here on, $C$ is the only thing about the data that PCA will ever use.

$$\text{spread along }\mathbf w=\mathbf w^\top C\,\mathbf w$$

For any arrow $\mathbf w$ of length 1: one number for every direction, and no data needed. PCA is now a clean question: which unit arrow $\mathbf w$ makes $\mathbf w^\top C\mathbf w$ as big as possible?

$$C\mathbf w=\lambda\,\mathbf w$$

On the leash, the best direction is the place where the uphill arrow $2C\mathbf w$ points straight along $\mathbf w$. That is exactly what an eigenvector is. The directions PCA is looking for are the eigenvectors of $C$.

$$\mathbf w^\top C\mathbf w=\lambda$$

The spread along an eigenvector is its eigenvalue. So the largest spread is the largest eigenvalue, and it lives along that eigenvector. The same number is the stretch, the spread and the fine. That is why we always list eigenvalues from biggest to smallest, $\lambda_1\ge\lambda_2\ge\dots$: it is a ranking of directions by how much of the data they show.

$$\begin{gathered}C\mathbf w_d=\lambda_d\mathbf w_d\\ \lambda_1\ge\lambda_2\ge\dots\ge\lambda_D\ge0\end{gathered}$$

Each new component is the best direction of what is left. Whether you add a leash or peel off the old components, you land on the next eigenvector of the same $C$ — and they all meet at right angles for free.

$$\operatorname{tr}(C)=\lambda_1+\lambda_2+\dots+\lambda_D$$