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?
$\begingroup$
$\endgroup$
5
-
3$\begingroup$ You can predict XOR using that structure. In fact you don't even need biases (see here). $\endgroup$– krychuCommented May 4, 2016 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$– userCommented May 4, 2016 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$– userCommented May 4, 2016 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$– krychuCommented May 4, 2016 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$– userCommented May 5, 2016 at 5:22
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
Here is a paper that analyses the xor problem: Learning XOR: exploring the space of a classic problem, Bland 1998.
-
$\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$– userCommented Apr 5, 2018 at 1:53
-
$\begingroup$
$\endgroup$
3
A network with one hidden layer containing two neurons should be enough to separate 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 threshold it's positive. You can just use linear decision neurons for this with adjusting the biases for the thresholds. 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 negatives of the biases. E.g. for input1=0 / input2=1, hidden neuron 1 would be sign function(0*1 + 1*1 - 0.5) == 1, meaning it passes the OR gate. The decision functions act as 0/1 decisions (or just the sign function works in this case too).
Picture thanks to "Abhranil blog"
answered May 4, 2016 at 15:33
-
$\begingroup$ Thank you, then it is not possible to do this using a logistic sigmoid, since it restricts the value to (0,1) $\endgroup$– userCommented May 4, 2016 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$ Commented May 4, 2016 at 16:34
-
$\begingroup$ The bias in the NAND gate should be a $+1.5$. $\endgroup$ Commented Jan 30, 2020 at 14:45
$\begingroup$
$\endgroup$
2
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.
answered May 4, 2016 at 21:18
-
$\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$– userCommented May 4, 2016 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$ Commented May 4, 2016 at 21:32