The perceptron and linear separability

The concept

The perceptron, introduced by Frank Rosenblatt in 1958, is the simplest artificial neuron. It computes a weighted sum of its inputs plus a bias and outputs 1 if the sum is above zero, and 0 otherwise. Geometrically it draws a line, or in higher dimensions a hyperplane, and classifies points by which side they fall on.

The perceptron learning rule adjusts the weights only when the neuron makes a mistake. For each wrong prediction it adds error × input to each weight and error to the bias, where error is the target minus the output. The perceptron convergence theorem guarantees that if the classes can be separated by a line, this procedure finds a separating line in a finite number of mistakes.

The AND function is linearly separable, so the program finds weights (2, 1) and bias −2 and stops when an entire pass makes no mistakes. XOR is not linearly separable: no single line puts (0,1) and (1,0) on one side and (0,0) and (1,1) on the other, so the rule never reaches a pass with zero mistakes, and the program reports False after its limit of 20 passes. This limitation, emphasized by Minsky and Papert in 1969, is the reason networks with hidden layers are needed.

Code example

def train_perceptron(data, epochs=20):
    w = [0, 0]
    b = 0
    for _ in range(epochs):
        mistakes = 0
        for (x1, x2), target in data:
            output = 1 if w[0] * x1 + w[1] * x2 + b > 0 else 0
            error = target - output
            if error:
                w[0] += error * x1
                w[1] += error * x2
                b += error
                mistakes += 1
        if mistakes == 0:
            return w, b, True
    return w, b, False


AND = [((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)]
XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]
print(train_perceptron(AND))
print(train_perceptron(XOR)[2])

([2, 1], -2, True)
False

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

([2, 1], -2, True)

([2, 1], -2, True)
False

Behind the scenes

Cost and common mistakes

Each pass costs O(n·d) for n examples with d inputs. For separable data the number of mistakes is bounded by (R/γ)², where R is the data radius and γ the margin.

• The convergence guarantee holds only for linearly separable data. On other data the weights keep changing.
• The weights found are not unique. Different starting points or example orders give different separating lines.
• A single neuron cannot represent XOR. Stacking neurons into layers with nonlinear activations overcomes the limit.

Try it yourself

Check that the learned weights classify (1, 0) correctly.

Further reading

• Rosenblatt (1958): The perceptron, a probabilistic model for information storage and organization in the brain (external)
• Stanford CS231n: Deep Learning for Computer Vision (external)
• Deep Learning (Goodfellow, Bengio, Courville) (external)