1
\$\begingroup\$

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];
            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)));
        }
        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<>();
    activations.add(x);

    //  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)
        zs.add(z);

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

        //  activations.append(activation)
        activations.add(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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.