Производная как матрица: от Тейлора до наименьших квадратовThe derivative as a matrix: from Taylor to least squares

Entry: how much does the loss change

Let the loss of a model, $f(x)=\lVert b-Ax\rVert^2$, depend on a weight vector $x\in\R^N$. Move the weights by a small vector $u$. How much does the loss change? The answer of this lesson: approximately by $Df(x)\,u$, where $Df(x)=-2(b-Ax)^tA$ is a single row of $N$ numbers. To get this row honestly, the lecturer starts from a function of one variable and replaces the number by a matrix step by step.

The derivative through little-o

Zoom far into the graph of a smooth function near a point $x_0$, and it is almost indistinguishable from a straight line. The slope of that line is the derivative: the change of the function equals “slope × shift” plus something much smaller than the shift.

Example. $f(x)=x^2$, $x_0=3$: $f(3+h)-f(3)=9+6h+h^2-9=6h+h^2$. The term $h^2$ is $o(h)$ because $h^2/h=h\to0$. So $f'(3)=6$. For $h=0.01$ the change is $0.06+0.0001$: the linear part gives almost everything.

The lecturer writes the chain rule in Leibniz notation, $\frac{dy}{dx}=\frac{dy}{du}\cdot\frac{du}{dx}$ — the lecturer’s favorite notation. Below, the product of numbers in this formula becomes a product of matrices.

The mean value theorem

If a car covered 120 km in two hours, then at some moment its speedometer showed exactly 60 km/h. On the graph: the chord between the endpoints is parallel to the tangent line at some interior point.

Compare with the little-o formula. There the derivative is taken at a known point, but there is an error $o(h)$. Here the equality is exact, but the point $\xi$ is unknown. All we know is that $\xi$ lies strictly inside $(a,b)$ — and in the proof of Taylor’s theorem this turns out to matter.

Example. $f(x)=x^2$ on $[1,3]$: $f(3)-f(1)=8$ and $f'(\xi)(3-1)=4\xi$, so $\xi=2$ — inside the interval.

Taylor’s theorem with the Lagrange remainder

The linear approximation uses one derivative. Add the second, the third, and so on, and the polynomial also follows the bending of the graph. The price is an error, and it turns out to have an exact form, as in the mean value theorem.

Example. $f(x)=e^x$, $a=0$, $b=0.1$, $N=2$. All derivatives equal $e^x$, and at zero they equal 1, so $e^{0.1}=1+0.1+\frac{0.01}{2}+\frac{e^{\xi}}{6}\cdot0.001=1.105+\frac{e^{\xi}}{6000}$ with $\xi\in(0,0.1)$. Since $e^{\xi}<e^{0.1}<2$, the error of the polynomial is less than $\frac{2}{6000}\approx0.0003$. The exact value is $e^{0.1}\approx1.10517$: the error is $0.00017$, and the bound holds.

The lecturer proved the theorem from the mean value theorem and explained why: mathematics is not a collection of facts but theorems linked by logic.

The proof in four steps

Idea. Replace $a$ by a variable $x$, build two helper functions that vanish at $b$, and apply the mean value theorem to a combination of them.

Step 1. Two helper functions.

At $x=b$ all powers $(b-x)^k$ vanish, so $\varphi(b)=f(b)-f(b)=0$ and $\psi(b)=0$. At $x=a$ we get $\psi(a)=(b-a)^{N+1}$, while $\varphi(a)$ is $f(b)$ minus the Taylor polynomial, that is, exactly the remainder we want to find.

Step 2. Derivatives. $\psi'(x)=-(N+1)(b-x)^N$ by the chain rule. For $\varphi$, each term of the sum is differentiated by the product rule, and the sum becomes telescoping: it has the form $(a_N-a_{N-1})+\dots+(a_1-a_0)$, and only $a_N-a_0$ survives. The result:

The intermediate computation is homework item 1: the lecturer asked you to redo it on your own.

Step 3. A Cauchy-style helper.

At $x=a$ both brackets containing $x$ vanish, so $F(a)=0$. At $x=b$ the two products coincide, so $F(b)=0$. By the mean value theorem $0=F(b)-F(a)=F'(\xi)(b-a)$ for some $\xi\in(a,b)$, that is,

Substitute $\psi(b)-\psi(a)=-(b-a)^{N+1}$, $\varphi(b)-\varphi(a)=-\varphi(a)$, and the derivatives from step 2:

Step 4. Cancel $(b-\xi)^N$. This is legal only because $\xi$ lies strictly inside $(a,b)$, so $b-\xi\ne0$. The lecturer stressed it: even this slight information about the point is useful. Divide by $(N+1)(b-\xi)^N$:

