4
$\begingroup$

my questions is related to this post Higher Order of Vectorization in Backpropagation in Neural Network @shimao

I don't really get the following claim (I know how the chain rule works and what is the essence of how reverse mode autodifferentiation ): "In reality, it's not necessary to compute the jacobian in order to perform backpropagation. All that is needed is the "vector jacobian product", or VJP."

As far as I know, you need to compute the Jacobian at each step in order to perform the gradient accumulation. For example suppose we are in the step of computing the derivative of the following operation (very typical in neural networks):

$$ t = Wz, \,\,\, z\in \mathbb{R}^{m\times 1}, t \in \mathbb{R}^{n \times 1}, W\in\mathbb{R}^{n \times m} $$

Then we now that the vector derivative (the Jacobian) is given by:

$$ \frac{\partial t}{\partial z} = W $$

which is then plug into the chain rule (assume $\frac{\partial y}{\partial o}$ is the already computed gradient), to compute the final derivative given by the chain rule:

$$ \frac{\partial y}{\partial o} \frac{\partial t}{\partial z} $$

Hence, I dont really understand that sentence because that sentence says that we dont need to compute the Jacobian to perform the back propagation as we only need a Jacobian vector product; but clearly for this step we do need to obtein the Jacobian of the transformation between $t$ and $z$. Can someone provide a bit of intuition of what is exactly refering to?. In general I have seen that reverse-mode autodiff can be efficiently implemented through vector Jacobian products (and that doesn't require to compute the Jacobian), but when I think about it I realize that we do need to compute the Jacobian's at each step

$\endgroup$
6
  • 1
    $\begingroup$ perhaps my phrasing wasn't optimal -- I meant that it's not necessary to "materialize" the jacobian as either a dense or sparse matrix in computer memory. Of course you still can, and it makes sense to do so in the above example, but it doesn't make sense to for computing $\partial t/ \partial W$. $\endgroup$
    – shimao
    Jan 20, 2021 at 15:53
  • $\begingroup$ Thank you. I still don't see the main point, probably because I dont understand the essence. Could it be possible to get an explanation of what the vector Jacobian product is exactly and what would happen if we dont use it? I dont see any reason of computing all the Jacobians in the chain rule and then multiply them instead of making partial Jacobian multiplications $\endgroup$
    – jdeJuan
    Jan 20, 2021 at 16:08
  • $\begingroup$ what is a "partial jacobian multiplication?" $\endgroup$
    – shimao
    Jan 20, 2021 at 16:30
  • 1
    $\begingroup$ Consider $\partial t / \partial W$, which is an $n \times n \times m$ dimensional object. Wouldn't writing down every element of this jacobian be very expensive? Multiplying it with a jacobian or vector even moreso. Even in the special case where this object is sparse, you have to do a bunch of work to deal with sparse matrix ops. But in fact we don't care about all dimensions of this jacobian -- only how it acts on vectors. And it turns out it acts on some vector $g$ by sending it to $gz^T$. And this requires only $n$ operations, much less than the $n^2 m$ of writing down the full jacobian. $\endgroup$
    – shimao
    Jan 21, 2021 at 15:29
  • 1
    $\begingroup$ thanks. So basically it has to do with the fact that you only compute the necessary things that take part in the product you have to perform by the chain rule. $\endgroup$
    – jdeJuan
    Feb 4, 2021 at 8:05

1 Answer 1

0
$\begingroup$

I myself is new to this topic so I can't be sure. But I will tell you my intuition.

Regardless whether it is forward or backward mode AD, to evaluate the gradient is vector calculus that can be expressed as matrix-vector multiplications.

If you have an expression for the gradient: g=ABCDe, where A,B,C,D are matrices and e is an vector, in the computer program it is common that you have a way to obtain D*e directly with no explicit storage of D in memory.

Such example operation of D is like the negation of the vector, permutation of the vector elements, vector cross-product or convolutions. The core operation can be represented by much much less variables than the full expression of D as a matrix.

From the product of D*e, then you can apply C,B,A consecutively (without explicit expression) to obtain g.

This concept appears often in linear algebra. When you only require the product of a matrix and a vector, but not the matrix explicitly, it is way easier to implement the computation in program and have much lower memory requirement.

It just happens that this concept applies to AD calculation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.