Answers.Body: <p>It can be done.</p>
  
  <p>The activation function of a neuron does not have to be monotonic. The activation that Rahul suggested can be implemented via a continuously differentiable function, for example <span class="math-container">$ f(s) = exp(-k(1-s)^2) $</span> which has a nice derivative <span class="math-container">$f'(s) = 2k~(1-s)f(s)$</span>. Here, <span class="math-container">$s=w_0~x_0+w_1~x_1$</span>. Therefore, standard gradient-based learning algorithms are applicable.</p>
  
  <p>The neuron's error is <span class="math-container">$ E = \frac{1}{2}(v-v_d)^2$</span>,
  where <span class="math-container">$v_d$</span> - desired output, <span class="math-container">$v$</span> - actual output. The weights <span class="math-container">$w_i, ~i=0,1$</span> are initialized randomly and then updated during training as follows
  <span class="math-container">$$w_i \to w_i - \alpha\frac{\partial E}{\partial w_i}$$</span>
  where <span class="math-container">$\alpha$</span> is a learning rate. We have
  <span class="math-container">$$\frac{\partial E}{\partial w_i} = (v-v_d)\frac{\partial v}{\partial w_i}=(f(s)-v_d)~\frac{\partial f}{\partial s}\frac{\partial s}{\partial w_i}=2k~(f(s)-v_d)(1-s)f(s)~x_i$$</span>
  Let's test it in Python.</p>
  
  <pre><code>import numpy as np 
  import matplotlib.pyplot as plt
  </code></pre>
  
  <p>For training, I take a few points randomly scattered around <span class="math-container">$[0, 0]$</span>, <span class="math-container">$[0, 1]$</span>, <span class="math-container">$[1, 0]$</span>, and <span class="math-container">$[1, 1]$</span>. </p>
  
  <pre><code>n = 10
  sd = [0.05, 0.05]
  
  x00 = np.random.normal(loc=[0, 0], scale=sd, size=(n,2))
  x01 = np.random.normal(loc=[0, 1], scale=sd, size=(n,2))
  x10 = np.random.normal(loc=[1, 0], scale=sd, size=(n,2))
  x11 = np.random.normal(loc=[1, 1], scale=sd, size=(n,2))
  
  x = np.vstack((x00,x01,x10,x11))
  y = np.vstack((np.zeros((x00.shape[0],1)), 
                 np.ones((x01.shape[0],1)), 
                 np.ones((x10.shape[0],1)), 
                 np.zeros((x11.shape[0],1)))).ravel()
  
  ind = np.arange(len(y))
  np.random.shuffle(ind)
  
  x = x[ind]
  y = y[ind]
  N = len(y)
  
  plt.scatter(*x00.T, label='00')
  plt.scatter(*x01.T, label='01')
  plt.scatter(*x10.T, label='10')
  plt.scatter(*x11.T, label='11')
  plt.legend()
  plt.show()
  </code></pre>
  
  <p><a href="https://i.sstatic.net/W3r4F.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/W3r4F.png" alt="enter image description here"></a></p>
  
  <p>Activation function:</p>
  
  <pre><code>k = 10
  
  def f(s):
      return np.exp(-k*(s-1)**2)
  </code></pre>
  
  <p>Initialize the weights, and train the network:</p>
  
  <pre><code>w = np.random.uniform(low=0.25, high=1.75, size=(2))
  
  print("Initial w:", w)
  
  rate = 0.01
  n_epochs = 20
  
  error = []
  for _ in range(n_epochs):
      err = 0
      for i in range(N):
          s = np.dot(x[i],w)
          w -= rate * 2 * k * (f(s) - y[i]) * (1-s) * f(s) * x[i]
          err += 0.5*(f(s) - y[i])**2
      err /= N
      error.append(err)
  
  print('Final w:', w)
  </code></pre>
  
  <p>The weights have indeed converged to <span class="math-container">$w_0=1,~w_1=1$</span>:</p>
  
  <pre><code>Initial w: [1.5915165  0.27594833]
  Final w: [1.03561356 0.96695205]
  </code></pre>
  
  <p>The training error is decreasing:</p>
  
  <pre><code>plt.scatter(np.arange(n_epochs), error)
  plt.grid()
  plt.xticks(np.arange(0, n_epochs, step=1))
  plt.show()
  </code></pre>
  
  <p><a href="https://i.sstatic.net/Vy119.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Vy119.png" alt="enter image description here"></a></p>
  
  <p>Let's test it. I create a testing set in the same way as the training set. My test data are different from my training data because I didn't fix the seed.</p>
  
  <pre><code>x00 = np.random.normal(loc=[0, 0], scale=sd, size=(n,2))
  x01 = np.random.normal(loc=[0, 1], scale=sd, size=(n,2))
  x10 = np.random.normal(loc=[1, 0], scale=sd, size=(n,2))
  x11 = np.random.normal(loc=[1, 1], scale=sd, size=(n,2))
  
  x_test = np.vstack((x00,x01,x10,x11))
  y_test = np.vstack((np.zeros((x00.shape[0],1)), 
                 np.ones((x01.shape[0],1)), 
                 np.ones((x10.shape[0],1)), 
                 np.zeros((x11.shape[0],1)))).ravel()
  </code></pre>
  
  <p>I calculate the root mean squared error, and the coefficient of determination (R^2 score):</p>
  
  <pre><code>def fwd(x,w):
      return f(np.dot(x,w))
  
  RMSE = 0
  
  for i in range(N):
      RMSE += (fwd(x_test[i],w) - y_test[i])**2
  
  RMSE = np.sqrt(RMSE/N)
  
  print("RMSE", RMSE)
  
  ybar = np.mean(y)
  
  S = 0
  D = 0
  for i in range(N):
      S += (fwd(x_test[i],w) - y_test[i])**2
      D += (fwd(x_test[i],w) - ybar)**2
  
  r2_score = 1 - S/D
  print("r2_score", r2_score)
  </code></pre>
  
  <p>Result:</p>
  
  <pre><code>RMSE 0.09199468888373698
  r2_score 0.9613632278609362
  </code></pre>
  
  <p>... or I am doing something wrong? Please tell me.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-18T16:24:38.307Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/118603/discussion-on-answer-by-vladislav-gladkikh-why-cant-the-xor-linear-inseparabili).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-15T18:14:13.280Z
