24
$\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$
2
  • 2
    $\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$ Commented Jul 13, 2015 at 13:15
  • $\begingroup$ This problem would become so easy if we only considered the right-most number x_train = np.apply_along_axis(lambda x: x%10, arr=x_train, axis=1) x_test = np.apply_along_axis(lambda x: x%10, arr=x_test, axis=1) $\endgroup$ Commented Mar 20, 2022 at 12:48

8 Answers 8

9
$\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$
5
  • $\begingroup$ I was thinking that performing a transformation on the inputs like computing the natural logarithm might be valuable. $\endgroup$ Commented Jul 13, 2015 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
    Commented Jul 13, 2015 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$ Commented Jul 13, 2015 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$ Commented Jul 13, 2015 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
    Commented Jul 14, 2015 at 12:27
12
$\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$
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$
5
  • 1
    $\begingroup$ Exactly based on your answer I created the model in here stackoverflow.com/questions/53671491/… $\endgroup$
    – prosti
    Commented Jan 16, 2019 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
    Commented May 30, 2019 at 20:36
  • 5
    $\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
    Commented Jun 7, 2019 at 11:59
  • 2
    $\begingroup$ @Syncrossus Exactly that. This is just putting the answer as an input, so of course it will work. This solution does not generalize. The question is about divisibility by 2. Using binary representation most likely will not work when trying to train for the question "is it divisible by 3". $\endgroup$
    – mxmlnkn
    Commented Nov 23, 2020 at 16:43
  • 1
    $\begingroup$ This is a little misleading. If you convert the numbers to a binary representation then the neural network with a single layer would do as it can project to a space based just on the rightmost bit where the classes are linearly separable. The original question is more about what it would take for the lower layers in a neural net to put the intermediate representation in this form. Said different, one can ask for a neural network that gives the binary representation of a number. $\endgroup$ Commented Jan 28, 2022 at 10:48
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$
1
$\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$
1
$\begingroup$

My solution

import numpy as np


def layer_1_z(x, w1, b1):
    return 1 / w1 * x + b1


def layer_2(x, w1, b1, w2, b2):
    y1 = layer_1_z(x, w1, b1)
    y2 = y1 - np.floor(y1)
    return w2 * y2 + b2


def layer_2_activation(x, w1, b1, w2, b2):
    y2 = layer_2(x, w1, b1, w2, b2)
    # return 1 / (1 + np.exp(-y2))
    return (y2 > 0) * 1


def loss(param):
    w1, b1, w2, b2 = param
    x = np.arange(0, 1000, 1)
    y_hat = layer_2_activation(x, w1, b1, w2, b2)
    y_true = (x % 2 > 0) * 1
    return sum(np.square(y_hat - y_true))


# %%

from sko.GA import GA

ga = GA(func=loss, n_dim=4, size_pop=50, max_iter=100, lb=[1, 0, 1, 0], ub=[32, 1, 2, 1], precision=1)
best_x, best_y = ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

for x in range(1001, 1200):
    y_hat = layer_2_activation(x, *best_x)
    print('input:{},divide by 2:{}'.format(x, y_hat == 0))

