Answers.Body: <p>When I check <a href="https://github.com/tensorflow/tensorflow" rel="nofollow noreferrer">the Tensorflow tool code</a>, it looks like they implemented own data structure for neural network operation including back propagation. The custom data structure is <a href="https://github.com/tensorflow/tensorflow/blob/v2.9.0/tensorflow/python/framework/ops.py#L1049" rel="nofollow noreferrer">EagerTensor</a>.</p>
  <p>I think to speed up the operation speed, the Tensorflow used <a href="https://www.tensorflow.org/tutorials/load_data/tfrecord" rel="nofollow noreferrer">the TFRECORD file</a> type/format.</p>
  <p>Additionally, for neural network structure (they called Graph), they used <a href="https://chromium.googlesource.com/external/github.com/tensorflow/tensorflow/+/r0.10/tensorflow/g3doc/how_tos/tool_developers/index.md" rel="nofollow noreferrer">the Protocol Buffer format</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-23T21:22:59.097Z
Answers.LastActivityDate: 2022-05-23T21:22:59.097Z
Answers.UserDisplayName: Cloud Cho
Answers.Body: <p><strong>TL;DR</strong>: You'll need to store a little bit more to perform backward passes. You'll need to store data from the forward pass. This stored information is used for calculating the gradient.</p>
  
  <p><strong>Overview</strong> (warning: not trivial)</p>
  
  <blockquote>
    <p>I know the weights can just be stored in an array</p>
  </blockquote>
  
  <p>You'll need a little more:</p>
  
  <p>To update the weights you need to keep a "cache" of the forward pass intermediate terms. That is, forward propagation can be seen as a series of transformations on your input <span class="math-container">$X$</span>:
  <span class="math-container">$$X\xrightarrow{\Theta^{[1]}+b^{[1]}} [ Z^{[1]} \xrightarrow{\alpha^{[1]}} A^{[1]}] \xrightarrow{\Theta^{[2]}+b^{[2]}}
  \dots 
  \xrightarrow{\Theta^{[L]}+b^{[L]}} [ Z^{[L]} \xrightarrow{\alpha^{[L]}} A^{[L]}]\xrightarrow{\frac{1}{m}\sum\limits_m\sum\limits_{n_L} loss\{A^{[L]},y\}} J
  $$</span></p>
  
  <p>where:</p>
  
  <p><span class="math-container">$Z^{[1]}=\Theta^{[1]}X+b^{[1]}$</span> (ie the linear part)</p>
  
  <p><span class="math-container">$A^{[l]}=\alpha^{[l]}(Z^{[l]})$</span> (ie element wise activation over linear part)</p>
  
  <p>You need to store the <span class="math-container">$Z^{[l]}$</span> &amp; <span class="math-container">$A^{[l]}$</span> terms in said "cache." You could store these in an array or some other similar data structure. You need these for calculating the gradient during the backwards pass. </p>
  
  <p><strong>Syntax</strong></p>
  
  <p><span class="math-container">$A^{[k]}$</span> - this means we are indexing by layer (eg <span class="math-container">$\alpha^{[k]}$</span> is the activation for k-th layer)</p>
  
  <p><span class="math-container">$m$</span> - is the number of examples in the batch</p>
  
  <p><span class="math-container">$n_k$</span> - denotes the number of neurons in the k-th layer</p>
  
  <p><span class="math-container">$L$</span> - the number of layers (so <span class="math-container">$n_L$</span> is the number of neurons in last layer)</p>
  
  <p><span class="math-container">$\Theta$</span> - The set of <em>all</em> weights (notice no superscript)</p>
  
  <p><strong>Backprop</strong></p>
  
  <p>In the case of neural networks the cost is a scalar function of inputs and parameters. To get backprop started calculate the <a href="https://en.wikipedia.org/wiki/Matrix_calculus#Scalar-by-matrix" rel="nofollow noreferrer">scalar by matrix</a> derivative of the cost with respect to the activations of the last layer call this matrix <span class="math-container">$dA^{[L]}$</span>. Observe:</p>
  
  <p><span class="math-container">$dA^{[L]} = \frac{\partial J(\Theta,X)}{\partial A^{[L]}}$</span></p>
  
  <p>Next, we calculate scalar-by-matrix derivative of <span class="math-container">$Z^{[L]}$</span>. Doing this one realizes:</p>
  
  <p><span class="math-container">$dZ^{[L]} = \frac{\partial J(\Theta,X)}{\partial Z^{[L]}} = dA\odot\alpha'^{[L]}(Z^{[L]})$</span></p>
  
  <p>Where <span class="math-container">$\odot$</span> denotes element wise (<a href="https://en.wikipedia.org/wiki/Hadamard_product_(matrices)" rel="nofollow noreferrer">Hadamard</a>) product.</p>
  
  <p>With the above one can make use of the matrix definitions for back propagation:</p>
  
  <p><span class="math-container">$\text{(A)}\quad d\Theta^{[l]} = \frac{1}{m}dZ^{[l]}\times (A^{[l-1]})^T$</span></p>
  
  <p><span class="math-container">$\text{(B)}\quad db^{[l]} = \frac{1}{m}\sum_{c=1}^m dZ^{[l](c)}$</span> (where the new superscript in <span class="math-container">$dZ^{[l](c)}$</span> denotes summing along the <em>batch</em> dimension )</p>
  
  <p><span class="math-container">$\text{(C)} \quad dZ^{[l]}= dA^{[l]}\odot \alpha^{'[l]}(Z^{[l]})$</span></p>
  
  <p><span class="math-container">$\text{(D)}\quad dA^{[k]} = (\Theta^{[k+1]})^T\times dZ^{[k+1]}$</span></p>
  
  <p>And of course the wight updates are:</p>
  
  <p><span class="math-container">$\Theta^{[L]} \leftarrow \Theta^{[L]} - \frac{\eta}{m}d\Theta $</span> </p>
  
  <p><span class="math-container">$b^{[L]} \leftarrow b^{[L]} - \frac{\eta}{m}db $</span> </p>
  
  <p>(where <span class="math-container">$\eta$</span> is the learning rate)</p>
  
  <p>Observe, how the forward pass terms are used during the backprop calculations. </p>
  
  <p><strong>A recommendation</strong></p>
  
  <p>Take the A. Ng deep learning specialization. He does a good job explaining the intuition and even has a project to implement this. Though, he does not derive the back propagation equations. You can find a not so easy derivation <a href="https://rojasinate.com/documents/backprop.pdf" rel="nofollow noreferrer">here</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-25T14:41:09.227Z
Answers.Text: During the backward pass can we "free" some cache? I mean when we calculate the gradient of loss $L$ with respect to layer $\ell_n$, i.e. $\frac{dL}{d\ell_{n}}$, we only need $\frac{dL}{d_{\ell-1}} \cdot \frac{d\ell_{n-1}}{d\ell_{n}}$. So can we remove from cache all terms above $\ell_{n-1}$?
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-26T16:22:23.620Z
Answers.Text: @adosar You could: (1) free it as you do the backward pass (2) free it all at the end of the backward pass (3) Use a mutable data-structure and replace the data during the next pass. Depends on you preferences/needs/constraints.
Answers.UserDisplayName: respectful
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-10T04:51:56.317Z
Answers.LastActivityDate: 2019-11-10T16:53:33.937Z
Answers.LastEditDate: 2019-11-10T16:53:33.937Z
Answers.UserDisplayName: respectful
Body: <p>In a feed-forward neural network, in order to efficiently do backpropagation, what kind of data structure is needed? </p>
  
  <p>I know the weights can just be stored in an array, and you need pointers of some kind to represent connections from one layer to the next (or just a default scheme/pattern), but is anything else needed for backpropagation to work?</p>
  
Tags: <neural-networks><backpropagation><feedforward-neural-networks>
Title: What kind of data structures are needed to efficiently do back-propagation in a feedforward neural network?
UserDisplayName: Michael Hearn
ThreadText: # What kind of data structures are needed to efficiently do back-propagation in a feedforward neural network?
  
  (Asked by: username_0 on 2019-11-10)
  
  In a feed-forward neural network, in order to efficiently do backpropagation, what kind of data structure is needed?
  
  I know the weights can just be stored in an array, and you need pointers of some kind to represent connections from one layer to the next (or just a default scheme/pattern), but is anything else needed for backpropagation to work?
  
  **Tags:** neural-networks, backpropagation, feedforward-neural-networks
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-11-10. Score: 2 | Accepted answer
  
  **TL;DR**: You'll need to store a little bit more to perform backward passes. You'll need to store data from the forward pass. This stored information is used for calculating the gradient.
  
  **Overview** (warning: not trivial)
  
  > I know the weights can just be stored in an array
  
  You'll need a little more:
  
  To update the weights you need to keep a "cache" of the forward pass intermediate terms. That is, forward propagation can be seen as a series of transformations on your input $X$:
  $$X\xrightarrow{\Theta^{[1]}+b^{[1]}} [ Z^{[1]} \xrightarrow{\alpha^{[1]}} A^{[1]}] \xrightarrow{\Theta^{[2]}+b^{[2]}}
  \dots
  \xrightarrow{\Theta^{[L]}+b^{[L]}} [ Z^{[L]} \xrightarrow{\alpha^{[L]}} A^{[L]}]\xrightarrow{\frac{1}{m}\sum\limits\_m\sum\limits\_{n\_L} loss\{A^{[L]},y\}} J
  $$
  
  where:
  
  $Z^{[1]}=\Theta^{[1]}X+b^{[1]}$ (ie the linear part)
  
  $A^{[l]}=\alpha^{[l]}(Z^{[l]})$ (ie element wise activation over linear part)
  
  You need to store the $Z^{[l]}$ & $A^{[l]}$ terms in said "cache." You could store these in an array or some other similar data structure. You need these for calculating the gradient during the backwards pass.
  
  **Syntax**
  
  $A^{[k]}$ - this means we are indexing by layer (eg $\alpha^{[k]}$ is the activation for k-th layer)
  
  $m$ - is the number of examples in the batch
  
  $n\_k$ - denotes the number of neurons in the k-th layer
  
  $L$ - the number of layers (so $n\_L$ is the number of neurons in last layer)
  
  $\Theta$ - The set of *all* weights (notice no superscript)
  
  **Backprop**
  
  In the case of neural networks the cost is a scalar function of inputs and parameters. To get backprop started calculate the [scalar by matrix](https://en.wikipedia.org/wiki/Matrix_calculus#Scalar-by-matrix) derivative of the cost with respect to the activations of the last layer call this matrix $dA^{[L]}$. Observe:
  
  $dA^{[L]} = \frac{\partial J(\Theta,X)}{\partial A^{[L]}}$
  
  Next, we calculate scalar-by-matrix derivative of $Z^{[L]}$. Doing this one realizes:
  
  $dZ^{[L]} = \frac{\partial J(\Theta,X)}{\partial Z^{[L]}} = dA\odot\alpha'^{[L]}(Z^{[L]})$
  
  Where $\odot$ denotes element wise ([Hadamard](https://en.wikipedia.org/wiki/Hadamard_product_(matrices))) product.
  
  With the above one can make use of the matrix definitions for back propagation:
  
  $\text{(A)}\quad d\Theta^{[l]} = \frac{1}{m}dZ^{[l]}\times (A^{[l-1]})^T$
  
  $\text{(B)}\quad db^{[l]} = \frac{1}{m}\sum\_{c=1}^m dZ^{[l](c)}$ (where the new superscript in $dZ^{[l](c)}$ denotes summing along the *batch* dimension )
  
  $\text{(C)} \quad dZ^{[l]}= dA^{[l]}\odot \alpha^{'[l]}(Z^{[l]})$
  
  $\text{(D)}\quad dA^{[k]} = (\Theta^{[k+1]})^T\times dZ^{[k+1]}$
  
  And of course the wight updates are:
  
  $\Theta^{[L]} \leftarrow \Theta^{[L]} - \frac{\eta}{m}d\Theta $
  
  $b^{[L]} \leftarrow b^{[L]} - \frac{\eta}{m}db $
  
  (where $\eta$ is the learning rate)
  
  Observe, how the forward pass terms are used during the backprop calculations.
  
  **A recommendation**
  
  Take the A. Ng deep learning specialization. He does a good job explaining the intuition and even has a project to implement this. Though, he does not derive the back propagation equations. You can find a not so easy derivation [here](https://rojasinate.com/documents/backprop.pdf).
  
  > **Comments:**
  > **username_3**: During the backward pass can we "free" some cache? I mean when we calculate the gradient of loss $L$ with respect to layer $\ell_n$, i.e. $\frac{dL}{d\ell_{n}}$, we only need $\frac{dL}{d_{\ell-1}} \cdot \frac{d\ell_{n-1}}{d\ell_{n}}$. So can we remove from cache all terms above $\ell_{n-1}$?  
  > **username_2**: @adosar You could: (1) free it as you do the backward pass (2) free it all at the end of the backward pass (3) Use a mutable data-structure and replace the data during the next pass. Depends on you preferences/needs/constraints.  
  
  ---
  
  ### Answer by username_1 on 2022-05-23. Score: 0
  
  When I check [the Tensorflow tool code](https://github.com/tensorflow/tensorflow), it looks like they implemented own data structure for neural network operation including back propagation. The custom data structure is [EagerTensor](https://github.com/tensorflow/tensorflow/blob/v2.9.0/tensorflow/python/framework/ops.py#L1049).
  
  I think to speed up the operation speed, the Tensorflow used [the TFRECORD file](https://www.tensorflow.org/tutorials/load_data/tfrecord) type/format.
  
  Additionally, for neural network structure (they called Graph), they used [the Protocol Buffer format](https://chromium.googlesource.com/external/github.com/tensorflow/tensorflow/+/r0.10/tensorflow/g3doc/how_tos/tool_developers/index.md).
  
  
  ---
  
  