1
$\begingroup$

I stumbled upon an alternative solution to neural network XOR-gate like classifier that uses fewer units. However, I'm not sure if there is actually any benefit or insight that I am missing.

The truth table for an XOR gate:

|      X1      |     X2    |     Y    |
|--------------|-----------|----------|
|      1       |     1     |     0    |
|      0       |     0     |     0    |
|      1       |     0     |     1    |
|      0       |     1     |     1    |

Because the examples cannot be shattered with a single line, a multi-layered perceptron is required. The standard solution shows two hidden units and an output unit:

x1   x2
| \ / |
h11 h12
 \   /
  h2

The 6 connections and 3 biases, total to 6 trainable parameters.

An example weights and bias solution with this architecture:

assume $h_{out} = step(w^{T}(input) + b)$

$w_{2} = (1, 1), w_{11} = (-1, 1), w_{12} = (1, −1)$

$b_{2} = −0.5, b_{11} = -0.5, b_{12} = -0.5$

|      X1      |     X2    |    h11   |    h12   |    h2   |
|--------------|-----------|----------|----------|---------|
|      1       |     1     |     0    |     0    |     0   |
|      0       |     0     |     0    |     0    |     0   |
|      1       |     0     |     0    |     1    |     1   |
|      0       |     1     |     1    |     0    |     1   |

So what I stumbled upon was a way using only one layer and an addition operation to reduce the number of paramters:

x1   x2
| \ / |
h11 h12
hout = step(h11 + h12)

This requires only 4 weights and 2 biases

$w_{11} = (-1, 1), w_{12} = (1, −1)$

$b_{11} = -0.5, b_{12} = -0.5$

again by adding the last outputs of h11 and h12 we generate the same final output:

|      X1      |     X2    |    h11   |    h12   |    h2   |
|--------------|-----------|----------|----------|---------|
|      1       |     1     |     0    |     0    |     0   |
|      0       |     0     |     0    |     0    |     0   |
|      1       |     0     |     1    |     0    |     1   |
|      0       |     1     |     0    |     1    |     1   |

So my questions are:

1) Is my reasoning correct? (I did run a script in python and was able to get working results)

2) Is this insightful at all or is it totally obvious?

$\endgroup$
  • 1
    $\begingroup$ Obvious now. I knew I was missing something thank you. $\endgroup$ – Nick Merrill Jan 13 at 22:07
0
$\begingroup$

Your "new" solution is the same as the "old" solution with $b=0$, as long as you define $\text{step}(0)=0$. (The "old" solution has values of $w^\top h + b$ which are decisively on either side of 0, so how you define $\text{step}(0)$ doesn't matter in that case.)

You can identify this by inspection because h11+h12 is just a dot product with $𝑤=(1,1)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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