Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
(+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.