Multilayer networks: a forward pass that computes XOR

Combine two layers of neurons with hand-chosen weights to compute XOR, which one neuron cannot.

def dense(inputs, weights, biases, activation):
    return [
        activation(sum(w * x for w, x in zip(row, inputs)) + bias)
        for row, bias in zip(weights, biases)
    ]


def step(z):
    return 1 if z > 0 else 0


hidden_weights = [[1, 1], [1, 1]]
hidden_biases = [-0.5, -1.5]
output_weights = [[1, -1]]
output_biases = [-0.5]

for x in ((0, 0), (0, 1), (1, 0), (1, 1)):
    hidden = dense(x, hidden_weights, hidden_biases, step)
    output = dense(hidden, output_weights, output_biases, step)[0]
    print(x, hidden, output)

(0, 0) [0, 0] 0
(0, 1) [1, 0] 1
(1, 0) [1, 0] 1
(1, 1) [1, 1] 0

Explanation

A multilayer perceptron (MLP) arranges neurons in layers. Each layer computes new values from the previous layer's outputs with a weight for every connection, a bias for every neuron, and an activation function. The forward pass computes the output by passing the inputs through the layers in order. The hidden layers, those between the input and the output, let the network build intermediate features.

XOR is not linearly separable, so a single neuron cannot compute it. With one hidden layer it is easy. Two hidden neurons detect simple features: the first fires when at least one input is on (OR), and the second fires when both are on (AND). The output neuron fires when OR is on and AND is off, which is exactly XOR. The weights here are set by hand to show the idea, and the next lesson shows how they can be learned.

The universal approximation theorem (Cybenko 1989, Hornik 1991) says a feedforward network with one hidden layer and enough neurons can approximate any continuous function on a bounded region arbitrarily well. It is an existence result: it does not say how many neurons are needed or that training will find the weights. In practice, deeper networks often represent useful functions much more efficiently than a single very wide layer.

—

—

—

—

(0, 0) [0, 0] 0
(0, 1) [1, 0] 1
(1, 0) [1, 0] 1
(1, 1) [1, 1] 0

Cost and common mistakes

A dense layer with m inputs and n outputs costs O(m·n) operations and stores m·n weights plus n biases.

• A threshold step is used here for clarity, but it cannot be trained by gradient descent because its slope is zero almost everywhere. Trainable networks use smooth or piecewise-linear activations.
• Hand-chosen weights show that a solution exists. They do not show that training will find one.
• More layers are not automatically better. Depth increases training difficulty as well as capacity.

Try it yourself

What does the network output for (1, 0), step by step?

Further reading

• Cybenko (1989): Approximation by superpositions of a sigmoidal function (external)
• Stanford CS231n: Deep Learning for Computer Vision (external)
• Deep Learning (Goodfellow, Bengio, Courville) (external)