Answers.LastActivityDate: 2018-12-15T18:14:13.280Z
Answers.UserDisplayName: Vladislav Gladkikh
Answers.Body: <p>The main problems are that your activation function is not <strong>monotonic</strong> (as pointed out by csrev), and that it is not <strong>continuously differentiable</strong>. These make it very difficult / impossible to use standard gradient-based learning algorithms. </p>
  
  <p>So yes, there may exist a good solution of weight values, but it is very difficult to find or approximate those weight values automatically through a learning algorithm. Also note that it completely breaks down as soon as you have a tiny error in one of the weights, even if it is approximate very closely; if one of the weights has a value of <span class="math-container">$0.999$</span> rather than <span class="math-container">$1.0$</span>, the solution breaks down completely.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-09T13:02:59.553Z
Answers.LastActivityDate: 2018-12-09T13:02:59.553Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>Indeed I think the problem is with the way you've defined the activation function. By selecting it arbitrarily, you could solve many specific problems. In practice, activation functions used are monotonic. It keeps the error function convex at a per-layer level. In theory though I'm not sure exactly what Rosenblatt has claimed so it might be worth calling him</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-09T20:19:43.790Z
Answers.Text: If activation functions are not compulsorily monotonic (even if it may be the case in practice), then doesn't this activation function hold?
Answers.UserDisplayName: rahs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-10T00:24:52.450Z
Answers.Text: I guess it does hold then. But it ruins the whole purpose of the perceptron. As Dennis said, you did not specify what are the value between each integer, if you would start training and changing your weight you would go somewhere random. So you might as well skip the perceptron alltogether haha.  Now I get that you're testing if there is a theoretical flaw. Only I don't know which theorem of Rosenblatt you are referring to, which would give the conditions. I would be curious to know though (as there is indeed one in that gist).
Answers.UserDisplayName: csrev
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-09T01:44:54.313Z
Answers.LastActivityDate: 2018-12-09T01:44:54.313Z
Answers.UserDisplayName: csrev
Answers.Body: <p>Another activation function that could be used for this problem:
  <span class="math-container">$$f(x) = \underset{i}{max}(x_i) - \underset{i}{min}(x_i)$$</span>
  It's not continuous, no backpropagation, sorry. Some other learning algorithm is required. </p>
  
  <p>However, this answers the question, if an XOR can be solved with one neuron. Maybe this function is a solution of some learning problem with weights. Something like
  <span class="math-container">$$f(x) = max(w_0x_0,w_1x_1) - min(w_0x_0,w_1x_1)$$</span>
  I don't know how this creature is generalizable to other tasks, and how much learning can be done by just manipulating maxima and minima of weighted inputs. Any ideas?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-16T11:34:00.113Z
