XOR from Scratch in Mojo with Multiple Perceptrons¶

A single perceptron learned AND in the previous notebook. Here we meet the smallest problem it cannot solve, watch it fail, and then compose three trained perceptrons into a tiny two-layer threshold network trained gate by gate to reproduce XOR exactly.

# Register the %%mojo cell magic in this Python-backed notebook.
import mojo.notebook

1. Write down XOR before writing a model¶

XOR means exclusive OR. It returns 1 when exactly one input is 1.

x1 x2 XOR target
0 0 0
0 1 1
1 0 1
1 1 0

The two positive points occupy opposite corners. No single straight decision boundary can separate them from both negative corners.

%%mojo
def main():
    var x1: List[Float64] = [0.0, 0.0, 1.0, 1.0]
    var x2: List[Float64] = [0.0, 1.0, 0.0, 1.0]
    var targets: List[Int] = [0, 1, 1, 0]

    print("x1 x2 | XOR")
    for i in range(len(targets)):
        print(x1[i], x2[i], "|", targets[i])

x1 x2 | XOR
0.0 0.0 | 0
0.0 1.0 | 1
1.0 0.0 | 1
1.0 1.0 | 0

2. Let one perceptron fail in public¶

We use the familiar update weight += learning_rate * error * input. In this notebook the step function returns 1 only when activation is strictly greater than zero, so a zero activation is classified as zero.

The model keeps changing, but the mistake count does not converge to zero. More epochs cannot create a second boundary.

%%mojo
def predict(x1: Float64, x2: Float64, w1: Float64, w2: Float64, bias: Float64) -> Int:
    return 1 if x1 * w1 + x2 * w2 + bias > 0.0 else 0

def main():
    var x1: List[Float64] = [0.0, 0.0, 1.0, 1.0]
    var x2: List[Float64] = [0.0, 1.0, 0.0, 1.0]
    var targets: List[Int] = [0, 1, 1, 0]
    var w1: Float64 = 0.0
    var w2: Float64 = 0.0
    var bias: Float64 = 0.0
    var learning_rate: Float64 = 1.0

    for epoch in range(6):
        var mistakes: Int = 0
        for i in range(len(targets)):
            var guess = predict(x1[i], x2[i], w1, w2, bias)
            var error = targets[i] - guess
            if error != 0:
                w1 += learning_rate * Float64(error) * x1[i]
                w2 += learning_rate * Float64(error) * x2[i]
                bias += learning_rate * Float64(error)
                mistakes += 1
        print("epoch", epoch + 1, "mistakes:", mistakes)

    print("final model:", w1, w2, bias)
    print("x1 x2 | prediction target")
    for i in range(len(targets)):
        print(x1[i], x2[i], "|", predict(x1[i], x2[i], w1, w2, bias), targets[i])

epoch 1 mistakes: 2
epoch 2 mistakes: 3
epoch 3 mistakes: 4
epoch 4 mistakes: 4
epoch 5 mistakes: 4
epoch 6 mistakes: 4
final model: -1.0 0.0 1.0
x1 x2 | prediction target
0.0 0.0 | 1 0
0.0 1.0 | 1 1
1.0 0.0 | 0 1
1.0 1.0 | 0 0

3. Replace one impossible boundary with three possible ones¶

The hidden layer contains two perceptrons:

  • OR returns one when at least one input is active.
  • NAND returns zero only when both inputs are active.

The output perceptron behaves like AND. Therefore XOR = AND(OR(x1, x2), NAND(x1, x2)). The hidden layer changes the representation before the final boundary is drawn.

%%mojo
def step(activation: Float64) -> Int:
    return 1 if activation > 0.0 else 0

def hidden_or(x1: Float64, x2: Float64) -> Int:
    return step(x1 + x2)

def hidden_nand(x1: Float64, x2: Float64) -> Int:
    return step(-2.0 * x1 - x2 + 3.0)

def output_and(left: Int, right: Int) -> Int:
    return step(Float64(left) + 2.0 * Float64(right) - 2.0)

