# Matrix and Vector Approaches to Backpropagation in a Neural Network

I recently implemented a neural network, with backpropagation in a fully matrix approach, as described here, where the whole dataset is used for each backprop: http://ufldl.stanford.edu/wiki/index.php/Neural_Network_Vectorization

This worked very quickly, much quicker than one run through of example by example backpropagation, which I will call vectorised here, based more on an iterative style like http://ufldl.stanford.edu/wiki/index.php/Backpropagation_Algorithm

However it took many iterations of the matrix backprop to achieve an 85% accuracy on MNIST, whereas vectorised I got 93% in one epoch. I understand this is because the vectorised approach updates the weights each example, so slowly converges, hence the matrix approach would need a bigger learning rate or much more iterations to achieve the same gradient descent, however, this completely defeated the point of the matrix approach as it ended up taking longer to run it with the required iterations. Note this was not GPU accelerated.

I was wondering if anyone has experience with trying to fully matrix the backprop, and if I am going wrong, or missing something or whether it is in fact best to do example by example because of the updated weights each step.

Many thanks,

• MATLAB is optimized for vectorized calculations. Did your matrix approach use for-loops? – jvolzer Feb 14 '17 at 19:14
• No for loops in the matrix implementation, infact I was using the above equations as a guide and using Numpy on python, can post the code if interested. – olliejday Feb 14 '17 at 20:19
• @olliejday -- if your implementation is fully vectorized and python / numpy only, I'd be interested to see your code (for my learning). – n8henrie Jul 16 '17 at 0:17
• @n8henrie -- it is, will try and get it uploaded and post here soon! I got a lot of inspiration from the book "Make your own neural network" - good place to start – olliejday Jul 22 '17 at 8:40

What it sounds like you are describing is that you are performing Batch Gradient Descent in your matrix implementation, and Mini Batch (size = 1) in your vector (iterative) implementation.

• Batch Gradient Descent: you run all the training data through the network, compute the total error, then propagate the error back.
• Mini Batch Gradient Descent: You run a subset of training data through the network compute the error within that subset and propagate the error back.
• Stochastic Gradient Descent: A special case of Mini Batch Gradient Descent where you select a random subset of training data for each iteration.
• Note that Batch size can be 1 or more.

It is common for matrix implementations to bundle all training data into a single matrix. This is likely because it is appealing to take advantage of the fact that you can feed-forward and back propagate, each with a single operation instead of doing a for-loop over each training sample. It can also makes the code read more concisely (less code, no for-loops, etc).

As you have noticed, this doesn't necessarily lead to more optimal training.

The solution is to not pass the entire training data matrix through your network. Instead, assuming that each row in the matrix represents a single training sample, iterate over each row, and pass it independently through your network and perform error calculation and back propagation one sample at a time.

If you choose to use Stochastic Gradient Descent, randomly select a single row to train on each iteration.

Below is a random sample of my code for training MNIST digits. The training matrix consists of 60,000 samples. Each row being a separate image. I am training via Stochastic Gradient Descent (randomly selecting training data, back propagate after each sample.)

val mnistImageLoader = MNISTImageLoader()
// load a double matrix of mnist data, each row is a sample

val visibleSize = 28 * 28
val hiddenSize = (visibleSize * 0.75).toInt()
val layer = AutoEncoder(
learningRate = 0.1,
visibleSize = visibleSize,
hiddenSize = hiddenSize)

val rand = Random()
(0.. 10000).forEach { i ->
// select a single random row of image data
val x = xs.getRow(rand.nextInt(xs.rows))
// feed-forward, calculate error, back-propagate for singe sample
layer.learn(x, 1) // learn one-step
// compute error for current training sample
val error = Errors.compute(x, layer.feedForward(x))
println(error)
}


choosing the best mini-batch size is a compromise. Too small, and you don't get to take full advantage of the benefits of good matrix libraries optimized for fast hardware. Too large and you're simply not updating your weights often enough. What you need is to choose a compromise value which maximizes the speed of learning.

Michael Neilson