11
\$\begingroup\$

I wrote a Java program implementing a neural network with backpropagation. For anyone who isn't familiar with Neural Networks and Backpropagation, here is a good resource. Here is another informational site with some code. (A great book/code that uses python is neuralnetworksanddeeplearning.com) Also the backpropagation is based on multilayer perceptrons.

I've tested it with XOR and Squaring numbers, and its taking too many numbers of epochs to learn. The XOR that is in the main method of this code works fairly quickly, but its largely in part because the learning rate and weight initialization are highly optimized.

I'd like it to learn faster. As it is, it's slower than expected, though it still works fine.

I would really just like someone to take a look at the train() and run() methods, because that is where it needs to be optimized.

import java.util.Arrays;
import java.util.Random;

public class OGmlp {

 public static class MLPLayer {

  float[] output;
  float[] input;
  float[] weights;
  float[] dweights;
  boolean isSigmoid = true;

  public MLPLayer(int inputSize, int outputSize, Random r) {
   output = new float[outputSize];
   input = new float[inputSize + 1];
   weights = new float[(1 + inputSize) * outputSize];
   dweights = new float[weights.length];
   initWeights(r);
  }

  public void setIsSigmoid(boolean isSigmoid) {
   this.isSigmoid = isSigmoid;
  }

  public void initWeights(Random r) {
   for (int i = 0; i < weights.length; i++) {
    weights[i] = (r.nextFloat() - 0.5f) * 4f;
   }
  }

  public float[] run(float[] in) {
   System.arraycopy(in, 0, input, 0, in.length);
   input[input.length - 1] = 1;
   int offs = 0;
   Arrays.fill(output, 0);
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < input.length; j++) {
     output[i] += weights[offs + j] * input[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += input.length;
   }
   return Arrays.copyOf(output, output.length);
  }

  public float[] train(float[] error, float learningRate, float momentum) {
   int offs = 0;
   float[] nextError = new float[input.length];
   for (int i = 0; i < output.length; i++) {
    float d = error[i];
    if (isSigmoid) {
     d *= output[i] * (1 - output[i]);
    }
    for (int j = 0; j < input.length; j++) {
     int idx = offs + j;
     nextError[j] += weights[idx] * d;
     float dw = input[j] * d * learningRate;
     weights[idx] += dweights[idx] * momentum + dw;
     dweights[idx] = dw;
    }
    offs += input.length;
   }
   return nextError;
  }
 }
 MLPLayer[] layers;

 public OGmlp(int inputSize, int[] layersSize) {
  layers = new MLPLayer[layersSize.length];
  Random r = new Random(1234);
  for (int i = 0; i < layersSize.length; i++) {
   int inSize = i == 0 ? inputSize : layersSize[i - 1];
   layers[i] = new MLPLayer(inSize, layersSize[i], r);
  }
 }

 public MLPLayer getLayer(int idx) {
  return layers[idx];
 }

 public float[] run(float[] input) {
  float[] actIn = input;
  for (int i = 0; i < layers.length; i++) {
   actIn = layers[i].run(actIn);
  }
  return actIn;
 }

 public void train(float[] input, float[] targetOutput, float learningRate, float momentum) {
  float[] calcOut = run(input);
  float[] error = new float[calcOut.length];
  for (int i = 0; i < error.length; i++) {
   error[i] = targetOutput[i] - calcOut[i]; // negative error
  }
  for (int i = layers.length - 1; i >= 0; i--) {
   error = layers[i].train(error, learningRate, momentum);
  }
 }