def main():
    var x1: List[Float64] = [0.0, 0.0, 1.0, 1.0]
    var x2: List[Float64] = [0.0, 1.0, 0.0, 1.0]

    print("x1 x2 | OR NAND | XOR")
    for i in range(len(x1)):
        var h_or = hidden_or(x1[i], x2[i])
        var h_nand = hidden_nand(x1[i], x2[i])
        print(x1[i], x2[i], "|", h_or, h_nand, "|", output_and(h_or, h_nand))

x1 x2 | OR NAND | XOR
0.0 0.0 | 0 1 | 0
0.0 1.0 | 1 1 | 1
1.0 0.0 | 1 1 | 1
1.0 1.0 | 1 0 | 0

4. Train all three perceptrons¶

The previous cell exposed the wiring with known working parameters. Now we learn them. train_perceptron() is the same algorithm for every unit. It returns [w1, w2, bias].

First we train OR and NAND from their truth tables. Their predictions become two new input columns. Finally we train the output perceptron against the XOR targets.

%%mojo
def predict(x1: Float64, x2: Float64, model: List[Float64]) -> Int:
    var activation = x1 * model[0] + x2 * model[1] + model[2]
    return 1 if activation > 0.0 else 0

def train_perceptron(
    x1: List[Float64],
    x2: List[Float64],
    targets: List[Int],
    epochs: Int,
    learning_rate: Float64,
) -> List[Float64]:
    var w1: Float64 = 0.0
    var w2: Float64 = 0.0
    var bias: Float64 = 0.0

    for _ in range(epochs):
        for i in range(len(targets)):
            var guess = predict(x1[i], x2[i], [w1, w2, bias])
            var error = targets[i] - guess
            if error != 0:
                w1 += learning_rate * Float64(error) * x1[i]
                w2 += learning_rate * Float64(error) * x2[i]
                bias += learning_rate * Float64(error)

    return [w1, w2, bias]

def main():
    var x1: List[Float64] = [0.0, 0.0, 1.0, 1.0]
    var x2: List[Float64] = [0.0, 1.0, 0.0, 1.0]
    var xor_targets: List[Int] = [0, 1, 1, 0]
    var or_targets: List[Int] = [0, 1, 1, 1]
    var nand_targets: List[Int] = [1, 1, 1, 0]
    var learning_rate: Float64 = 1.0

    var or_model = train_perceptron(x1, x2, or_targets, 10, learning_rate)
    var nand_model = train_perceptron(x1, x2, nand_targets, 10, learning_rate)

    var h_or = List[Float64]()
    var h_nand = List[Float64]()
    for i in range(len(xor_targets)):
        h_or.append(Float64(predict(x1[i], x2[i], or_model)))
        h_nand.append(Float64(predict(x1[i], x2[i], nand_model)))

    var output_model = train_perceptron(h_or, h_nand, xor_targets, 10, learning_rate)

    print("OR model:", or_model[0], or_model[1], or_model[2])
    print("NAND model:", nand_model[0], nand_model[1], nand_model[2])
    print("Output model:", output_model[0], output_model[1], output_model[2])
    print("\nx1 x2 | OR NAND | prediction target")
    for i in range(len(xor_targets)):
        var guess = predict(h_or[i], h_nand[i], output_model)
        print(x1[i], x2[i], "|", h_or[i], h_nand[i], "|", guess, xor_targets[i])

OR model: 1.0 1.0 0.0
NAND model: -2.0 -1.0 3.0
Output model: 1.0 2.0 -2.0

x1 x2 | OR NAND | prediction target
0.0 0.0 | 0.0 1.0 | 0 0
0.0 1.0 | 1.0 1.0 | 1 1
1.0 0.0 | 1.0 1.0 | 1 1
1.0 1.0 | 1.0 0.0 | 0 0

5. What the hidden layer changed¶

The original XOR points were not linearly separable. The hidden units map them to a new representation:

x1 x2 OR NAND
0 0 0 1
0 1 1 1
1 0 1 1
1 1 1 0

In this hidden space, the positive XOR rows share (1, 1). The output perceptron can separate that point with one boundary.

This network is deliberately trained gate by gate. The next step is to let a shared loss adjust all layers together—the reason backpropagation enters the story.