input:1001,divide by 2:False input:1002,divide by 2:True input:1003,divide by 2:False input:1004,divide by 2:True input:1005,divide by 2:False input:1006,divide by 2:True input:1007,divide by 2:False input:1008,divide by 2:True input:1009,divide by 2:False input:1010,divide by 2:True input:1011,divide by 2:False input:1012,divide by 2:True input:1013,divide by 2:False input:1014,divide by 2:True input:1015,divide by 2:False input:1016,divide by 2:True input:1017,divide by 2:False input:1018,divide by 2:True input:1019,divide by 2:False input:1020,divide by 2:True input:1021,divide by 2:False input:1022,divide by 2:True input:1023,divide by 2:False input:1024,divide by 2:True input:1025,divide by 2:False input:1026,divide by 2:True input:1027,divide by 2:False input:1028,divide by 2:True input:1029,divide by 2:False input:1030,divide by 2:True input:1031,divide by 2:False input:1032,divide by 2:True input:1033,divide by 2:False input:1034,divide by 2:True input:1035,divide by 2:False input:1036,divide by 2:True input:1037,divide by 2:False input:1038,divide by 2:True input:1039,divide by 2:False input:1040,divide by 2:True input:1041,divide by 2:False input:1042,divide by 2:True input:1043,divide by 2:False input:1044,divide by 2:True input:1045,divide by 2:False input:1046,divide by 2:True input:1047,divide by 2:False input:1048,divide by 2:True input:1049,divide by 2:False input:1050,divide by 2:True input:1051,divide by 2:False input:1052,divide by 2:True input:1053,divide by 2:False input:1054,divide by 2:True input:1055,divide by 2:False input:1056,divide by 2:True input:1057,divide by 2:False input:1058,divide by 2:True input:1059,divide by 2:False input:1060,divide by 2:True input:1061,divide by 2:False input:1062,divide by 2:True input:1063,divide by 2:False input:1064,divide by 2:True input:1065,divide by 2:False input:1066,divide by 2:True input:1067,divide by 2:False input:1068,divide by 2:True input:1069,divide by 2:False input:1070,divide by 2:True input:1071,divide by 2:False input:1072,divide by 2:True input:1073,divide by 2:False input:1074,divide by 2:True input:1075,divide by 2:False input:1076,divide by 2:True input:1077,divide by 2:False input:1078,divide by 2:True input:1079,divide by 2:False input:1080,divide by 2:True input:1081,divide by 2:False input:1082,divide by 2:True input:1083,divide by 2:False input:1084,divide by 2:True input:1085,divide by 2:False input:1086,divide by 2:True input:1087,divide by 2:False input:1088,divide by 2:True input:1089,divide by 2:False input:1090,divide by 2:True input:1091,divide by 2:False input:1092,divide by 2:True input:1093,divide by 2:False input:1094,divide by 2:True input:1095,divide by 2:False input:1096,divide by 2:True input:1097,divide by 2:False input:1098,divide by 2:True input:1099,divide by 2:False input:1100,divide by 2:True input:1101,divide by 2:False input:1102,divide by 2:True input:1103,divide by 2:False input:1104,divide by 2:True input:1105,divide by 2:False input:1106,divide by 2:True input:1107,divide by 2:False input:1108,divide by 2:True input:1109,divide by 2:False input:1110,divide by 2:True input:1111,divide by 2:False input:1112,divide by 2:True input:1113,divide by 2:False input:1114,divide by 2:True input:1115,divide by 2:False input:1116,divide by 2:True input:1117,divide by 2:False input:1118,divide by 2:True input:1119,divide by 2:False input:1120,divide by 2:True input:1121,divide by 2:False input:1122,divide by 2:True input:1123,divide by 2:False input:1124,divide by 2:True input:1125,divide by 2:False input:1126,divide by 2:True input:1127,divide by 2:False input:1128,divide by 2:True input:1129,divide by 2:False input:1130,divide by 2:True input:1131,divide by 2:False input:1132,divide by 2:True input:1133,divide by 2:False input:1134,divide by 2:True input:1135,divide by 2:False input:1136,divide by 2:True input:1137,divide by 2:False input:1138,divide by 2:True input:1139,divide by 2:False input:1140,divide by 2:True input:1141,divide by 2:False input:1142,divide by 2:True input:1143,divide by 2:False input:1144,divide by 2:True input:1145,divide by 2:False input:1146,divide by 2:True input:1147,divide by 2:False input:1148,divide by 2:True input:1149,divide by 2:False input:1150,divide by 2:True input:1151,divide by 2:False input:1152,divide by 2:True input:1153,divide by 2:False input:1154,divide by 2:True input:1155,divide by 2:False input:1156,divide by 2:True input:1157,divide by 2:False input:1158,divide by 2:True input:1159,divide by 2:False input:1160,divide by 2:True input:1161,divide by 2:False input:1162,divide by 2:True input:1163,divide by 2:False input:1164,divide by 2:True input:1165,divide by 2:False input:1166,divide by 2:True input:1167,divide by 2:False input:1168,divide by 2:True input:1169,divide by 2:False input:1170,divide by 2:True input:1171,divide by 2:False input:1172,divide by 2:True input:1173,divide by 2:False input:1174,divide by 2:True input:1175,divide by 2:False input:1176,divide by 2:True input:1177,divide by 2:False input:1178,divide by 2:True input:1179,divide by 2:False input:1180,divide by 2:True input:1181,divide by 2:False input:1182,divide by 2:True input:1183,divide by 2:False input:1184,divide by 2:True input:1185,divide by 2:False input:1186,divide by 2:True input:1187,divide by 2:False input:1188,divide by 2:True input:1189,divide by 2:False input:1190,divide by 2:True input:1191,divide by 2:False input:1192,divide by 2:True input:1193,divide by 2:False input:1194,divide by 2:True input:1195,divide by 2:False input:1196,divide by 2:True input:1197,divide by 2:False input:1198,divide by 2:True input:1199,divide by 2:False


