XOR, Boolean Functions and the Power of a Network of Perceptrons

Start here One perceptron draws one straight line. Some problems — even a tiny one called XOR — cannot be solved with one line. The fix is surprisingly simple: use many perceptrons in layers. This page proves that such a network can represent any Boolean function.

XOR (“exclusive OR”) is 1 when the two inputs are different.

The contradiction, step by step:

1. From rows 2 and $3: w_{1} + w_{2} \ge -w_{0} + (-w_{0}) = -2w_{0}$.
2. From $row 1, w_{0} < 0$, so $-w_{0} > 0$, so $-2w_{0} > -w_{0}$.
3. $So w_{1} + w_{2} \ge -2w_{0} > -w_{0}, i$.e. $w_{1} + w_{2} > -w_{0}$.
4. Row 4 needs $w_{1} + w_{2} < -w_{0}$. Impossible.

Real data is like this too. Most real-world data is not linearly separable. It has outliers, and sometimes even without outliers no line can separate it. We need models that can handle this. A single perceptron cannot — but a network of perceptrons can.

Each function is one way of filling the output column for the 4 input rows. Each row can be 0 or 1, so there are $2 \times 2 \times 2 \times 2 =$ $2^{4} = 16$ functions.

Of these 16, 14 are linearly separable. Only $f7 = XOR$ and $f10 = !XOR (XNOR)$ are not.

For n inputs: there are $2^{n}$ input rows, and each can output 0 or 1, so there are $2^{2^{n}}$ Boolean functions. ($n = 2 \to 2^{4} = 16; n = 3 \to 2^{8} = 256$.) Some of these are not linearly separable. (The exact count is not needed for this course.)

For this part, use True $= +1$ and False $= -1$.

The network:

• Input layer:$x_{1}, x_{2}.$
• Hidden layer: 4 perceptrons $h_{1}, h_{2}, h_{3}, h_{4}$. Each gets both inputs with weights +1 (blue edge) or −1 (red edge). Each has bias −2 — it fires only if its weighted sum is $\ge 2$.
• Output layer: one perceptron y, with weights $w_{1}, w_{2}, w_{3}, w_{4}$ from the hidden units (these are what we choose/learn).

Terminology: input layer, hidden layer (the middle one), output layer. Red/blue edges $=$ layer 1 weights$. w_{1}\ldots w_{4} =$layer 2 weights. Outputs of the hidden perceptrons $= h_{1}\ldots h_{4}$.

Key trick: each hidden perceptron fires for exactly one input.

For any other input, the sum is 0 or −2, which is $< 2$, so the unit stays off.

Lecture example — XOR with this network Let the output fire if $\sum w_{i}h_{i} \ge w_{0}$ (output threshold). For each input only one $h_{i} = 1$, so the sum is just that $w_{i}$:

$x_{1}$	$x_{2}$	XOR	$h_{1} h_{2} h_{3} h_{4}$	$\sum w_{i}h_{i}$
0 (−1)	0 (−1)	0	1 0 0 0	$w_{1}$
0 (−1)	1 (+1)	1	0 1 0 0	$w_{2}$
1 (+1)	0 (−1)	1	0 0 1 0	$w_{3}$
1 (+1)	1 (+1)	0	0 0 0 1	$w_{4}$

Conditions: $w_{1} < w_{0}, w_{2} \ge w_{0}, w_{3} \ge w_{0}, w_{4} < w_{0}.$ No contradiction now! One answer: $w_{0} = 0, w_{1} = -1, w_{2} = +1, w_{3} = +1, w_{4} = -1$.

Why it works: each $w_{i}$ controls one row alone, so we can set every row’s answer freely. The same network can do all 16 functions — just change $w_{1}\ldots w_{4}$. Each function gives its own set of non-contradicting inequalities.

• 3 inputs: 8 input combinations → 8 hidden perceptrons (bias −3, each fires for one combination) → 8 output weights.
• n inputs: $2^{n}$ combinations $\to 2^{n}$ hidden perceptrons.

Theorem. Any Boolean function of n inputs can be represented exactly by a network of perceptrons with 1 hidden layer of $2^{n}$ perceptrons and 1 output perceptron. Proof (informal): we just built it.

Note: $2^{n} + 1$ perceptrons is sufficient, not necessary. AND needs just 1 perceptron.

The catch: the hidden layer grows exponentially.

We have past data: for each movie, features $x_{1} \ldots x_{n}$ and the label y (like $= 1$ / dislike $= 0$). Points with $y = 1$ are $p_{1}, p_{2}, \ldots$; points with $y = 0$ are $n_{1}, n_{2}, \ldots$. The data may or may not be linearly separable.

The theorem says: there exists a network of perceptrons whose weights can be learned so that its output matches y for every $p_{i}$ and $n_{j}$. So a network can separate positive and negative points even when one line cannot.

Networks with an input layer, one or more hidden layers, and an output layer are called Multilayer Perceptrons (MLPs). (A more accurate name would be “multilayered network of perceptrons”, but MLP is the common name.)

Representation power of an MLP with one hidden layer: it can represent any Boolean function exactly.

In one line: One perceptron fails on XOR, but one hidden layer of $2^{n}$ perceptrons can represent any Boolean function — at the cost of exponentially many units.

Exam words: XOR, XNOR, not linearly separable, $2^{2^{n}}$ Boolean functions, hidden layer, input layer, output layer, layer 1/layer 2 weights, multilayer perceptron (MLP), representation power, $2^{n}$ hidden perceptrons, sufficient vs necessary.