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:


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

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


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];
            nablaB.set(n, MLMaths.add(nb, dnb));

        // 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];
            nablaW.set(n, MLMaths.add(nw, dnw));

    // 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)));
            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)));


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);
        z = MLMaths.add(z, b);

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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.