# Stochastic gradient descent - backpropagation over mini-batches in one go

I have been working through a tutorial on neural networks. I have then been translating the code to java, to help improve my understanding of what the code is doing.

The book mentions a way of speeding up the program:

Our implementation of stochastic gradient descent loops over training examples in a mini-batch. It's possible to modify the backpropagation algorithm so that it computes the gradients for all training examples in a mini-batch simultaneously. The idea is that instead of beginning with a single input vector, x, we can begin with a matrix X=[x1x2…xm] whose columns are the vectors in the mini-batch. We forward-propagate by multiplying by the weight matrices, adding a suitable matrix for the bias terms, and applying the sigmoid function everywhere. We backpropagate along similar lines.

I get the concept of treating the items in a mini-batch as an array of items, but I'm struggling to figure out the maths for implementing this change.

I've posted because the code is working; I'm just wanting to implement this improvement to get it to run faster.

In the code below, the comments are (mostly) the python code that the java was translated from:

SGD

// for j in xrange(epochs):
for (int j = 1; j <= maxEpochs; j++)
{
// random.shuffle(training_data)
Collections.shuffle(trainingData);

// mini_batches = [training_data[k:k+mini_batch_size] for k in xrange(0, trainingData.size, mini_batch_size)]
ArrayList<ArrayList<MnistEntry>> miniBatches = MLMaths.segment(trainingData, miniBatchSize);

// for mini_batch in mini_batches:
for (ArrayList<MnistEntry> miniBatch : miniBatches)
{
//  self.update_mini_batch(mini_batch, eta)
if (!miniBatch.isEmpty())
{
updateMiniBatch(miniBatch, schedule.eta, lambda, nTraining, regStrategy);
}
}

// etc.
}


updateMiniBatch

private void updateMiniBatch(ArrayList<MnistEntry> miniBatch, double eta, double lambda, int totalSizeOfTrainingSet
, RegularisationStrategy regStrategy)
{
// nabla_b = [np.zeros(b.shape) for b in self.biases]
ArrayList<double[][]> nablaB = MLMaths.fill(0.0, biases);

// nabla_w = [np.zeros(w.shape) for w in self.weights]
ArrayList<double[][]> nablaW = MLMaths.fill(0.0, weights);

// for x, y in mini_batch:
// TODO: Speed improvement by multiplying over the minibatch all at once (see http://neuralnetworksanddeeplearning.com/chap2.html#backprop_over_minibatch)
for (int i = 0; i < miniBatch.size(); i++)
{
MnistEntry e = miniBatch.get(i);
// double[pixels_in_image][1] - each pixel in the image is represented by a double[] containing a single value in the range 0..1 (white..black)
double[][] x = e.getImageDataAsDoubles();
double[][] y = e.getLabelAsArray(); // answer, vectorised array of length 10, where each entry is a double[1] containing either {0} for the incorrect answer; or {1} for the correct answer.

// delta_nabla_b, delta_nabla_w = self.backprop(x, y)
// note: using SimpleEntry as the simplest Pair type in java - they're not really key-value
SimpleEntry<ArrayList<double[][]>, ArrayList<double[][]>> deltaNablas = backprop(x,y);

ArrayList<double[][]> deltaNablaB = deltaNablas.getKey();
ArrayList<double[][]> deltaNablaW = deltaNablas.getValue();

// nabla_b = [nb+dnb for nb, dnb in zip(nabla_b, delta_nabla_b)]
ArrayList<double[][][]> zipB = MLMaths.zip(nablaB, deltaNablaB);

for (int n = 0; n <zipB.size(); n++)
{
double[][] nb = zipB.get(n)[0];
double[][] dnb = zipB.get(n)[1];
}

// nabla_w = [nw+dnw for nw, dnw in zip(nabla_w, delta_nabla_w)]
ArrayList<double[][][]> zipW = MLMaths.zip(nablaW, deltaNablaW);

for (int n = 0; n <zipW.size(); n++)
{
double[][] nw = zipW.get(n)[0];
double[][] dnw = zipW.get(n)[1];
}
}

// eta/len(mini_batch)

double etaOverMBSize = (eta / miniBatch.size()); // calculate here to save repeated calcualtion, as these values don't change
double regularisationRate = 1;
if (regStrategy == RegularisationStrategy.L1 || regStrategy == RegularisationStrategy.L2)
{
regularisationRate = ((eta*lambda)/(double)totalSizeOfTrainingSet);
}
else if(regStrategy == RegularisationStrategy.NONE)
{
regularisationRate = 1;
}

// for L2 regularisation,
// self.weights = [(1-eta*(lmbda/n))*w-(eta/len(mini_batch))*nw for w, nw in zip(self.weights, nabla_w)]
// for L1 reg:
// self.weights = [w-((eta*(lmbda/n))*sgn(w))-(eta/len(mini_batch))*nw for w, nw in zip(self.weights, nabla_w)]
ArrayList<double[][][]> zipW = MLMaths.zip(weights, nablaW);

for (int n = 0; n <zipW.size(); n++)
{
double[][] w = zipW.get(n)[0];
double[][] nw = zipW.get(n)[1];

if (regStrategy == RegularisationStrategy.L1)
{
weights.set(n, MLMaths.subtract(MLMaths.subtract(w, MLMaths.multiply(regularisationRate, MLMaths.sign(w))),MLMaths.multiply(etaOverMBSize, nw)));
}
else if (regStrategy == RegularisationStrategy.L2)
{
weights.set(n, MLMaths.multiply(1-regularisationRate, MLMaths.subtract(w, MLMaths.multiply(etaOverMBSize, nw))));
}
else if (regStrategy == RegularisationStrategy.NONE)
{
weights.set(n, MLMaths.subtract(w, MLMaths.multiply(etaOverMBSize, nw)));
}
else
{
throw new IllegalArgumentException("Regularisation Strategy " + regStrategy + " not implemented.");
}
}

// self.biases = [b-(eta/len(mini_batch))*nb for b, nb in zip(self.biases, nabla_b)]
ArrayList<double[][][]> zipB = MLMaths.zip(biases, nablaB);

for (int n = 0; n <zipB.size(); n++)
{
double[][] b = zipB.get(n)[0];
double[][] nb = zipB.get(n)[1];

biases.set(n, MLMaths.subtract(b, MLMaths.multiply(etaOverMBSize, nb)));
}
}


