A Network of Perceptrons

One perceptron cannot compute XOR. Can several? Yes, and the construction below works for any Boolean function.

The construction

For this lesson, encode true as $+1$ and false as $-1$. Take two inputs and build this network:

• Each input connects to all four hidden perceptrons. These connections are fixed to $-1$ or $+1$, and each hidden perceptron has bias $-2$.
• The four hidden perceptrons connect to one output perceptron through weights $w_1, w_2, w_3, w_4$. These are the only weights that will vary.

Terminology that stays with us

• The layer of inputs is the input layer.
• The layer of four perceptrons is the hidden layer, because it sits between the input and the output and the outside world does not see it.
• The last perceptron is the output layer.
• The fixed connections are the layer 1 weights and $w_1, \dots, w_4$ are the layer 2 weights. We do not count the input layer, so this is a two-layer network.

Each hidden perceptron listens for one input

Give the four hidden perceptrons these input weights:

Check $h_1$, with weights $(-1, -1)$ and bias $-2$. For input $(-1, -1)$ the sum is $-2 + 1 + 1 = 0 \ge 0$, so it fires. For $(-1, +1)$ it is $-2 + 1 - 1 = -2 < 0$, so it does not. The same holds for the other two inputs. The other hidden units work the same way: each fires for exactly one of the four inputs, and for no other.

So for any input, exactly one hidden unit is on.

Solving XOR

Now the output perceptron. Whichever input arrives, only one $h_k$ equals 1 and the rest are 0, so the output's weighted sum is just the single weight $w_k$ of the unit that fired (plus the output bias, which we set to 0).

XOR should output 1 for $(-1, +1)$ and $(+1, -1)$, and 0 for $(-1, -1)$ and $(+1, +1)$. So we need

• $w_2 \ge 0$ and $w_3 \ge 0$ (the two inputs where XOR is 1),
• $w_1 < 0$ and $w_4 < 0$ (the two where XOR is 0).

For example, $w = (-1, +1, +1, -1)$. Every condition concerns a different weight, so nothing conflicts, unlike the single-perceptron case where all the conditions fought over the same three numbers.

Any Boolean function

The same trick works for every two-input function. Each truth-table row controls one weight, and the rows never interfere, so you can pick the four weights to match any pattern of outputs. There are 16 such patterns, and all 16 are reachable by changing $w_1, \dots, w_4$ alone.

It also scales up. With $n$ inputs there are $2^n$ possible input patterns, so use $2^n$ hidden perceptrons, one per pattern, and one output perceptron. This gives a result:

Any Boolean function of $n$ inputs can be represented exactly by a network with one hidden layer of $2^n$ perceptrons and one output perceptron.

The proof is the construction itself.

The catch

• It is sufficient, not necessary. AND needs just one perceptron. The construction is a guarantee, not the smallest design.
• It grows exponentially. 10 inputs need 1,024 hidden units. 100 inputs need about $10^{30}$, far more than can be built.

Why it matters for real data

Real datasets, like the film example, are usually not linearly separable. This result says some network of perceptrons can match any truth table exactly, so separation is possible in principle. The open questions are how to do it with far fewer units, how to handle non-Boolean data, and how to learn all the weights, not just the last layer.

A network like this is called a multi-layer perceptron (MLP). Strictly it is a multi-layered network of perceptrons, but "MLP" is the common name.

The next topics in the course address the two problems above: smooth neurons that can be trained by gradient descent, and deeper networks that are much more compact.