13
$\begingroup$

Question: is it possible to train a NN to distinguish between odd and even numbers only using as input the numbers themselves?

I have the following dataset:

Number Target
1      0
2      1
3      0
4      1
5      0
6      1
...   ...
99     0
100    1

I trained a NN with two input neurons (one being the variable Number, the other being a bias neuron), nine neurons in the hidden layer and one output neuron using a very simple genetic algorithm: at each epoch, two sets of weights "fight" against each other; the one with the highest error loses and it's replaced by a modified version of the winner.

The script easily solve simple problems like the AND, the OR and the XOR operators but get stuck while trying to categorise odd and even numbers. Right now the best it managed to do is to identify 53 numbers out of 100 and it took several hours. Whether I normalize or not the inputs seems to make no difference.

If I wanted to cheat I could just pre-processed the data and feed % 2 to the NN as an input but I don't want to do that; NN should be able to approximate every function, including the modulo operator (I believe). What am I doing wrong?

$\endgroup$
  • 1
    $\begingroup$ It seems that you are trying to approximate the "mod" function with a neural network. This is one of my favorite classes of problem - "when is it the right thing to approximate a chicken as a sphere". Finite element models are a great place for it. When asking this of neural network, I like to think in terms of "basis". We know the exact answer contains division by 2, and truncation while the classic network is vector multiplication and sigmoid functions. NN's are best used for interpolation, not extrapolation - so is your domain bounded? $\endgroup$ – EngrStudent - Reinstate Monica Jul 13 '15 at 13:15
  • 3
    $\begingroup$ I think your question goes deeper than the currently accepted answer. Consider the following generalization: construct a neural network (using only operations that can be expected to occur in the brain) that would compute n mod k, where n and k are its inputs. I wonder if this is possible with a feedforward network of fixed size. $\endgroup$ – user66081 Jul 18 '16 at 22:01
7
$\begingroup$

As with any machine learning task, the representation of your input plays a crucial role in how well you learn and generalise.

I think, the problem with the representation is that the function (modulo) is highly non-linear and not smooth in the input representation you've chosen for this problem.

I would try the following:

  1. Try a better learning algorithm (back-propagation/gradient descent and its variants).

  2. Try representing the numbers in binary using a fixed length precision.

  3. If your input representation is a b-bit number, I would ensure your training set isn't biased towards small or large numbers. Have numbers that are uniformly, and independently chosen at random from the range $[0, 2^b-1]$.

  4. As you've done, use a multi-layer network (try 2 layers first: i.e., hidden+output, before using more layers).

  5. Use a separate training+test set. Don't evaluate your performance on the training set.

$\endgroup$
  • $\begingroup$ I was thinking that performing a transformation on the inputs like computing the natural logarithm might be valuable. $\endgroup$ – EngrStudent - Reinstate Monica Jul 13 '15 at 13:16
  • $\begingroup$ It might. In fact, knowing the answer here (modulo 2 is just the last bit), the binary representation of the raw number would work extremely well. Just connect the last bit of input to the output. :) It would be interesting to see if modulo (not-power-of-2) works well with a neural network. It may not work as well. $\endgroup$ – Vimal Jul 13 '15 at 15:00
  • $\begingroup$ Hi @Vimal, thank you for the answer. Do you know whether representing the inputs in binary is always a good idea or it just happened to be helpful in this specific case? $\endgroup$ – Edgar Derby Jul 13 '15 at 16:22
  • $\begingroup$ @AnnoysParrot - there are no "silver bullets". There is no single universal best representation because best can mean different and mutually exclusive things. The binary representation is useful in this case, but there are plenty where it is not. Consider deep-learning on visual data. If you had a separate input neuron for each unique input bit, you would need about 256*5.2 million inputs for a 5 Megapixel image. $\endgroup$ – EngrStudent - Reinstate Monica Jul 13 '15 at 17:29
  • 2
    $\begingroup$ Agree with @EngrStudent here. A lot of prior knowledge goes into designing a suitable input representation and also the neural network topology itself. Since a neural network is roughly a continuous, differentiable equivalent of a digital circuit, you can adapt the topology of the network using inspiration from digital circuits for addition/multiplication/division/modulo/etc. This prior on the topology (instead of a fully connected layer) can lead to faster training, better generalisation, etc., much like how convnets worked well for natural images. $\endgroup$ – Vimal Jul 14 '15 at 12:27
