Artificial intelligence → Module 3 → The perceptron

The perceptron: one neuron in Python

In module 2 we set the weights of an artificial neuron ourselves. Now we write a program in which the neuron learns the weights by itself, from examples. Such a neuron is called a perceptron – it was invented by Frank Rosenblatt in 1958. We will teach it the logical functions AND and OR, and we will also see what one neuron can't do.

Reminder: how a neuron works

A neuron multiplies each input by its weight, adds them up and compares the sum with a threshold: if the sum ≥ threshold, the output is 1, otherwise 0. (See the interactive example in the lesson Neural networks.)

These tables are our training examples: the inputs (a, b) and the correct output.

The learning rule

At the beginning all weights are 0. For each example:

1. we calculate the output of the neuron;
2. error = correct output − neuron output (0 if it is correct, +1 if it should have been 1, −1 if it should have been 0);
3. if there is an error: we move each weight by error · input, and the threshold by −error.

We repeat this through all the examples (“rounds”) until there are no errors in a whole round.

Program: the perceptron learns AND and OR

# The perceptron: one artificial neuron that learns the logical functions AND and OR

def output(x, weights, threshold):
    """Neuron: sum of (input · weight); if the sum ≥ threshold, the output is 1, otherwise 0."""
    total = sum(xi * wi for xi, wi in zip(x, weights))
    return 1 if total >= threshold else 0


def train(examples, rate=1, rounds=20):
    weights = [0, 0]                # at the beginning the neuron knows nothing
    threshold = 0
    for round_no in range(1, rounds + 1):
        errors = 0
        for x, correct in examples:
            error = correct - output(x, weights, threshold)     # 0 if correct, +1 or −1 if not
            if error != 0:
                errors += 1
                # the learning rule: move the weights a little in the direction of the correct answer
                for i in range(len(weights)):
                    weights[i] += rate * error * x[i]
                threshold -= rate * error
        print(f"round {round_no}: errors {errors}, weights {weights}, threshold {threshold}")
        if errors == 0:
            break                    # the neuron has learned – we stop
    return weights, threshold


AND_FUNCTION = [((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)]
OR_FUNCTION = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 1)]

for name, examples in [("AND", AND_FUNCTION), ("OR", OR_FUNCTION)]:
    print(f"--- learning the function {name} ---")
    weights, threshold = train(examples)
    for x, correct in examples:
        print(f"  {x} -> {output(x, weights, threshold)} (correct: {correct})")

Program output:

--- learning the function AND ---
round 1: errors 2, weights [1, 1], threshold 0
round 2: errors 3, weights [2, 1], threshold 1
round 3: errors 3, weights [2, 1], threshold 2
round 4: errors 2, weights [2, 2], threshold 2
round 5: errors 1, weights [2, 1], threshold 3
round 6: errors 0, weights [2, 1], threshold 3
  (0, 0) -> 0 (correct: 0)
  (0, 1) -> 0 (correct: 0)
  (1, 0) -> 0 (correct: 0)
  (1, 1) -> 1 (correct: 1)
--- learning the function OR ---
round 1: errors 2, weights [0, 1], threshold 0
round 2: errors 2, weights [1, 1], threshold 0
round 3: errors 1, weights [1, 1], threshold 1
round 4: errors 0, weights [1, 1], threshold 1
  (0, 0) -> 0 (correct: 0)
  (0, 1) -> 1 (correct: 1)
  (1, 0) -> 1 (correct: 1)
  (1, 1) -> 1 (correct: 1)

• For the function AND, the neuron learned the weights [2, 1] and the threshold 3: only when both inputs are 1 is the sum 3. For OR: the weights [1, 1] and the threshold 1.
• Notice that the weights at the end are not “nice” – the neuron doesn't care, what matters is that the answers are correct.
• We use whole numbers (step 1) so that the calculations are easy to follow; in real networks the step is a small decimal number.

What one neuron can't do: XOR

# The same perceptron tries to learn XOR (“either one or the other, but not both”)

def output(x, weights, threshold):
    total = sum(xi * wi for xi, wi in zip(x, weights))
    return 1 if total >= threshold else 0


XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]
weights, threshold = [0, 0], 0
for round_no in range(1, 101):
    errors = 0
    for x, correct in XOR:
        error = correct - output(x, weights, threshold)
        if error:
            errors += 1
            weights = [w + error * xi for w, xi in zip(weights, x)]
            threshold -= error
    if round_no in (1, 10, 50, 100):
        print(f"round {round_no}: errors {errors}")
