# Why can't the XOR linear inseparability problem be solved with one perceptron - like this?

Consider a perceptron where $$w_0=1$$ and $$w_1=1$$: Now, say we use an activation function

$$f(x)=1,~for~x=1$$

$$~~~~~~~~~~~~~0, otherwise$$

The output is then summarised as:

$$x_0~~~~~x_1~~~~~w_0*x_0 + w_1*x1~~~~~f(.)$$

$$0~~~~~~~0~~~~~~~~~~~~~~0~~~~~~~~~~~~~~~~~~~~~~~~~~~~0$$

$$0~~~~~~~1~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~1$$

$$1~~~~~~~0~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~~~~~~~~~~~~~~1$$

$$1~~~~~~~1~~~~~~~~~~~~~~2~~~~~~~~~~~~~~~~~~~~~~~~~~~~0$$

Someone tell Rosenblatt I solved his problem ...

...or have I?

Is there something wrong with the way I've defined the activation function?

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()


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()


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.

• I think what this shows is that activation functions do not necessarily have to be monotonic, learning might still be successful if the activation function is not monotonic... but I still think it will be highly likely to fail in many cases. In particular, it will be highly reliant on a good (task-specific) initialization of the weights. I see you initialize weights to lie in $[0.25, 1.75]$. This looks very much... task-specific. I suspect this would break down if they were, for example, initialized to lie in $[-0.1, 0.1]$. – Dennis Soemers Dec 15 '18 at 18:36
• Without monotonicity, gradient-based learning becomes much less reliable. It might still work if you happen to select good initialziations, but that's going to be difficult to do for tasks that are more complex than XOR. The detailed analysis deserves an upvote though :D – Dennis Soemers Dec 15 '18 at 18:37
• @DennisSoemers Training any neural network depends on initialization. I chose this interval because I took a specific $k=10$ in my $f$. I initialized the weights where $f'(s)$ is far from 0. I could initialize it in a broader interval. It would still converge but would require much more training epochs (thousands, millions). The same considerations are always taken into account even for monotonic activation. Non-monotonic activations are not something new. See here – Vladislav Gladkikh Dec 16 '18 at 2:06
• @DennisSoemers The activation function that I took here is used in Radial basis function networks – Vladislav Gladkikh Dec 16 '18 at 2:20
• @DennisSoemers Correct. For convergence, the weights for this problem should be initialized within the interval where $\frac{\partial E}{\partial w_i}$ is far from zero. – Vladislav Gladkikh Dec 16 '18 at 11:08

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

• If activation functions are not compulsorily monotonic (even if it may be the case in practice), then doesn't this activation function hold? – rahs Dec 9 '18 at 20:19
• 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). – csrev Dec 10 '18 at 0:24

The main problems are that your activation function is not monotonic (as pointed out by csrev), 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.

• Another part I think you should detail is they are not linearly separable, and also the activation function has a kind of Dirac Delta feeling to it. – DuttaA Dec 9 '18 at 14:00
• ReLU and other popular activation functions are not continuously differentiable. It is not a constraint, but separability is. – han_nah_han_ Dec 11 '18 at 10:40
• @han_nah_han_ That's correct, which is why I said "very difficult / impossible" rather than just "impossible". ReLU and other similar style activation functions tend to just have a single point ($0$) where they're not differentiable though. In this regard the activation function proposed in the OP is very different. Lack of continuous differentiability still is a complicating factor regardless, even if it isn't a complete deal-breaker in all cases. – Dennis Soemers Dec 11 '18 at 19:24
• Binary step, leaky ReLU, and many others are used without difficulty. I know because I use them. They are fast, so undefined derivatives on very rare occasion is an acceptable trade-off and the techniques for handling the discontinuities are mature. – han_nah_han_ Dec 24 '18 at 5:57
• @han_nah_han_ I know, that's consistent with my answer. You're mentioning trade-offs, and the fact that people put thought into techniques for handling the discontinuities. Both of those things are indicative of the complicating factors that I mentioned -- they can be overcome (in some cases, likely not in the case proposed by the question author), but they're still there. – Dennis Soemers Dec 24 '18 at 9:30

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.

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?

The proposal is that logical exclusive-or can be learned using one perceptron cell defined as

$$s = \vec{i} \cdot \vec{P}$$

$$f(s) = \begin{cases} 0 & \text{where } s = 0 \\ 1 & \text{where } s = 1 \\ 0 & \text{where } s = 2 \end{cases} \, \text{,}$$

where $$f()$$ is the activation function, its output is the output of the proposed learning system, $$P$$ is the attenuation vector containing parameters to learn, and $$i$$ is the input.

If $$\vec{P}$$ is initialized to $$(1, 1)$$, the proposed perceptron provides an exclusive-or function, but no learning occurred, and the dot product and activation function could be replaced with

$$f(i) = \Big(\sum i\Big) \, \bmod \, 2 \quad \text{,}$$

leaving a basic exclusive-or. Reliable convergence

$$\lim_{t \rightarrow \infty} \vec{P} \Rightarrow (1, 1)$$

is not achieved with the above activation function because the discrete gradient is multi-valued. There are slopes of both 1 and -1 for a single training instance. Thus no loss function exists that can guarantee descent. That is the monotonic constraint on activation functions discussed in early literature on perceptrons.

A distinct but related caveat is that other instances of the larger concept class, any arbitrary truth table in two binary input variables and one binary output variable, would not be learnable using the same activation function. With a MLP (multi-layer perceptron), it is possible to learn any arbitrary binary operator from any initial state reliably using a single activation function, and the usability of MLPs extend much further.