Two threshold solutions for XOR
Section of Neural units, part of Statistical learning
Two threshold solutions for XOR
| Type | Section |
| Taught in | Neural units |
| Part | Statistical learning |
Two constructions with threshold units and integer weights show that a hidden layer is enough for this function. Weights are the numbers on connections, the bias is the number inside a unit, and the hidden units are h_3,h_4,h_5 with output unit o.
Copy the inputs and subtract AND. Nodes 3 and 5 copy x_1 and x_2, and node 4 computes x_1\wedge x_2:
\begin{aligned} h_3&=f(1\cdot x_1-0.5)=x_1,\\ h_4&=f(1\cdot x_1+1\cdot x_2-1.5)=x_1\wedge x_2,\\ h_5&=f(1\cdot x_2-0.5)=x_2,\\ o&=f(1\cdot h_3-2 h_4+1\cdot h_5-0.5). \end{aligned}
The output is 1 if x_1 OR x_2, and it is 0 if x_1 AND x_2.
| x_1 | x_2 | h_3 | h_4 | h_5 | net input of o | o |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | -0.5 | 0 |
| 0 | 1 | 0 | 0 | 1 | +0.5 | 1 |
| 1 | 0 | 1 | 0 | 0 | +0.5 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1-2+1-0.5=-0.5 | 0 |
OR minus AND. Node 3 does AND and node 4 does OR, and the output calculates OR minus AND. The threshold lets only XOR through:
\begin{aligned} h_3&=f(2x_1+2x_2-3)=x_1\wedge x_2,\\ h_4&=f(2x_1+2x_2-1)=x_1\vee x_2,\\ o&=f(-2h_3+2h_4-1). \end{aligned}
| x_1 | x_2 | net of h_3 | net of h_4 | (h_3,h_4) | net of o | o |
|---|---|---|---|---|---|---|
| 0 | 0 | -3 | -1 | (0,0) | -1 | 0 |
| 0 | 1 | -1 | +1 | (0,1) | +1 | 1 |
| 1 | 0 | -1 | +1 | (0,1) | +1 | 1 |
| 1 | 1 | +1 | +3 | (1,1) | -1 | 0 |
In the second solution the hidden layer maps the four input points to three points of the (h_3,h_4) plane: (0,0) for the input (0,0), (1,1) for (1,1), and (0,1) for both (0,1) and (1,0). In the hidden space the problem is linearly separable. The output unit’s boundary h_4=h_3+0.5 puts (0,1) above it and the other two points below. The hidden units have re-described the inputs by two logical features, “at least one is on” and “both are on”, and XOR means “at least one is on, but not both”. The first solution does the same with a three-dimensional representation in which two of the coordinates are the raw inputs.
Neither solution is unique. Weights can be rescaled by any common positive factor, and the network can be permuted by relabelling hidden units. What the constructions establish is existence of a representation. A learning rule is a separate question. The threshold units used here have a derivative that is zero on each open half-space, so a gradient method receives no signal from them.
Used in
- Taught in Neural units
- All 7 questions on Neural units
See also
Artificial neuron · Perceptron learning rule · A single threshold unit cannot compute XOR · One hidden layer approximates continuous functions · History of the neural unit · Neural unit · Linear separability · Threshold unit without a bias