
Matrix Gradients, Without the Pain
A simple trick for deriving gradients without drowning in subscripts
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
A simple trick for deriving gradients without drowning in subscripts
In this post I want to share a simple trick to make computing gradients and backward passes mechanical, without drowning in indices and ruining your eyesight.
To start with, let’s remember how we all first learned to compute gradients. Suppose we have a linear layer $Y = XW$, where $X$ is an $N\times D$ batch of inputs and $W$ is a $D\times F$ weight matrix, followed by some scalar loss $L(Y) \in \reals$. Suppose you already know the gradient of the loss with respect to the outputs, $\grad L(Y)$, an $N\times F$ matrix.
Write $\Lcal(W) = L(XW)$ for the loss as a function of the weights, with $X$ held fixed. Throughout the post, $L$ takes a layer’s output, and $\Lcal$ is the loss as a function of whatever we’re differentiating.
What’s the gradient of the loss with respect to $W$, $\grad \Lcal(W)$?
The rote way is to compute the answer one entry at a time.
Pick an entry $W_{ab}$ and apply the chain rule over every entry of $Y$, where $\partial L/\partial Y_{ij}$ is entry $(i,j)$ of $\grad L(Y)$:
Next, expand $Y_{ij} = \sum_k X_{ik}W_{kj}$ to find that $\partial Y_{ij}/\partial W_{ab}$ is $X_{ia}$ when $j = b$ and zero otherwise. That collapses the sum to
The last step is to recognize this sum as a matrix product. The index $i$ is summed over, but it sits first on both $X$ and $\grad L(Y)$, so one of them must be transposed. After staring at it, you land on $\grad \Lcal(W) = X\transpose \grad L(Y)$. That’s a lot of work for one of the simplest layers there is.
Here’s how I would compute the gradient (I’ll explain the notation later):
So $\grad \Lcal(W) = X\transpose \grad L(Y)$. There are no indices, and the transpose comes from moving $X$ across the inner product. Magical, right?
By the end of the post, you will understand the machinery behind this trick. The trick rests on clearly understanding two related ideas:
With these two ideas, we can compute gradient by following the same recipe.
Let $f: \reals^D \to \reals^{D'}$ be a function with vector input and vector output. The derivative of $f$ at some point $x\in \reals^D$ is a linear function written $\dd f_x: \reals^D \to \reals^{D'}$. It is the best linear approximation of how $f$ changes near $x$.
What does it mean to be the best linear approximation? Suppose you know $f(x)$ and you want to estimate $f(x + \dd x)$ for some small change $\dd x \in \reals^D$. Here $\dd x$ is a regular ol’ vector like any other. We could have written $\Delta x$, but the “differential” notation will pay off later. Given the small change $\dd x$, $\dd f_x$ outputs the first-order change in $f$:
where the residual $r(\dd x)$ decays faster than $\dd x$. For small changes $\dd x$, the change in the output is approximately the linear function $\dd f_x$ applied to $\dd x$: $f(x+\dd x) - f(x) \approx \dd_x f(\dd x)$.
Recall that every linear function between $\reals^D$ and $\reals^{D'}$ can be written as a matrix. For the derivative at a point $x$, $\dd f_x$, its matrix representation is the Jacobian $J_f(x)$:
Its entries are $(J_f(x))_{ij} = (\dd f_x(e_j))i$, where $e_j$ is the $j$th standard basis vector. Sometimes this is written as $J_f(x){ij} = \partial_j f_i(x)$. In automatic differentiation, multiplying the Jacobian by a vector like this is called a Jacobian-vector product, or forward-mode differentiation.
Suppose $f = g\circ h$, where $g$ and $h$ are vector-valued functions with vector-valued inputs and outputs. Define $y = h(x)$. Then the chain rule says:
In words: push the small change $\dd x$ through $h$’s derivative to get the change in $h$, then push the change in $h$ through $g$’s derivative to get the overall change in $f$.
To talk about gradients, we first need inner products.
The inner product of two vectors $a, b \in \reals^D$ is $\inner{a}{b} = a\transpose b = \sum_i a_i b_i$. For two matrices of the same shape, the standard inner product does the same thing, multiplying matching entries and summing them:
These properties will help us “move terms around” when computing gradients via inner products.
The gradient is only defined for scalar-valued functions, such as the loss function $L$ we saw at the beginning. So let’s consider a function $f: \reals^D\to \reals$. The derivative of $f$ at $x$, $\dd f_x$, is a linear function from $\reals^D$ to $\reals$.
The gradient of $f$ at $x$, written $\grad f(x)$, is the unique vector in $\reals^D$ such that for every $\dd x\in \reals^D$:
In other words, the inner product of $\dd x$ with the gradient vector gives the approximate change in $f$.
Why does such a vector exist, and why is it unique? Plug in the basis vector $\dd x = e_i$. The $i$th entry of $\grad f(x)$ must equal $\dd f_x(e_i)$, which is the partial derivative $\partial f/\partial x_i$. So the gradient is the vector of partial derivatives you already know, and this definition just describes it without indices. For a matrix input $W$, the same argument says entry $(i,j)$ of $\grad f(W)$ is $\partial f/\partial W_{ij}$. In every case, the gradient vector always has the same shape as the variable it’s taken with respect to.
For a fixed $x$, $\dd f_x$ takes an input $\dd x$ and returns a number. This is why a derivative acts like the row vector $\grad f(x)\transpose$, while $\grad f(x)$ itself is a column vector.
Characterizing the gradient as a dual representation of the derivative gives us a simple way to compute gradients by first computing derivatives (which lets us use the chain rule):
Let $f(x) = x\transpose A x$, where $A$ is a $D\times D$ matrix. We want $\grad f(x)$.
Before we start, let’s define our differential notation/shorthand, which we’ll use in our derivations.
Let $g(x) = Ax$. Its derivative applied to a small change $\dd x$ is $\dd g_x(\dd x) = A,\dd x$, because $g$ is linear, so its best linear approximation is itself. Differential notation writes this as $\dd(Ax) = A,\dd x$, which says “the derivative of the anonymous function $x \mapsto Ax$, applied to $\dd x$, is $A$ times $\dd x$.” In general, $\dd(\text{expression})$ means the derivative of $x \mapsto \text{expression}$ applied to $\dd x$2.
Let’s now return to our $f(x) = x\transpose A x$. Using the product rule and differential notation, step 1 is one line:
For step 2, we rewrite the result as an inner product with $\dd x$. The first term is a scalar, so it equals its own transpose, $(\dd x)\transpose Ax = x\transpose A\transpose \dd x$. So
By uniqueness of the gradient, $\grad f(x) = (A +A\transpose)x$.
I remember being confused why the chain rule we learned for derivatives didn’t work exactly for gradients. Gradients seemed to obey something that only resembled the chain rule. For example, in single-variable calculus the chain rule says $(g\circ h)'(x) = g'(h(x)), h'(x)$: the outer derivative times the inner derivative. Now take $\Lcal(x) = L(Wx)$ for a scalar loss $L$ and a matrix $W$. Its gradient is
The inner derivative $W$ shows up transposed, and it comes before the outer gradient instead of after. Where did the transpose come from, and why did the order flip? People often just wave it off as “oh it has to be like this to make the shapes work out.
Turns out, derivatives compose by the chain rule, but gradients compose via vector-Jacobian products. Suppose $f = g\circ h$ is scalar-valued, so $g$ is scalar-valued but $h$ need not be. For any $x\in \reals^D$ and any small change $\dd x\in \reals^D$, define $y=h(x)$ and $\dd y = \dd h_x(\dd x)$. The chain rule reads $\dd f_x(\dd x) = \dd g_y(\dd y)$. Writing both sides with the definition of the gradient gives:
for every small change $\dd x$, where $\dd y = \dd h_x(\dd x)$. This is the chain rule in inner-product form.
We can solve this equation for $\grad f(x)$, given $\grad g(y)$, just like backprop. To do this, express $\dd y$ in terms of $\dd x$ on the right-hand side, then rearrange until it reads $\inner{\textit{something}}{\dd x}$. That something is $\grad f(x)$.
Let’s see how to do this in general. First write the derivative of $h$ as its Jacobian, $\dd y = J_h(x),\dd x$ (see the Jacobian aside above), and hop it across the inner product:
By uniqueness of the gradient, we arrive at the chain rule for gradients:
This rule is the basis of backprop.3 Each layer takes the gradient flowing back from the layer above, $\grad g(y)$, and multiplies it by its own transposed Jacobian to get the gradient to pass further back. In practice you avoid materializing $J_h$, which could be enormous.
Writing $\grad$ everywhere gets heavy, so from here on I’ll use bars: $\bar y := \grad L(y)$ is the gradient of the loss with respect to an intermediate value $y$, and likewise $\bar x := \grad \Lcal(x)$ and $\bar W := \grad \Lcal(W)$ for whatever we’re differentiating. This bar notation comes from reverse-mode automatic differentiation, where $\bar y$ is called the adjoint of $y$4.
Take a single input instead of a batch: the layer is $y = Wx$, where $x$ is a column vector (e.g. a data point) and $W$ is a fixed $F\times D$ weight matrix, and $L(y)$ is a scalar loss on the output. Write $\Lcal(x) = L(Wx)$ for the loss as a function of the input. We want $\bar x$, and we know $\bar y$. Since $y = Wx$, $\dd y = W\dd x$. Then
By uniqueness of the gradient, the gradient of the loss with respect to the input is $\bar x = W\transpose \bar y$.
In the example above, $\dd \Lcal_x(\dd x) = \bar y\transpose W, \dd x$, and $W$ is the Jacobian of the inner function $x\mapsto Wx$. There are two orders in which to compute this product:
One vector-Jacobian product gives the whole gradient, while forward mode would need one Jacobian-vector product per input dimension. That is why neural networks are trained with backpropagation.
The inner-product definition of the gradient also works for scalar-valued functions of matrices. The only change is that we use the matrix inner product from earlier, $\inner{A}{B} = \trace{A\transpose B}$.
Now we can work through the example from the start of the post properly. Recall the linear layer $Y = XW$, where $X$ is an $N\times D$ batch of inputs, $W$ is a $D\times F$ weight matrix, and $L(Y)$ is a scalar loss. Hold $X$ fixed and treat $W$ as the input, so $\Lcal(W) = L(XW)$. We want $\bar W$, and we know $\bar Y$. The layer is linear in $W$, so $\dd Y = X,\dd W$. Then
By uniqueness of the gradient, the gradient of the loss with respect to the weight matrix is $\bar W = X\transpose \bar Y$, as we derived at the beginning. As an exercise, try computing $\bar X$, the gradient with respect to the activations5!
Now swap the layer for $y = W\inverse x$, where $W$ is a square invertible matrix, and let $\Lcal(W) = L(W\inverse x)$ be the loss as a function of $W$. We want $\bar W$. Following the steps above, $\inner{\bar W}{\dd W} = \inner{\bar y}{\dd y} = \inner{\bar y}{\dd (W\inverse), x}$. But what is $\dd (W\inverse)$?
Notice that $WW\inverse = I$. Take the derivative of both sides. The identity matrix is constant, so its derivative is zero, and the product rule gives the first line below. Multiplying on the left by $W\inverse$ gives the second.
Plugging this back in, and using $W\inverse x = y$:
So we get the gradient $\bar W = -(W\inverse)\transpose\bar y, y\transpose$.
Here is the whole method as a recipe. Say a scalar loss depends on some variable $\theta$ (an input, a weight matrix, anything) through a layer $y = h(\theta)$, and you already know $\bar y$, the gradient of the loss with respect to the layer’s output. Write $\Lcal(\theta) = L(h(\theta))$ for the loss as a function of $\theta$.
Recipe: finding $\bar\theta = \grad \Lcal(\theta)$
Remember, before taking any gradients, ask yourself if the function $f$ is a scalar function. ↩︎
Conveniently, this also covers $\dd x$ itself: the identity function
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。