Backpropagation

private SimpleEntry<ArrayList<double[][]>, ArrayList<double[][]>> backprop(double[][] x, double[][] y)
{
// nabla_b = [np.zeros(b.shape) for b in self.biases]
ArrayList<double[][]> nablaB = MLMaths.fill(0.0, biases);

// nabla_w = [np.zeros(w.shape) for w in self.weights]
ArrayList<double[][]> nablaW = MLMaths.fill(0.0, weights);

// # feedforward

// activation = x
double[][] activation = x;

// activations = [x] # list to store all the activations, layer by layer
ArrayList<double[][]> activations = new ArrayList<>();

//  zs = [] # list to store all the z vectors, layer by layer
ArrayList<double[][]> zs = new ArrayList<>();

// for b, w in zip(self.biases, self.weights):
ArrayList<double[][][]> zip = MLMaths.zip(biases, weights);

for (double[][][] bw : zip)
{
double[][] b = bw[0];
double[][] w = bw[1];

//z = np.dot(w, activation)+b
double[][] z = MLMaths.dotProduct(w, activation);

// zs.append(z)

// activation = sigmoid(z)
activation = MLMaths.sigmoid(z);

//  activations.append(activation)
}

// # backward pass

// delta = (self.cost).delta(zs[-1], activations[-1], y)
double[][] delta = cost.delta(zs.get(zs.size()-1), activations.get(activations.size()-1), y);

// nabla_b[-1] = delta
nablaB.set(nablaB.size()-1, delta);

//nabla_w[-1] = np.dot(delta, activations[-2].transpose())
nablaW.set(nablaW.size()-1, MLMaths.dotProduct(delta, MLMaths.transpose(activations.get(activations.size()-2))));

// for l in xrange(2, self.num_layers):
for (int l = 2; l < numLayers; l++)
{
// z = zs[-l]
double[][] z = zs.get(zs.size()-l);

// sp = sigmoid_prime(z)
double[][] sp = MLMaths.sigmoidPrime(z);

// delta = np.dot(self.weights[-l+1].transpose(), delta) * sp
delta = MLMaths.multiply(MLMaths.dotProduct(MLMaths.transpose(weights.get((weights.size()-l)+1)),delta), sp);

// nabla_b[-l] = delta
nablaB.set(nablaB.size()-l, delta);

// nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())
nablaW.set(nablaW.size()-l, MLMaths.dotProduct(delta,MLMaths.transpose(activations.get((activations.size()-l)-1))));
}

// return (nabla_b, nabla_w)
return new SimpleEntry<>(nablaB, nablaW);
}


My intuition is saying that I should be able to get rid of the loop for (int i = 0; i < miniBatch.size(); i++) in the updateMiniBatch method altogether, by merging the x's into a double[][][]; and passing that into the backprop method instead.

The questions are:

• What is the maths (matrix transformations) required to make this work?
• Is this actually only a saving in Python, because it has more fully-formed mathematical operations?

The MLMaths class is a helper class I have written to do matrix mathematics on arrays in Java, specifically for this project. It's based on this.

The MnistEntry class simply stores the data in the correct format.