Perceptron Learning Algorithm

The Perceptron Learning Algorithm is the rule Rosenblatt introduced for automatically adjusting a Perceptron's weights from labeled examples — no human hand-tuning required. It's the historical ancestor of gradient descent, though simpler and more limited.

The Update Rule

\(\eta\) is the learning rate. The key term is \((y_{\text{true}} - y_{\text{pred}})\) — the error. If the prediction is already correct, this is 0 and no update happens at all. If the prediction is wrong, the weights shift in the direction that would have made this specific example more likely to be classified correctly.

Step-by-Step Algorithm

1. Initialize weights and bias (commonly to zero or small random values).
2. For each training example \((\mathbf{x}, y_{\text{true}})\): compute the Perceptron's prediction \(y_{\text{pred}}\).
3. Update weights and bias using the rule above.
4. Repeat over the full dataset for multiple passes (epochs) until no more mistakes are made, or a maximum number of epochs is reached.

Numerical Example

Learning AND with \(\eta=1\), starting from \(\mathbf{w}=[0,0], b=0\). Example \((\mathbf{x},y)=([1,1],1)\): prediction \(z=0\ge0\Rightarrow y_{\text{pred}}=1\). Error \(=1-1=0\) — no update. Example \(([0,1],0)\): \(z=0\ge0\Rightarrow y_{\text{pred}}=1\). Error \(=0-1=-1\). Update: \(w_1 \leftarrow 0+1(-1)(0)=0\), \(w_2\leftarrow0+1(-1)(1)=-1\), \(b\leftarrow0+1(-1)=-1\). The weights shift specifically to push this particular misclassified example toward the correct side of the boundary.

Code

import numpy as np

X = np.array([[0,0],[0,1],[1,0],[1,1]])
y = np.array([0,0,0,1])   # AND

w = np.zeros(2)
b = 0.0
lr = 1.0

for epoch in range(10):
    errors = 0
    for xi, yi in zip(X, y):
        z = np.dot(w, xi) + b
        y_pred = 1 if z >= 0 else 0
        error = yi - y_pred
        w += lr * error * xi
        b += lr * error
        errors += abs(error)
    if errors == 0:
        print(f"Converged after {epoch+1} epochs")
        break

print("weights:", w, "bias:", b)

The Perceptron Convergence Theorem

Rosenblatt proved that if the training data is linearly separable, this algorithm is guaranteed to converge — find a perfectly separating boundary — in a finite number of steps. This was a genuinely important theoretical result. But the guarantee has a critical condition attached: if the data is linearly separable. When it isn't (like XOR), the algorithm simply never converges, oscillating forever — exactly the failure mode explored in the next note.

Common Mistakes

• Forgetting the convergence guarantee is conditional on linear separability — running the algorithm on non-separable data and expecting it to eventually settle is a common misunderstanding.
• Confusing this update rule with gradient descent — the Perceptron update is not derived from minimizing a smooth loss function via calculus; it's a simpler, purpose-built correction rule that predates gradient-based training of neural networks.

Interview Relevance

Q: "What does the Perceptron Convergence Theorem guarantee, and what's its key limitation?" It guarantees the Perceptron Learning Algorithm will find a perfectly separating decision boundary in finite time, if the training data is linearly separable. If the data isn't linearly separable, the algorithm has no such guarantee and can fail to converge at all — a limitation that motivated the shift toward multi-layer networks.

Practice Question

Starting from \(\mathbf{w}=[0,0], b=0\) with \(\eta=1\), perform one more update step using the example \(([1,0],0)\) after the update already shown above (\(\mathbf{w}=[0,-1], b=-1\)). Does the Perceptron now correctly classify this example, or does another update occur?

Related DL Notes

• Perceptron
• Limitations of Perceptron
• Gradient Descent (Intro)