8
$\begingroup$

It is a well known fact that a 1-layer network cannot predict the xor function, since it is not linearly separable. I attempted to create a 2-layer network, using the logistic sigmoid function and backprop, to predict xor. My network has 2 neurons (and one bias) on the input layer, 2 neurons and 1 bias in the hidden layer, and 1 output neuron. To my surprise, this will not converge. if I add a new layer, so I have a 3-layer network with input (2+1), hidden1 (2+1), hidden2 (2+1), and output, it works. Also, if I keep a 2-layer network, but I increase the hidden layer size to 4 neurons + 1 bias, it also converges. Is there a reason why a 2-layer network with 3 or less hidden neurons won't be able to model the xor function?

$\endgroup$
  • 2
    $\begingroup$ You can predict XOR using that structure. In fact you don't even need biases (see here). $\endgroup$ – krychu May 4 '16 at 16:48
  • $\begingroup$ Do I need to initialise my weights in any special way to get convergence? I a trying a simple neural net with weights between (-1,1) initialised randomly, but I cannot get it to converge (even using biases) $\endgroup$ – user May 4 '16 at 17:27
  • $\begingroup$ Actually, using the logistic sigmoid it does converge sometimes, but not all the times, it depends on the initial choice of random weights. $\endgroup$ – user May 4 '16 at 21:18
  • $\begingroup$ Your range seems quite large, try (-0.1, 0.1). Otherwise you risk that input signal to a neuron might be large from the start in which case learning for that neuron is slow. You might also want to decrease learning rate and increase number of iterations. $\endgroup$ – krychu May 4 '16 at 22:43
  • $\begingroup$ On the contrary, larger values make it converge faster. I have tried smaller learning rate and many iterations. I think Neil Slater's answer below sums up the issues, though I am still not sure why. $\endgroup$ – user May 5 '16 at 5:22
6
$\begingroup$

Yes, there is a reason. It has to do with how you initialize your weights.

There are 16 local minimums that have the highest probability of converging between 0.5 - 1.

enter image description here

Here is a paper that analyses the xor problem.

$\endgroup$
  • 2
    $\begingroup$ Appears the link is broken. $\endgroup$ – Adam Kingsley Feb 6 '18 at 17:25
  • $\begingroup$ @Emil So, if the weights are very small, you are saying that it will never converge? I also fixed the link for you. $\endgroup$ – user Apr 5 '18 at 1:53
  • $\begingroup$ @user Correct . $\endgroup$ – Emil Mar 4 at 9:08
6
$\begingroup$

A network with one hidden layer containing two neurons should be enough to seperate the XOR problem. The first neuron acts as an OR gate and the second one as a NOT AND gate. Add both the neurons and if they pass the treshold it's positive. You can just use linear decision neurons for this with adjusting the biases for the tresholds. The inputs of the NOT AND gate should be negative for the 0/1 inputs. This picture should make it more clear, the values on the connections are the weights, the values in the neurons are the biases, the decision functions act as 0/1 decisions (or just the sign function works in this case too).

XOR Neural Network

Picture thanks to "Abhranil blog"

$\endgroup$
  • $\begingroup$ Thank you, then it is not possible to do this using a logistic sigmoid, since it restricts the value to (0,1) $\endgroup$ – user May 4 '16 at 15:59
  • $\begingroup$ No it should still be possible to learn this with a logistic sigmoid, it should just learn the thresholds/weights differently $\endgroup$ – Jan van der Vegt May 4 '16 at 16:34
4
$\begingroup$

If you are using basic gradient descent (with no other optimisation, such as momentum), and a minimal network 2 inputs, 2 hidden neurons, 1 output neuron, then it is definitely possible to train it to learn XOR, but it can be quite tricky and unreliable.

  • You may need to adjust learning rate. Most usual mistake is to set it too high, so the network will oscillate or diverge instead of learn.

  • It can take a surprisingly large number of epochs to train the minimal network using batched or online gradient descent. Maybe several thousand epochs will be required.

  • With such a low number of weights (only 6), sometimes random initialisation can create a combination that gets stuck easily. So you may need to try, check results and then re-start. I suggest you use a seeded random number generator for initialisation, and adjust the seed value if error values get stuck and do not improve.

$\endgroup$
  • $\begingroup$ Yes, that is what I am observing, with some seed values it does converge, others, it won't. Also, if I use hyperbolic tangent instead of sigmoid it works rather well all the times, with sigmoid it does depend on the seed, as you observed. What is the reason for it to be so tricky? $\endgroup$ – user May 4 '16 at 21:21
  • $\begingroup$ I'm not entirely sure what the mathematical reason is, this is just from my experience writing test suite around learning xor. In my case, adding momentum helped, but I think pretty much any adjustment away from the simplest network and/or optimiser helps. $\endgroup$ – Neil Slater May 4 '16 at 21:32

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.