5
$\begingroup$

So I'm working with neural nets right now and I ran into the same issue as you. What I ended up doing was representing the input number as an array with values equal to the binary representation of the number. Since what we are doing is classifying I represented my output as an array, not a single value. ex:

input = [
  [0, 0, 0, 1], // 1
  [0, 0, 1, 0], // 2
  [0, 0, 1, 1], // 3
  [0, 1, 0, 0]  // 4
]
output = [
  [1, 0], // odd
  [0, 1], // even
  [1, 0], // odd
  [0, 1]  // even
]

Hope this helps!

$\endgroup$
  • 1
    $\begingroup$ Exactly based on your answer I created the model in here stackoverflow.com/questions/53671491/… $\endgroup$ – prosti Jan 16 at 21:01
  • $\begingroup$ Superb! This shows how the representation of data is important for any ML algorithm. When I used decimal representation, I got exactly 50 % accuracy, but following this idea, I got 100% accuracy even on unseen data. Thanks. Here is the implementation: colab.research.google.com/drive/… $\endgroup$ – Kaushal28 May 30 at 20:36
  • 2
    $\begingroup$ In binary, even numbers always end in 0 and odd numbers always end in 1. It's not surprising that the model works, since it's likely that it just learned to spit out the value of the last digit. $\endgroup$ – Syncrossus Jun 7 at 11:59
4
$\begingroup$

Learning to classify odd numbers and even numbers is a difficult problem. A simple pattern keeps repeating infinitely. 2,4,6,8..... 1,3,5,7.....

Nonlinear activation functions like sin(x) and cos(x) behave similarly. Therefore, if you change your neurons to implement sin and cos instead of popular activation functions like tanh or relu, I guess you can solve this problem fairly easily using a single neuron.

Linear transformations always precede nonlinear transformations. Therefore a single neuron will end up learning sin(ax+b) which for the right combination of a & b will output 0's and 1's alternatively in the desired frequency we want which in this case is 1.

I have never tried sin or cos in my neural networks before. So, apologies if it ends up being a very bad idea.

$\endgroup$
2
$\begingroup$

I get here where was struggle with similar problem. So I write what I managed.

As far as I know one layer perceptron is able to solve every problem, which can be at the end simplified to divide objects in any geometry using straight line. And this is this kind of problem. If you draw last bit of binary representation on paper you can also draw line, and all Odd numbers are on one side, and Even on other. For the same reason it is impossible to solve xor problem with one layer network.

Ok. This problem looks very simple, so lets take Heaviside step as activation function. After I played a little with my number I realized that problem here is with bias. I google a little, and what I found is that if you stay with geometry representation, bias enable you to change place of activation in coordinate system.

Very educational problem

$\endgroup$
0
$\begingroup$

It is well known that logic gates NOT, AND, OR can all be done with very simple neural networks (NN), and that you can build a complete arithmetic calculator with logic gates using binary numbers as input. Therefore you should be able to create a NN to calculate n modulo k, for any n and k numbers expressed in base 2.

If you wish to calculate n modulo k for a fixed k number (for example k = 4) you can actually create an extremely simple NN that does that: express the input number n in base k, and ignore all digits other than the lowest rank digit, and you have the answer!

$\endgroup$
0
$\begingroup$

One idea evading the use of explicit "mod 2" in the input could be to codify the number as a sequence of pixels, then the problem amounts to recognize if the segment can be split into two equal segments. This is a machine vision problem and that could be learned by conventional networks.

On the other extreme, if the number is stored as a float, the question reduces (or generalizes) to recognize when a float number is approximately an integer.

$\endgroup$
  • $\begingroup$ Interesting thought. Can you elaborate how would you like to codify the number into pixels? $\endgroup$ – Jan Kukacka Feb 21 '18 at 20:22
  • $\begingroup$ well, think "base 1". To codify n, draw a black bar having n pixels. My guess is that convolution kernels will notice the difference between an odd and an even number of pixels. $\endgroup$ – arivero Feb 22 '18 at 3:13
0
$\begingroup$

I created such a network in here.

The representation @William Gottschalk gave was the foundation.

It just uses 1 neuron in the first hidden layer with 32 inputs. The output layer has just 2 neurons for one-hot encoding of 0 and 1.

$\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.