Are ReLUs incapable of solving certain problems?

Question

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, after reading about the ReLUs, I decided to switch over for speed.

Problem

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.

More details

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 (really, >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 a set of 4 inputs $\{ (00, 0), (01, 1), (10, 1), (11, 0) \}$.

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

Answer 1

There are a variety of possible things that could be wrong, but let me give you some potentially useful information.

Neural networks with ReLU activation functions are Turing complete for a computation with on order as many steps as the network contains nodes - for a recurrent network (an RNN), that means the same level of turing completeness as any finite computer. In other words, for any function/algorithm that you want to compute, you can devise a neural network, potentially recurrent, that will approximate/compute it.

As an example, suppose that we want to compute the NOR function, which can be used to implement a Turing machine. We can do it with the following neural network with a ReLU activation function.

Let the input be

$$ W = \begin{bmatrix}x_1 \ \ x_2 \end{bmatrix}$$

the weight matrix be

$$ W = \begin{bmatrix} -20 \\ -20 \end{bmatrix}$$

and the bias be

$$ b = \begin{bmatrix} 1 \end{bmatrix}$$

Then the ReLU unit (or neuron) performs the following operation

$$o = \max(Wx + b, 0)$$

So, $o = 1$ only when both $x_1$ and $x_2$ are $0$, otherwise, it's always $0$.

However, gradient descent is a finicky 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.

For further reading on general understanding of this level of deep learning's capability limitations, I'd recommend this blog post by Ilya Sutskever, now an OpenAI researcher: http://yyue.blogspot.com/2015/01/a-brief-overview-of-deep-learning.html?m=1

Answer 2

While I have not determined if there are problems that cannot be solved with ReLU, I have found ample documentation in the literature that XOR is solvable with as few as 1 hidden node.

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.

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.

Answer 3

I tried to use 2 hidden ReLU-based unit, 1 output unit to solve the XOR problem and found that gradient will always become really small after training 1000 times.

The Loss vs training times:

And the gradient looks like:

I think that means the units all dead. The robust way to solve this problem is increase the number of units.

When it comes to 4 units, some times I will success, but sometimes not.

And 5 units, I will fail but the rate decrease.

And so on. That is all.

I will try to use sigmoid + cross entropy instead of ReLU, I imagine linear function will work better in this case.