 public static void main(String[] args) throws Exception {
  float[][] train = new float[][]{new float[]{0, 0}, new float[]{0, 1}, new float[]{1, 0}, new float[]{1, 1}};
  float[][] res = new float[][]{new float[]{0}, new float[]{1}, new float[]{1}, new float[]{0}};
  OGmlp mlp = new OGmlp(2, new int[]{2, 1});
  mlp.getLayer(1).setIsSigmoid(false);
  Random r = new Random();
  int en = 500;
  for (int e = 0; e < en; e++) {

   for (int i = 0; i < res.length; i++) {
    int idx = r.nextInt(res.length);
    mlp.train(train[idx], res[idx], 0.3f, 0.6f);
   }

   if ((e + 1) % 100 == 0) {
    System.out.println();
    for (int i = 0; i < res.length; i++) {
     float[] t = train[i];
     System.out.printf("%d epoch\n", e + 1);
     System.out.printf("%.1f, %.1f --> %.3f\n", t[0], t[1], mlp.run(t)[0]);
    }
   }
  }
 }
}
\$\endgroup\$
  • \$\begingroup\$ Also, quick question: Is this the backpropogation you're talking about? I.e. are you making a "multilayer perceptron"? \$\endgroup\$ – Fund Monica's Lawsuit Jun 7 '15 at 20:16
  • \$\begingroup\$ Yes, it is a MLP \$\endgroup\$ – jonbon Jun 7 '15 at 20:17
  • \$\begingroup\$ Let's continue this in chat. It's getting a bit long for the comments :P \$\endgroup\$ – Fund Monica's Lawsuit Jun 7 '15 at 20:19
  • 3
    \$\begingroup\$ This question is being discussed on meta: Optimizing a genetic algorithm. \$\endgroup\$ – rolfl Jun 7 '15 at 21:07
  • \$\begingroup\$ Still interested? My stupid (no momentum, no tuning) implementation needs something like 2000 iterations for learning xor. How does yours? \$\endgroup\$ – maaartinus Jul 12 '15 at 2:11
5
\$\begingroup\$

So, this is going to be a performance focused review. I'm going to be sacrificing other things to get some more performance. Keep in mind that you should benchmark each run because JIT compilers, memory paging and all the other stuff that tries to make code run fast these days can and will sometimes do a better job than humans.

This is your run method...

  public float[] run(float[] in) {
   System.arraycopy(in, 0, input, 0, in.length);
   input[input.length - 1] = 1;
   int offs = 0;
   Arrays.fill(output, 0);
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < input.length; j++) {
     output[i] += weights[offs + j] * input[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += input.length;
   }
   return Arrays.copyOf(output, output.length);
  }

First, you duplicate an entire array just to change a single variable, with the line System.arraycopy(in, 0, input, 0, in.length). Let's not, and just temporarily store the altered variable in a temporary local variable:

  public float[] run(float[] in) {
   float oldLastValue = in[in.length - 1];
   in[in.length - 1] = 1;
   int offs = 0;
   Arrays.fill(output, 0);
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < in.length; j++) {
     output[i] += weights[offs + j] * in[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += in.length;
   }
   in[in.length - 1] = oldLastValue;
   return Arrays.copyOf(output, output.length);
  }

Next, we refer loads of times to in.length, and it could benefit from being cached (this inlining is questionable, benchmark it!):

  public float[] run(float[] in) {
   int inputArrayLength = in.length;
   float oldLastValue = in[inputArrayLength  - 1];
   in[inputArrayLength - 1] = 1;
   int offs = 0;
   Arrays.fill(output, 0);
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < inputArrayLength; j++) {
     output[i] += weights[offs + j] * in[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += inputArrayLength;
   }
   in[inputArrayLength - 1] = oldLastValue;
   return Arrays.copyOf(output, output.length);
  }