print("After 100 rounds the neuron still makes mistakes – XOR can't be learned by one neuron.")

Program output:

round 1: errors 3
round 10: errors 4
round 50: errors 4
round 100: errors 4
After 100 rounds the neuron still makes mistakes – XOR can't be learned by one neuron.

In essence, a neuron draws one straight line that divides the inputs into those with output 1 and those with output 0. For AND and OR such a line exists. For XOR it doesn't: the points (0, 1) and (1, 0) must be on one side, and (0, 0) and (1, 1) on the other, and no straight line can do that.

This was shown by Minsky and Papert in 1969, and it was one of the causes of the first “AI winter”. The solution was found later: more layers of neurons – you will see it in the third task and in the next lesson.

Common misconceptions

• “A perceptron always learns if it learns long enough” – it learns only if the task can be solved with one straight line (like AND and OR); XOR can't.
• “The weights after learning must be the same for everyone” – many weights work; which ones you get depends on the order of the examples and the starting values.

Practice tasks

Try it yourself first, and only then open the solution.

1. Teach a perceptron with one input the function NOT (0 → 1, 1 → 0).
2. Teach a perceptron with three inputs the function “at least two of three” (output 1 if at least two inputs are 1).
3. Build XOR from three neurons in two layers: the first layer calculates “a OR b” and “not (a AND b)”, the second layer combines them with the function AND. Choose the weights yourself.

# Task: a perceptron with ONE input learns the function NOT (0 -> 1, 1 -> 0)
def output(x, weights, threshold):
    return 1 if sum(xi * wi for xi, wi in zip(x, weights)) >= threshold else 0


NOT = [((0,), 1), ((1,), 0)]
weights, threshold = [0], 0
for round_no in range(1, 21):
    errors = 0
    for x, correct in NOT:
        error = correct - output(x, weights, threshold)
        if error:
            errors += 1
            weights = [w + error * xi for w, xi in zip(weights, x)]
            threshold -= error
    if errors == 0:
        break
print(f"weight: {weights}, threshold: {threshold} (learned in {round_no} rounds)")
for x, correct in NOT:
    print(x, "->", output(x, weights, threshold))

weight: [-1], threshold: 0 (learned in 3 rounds)
(0,) -> 1
(1,) -> 0

# Task: “at least two of three” – the output is 1 if at least two of the three inputs are equal to 1
from itertools import product


def output(x, weights, threshold):
    return 1 if sum(xi * wi for xi, wi in zip(x, weights)) >= threshold else 0


examples = [(x, 1 if sum(x) >= 2 else 0) for x in product([0, 1], repeat=3)]   # all 8 combinations
weights, threshold = [0, 0, 0], 0
for round_no in range(1, 51):
    errors = 0
    for x, correct in examples:
        error = correct - output(x, weights, threshold)
        if error:
            errors += 1
            weights = [w + error * xi for w, xi in zip(weights, x)]
            threshold -= error
    if errors == 0:
        break
print("weights:", weights, "threshold:", threshold, "rounds:", round_no)
for x, correct in examples:
    print(f"{x} -> {output(x, weights, threshold)} (correct: {correct})")

weights: [1, 1, 1] threshold: 2 rounds: 4
(0, 0, 0) -> 0 (correct: 0)
(0, 0, 1) -> 0 (correct: 0)
(0, 1, 0) -> 0 (correct: 0)
(0, 1, 1) -> 1 (correct: 1)
(1, 0, 0) -> 0 (correct: 0)
(1, 0, 1) -> 1 (correct: 1)
(1, 1, 0) -> 1 (correct: 1)
(1, 1, 1) -> 1 (correct: 1)

# Task: XOR with TWO LAYERS of neurons (we chose the weights ourselves)
# XOR(a, b) = (a OR b) AND NOT(a AND b)
def neuron(x, weights, threshold):
    return 1 if sum(xi * wi for xi, wi in zip(x, weights)) >= threshold else 0


def xor(a, b):
    or_out = neuron((a, b), (1, 1), 1)          # first layer: OR
    nand_out = neuron((a, b), (-1, -1), -1)        # first layer: NAND (1 except when both are 1)
    return neuron((or_out, nand_out), (1, 1), 2)      # second layer: AND


for a in (0, 1):
    for b in (0, 1):
        print(a, b, "->", xor(a, b))

0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 0

Check your knowledge