Higher Order of Vectorization in Backpropagation in Neural Network - Cross Validated most recent 30 from stats.stackexchange.com 2019-06-26T08:12:50Z https://stats.stackexchange.com/feeds/question/368084 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://stats.stackexchange.com/q/368084 2 Higher Order of Vectorization in Backpropagation in Neural Network Wei https://stats.stackexchange.com/users/221317 2018-09-21T20:06:37Z 2019-04-19T23:07:16Z <p>I am learning a machine learning class online from Stanford, namely CS 229. There is one section about deep learning and back-propagation in deep learning.</p> <p>The network looks like:</p> <p><a href="https://i.stack.imgur.com/FeNRC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FeNRC.png" alt="Network Structure"></a> </p> <p>The forward propagation can be defined as:</p> <p><a href="https://i.stack.imgur.com/ASrQU.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ASrQU.png" alt="Forward Calculation"></a></p> <p>where g is the activation function. </p> <p>The dimensions of each variable can also be given as:</p> <p><a href="https://i.stack.imgur.com/3X37W.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3X37W.png" alt="Dimensions"></a> </p> <p>Now, for back-propagation, by using chain rule, we can get:</p> <p><a href="https://i.stack.imgur.com/spLta.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/spLta.png" alt="Chain Rule"></a></p> <p>To match up with the dimensions, we have:</p> <p><a href="https://i.stack.imgur.com/wLh8t.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wLh8t.png" alt="Results"></a></p> <p>I know that after applying chain rule, the normal way is to calculate generalized Jacobian matrix and do matrix multiplication. However, the dimension of each part in chain rule above does not match what generalized Jacobian matrix will give us. For example, for the last term in chain rule, the dimension from generalized Jacobian matrix should be (2 X 1) X (2 X 3). However, what course notes say is 1 X 3. </p> <p>Why is it true? </p> <p>Any comments are appreciated! </p> https://stats.stackexchange.com/questions/368084/-/404046#404046 0 Answer by shimao for Higher Order of Vectorization in Backpropagation in Neural Network shimao https://stats.stackexchange.com/users/26948 2019-04-19T23:07:16Z 2019-04-19T23:07:16Z <p>You're right that that doesn't make sense as the Jacobian. Furthermore if multiplying jacobians was really how autodiff worked, any pointwise function applied on vector of length <span class="math-container">$n$</span> would result in a huge <span class="math-container">$n \times n$</span> Jacobian being created. This is not what happens in any competant autodiff implementation.</p> <p>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.</p> <p>If you have a function <span class="math-container">$f : \mathbb{R}^n \rightarrow \mathbb{R}^m$</span>, then <span class="math-container">$\text{VJP} : \mathbb{R}^m \times \mathbb{R}^n \rightarrow \mathbb{R}^n$</span> is a function which computes <span class="math-container">$\text{VJP}(g,x) = J_f(x)^T g$</span>, where <span class="math-container">$g$</span> is the incoming gradient vector <span class="math-container">$\frac{\partial \mathcal{L}}{\partial f}$</span> and <span class="math-container">$J_f(x)$</span> is the jacobian of <span class="math-container">$f$</span>. Technically this is a JVP rather than VJP but that's just a matter of convention.</p> <p>The key point is that although one way to implement the VJP is explicitly computing the jacobian and then performing this vector-matrix product, if you are able to compute the VJP without doing that, it is also perfectly fine.</p> <p>For example, the VJP for <span class="math-container">$\sin(x)$</span> is just <span class="math-container">$\text{VJP}(g,x) = g \circ \cos(x)$</span>. The VJP of <span class="math-container">$f(W, x) = Wx$</span> with respect to <span class="math-container">$x$</span> is simply <span class="math-container">$\text{VJP}(g, W, x) = W^Tg$</span> and the VJP with respect to <span class="math-container">$W$</span> is <span class="math-container">$\text{VJP}(g, W, x) = gx^T$</span></p> <p>Returning to your question: the expression in 3.30 is actually just computing <span class="math-container">$\text{VJP}(g, W, x) = gx^T$</span>, with all the terms on the RHS except for the right-most being part of <span class="math-container">$g$</span>, and the last term being <span class="math-container">$x^T$</span>.</p>