6
$\begingroup$

Background: I've been interested in, and reading about, Neural Networks for several years, but I haven't gotten around to testing them out until recently. Both for fun and to increase my understanding, I tried to write a class library from scratch in .Net. For tests, I've tried some simple functions, such as generating output identical to the input, working with the MNIST dataset, and a few binary functions (two input OR, AND and XOR, with two outputs: one for true, one for false). Everything seemed fine when I used a sigmoid function as the activation function but, reading of the ReLUs I decided to switch over for speed.

My current problem is that, when I switch to using ReLUs, I found that I was unable to train a network of any complexity (tested from as few as 2 internal nodes up to a mesh of 100x100 nodes) to correctly function as an XOR gate. I see two possibilities here:

1) My implementation is faulty, (This one is frustrating, as I've re-written the code multiple times in various ways, and I still get the same result),

2) Aside from being faster or slower to train, there are some problems that are impossible to solve given a specific activation function, (Fascinating idea, but I've no idea if it's true or not)

My inclination is to think that 1) above is correct. However, given the amount of time I've invested, it would be nice if I could rule out 2) definitively before I spend even more time going over my implementation.

Edit for specifics: For the XOR network, I have tried both using two inputs (0 for false, 1 for true), and using four inputs (each pair, one signals true and one false, per "bit" of input). I have also tried using 1 output (with a 1 (realy, >0.9) corresponding to true and a 0 (or <0.1) corresponding to false), as well as two outputs (one signaling true and the other false).

Each training epoch, I run against four sets of input: 00->0, 01->1, 10->1, 11->0.

I find that the first three converge towards correct answer, but the final input (11) converges towards 1, even though I train it with an expected value of 0.

$\endgroup$
1
$\begingroup$

There are a variety of possible things that could be wrong, but to answer the short question specifically:

relu networks are turing complete (well, if you put them in an RNN so they can compute indefinitely, anyway). for any computation, you can devise an rnn that will perform it.

as a proof of this, here is a relu neuron that implements nor, which with recursion (cs)/recurrence (nns) and routing matrices is enough to implement a turing machine:

W: [ -20
-20 ] b: [ 1 ]

o = max(Wx + b, 0)

however, gradient descent is a finnicky way to search for rnns. there are a wide variety of ways that it might have been failing. In general, once you have very thoroughly checked your gradient, I'd make sure to use Adam as the optimizer and then play with the hyperparameters endlessly until I find an incantation that works. http://russellsstewart.com/notes/0.html http://yyue.blogspot.com/2015/01/a-brief-overview-of-deep-learning.html?m=1

$\endgroup$
  • $\begingroup$ not sure precisely what you're looking for, but I added some stuff. $\endgroup$ – lahwran Nov 28 '16 at 0:33
1
$\begingroup$

While I have not determined if there are problems which cannot be solved with ReLU, I have found ample documentation in the literature that XOR is solvable with as few as 1 hidden node. Therefore, I must assume there is something wrong with my implementation.

Edit: The solution is simpler than I thought. The output layer needs connections, not just to the intermediate layer, but directly to the input layer as well. This allows the network to train XOR effectively.

Edit 2: One final note, the XOR is EXTREMELY sensitive to the learning rate. Essentially, whatever learning rate is appropriate for the AND and OR functions, is approximately 1000x too large to train XOR effectively.

$\endgroup$
  • $\begingroup$ Hi! If you ever find out what exactly was wrong, please come back and tell us about it -- it may help people in the future with a similar problem. $\endgroup$ – Alpha Nov 19 '16 at 0:01
  • 1
    $\begingroup$ Still working on it. My first problem was that I was presenting the training data in a fixed order; I found that randomizing the order makes all outputs tend towards a value 0.5, with some minor variations, making the (1 hot) output essentially random. Next I'll try implementing drop-out and momentum, and see if those give me better results. Even so, those shouldn't be necessary, as the problem SHOULD be solvable with a small network. $\endgroup$ – Benjamin Chambers Nov 19 '16 at 13:39
  • $\begingroup$ Still not sure why the connections to inputs are necessary; with a sufficiently wide hidden layer, some of them should eventually train to act as pass-throughs for the input nodes, shouldn't they? $\endgroup$ – Benjamin Chambers Nov 19 '16 at 16:19

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.