Can a 2-2-1 feedforward neural network with sigmoid activation functions represent a solution to XOR?

I'v been playing around with back propagation, trying to see if I can find a solution to the XOR problem using a 2-2-1 network. Based on my simulations and calculations, a solution is not possible without implementing a bias for every neuron. Is this correct?

It is not possible to give a perfect logical gate with a logistic output neuron because the range is $(0,1)$, but you can approximate $(0,0)\mapsto 0, (0,1)\mapsto 1, (1,0) \mapsto 1, (1,1) \mapsto 0$ arbitrarily well, contrary to the previous answer.

Let the inputs be $i,j$. Let the first hidden neuron have weights $(1,1)$ so that its output is $\sigma(i+j)$ where $\sigma$ is the logistic function $\sigma(x) = \frac{\exp(x)}{1+\exp(x)}$, which is $(0,0)\mapsto 1/2, (1,0),(0,1) \mapsto \sigma(1) = 0.731, (1,1) \mapsto \sigma(2) = 0.881$. Let the second hidden neuron have weights $(2,2)$ so that it takes the values $1/2, \sigma(2) = 0.881, \sigma(4) = 0.982$. Let the output neuron have weights $(\alpha,\beta)$. In order to produce the XOR function, we want

$$\begin{eqnarray}\frac12 \alpha + \frac12 \beta &\ll& 0 \newline \sigma(1) \alpha + \sigma(2) \beta & \gg & 0 \newline \sigma(2) \alpha + \sigma(4) \beta &\ll & 0.\end{eqnarray}$$

If we find $(\alpha,\beta)$ so that the inequalities are satisfied, this puts the outputs on the correct sides of $1/2$. Then we can rescale so that the output of the network is arbitrarily close to XOR.

The inequalities are satisfied by $(-1,\beta)$ if $0.830 = \frac{\sigma(1)}{\sigma(2)} \lt \beta \lt \frac{\sigma(2)}{\sigma(4)} = 0.897$. For example, $(\alpha,\beta) = (-1,0.85)$ produces outputs of $(0.481, 0.504, 0.488)$. Scaling this up to $(\alpha,\beta) = (-1000,850)$ gives a neural network of the required structure and no biases which takes the following values:

$$\begin{eqnarray} (0,0) & \mapsto & 2.7 \times 10^{-33} & \approx & 0\newline (0,1) & \mapsto & 1 - (2.2 \times 10^{-8}) & \approx & 1\newline (1,0) & \mapsto & 1 - (2.2 \times 10^{-8}) & \approx & 1\newline (1,1) & \mapsto & 9.7 \times 10^{-21} & \approx & 0. \end{eqnarray}$$

So, you can produce XOR using that structure and no biases.

• (+1) I (and everyone who gave me an upvote) stand corrected. Well done ! I have worked through your numbers, but I was not able to reproduce (0.481,0.504,0.488), since e.g. $\frac{1}{2} \alpha + \frac{1}{2}\beta$ for $(\alpha,\beta)=(-1,0.85)$ results in -0.075. Your "proof by example" remains of course still correct. – steffen Dec 5 '12 at 8:45
• I'm using logistic activations everywhere. $\sigma(-1(1/2) + 0.85(1/2)) = \sigma(-0.075) = 0.481$, $\sigma(-1000(1/2) + 850(1/2)) = \sigma(-75) = 2.7 \times 10^{-33}$. – Douglas Zare Dec 5 '12 at 18:59