The Perceptron Learning Algorithm

Now the algorithm we have been heading toward. First, what problem does it solve?

The setting

You have $m$ past examples. Each has $n$ features and a label of 1 (positive) or 0 (negative). In the film example, each past film is a row of yes/no features, and the label says whether you liked it. Some features could also be real numbers, such as a rating.

Assume the data is linearly separable, so some line, plane or hyperplane puts all the positives on one side and all the negatives on the other. The goal is to find weights $w$ that do that.

Write $P$ for the set of positive examples and $N$ for the set of negative ones. Each example $x$ includes the constant $x_0 = 1$, so the bias is part of $w$.

The algorithm

1. Start with random weights $w$.
2. Repeat until converged:
   1. Pick a random example $x$ from $P \cup N$.
   2. If $x \in P$ and $w \cdot x < 0$, the perceptron missed a positive. Add the example: $w \leftarrow w + x$.
   3. If $x \in N$ and $w \cdot x \ge 0$, the perceptron accepted a negative. Subtract the example: $w \leftarrow w - x$.
   4. Otherwise the example is fine. Change nothing.

Convergence means every positive has $w \cdot x \ge 0$ and every negative has $w \cdot x < 0$: a full pass over the data needs no correction.

At this point "add" and "subtract" look like a magic recipe. The next lesson shows why they move the weights in the right direction.

In code

import numpy as np

class Perceptron:
    def __init__(self, num_features):
        # One extra weight for the bias (w_0)
        self.w = np.random.rand(num_features + 1)

    def predict(self, x):
        # Insert the dummy input x_0 = 1 at the front
        x_with_bias = np.insert(x, 0, 1)
        return 1 if np.dot(self.w, x_with_bias) >= 0 else 0

    def fit(self, X_train, Y_train, max_epochs=1000):
        """Train until a full pass makes no errors, or max_epochs is reached."""
        for epoch in range(max_epochs):
            errors = 0

            for x, y_true in zip(X_train, Y_train):
                y_pred = self.predict(x)
                x_with_bias = np.insert(x, 0, 1)

                if y_true == 1 and y_pred == 0:      # missed a positive
                    self.w = self.w + x_with_bias
                    errors += 1
                elif y_true == 0 and y_pred == 1:    # accepted a negative
                    self.w = self.w - x_with_bias
                    errors += 1

            if errors == 0:
                print(f"Converged in {epoch + 1} epochs.")
                break

Train it on AND:

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
Y = [0, 0, 0, 1]

p = Perceptron(num_features=2)
p.fit(X, Y)
print([p.predict(x) for x in X])   # [0, 0, 0, 1]

Because the starting weights are random, the number of epochs changes from run to run (a few epochs in our runs), but the final predictions are the same. Try OR. Then try XOR, where it never converges ("Where One Perceptron Fails" explains why).