Next, we first fill the output array with all zero's with Arrays.fill(output, 0), and then we iterate over it again to add values with the j for loop. Why bother, just set the values in there straight away:

  public float[] run(float[] in) {
   int inputArrayLength = in.length;
   float oldLastValue = in[inputArrayLength  - 1];
   in[inputArrayLength - 1] = 1;
   for (int i = 0; i < output.length; i++) {
    output[i] = weights[i * inputArrayLength] * in[0];
   }
   int offs = 0;
   for (int i = 0; i < output.length; i++) {
    for (int j = 1; j < inputArrayLength; j++) {
     output[i] += weights[offs + j] * in[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += inputArrayLength;
   }
   in[inputArrayLength - 1] = oldLastValue;
   return Arrays.copyOf(output, output.length);
  }

But since you are setting the last index to 1 anyway, why not use the last index? Saves 1 array retrieval.

  public float[] run(float[] in) {
   int offsetPerIteration = in.length;
   int inputArrayLengthExcludingLast = in.length-1;
   for (int i = 0; i < output.length; i++) {
    output[i] = weights[(i * offsetPerIteration) + inputArrayLengthExcludingLast];
   }
   int offs = 0;
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < inputArrayLengthExcludingLast; j++) {
     output[i] += weights[offs + j] * in[j];
    }
    if (isSigmoid) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
    offs += offsetPerIteration;
   }
   return Arrays.copyOf(output, output.length);
  }

isSigmoid is also being a pain; it's being checked for every i. How about we check that later?

  public float[] run(float[] in) {
   int offsetPerIteration = in.length;
   int inputArrayLengthExcludingLast = in.length-1;
   for (int i = 0; i < output.length; i++) {
    output[i] = weights[(i * offsetPerIteration) + inputArrayLengthExcludingLast];
   }
   int offs = 0;
   for (int i = 0; i < output.length; i++) {
    for (int j = 0; j < inputArrayLengthExcludingLast; j++) {
     output[i] += weights[offs + j] * in[j];
    }
    offs += offsetPerIteration;
   }
   if (isSigmoid) {
    for (int i = 0; i < output.length; i++) {
     output[i] = (float) (1 / (1 + Math.exp(-output[i])));
    }
   }
   return Arrays.copyOf(output, output.length);
  }

If possible, you'd check isSigmoid somewhere completely different.

Lastly...

 public OGmlp(int inputSize, int[] layersSize) {
  layers = new MLPLayer[layersSize.length];
  Random r = new Random(1234);
  for (int i = 0; i < layersSize.length; i++) {
   int inSize = i == 0 ? inputSize : layersSize[i - 1];
   layers[i] = new MLPLayer(inSize, layersSize[i], r);
  }
 } 

Don't screw around with that ternary. Far easier to get rid of a local variable like so:

 public OGmlp(int inputSize, int[] layersSize) {
  Random r = new Random(1234);
  layers = new MLPLayer[layersSize.length];
  layers[0] = new MLPLayer(inputSize, layersSize[0], r);
  for (int i = 1; i < layersSize.length; i++) {
   layers[i] = new MLPLayer(layersSize[i - 1], layersSize[i], r);
  }
 }

Yes, it now crashes for layersSize.length == 0. Either add a check or don't support it. Like so:

 public OGmlp(int inputSize, int[] layersSize) {
  if(layersSize.length != 0){
   Random r = new Random(1234);
   layers = new MLPLayer[layersSize.length];
   layers[0] = new MLPLayer(inputSize, layersSize[0], r);
   for (int i = 1; i < layersSize.length; i++) {
    layers[i] = new MLPLayer(layersSize[i - 1], layersSize[i], r);
   }
  }
 }

Oh, and, lets fix that indentation a bit, shall we:

public float[] run(float[] in) {
    int offsetPerIteration = in.length;
    int inputArrayLengthExcludingLast = in.length-1;
    for (int i = 0; i < output.length; i++) {
        output[i] = weights[(i * offsetPerIteration) + inputArrayLengthExcludingLast];
    }
    int offs = 0;
    for (int i = 0; i < output.length; i++) {
        for (int j = 0; j < inputArrayLengthExcludingLast; j++) {
            output[i] += weights[offs + j] * in[j];
        }
        offs += offsetPerIteration;
    }
    if (isSigmoid) {
        for (int i = 0; i < output.length; i++) {
            output[i] = (float) (1 / (1 + Math.exp(-output[i])));
        }
    }
    return Arrays.copyOf(output, output.length);
}

That should increase the performance of the maintenance programmer =)

| improve this answer | |
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.