Answers.Body: <p>There are a variety of possible things that could be wrong, but let me give you some potentially useful information.</p>
  <p>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.</p>
  <p>As an example, suppose that we want to compute the <a href="https://en.wikipedia.org/wiki/NOR_gate" rel="nofollow noreferrer">NOR</a> function, which can be used to implement a Turing machine.  We can do it with the following neural network with a ReLU activation function.</p>
  <p>Let the input be</p>
  <p><span class="math-container">$$ W = \begin{bmatrix}x_1 \ \ x_2 \end{bmatrix}$$</span></p>
  <p>the weight matrix be</p>
  <p><span class="math-container">$$ W = \begin{bmatrix} -20 \\ -20 \end{bmatrix}$$</span></p>
  <p>and the bias be</p>
  <p><span class="math-container">$$ b = \begin{bmatrix} 1 \end{bmatrix}$$</span></p>
  <p>Then the ReLU unit (or neuron) performs the following operation</p>
  <p><span class="math-container">$$o = \max(Wx + b, 0)$$</span></p>
  <p>So, <span class="math-container">$o = 1$</span> only when both <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> are <span class="math-container">$0$</span>, otherwise, it's always <span class="math-container">$0$</span>.</p>
  <p>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 <em>very thoroughly checked your gradient</em>, I'd make sure to use Adam as the optimizer and then play with the hyperparameters endlessly until I find an incantation that works.</p>
  <p>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: <a href="http://yyue.blogspot.com/2015/01/a-brief-overview-of-deep-learning.html?m=1" rel="nofollow noreferrer">http://yyue.blogspot.com/2015/01/a-brief-overview-of-deep-learning.html?m=1</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-11-25T23:02:48.910Z
Answers.LastActivityDate: 2021-01-18T05:13:16.110Z
Answers.LastEditDate: 2021-01-18T05:13:16.110Z
Answers.UserDisplayName: lahwran
Answers.Body: <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-11-18T18:23:32.520Z
Answers.LastActivityDate: 2021-01-17T20:52:56.763Z
Answers.LastEditDate: 2021-01-17T20:52:56.763Z
Answers.UserDisplayName: Benjamin Chambers
Answers.Body: <p>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.</p>
  
  <p>The Loss vs training times:</p>
  
  <p><a href="https://i.sstatic.net/5k4pz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5k4pz.png" alt="enter image description here"></a></p>
  
  <p>And the gradient looks like:</p>
  
  <p><a href="https://i.sstatic.net/gyT5T.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gyT5T.png" alt="enter image description here"></a></p>
  
  <p>I think that means the units all dead. The robust way to solve this problem is increase the number of units.</p>
  
  <p>When it comes to 4 units, some times I will success, but sometimes not.</p>
  
  <p>And 5 units, I will fail but the rate decrease.</p>
  
  <p><a href="https://i.sstatic.net/s40oj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/s40oj.png" alt="enter image description here"></a></p>
  
  <p>And so on. That is all.</p>
  
  <p>I will try to use sigmoid + cross entropy instead of ReLU, I imagine linear function will work better in this case.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-21T02:54:03.893Z
Answers.LastActivityDate: 2020-05-21T02:54:03.893Z
Answers.UserDisplayName: kobako
Body: <h3>Background</h3>
  <p>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.</p>
  <p>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).</p>
  <p>Everything seemed fine when I used a <strong>sigmoid</strong> function as the activation function, but, after reading about the ReLUs, I decided to switch over for speed.</p>
  <h3>Problem</h3>
  <p>My current problem is that, when I switch to using ReLUs, I found that I was <em>unable</em> 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.</p>
  <p>I see two possibilities here:</p>
  <ol>
  <li><p>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).</p>
  </li>
  <li><p>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).</p>
  </li>
  </ol>
  <p>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.</p>
  <h3>More details</h3>
  <p>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 &quot;bit&quot; of input). I have also tried using 1 output (with a 1 (really, &gt;0.9) corresponding to true and a 0 (or &lt;0.1) corresponding to false), as well as two outputs (one signaling true and the other false).</p>
  <p>Each training epoch, I run against a set of 4 inputs <span class="math-container">$\{ (00, 0), (01, 1), (10, 1), (11, 0) \}$</span>.</p>
  <p>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.</p>
  
Tags: <neural-networks><activation-functions><function-approximation><relu><sigmoid>
Title: Are ReLUs incapable of solving certain problems?
UserDisplayName: Benjamin Chambers
ThreadText: # Are ReLUs incapable of solving certain problems?
  
  (Asked by: username_0 on 2016-11-17)
  
  ### 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.
  
  **Tags:** neural-networks, activation-functions, function-approximation, relu, sigmoid
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2016-11-25. Score: 1 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/NOR_gate) 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 by username_0 on 2016-11-18. Score: 1
  
  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 by username_2 on 2020-05-21. Score: 0
  
  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:
  
  [![enter image description here](https://i.sstatic.net/5k4pz.png)](https://i.sstatic.net/5k4pz.png)
  
  And the gradient looks like:
  
  [![enter image description here](https://i.sstatic.net/gyT5T.png)](https://i.sstatic.net/gyT5T.png)
  
  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.
  
  [![enter image description here](https://i.sstatic.net/s40oj.png)](https://i.sstatic.net/s40oj.png)
  
  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.
  
  
  ---
  
  