Answers.LastActivityDate: 2018-12-16T11:34:00.113Z
Answers.UserDisplayName: Vladislav Gladkikh
Answers.Body: <p>I'm also working on a perceptron that is able to solve the XOR Problem, and I get interesting results using sine as an activation function, and using the derivative to make the perceptron learn. But you will need bias to make sure the perceptron is able to solve the problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-16T02:37:20.897Z
Answers.Text: I think these links are relevant here: [this](https://stackoverflow.com/questions/30412427/solving-xor-with-single-layer-perceptron), [this](https://ai.stackexchange.com/questions/9534/non-monotonic-activation-function-and-xor-problem-with-perceptron) and [this](https://stackoverflow.com/questions/53785922/is-the-use-of-a-non-monotonic-activation-function-is-a-correct-and-viable-solut?noredirect=1#comment94423971_53785922)
Answers.UserDisplayName: Vladislav Gladkikh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-15T20:29:43.417Z
Answers.LastActivityDate: 2018-12-15T20:29:43.417Z
Answers.UserDisplayName: app_idea54
Body: <p>Consider a perceptron where <span class="math-container">$w_0=1$</span> and <span class="math-container">$w_1=1$</span>:</p>
  <p><a href="https://i.sstatic.net/eBSki.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/eBSki.jpg" alt="Perceptron" /></a></p>
  <p>Now, suppose that we use the following activation function</p>
  <p><span class="math-container">\begin{align}
  f(x)=
  \begin{cases}
  1, \text{ if }x =1\\
  0, \text{ otherwise}
  \end{cases}
  \end{align}</span></p>
  <p>The output is then summarised as:</p>
  <p><span class="math-container">\begin{array}{|c|c|c|c|}
  \hline
  x_0 &amp; x_1 &amp; w_0x_0 + w_1x_1 &amp; f( \cdot )\\ \hline
  0 &amp; 0 &amp; 0 &amp; 0 \\ \hline
  0 &amp; 1 &amp; 1 &amp; 1 \\ \hline
  1 &amp; 0 &amp; 1 &amp; 1 \\ \hline
  1 &amp; 1 &amp; 2 &amp; 0 \\ \hline
  \end{array}</span></p>
  <p>Is there something wrong with the way I've defined the activation function?</p>
  
Tags: <neural-networks><activation-functions><perceptron><xor-problem>
Title: Why can't the XOR linear inseparability problem be solved with one perceptron like this?
UserDisplayName: rahs
ThreadText: # Why can't the XOR linear inseparability problem be solved with one perceptron like this?
  
  (Asked by: username_0 on 2018-12-08)
  
  Consider a perceptron where $w\_0=1$ and $w\_1=1$:
  
  [![Perceptron](https://i.sstatic.net/eBSki.jpg)](https://i.sstatic.net/eBSki.jpg)
  
  Now, suppose that we use the following activation function
  
  \begin{align}
  f(x)=
  \begin{cases}
  1, \text{ if }x =1\\
  0, \text{ otherwise}
  \end{cases}
  \end{align}
  
  The output is then summarised as:
  
  \begin{array}{|c|c|c|c|}
  \hline
  x\_0 & x\_1 & w\_0x\_0 + w\_1x\_1 & f( \cdot )\\ \hline
  0 & 0 & 0 & 0 \\ \hline
  0 & 1 & 1 & 1 \\ \hline
  1 & 0 & 1 & 1 \\ \hline
  1 & 1 & 2 & 0 \\ \hline
  \end{array}
  
  Is there something wrong with the way I've defined the activation function?
  
  **Tags:** neural-networks, activation-functions, perceptron, xor-problem
  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_1 on 2018-12-15. Score: 4 | Accepted answer
  
  It can be done.
  
  The activation function of a neuron does not have to be monotonic. The activation that Rahul suggested can be implemented via a continuously differentiable function, for example $ f(s) = exp(-k(1-s)^2) $ which has a nice derivative $f'(s) = 2k~(1-s)f(s)$. Here, $s=w\_0~x\_0+w\_1~x\_1$. Therefore, standard gradient-based learning algorithms are applicable.
  
  The neuron's error is $ E = \frac{1}{2}(v-v\_d)^2$,
  where $v\_d$ - desired output, $v$ - actual output. The weights $w\_i, ~i=0,1$ are initialized randomly and then updated during training as follows
  $$w\_i \to w\_i - \alpha\frac{\partial E}{\partial w\_i}$$
  where $\alpha$ is a learning rate. We have
  $$\frac{\partial E}{\partial w\_i} = (v-v\_d)\frac{\partial v}{\partial w\_i}=(f(s)-v\_d)~\frac{\partial f}{\partial s}\frac{\partial s}{\partial w\_i}=2k~(f(s)-v\_d)(1-s)f(s)~x\_i$$
  Let's test it in Python.
  
  ```
  import numpy as np 
  import matplotlib.pyplot as plt
  
  ```
  
  For training, I take a few points randomly scattered around $[0, 0]$, $[0, 1]$, $[1, 0]$, and $[1, 1]$.
  
  ```
  n = 10
  sd = [0.05, 0.05]
  
  x00 = np.random.normal(loc=[0, 0], scale=sd, size=(n,2))
  x01 = np.random.normal(loc=[0, 1], scale=sd, size=(n,2))
  x10 = np.random.normal(loc=[1, 0], scale=sd, size=(n,2))
  x11 = np.random.normal(loc=[1, 1], scale=sd, size=(n,2))
  
  x = np.vstack((x00,x01,x10,x11))
  y = np.vstack((np.zeros((x00.shape[0],1)), 
                 np.ones((x01.shape[0],1)), 
                 np.ones((x10.shape[0],1)), 
                 np.zeros((x11.shape[0],1)))).ravel()
  
  ind = np.arange(len(y))
  np.random.shuffle(ind)
  
  x = x[ind]
  y = y[ind]
  N = len(y)
  
  plt.scatter(*x00.T, label='00')
  plt.scatter(*x01.T, label='01')
  plt.scatter(*x10.T, label='10')
  plt.scatter(*x11.T, label='11')
  plt.legend()
  plt.show()
  
  ```
  
  [![enter image description here](https://i.sstatic.net/W3r4F.png)](https://i.sstatic.net/W3r4F.png)
  
  Activation function:
  
  ```
  k = 10
  
  def f(s):
      return np.exp(-k*(s-1)**2)
  
  ```
  
  Initialize the weights, and train the network:
  
  ```
  w = np.random.uniform(low=0.25, high=1.75, size=(2))
  
  print("Initial w:", w)
  
  rate = 0.01
  n_epochs = 20
  
  error = []
  for _ in range(n_epochs):
      err = 0
      for i in range(N):
          s = np.dot(x[i],w)
          w -= rate * 2 * k * (f(s) - y[i]) * (1-s) * f(s) * x[i]
          err += 0.5*(f(s) - y[i])**2
      err /= N
      error.append(err)
  
  print('Final w:', w)
  
  ```
  
  The weights have indeed converged to $w\_0=1,~w\_1=1$:
  
  ```
  Initial w: [1.5915165  0.27594833]
  Final w: [1.03561356 0.96695205]
  
  ```
  
  The training error is decreasing:
  
  ```
  plt.scatter(np.arange(n_epochs), error)
  plt.grid()
  plt.xticks(np.arange(0, n_epochs, step=1))
  plt.show()
  
  ```
  
  [![enter image description here](https://i.sstatic.net/Vy119.png)](https://i.sstatic.net/Vy119.png)
  
  Let's test it. I create a testing set in the same way as the training set. My test data are different from my training data because I didn't fix the seed.
  
  ```
  x00 = np.random.normal(loc=[0, 0], scale=sd, size=(n,2))
  x01 = np.random.normal(loc=[0, 1], scale=sd, size=(n,2))
  x10 = np.random.normal(loc=[1, 0], scale=sd, size=(n,2))
  x11 = np.random.normal(loc=[1, 1], scale=sd, size=(n,2))
  
  x_test = np.vstack((x00,x01,x10,x11))
  y_test = np.vstack((np.zeros((x00.shape[0],1)), 
                 np.ones((x01.shape[0],1)), 
                 np.ones((x10.shape[0],1)), 
                 np.zeros((x11.shape[0],1)))).ravel()
  
  ```
  
  I calculate the root mean squared error, and the coefficient of determination (R^2 score):
  
  ```
  def fwd(x,w):
      return f(np.dot(x,w))
  
  RMSE = 0
  
  for i in range(N):
      RMSE += (fwd(x_test[i],w) - y_test[i])**2
  
  RMSE = np.sqrt(RMSE/N)
  
  print("RMSE", RMSE)
  
  ybar = np.mean(y)
  
  S = 0
  D = 0
  for i in range(N):
      S += (fwd(x_test[i],w) - y_test[i])**2
      D += (fwd(x_test[i],w) - ybar)**2
  
  r2_score = 1 - S/D
  print("r2_score", r2_score)
  
  ```
  
  Result:
  
  ```
  RMSE 0.09199468888373698
  r2_score 0.9613632278609362
  
  ```
  
  ... or I am doing something wrong? Please tell me.
  
  > **Comments:**
  > **username_2**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/118603/discussion-on-answer-by-username_1-why-cant-the-xor-linear-inseparabili).  
  
  ---
  
  ### Answer by username_3 on 2018-12-09. Score: 3
  
  The main problems are that your activation function is not **monotonic** (as pointed out by username_4), and that it is not **continuously differentiable**. These make it very difficult / impossible to use standard gradient-based learning algorithms.
  
  So yes, there may exist a good solution of weight values, but it is very difficult to find or approximate those weight values automatically through a learning algorithm. Also note that it completely breaks down as soon as you have a tiny error in one of the weights, even if it is approximate very closely; if one of the weights has a value of $0.999$ rather than $1.0$, the solution breaks down completely.
  
  
  ---
  
  ### Answer by username_4 on 2018-12-09. Score: 2
  
  Indeed I think the problem is with the way you've defined the activation function. By selecting it arbitrarily, you could solve many specific problems. In practice, activation functions used are monotonic. It keeps the error function convex at a per-layer level. In theory though I'm not sure exactly what Rosenblatt has claimed so it might be worth calling him
  
  > **Comments:**
  > **username_0**: If activation functions are not compulsorily monotonic (even if it may be the case in practice), then doesn't this activation function hold?  
  > **username_4**: I guess it does hold then. But it ruins the whole purpose of the perceptron. As username_3 said, you did not specify what are the value between each integer, if you would start training and changing your weight you would go somewhere random. So you might as well skip the perceptron alltogether haha.  Now I get that you're testing if there is a theoretical flaw. Only I don't know which theorem of Rosenblatt you are referring to, which would give the conditions. I would be curious to know though (as there is indeed one in that gist).  
  
  ---
  
  ### Answer by username_1 on 2018-12-16. Score: 0
  
  Another activation function that could be used for this problem:
  $$f(x) = \underset{i}{max}(x\_i) - \underset{i}{min}(x\_i)$$
  It's not continuous, no backpropagation, sorry. Some other learning algorithm is required.
  
  However, this answers the question, if an XOR can be solved with one neuron. Maybe this function is a solution of some learning problem with weights. Something like
  $$f(x) = max(w\_0x\_0,w\_1x\_1) - min(w\_0x\_0,w\_1x\_1)$$
  I don't know how this creature is generalizable to other tasks, and how much learning can be done by just manipulating maxima and minima of weighted inputs. Any ideas?
  
  
  ---
  
  ### Answer by username_5 on 2018-12-15. Score: 0
  
  I'm also working on a perceptron that is able to solve the XOR Problem, and I get interesting results using sine as an activation function, and using the derivative to make the perceptron learn. But you will need bias to make sure the perceptron is able to solve the problem.
  
  > **Comments:**
  > **username_1**: I think these links are relevant here: [this](https://stackoverflow.com/questions/30412427/solving-xor-with-single-layer-perceptron), [this](https://ai.stackexchange.com/questions/9534/non-monotonic-activation-function-and-xor-problem-with-perceptron) and [this](https://stackoverflow.com/questions/53785922/is-the-use-of-a-non-monotonic-activation-function-is-a-correct-and-viable-solut?noredirect=1#comment94423971_53785922)  
  
  ---
  
  