What kind of data structures are needed to efficiently do back-propagation in a feedforward neural network?

Question

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?

Answer 1

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 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) 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.

Answer 2

When I check the Tensorflow tool code, it looks like they implemented own data structure for neural network operation including back propagation. The custom data structure is EagerTensor.

I think to speed up the operation speed, the Tensorflow used the TFRECORD file type/format.

Additionally, for neural network structure (they called Graph), they used the Protocol Buffer format.