The Taylor series of $e^x$

With $a=0$, every derivative of $e^x$ equals 1 at zero, so for any $b$

We get a series if the remainder goes to zero as $N\to\infty$. The factor $e^{\theta}$ is at most $e^{\lvert b\rvert}$ and does not depend on $N$. It remains to see why $\lvert b\rvert^n/n!\to0$. A student’s argument in class: write $\frac{b^n}{n!}=\frac b1\cdot\frac b2\cdots\frac bn$. For example, with $b=3$ the first three factors give $4.5$, and every later factor is at most $\frac34$, so $\frac{3^n}{n!}\le4.5\cdot\left(\frac34\right)^{n-3}\to0$. Hence $e^x=\sum_{k\ge0}\frac{x^k}{k!}$ for all $x$: the series converges to $e^x$ because the error of the finite polynomial is under control.

Vectors, covectors, and matrices

The lecturer’s notation, used for everything below:

• $\R^N$ — columns of height $N$; coordinates carry upper indices: $x=(x^1,\dots,x^N)^t$.
• $M_{m\times n}$ — real matrices with $m$ rows and $n$ columns; the entry $a_{ij}$ sits in row $i$, column $j$.
• $(\R^N)^*$ — rows, covectors: a row $a^t$ takes a column $x$ and returns the number $a^tx$.
• A column and a row are just matrices with one column or one row. A number is a $1\times1$ matrix.

On the board the lecturer puts arrows over vectors ($\vec x$); here the arrows are omitted, and a vector is always a column.

Example. $a=(1,2)^t$; then $a^t$ is a covector, and $a^tx=x^1+2x^2$ for $x\in\R^2$. A $1\times1$ matrix does not change under transposition: $(a^tx)^t=x^ta=a^tx$. This fact resolves the main difficulty of the section on least squares.

Length and inner product of matrices

An $m\times n$ matrix can be read as a long vector of $mn$ numbers. Then its length is the square root of the sum of squares of all entries, and the inner product is the sum of products of corresponding entries.

The transpose is needed here: $A^tB$ is a square $n\times n$ matrix, it has a trace, and $\langle A,A\rangle\ge0$. For columns the formula becomes the familiar $x^ty$, because the trace of a $1\times1$ matrix is that matrix itself.

Example. $A=\begin{pmatrix}1&2\\0&3\end{pmatrix}$: $A^tA=\begin{pmatrix}1&0\\2&3\end{pmatrix}\begin{pmatrix}1&2\\0&3\end{pmatrix}=\begin{pmatrix}1&2\\2&13\end{pmatrix}$, the trace is $1+13=14$, and the sum of squares of the entries is $1+4+0+9=14$. So $\lVert A\rVert=\sqrt{14}$.

Length gives distance, and distance gives limits: “$u\to0$” means $\lVert u\rVert\to0$.

Example. $A=(1\ \ 2)$, $B=(3,4)^t$: $AB=(11)$, trace 11; $BA=\begin{pmatrix}3&6\\4&8\end{pmatrix}$, trace $3+8=11$.

The board also listed inequalities: $\lVert x+y\rVert\le\lVert x\rVert+\lVert y\rVert$, $\lVert Ax\rVert\le\lVert A\rVert\,\lVert x\rVert$, $\lVert A+B\rVert\le\lVert A\rVert+\lVert B\rVert$, $\lVert AB\rVert\le\lVert A\rVert\,\lVert B\rVert$. Their proofs and the proof of the cyclic property are homework.

The derivative of a map $\R^N\to\R^D$ is a $D\times N$ matrix

The same sentence as for numbers: the change equals the linear part plus something negligible. Only now the shift is a vector $u\in\R^N$, the change is a vector in $\R^D$, and “multiply by a number” becomes “multiply by a matrix”.

Example. $f:\R^3\to\R^2$, $f(x)=\big(x^1x^2,\ x^2+(x^3)^2\big)^t$, $x_0=(1,2,1)^t$. Partial derivatives:

Size $2\times3$: two components, three variables.

Gradient and directional derivative

When $D=1$, the matrix $Df(x_0)$ is a $1\times N$ row. The gradient is its transpose, a column: $\nabla f(x_0)=Df(x_0)^t$. The lecturer insisted: the gradient is a vector, not a covector.

Proof. For $u=0$ both sides are zero. Let $u\ne0$. By the definition with the vector $hu$ in place of $u$: $f(x_0+hu)-f(x_0)=Df(x_0)(hu)+o(\lVert hu\rVert)$. Divide by $h$:

The first fraction goes to zero, and the absolute value of the second equals $\lVert u\rVert$ and does not depend on $h$. The product goes to zero. ∎

