Perceptron Learning Algorithm (Rosenblatt 1957):

Linear binary classifier $f(x)=sign(w^T x + b)$, $y\in\{-1,1\}$ (or $\{0,1\}$).

Algorithm:
Initialize $w=0, b=0$
Repeat until convergence:
For each $(x_i,y_i)$ in training (random order):
Compute $z = w^T x_i + b$
Predict $\hat y = sign(z)$
If $y_i z \le 0$ (misclassified):
$w := w + \eta y_i x_i$
$b := b + \eta y_i$
else no update
$\eta>0$ learning rate (often 1).

Weight Update Intuition: Move weight vector toward misclassified positive example ($+y x$) and away from negative, increasing score for correct class.

With $\{0,1\}$ labels: $w:=w+\eta(y-\hat y)x$, $b:=b+\eta(y-\hat y)$

Convergence Properties:

• Perceptron Convergence Theorem: If data is linearly separable with margin $\gamma>0$ and radius $R=\max||x_i||$, perceptron makes at most $(R/\gamma)^2$ mistakes and converges to a separating hyperplane in finite steps, regardless of initialization or order. Does not guarantee maximum margin (unlike SVM).
• If data not separable, algorithm never converges, cycles — use Pocket algorithm (keep best weights) or averaging.
• Not sensitive to $\eta$ when separable (scaling).
• Online algorithm, mistake-driven, $O(nd)$ per epoch, fast.

Limitations: Cannot solve XOR, needs separable data; output is hard threshold, no probabilities. Extensions: kernel perceptron, voted perceptron, averaged perceptron for stability.
Example: AND gate converges in few steps; XOR never converges without hidden layer.