11. The Perceptron

The Perceptron, invented by Frank Rosenblatt in 1957, was the first algorithmically described neural network. It sparked enormous optimism but was later shown by Minsky and Papert (1969) to be incapable of learning non-linearly separable functions (like XOR). This insight ultimately led to the development of multi-layer networks and backpropagation.

Perceptron Model

Given input x in R^d, the perceptron computes: y_hat = sign(w^T x + b) = sign(sum(w_i x_i) + b)

Where w is the weight vector and b is the bias term.

Perceptron Learning Algorithm

1. Initialize weights w = 0 (or random small values)
2. For each epoch:

• For each training example (x_i, y_i):
• Compute prediction: y_hat = sign(w^T * x_i)
• If y_hat != y_i (misclassified):
• Update: w = w + learning_rate y_i x_i
• Update: b = b + learning_rate * y_i

1. Repeat until convergence (no misclassifications) or max epochs reached

Perceptron Convergence Theorem

Theorem (Rosenblatt, 1962): If the training data is linearly separable, the Perceptron algorithm will converge to a separating hyperplane in a finite number of steps.

Specifically, convergence occurs in at most (R / gamma)^2 mistakes, where:

• R = max norm of training examples
• gamma = geometric margin of the optimal separating hyperplane

Geometric Interpretation

The perceptron finds a hyperplane w^T * x + b = 0 that separates positive from negative examples. The weight update rule moves the hyperplane toward correctly classifying misclassified examples.

Limitations

Common Pitfalls

• The convergence theorem assumes linear separability — must verify this holds
• Learning rate affects convergence speed but not the final solution (for separable data)
• Multiple valid separating hyperplanes exist — the perceptron finds one, not necessarily the best (SVM finds the maximum-margin one)

Exam-Ready Summary

• Perceptron: linear classifier using sign activation and error-based weight updates
• Convergence theorem: guaranteed convergence in finite steps on linearly separable data
• Number of mistakes bounded by (R/gamma)^2 (margin-dependent)
• Cannot solve XOR — requires hidden layers (MLP)
• Perceptron mistake bound is the precursor to Support Vector Machine theory