This is the main computing tool of the lesson: to find the matrix $Df(x_0)$, compute this limit for an arbitrary $u$ and read off what multiplies $u$.

Example. $f(x)=(x^1)^2x^2$, $x_0=(1,2)^t$, $u=(1,1)^t$. Partial derivatives give $Df(x_0)=(2x^1x^2,\ (x^1)^2)=(4,\ 1)$, and $Df(x_0)u=4+1=5$. Check by the limit: $f(1+h,2+h)=(1+2h+h^2)(2+h)=2+5h+4h^2+h^3$, so $\frac{f(x_0+hu)-f(x_0)}{h}=5+4h+h^2\to5$.

The chain rule as a matrix product

The essential special case. Let $y=f(u^1,\dots,u^N)$ and $u^j=g^j(t)$, $u_0^j=g^j(t_0)$. If $Df(u_0)$ exists and all $(g^j)'(t_0)$ exist, then

The right-hand side is not on the board photo; it is the standard formula, and it follows from the general form below. The condition is the existence of the whole matrix $Df(u_0)$, not only of the partial derivatives.

The lecturer gave the proof in the next lecture (lesson m02).

Example. $G(x)=(x^1+x^2,\ x^1-x^2)^t$, $F(u)=u^1u^2$, $x_0=(2,1)^t$. Then $u_0=G(x_0)=(3,1)^t$, $DF(u_0)=(u^2,\ u^1)=(1,\ 3)$, $DG=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$, and

Check: $F(G(x))=(x^1)^2-(x^2)^2$, with partial derivatives $2x^1=4$ and $-2x^2=-2$.

The lecturer’s example: least squares

$f(x)=\lVert b-Ax\rVert^2$, $x\in\R^N$, $A\in M_{D\times N}$, $b\in\R^D$ — the loss of linear regression. The lecturer derived its derivative by the scheme that is worked out in full in the model problem below. Two rules from that derivation:

• Never differentiate a length; differentiate the squared length. A length behaves like $\lvert x\rvert$, which has no derivative at zero, while the squared length is a product $(b-Ax)^t(b-Ax)$.
• A number equals its own transpose. The two middle terms of the expansion coincide: $(Au)^t(b-Ax_0)=\big((Au)^t(b-Ax_0)\big)^t=(b-Ax_0)^tAu$.

The result, boxed on the board:

Derivative with respect to a matrix: trace and cyclic property

Let $X\in M_{m\times n}$ be the variable, $a\in\R^m$ and $b\in\R^n$ fixed, and $f(X)=a^tXb$ a number.

The limit takes one line because $f$ is linear: $\frac{a^t(X_0+hU)b-a^tX_0b}{h}=a^tUb$. The difficulty is elsewhere: $U$ is trapped in the middle, and matrix multiplication is not commutative, so you cannot simply move it to the right. The lecturer’s trick uses two facts: a number equals its own trace, and the trace is cyclic:

So $Df(X_0)=ba^t$, an $n\times m$ matrix. Its transpose $ab^t$ has the same shape as $X$; ML libraries call this shape-matched form the gradient.

Example. $m=2$, $n=3$, $a=(1,2)^t$, $b=(1,0,1)^t$: $Df(X_0)=ba^t=\begin{pmatrix}1&2\\0&0\\1&2\end{pmatrix}$, size $3\times2$. Check one entry: the shift $U$ with a one in row 1, column 1 and zeros elsewhere gives $a^tUb=a^1b^1=1$, and $\tr(Df(X_0)\,U)$ equals the entry of $Df(X_0)$ in row 1, column 1, which is also 1.

What should stay with you

1. The derivative is the best linear approximation: change $=$ linear part $+\,o(\cdot)$.
2. The mean value theorem is an exact equality at an unknown point $\xi$ strictly inside the interval.
3. The Lagrange remainder $\frac{f^{(N+1)}(\xi)}{(N+1)!}(b-a)^{N+1}$ gives a guaranteed error bound for a Taylor polynomial.
4. For $f:\R^N\to\R^D$ the derivative is the $D\times N$ matrix of partial derivatives, and the gradient $\nabla f=(Df)^t$ is a column.
5. The matrix $Df(x_0)$ is found through the limit $\frac{f(x_0+hu)-f(x_0)}{h}$ by reading off the coefficient of $u$.
6. Chain rule: $D(F\circ G)=DF\cdot DG$, with sizes $D\times N$ and $N\times M$.
7. Do not differentiate a length — differentiate the squared length; a number equals its own transpose.
8. For a function of a matrix: a number $=$ its trace, the cyclic property moves $U$ to the right, $Df(X_0)\in M_{n\times m}$.