Moreover, divide by other numbers (say, 7) is well, too:

import numpy as np


def layer_1_z(x, w1, b1):
    return 1 / w1 * x + b1


def layer_2(x, w1, b1, w2, b2):
    y1 = layer_1_z(x, w1, b1)
    y2 = y1 - np.floor(y1)
    return w2 * y2 + b2


def layer_2_activation(x, w1, b1, w2, b2):
    y2 = layer_2(x, w1, b1, w2, b2)
    # return 1 / (1 + np.exp(-y2))
    return (y2 > 0) * 1


def loss(param):
    w1, b1, w2, b2 = param
    x = np.arange(0, 1000, 1)
    y_hat = layer_2_activation(x, w1, b1, w2, b2)
    y_true = (x % 7 > 0) * 1
    return sum(np.square(y_hat - y_true))


# %%

from sko.GA import GA

ga = GA(func=loss, n_dim=4, size_pop=50, max_iter=100, lb=[1, 0, 1, 0], ub=[32, 1, 2, 1], precision=1)
best_x, best_y = ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

for x in range(1001, 1200):
    y_hat = layer_2_activation(x, *best_x)
    print('input:{},divide by 7:{}'.format(x, y_hat == 0))

input:1001,divide by 7:True input:1002,divide by 7:False input:1003,divide by 7:False input:1004,divide by 7:False input:1005,divide by 7:False input:1006,divide by 7:False input:1007,divide by 7:False input:1008,divide by 7:True input:1009,divide by 7:False input:1010,divide by 7:False input:1011,divide by 7:False input:1012,divide by 7:False input:1013,divide by 7:False input:1014,divide by 7:False input:1015,divide by 7:True input:1016,divide by 7:False input:1017,divide by 7:False input:1018,divide by 7:False input:1019,divide by 7:False input:1020,divide by 7:False input:1021,divide by 7:False input:1022,divide by 7:True input:1023,divide by 7:False input:1024,divide by 7:False input:1025,divide by 7:False input:1026,divide by 7:False input:1027,divide by 7:False input:1028,divide by 7:False input:1029,divide by 7:True input:1030,divide by 7:False input:1031,divide by 7:False input:1032,divide by 7:False input:1033,divide by 7:False input:1034,divide by 7:False input:1035,divide by 7:False input:1036,divide by 7:True input:1037,divide by 7:False input:1038,divide by 7:False input:1039,divide by 7:False input:1040,divide by 7:False input:1041,divide by 7:False input:1042,divide by 7:False input:1043,divide by 7:True input:1044,divide by 7:False input:1045,divide by 7:False input:1046,divide by 7:False input:1047,divide by 7:False input:1048,divide by 7:False input:1049,divide by 7:False input:1050,divide by 7:True input:1051,divide by 7:False input:1052,divide by 7:False input:1053,divide by 7:False input:1054,divide by 7:False input:1055,divide by 7:False input:1056,divide by 7:False input:1057,divide by 7:True input:1058,divide by 7:False input:1059,divide by 7:False input:1060,divide by 7:False input:1061,divide by 7:False input:1062,divide by 7:False input:1063,divide by 7:False input:1064,divide by 7:True input:1065,divide by 7:False input:1066,divide by 7:False input:1067,divide by 7:False input:1068,divide by 7:False input:1069,divide by 7:False input:1070,divide by 7:False input:1071,divide by 7:True input:1072,divide by 7:False input:1073,divide by 7:False input:1074,divide by 7:False input:1075,divide by 7:False input:1076,divide by 7:False input:1077,divide by 7:False input:1078,divide by 7:True input:1079,divide by 7:False input:1080,divide by 7:False input:1081,divide by 7:False input:1082,divide by 7:False input:1083,divide by 7:False input:1084,divide by 7:False input:1085,divide by 7:True input:1086,divide by 7:False input:1087,divide by 7:False input:1088,divide by 7:False input:1089,divide by 7:False input:1090,divide by 7:False input:1091,divide by 7:False input:1092,divide by 7:True input:1093,divide by 7:False input:1094,divide by 7:False input:1095,divide by 7:False input:1096,divide by 7:False input:1097,divide by 7:False input:1098,divide by 7:False input:1099,divide by 7:True input:1100,divide by 7:False input:1101,divide by 7:False input:1102,divide by 7:False input:1103,divide by 7:False input:1104,divide by 7:False input:1105,divide by 7:False input:1106,divide by 7:True input:1107,divide by 7:False input:1108,divide by 7:False input:1109,divide by 7:False input:1110,divide by 7:False input:1111,divide by 7:False input:1112,divide by 7:False input:1113,divide by 7:True input:1114,divide by 7:False input:1115,divide by 7:False input:1116,divide by 7:False input:1117,divide by 7:False input:1118,divide by 7:False input:1119,divide by 7:False input:1120,divide by 7:True input:1121,divide by 7:False input:1122,divide by 7:False input:1123,divide by 7:False input:1124,divide by 7:False input:1125,divide by 7:False input:1126,divide by 7:False input:1127,divide by 7:True input:1128,divide by 7:False input:1129,divide by 7:False input:1130,divide by 7:False input:1131,divide by 7:False input:1132,divide by 7:False input:1133,divide by 7:False input:1134,divide by 7:True input:1135,divide by 7:False input:1136,divide by 7:False input:1137,divide by 7:False input:1138,divide by 7:False input:1139,divide by 7:False input:1140,divide by 7:False input:1141,divide by 7:True input:1142,divide by 7:False input:1143,divide by 7:False input:1144,divide by 7:False input:1145,divide by 7:False input:1146,divide by 7:False input:1147,divide by 7:False input:1148,divide by 7:True input:1149,divide by 7:False input:1150,divide by 7:False input:1151,divide by 7:False input:1152,divide by 7:False input:1153,divide by 7:False input:1154,divide by 7:False input:1155,divide by 7:True input:1156,divide by 7:False input:1157,divide by 7:False input:1158,divide by 7:False input:1159,divide by 7:False input:1160,divide by 7:False input:1161,divide by 7:False input:1162,divide by 7:True input:1163,divide by 7:False input:1164,divide by 7:False input:1165,divide by 7:False input:1166,divide by 7:False input:1167,divide by 7:False input:1168,divide by 7:False input:1169,divide by 7:True input:1170,divide by 7:False input:1171,divide by 7:False input:1172,divide by 7:False input:1173,divide by 7:False input:1174,divide by 7:False input:1175,divide by 7:False input:1176,divide by 7:True input:1177,divide by 7:False input:1178,divide by 7:False input:1179,divide by 7:False input:1180,divide by 7:False input:1181,divide by 7:False input:1182,divide by 7:False input:1183,divide by 7:True input:1184,divide by 7:False input:1185,divide by 7:False input:1186,divide by 7:False input:1187,divide by 7:False input:1188,divide by 7:False input:1189,divide by 7:False input:1190,divide by 7:True input:1191,divide by 7:False input:1192,divide by 7:False input:1193,divide by 7:False input:1194,divide by 7:False input:1195,divide by 7:False input:1196,divide by 7:False input:1197,divide by 7:True input:1198,divide by 7:False input:1199,divide by 7:False


Explanation:

I get 2 different solutions. They both are good:
1. sin as activation
2. floor(or int) as activation

It is impossible to find the best weights using gradient descent, and I use genetic algorithm (from scikit-opt)

$\endgroup$
2
  • 1
    $\begingroup$ Hi Man, welcome to CV and thank you for your detailed answer. Can you please add some explanation to the code you have written? $\endgroup$
    – Ferdi
    Commented Jan 13, 2020 at 8:50
  • $\begingroup$ I get 2 good solutions, see here, 1. sin as activation 2. floor(or int) as activation $\endgroup$
    – guofei9987
    Commented Jan 14, 2020 at 9:14
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$
2
  • $\begingroup$ Interesting thought. Can you elaborate how would you like to codify the number into pixels? $\endgroup$ Commented Feb 21, 2018 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
    Commented Feb 22, 2018 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$

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