# Perceptron

> Update w ← w + y·x on every mistake; if the classes are linearly separable, it converges in finitely many steps.

Source: https://www.mlfoundry.in/learn/perceptron  
Section: ML Algorithms › Supervised · Classification  
Level: core · 16 min read · updated 2026-10-07

**The perceptron:** is a linear classifier $\hat y=\operatorname{sign}(w\cdot x+b)$ trained by one rule: go through the examples, and whenever one is on the wrong side of the line, add $y\,x$ to the weights. Correctly classified examples are ignored. Rosenblatt proposed it in 1957. It was the first learning algorithm that came with a proof that it works, and it is the ancestor of every neural network.

- **Task:** Binary classification (labels $y\in\{-1,+1\}$); multiclass by extension
- **Input → output:** feature vector $x\in\mathbb{R}^d$ → a hard label $\pm1$ (no probability)
- **Learns:** a weight vector $w\in\mathbb{R}^d$ and a bias $b$; the boundary is the hyperplane $w\cdot x+b=0$
- **Training:** $O(n\,d)$ per epoch (one pass over the data); on separable data at most $(R/\gamma)^2$ updates in total
- **Prediction:** $O(d)$: one dot product and a sign
- **Hyperparameters:** number of epochs, data order / shuffling, learning rate η (usually irrelevant), optional regularization and early stopping
- **Assumes:** for convergence: the classes are linearly separable. Nothing is assumed about distributions

## The problem

In 1943 McCulloch and Pitts described an artificial neuron as a threshold unit: add up weighted inputs and fire if the sum is above a threshold. Such a unit can compute AND, OR and NOT, but its weights had to be **set by hand**. The open question was how a machine could find the weights by itself, just from labelled examples.

Least squares was the obvious tool, but it solves a different problem. Regressing the $\pm1$ labels on $x$ minimizes squared error, so a point that is correctly classified but far from the line still has a large residual and pulls the line toward itself. The fit can end up misclassifying points even when a perfect line exists. What we want is a rule that **only reacts to errors**, works one example at a time (the data may arrive as a stream), and is guaranteed to find a separating line whenever one exists. The perceptron is that rule.

## The idea

The score $s=w\cdot x+b$ says which side of the line $x$ is on: positive means class $+1$, negative means class $-1$. A point is classified correctly exactly when $y$ and $s$ have the same sign, i.e. when $y\,s>0$. When a point is wrong, nudge $w$ so that its score moves toward the correct sign. Adding $x$ to $w$ raises the score of $x$; subtracting $x$ lowers it. Both cases are covered by "add $y\,x$". Geometrically, $w$ is the **normal** of the boundary. Adding a misclassified positive point turns the normal toward that point, and subtracting a misclassified negative point turns it away, so the line rotates and shifts until the point is on the right side. Repeat until a full pass makes no mistakes.

**Vocabulary**

- **Augmented input:** $\tilde x=(1,x_1,\dots,x_d)$. Prepending a constant 1 lets the bias be the weight $w_0$, so $w\cdot\tilde x=w_0+w_1x_1+\dots$ and one update rule trains both
- **Score (activation):** $s=w\cdot\tilde x$, the signed, unnormalized distance of $x$ from the boundary
- **Decision boundary:** the hyperplane $s=0$; $w$ (without $w_0$) is perpendicular to it and points toward the $+1$ side
- **Functional margin:** $y\,s$. Positive means the point is correct; $y\,s\le0$ is a **mistake** (a point exactly on the line counts as wrong)
- **Geometric margin:** $y\,s/\lVert w\rVert$, the true distance to the boundary with a sign. The margin $\gamma$ of a dataset is the largest achievable value of the smallest geometric margin
- **Linearly separable:** some $w$ gives every point $y\,s>0$, i.e. a hyperplane with all $+1$ points on one side and all $-1$ points on the other
- **Epoch:** one full pass over the training set in a fixed (or shuffled) order
- **Update:** $w\leftarrow w+\eta\,y\,\tilde x$, applied only on a mistake. The perceptron is **mistake-driven**

## The math

Absorb the bias into $w$ with the augmented input. The model and the mistake test are:

$$
\hat y=\operatorname{sign}(w\cdot\tilde x),\qquad \text{mistake on }(x_i,y_i)\iff y_i\,(w\cdot\tilde x_i)\le 0
$$

- $w$: weights $(w_0,w_1,\dots,w_d)$, where $w_0$ is the bias
- $\tilde x_i$: augmented input $(1,x_{i1},\dots,x_{id})$
- $y_i$: true label, $+1$ or $-1$
- $\hat y$: predicted label

**From a loss to the update.** The perceptron minimizes the *perceptron criterion*, which charges each misclassified point by how far it is on the wrong side and charges nothing for correct points:

$$
L(w)=\sum_{i=1}^{n}\max\bigl(0,\,-y_i\,w\cdot\tilde x_i\bigr),\qquad \nabla_w \max(0,-y_i w\cdot\tilde x_i)=\begin{cases}-y_i\tilde x_i & y_iw\cdot\tilde x_i<0\\ 0 & y_iw\cdot\tilde x_i>0\end{cases}
$$

- $L(w)$: total perceptron loss; 0 exactly when every point is strictly correct
- $\max(0,-y\,s)$: a hinge at 0: zero on the correct side, growing linearly with the wrong-side score

Take a stochastic gradient step on a single example, $w\leftarrow w-\eta\nabla_w L_i$. On a correct point the gradient is 0, so nothing happens. On a mistake it is $-y_i\tilde x_i$, which gives the perceptron rule:

$$
w \leftarrow w+\eta\,y_i\,\tilde x_i \quad\text{if } y_i\,w\cdot\tilde x_i\le 0
$$

- $\eta$: learning rate (step size), $\eta>0$; classically $\eta=1$

**Why one update helps.** After the update the point's functional margin is $y_i(w+\eta y_i\tilde x_i)\cdot\tilde x_i=y_i\,w\cdot\tilde x_i+\eta\lVert\tilde x_i\rVert^2$, because $y_i^2=1$. The margin rises by exactly $\eta\lVert\tilde x_i\rVert^2>0$. One update does not always fix the point, and it can break others, which is why we keep cycling.

**The convergence theorem (Novikoff, 1962).** Suppose every $\lVert\tilde x_i\rVert\le R$ and some unit vector $u$ separates the data with margin $\gamma$, meaning $y_i\,u\cdot\tilde x_i\ge\gamma>0$ for all $i$. Start from $w=0$ with $\eta=1$, and let $w_k$ be the weights after $k$ mistakes.

**Proof sketch: at most (R/γ)² mistakes**

1. **Progress toward $u$.** Each update adds $y_i\tilde x_i$, so $w_{k}\cdot u=w_{k-1}\cdot u+y_i\tilde x_i\cdot u\ge w_{k-1}\cdot u+\gamma$. After $k$ mistakes, $w_k\cdot u\ge k\gamma$.
2. **Slow growth of the norm.** $\lVert w_k\rVert^2=\lVert w_{k-1}\rVert^2+2y_i\,w_{k-1}\cdot\tilde x_i+\lVert\tilde x_i\rVert^2$. The middle term is $\le0$ because it was a mistake, so $\lVert w_k\rVert^2\le\lVert w_{k-1}\rVert^2+R^2$, and $\lVert w_k\rVert^2\le kR^2$.
3. **Combine.** Cauchy–Schwarz gives $k\gamma\le w_k\cdot u\le\lVert w_k\rVert\le\sqrt k\,R$. Squaring gives $k\le R^2/\gamma^2$.

$$
k\;\le\;\left(\frac{R}{\gamma}\right)^{2}
$$

- $k$: total number of updates (mistakes) over the whole run, across all epochs
- $R$: $\max_i\lVert\tilde x_i\rVert$, the radius of the (augmented) data
- $\gamma$: margin of the best separating hyperplane through the origin in augmented space

The bound depends on neither $n$ nor $d$, only on how wide the gap between the classes is relative to the size of the data. Wide margins mean few mistakes. If the data are **not** separable, no such $u$ exists, and the algorithm keeps making mistakes forever.

**The learning rate does almost nothing.** Starting from $w=0$, every update adds $\eta\,y\,\tilde x$, so the weights are always $\eta$ times the weights of the $\eta=1$ run. The signs of all scores are unchanged, so the same mistakes happen in the same order and the final classifier is the same. (On the worked example below, $\eta=0.1$ gives exactly $w=(-0.5,0.1,0.1)$.) $\eta$ matters only with a non-zero start or with regularization. The real hyperparameters are the **number of epochs** and the **order** of the data.

## Worked example: eight points, seven updates

Two features $x_1,x_2$ (think of two exam scores from 0 to 5) and a pass/fail label. The points are visited in the order of the table, every epoch, with $w=(w_0,w_1,w_2)$ starting at $(0,0,0)$ and $\eta=1$.

Training data, in visiting order. Highlighted rows are the +1 (pass) class.

| # | x₁ | x₂ | y | augmented x̃ |
| --- | --- | --- | --- | --- |
| 1 | 1 | 0 | −1 | (1, 1, 0) |
| 2 | 0 | 0 | −1 | (1, 0, 0) |
| 3 | 5 | 5 | +1 | (1, 5, 5) |
| 4 | 0 | 1 | −1 | (1, 0, 1) |
| 5 | 2 | 5 | +1 | (1, 2, 5) |
| 6 | 1 | 1 | −1 | (1, 1, 1) |
| 7 | 4 | 3 | +1 | (1, 4, 3) |
| 8 | 3 | 5 | +1 | (1, 3, 5) |

**Epoch 1 by hand**

1. **Point 1** $(1,0)$, $y=-1$: $s=(0,0,0)\cdot(1,1,0)=0$, so $y\,s=0\le0$, a mistake. $w\leftarrow(0,0,0)-(1,1,0)=(-1,-1,0)$.
2. **Point 2** $(0,0)$, $y=-1$: $s=-1$, $y\,s=1>0$. Correct, no change.
3. **Point 3** $(5,5)$, $y=+1$: $s=-1-5+0=-6$, $y\,s=-6$, a mistake. $w\leftarrow(-1,-1,0)+(1,5,5)=(0,4,5)$.
4. **Point 4** $(0,1)$, $y=-1$: $s=0+0+5=5$, $y\,s=-5$, a mistake. $w\leftarrow(0,4,5)-(1,0,1)=(-1,4,4)$.
5. **Point 5** $(2,5)$, $y=+1$: $s=-1+8+20=27$. Correct.
6. **Point 6** $(1,1)$, $y=-1$: $s=-1+4+4=7$, $y\,s=-7$, a mistake. $w\leftarrow(-1,4,4)-(1,1,1)=(-2,3,3)$.
7. **Points 7, 8**: $s=-2+12+9=19$ and $s=-2+9+15=22$, both positive and correct. **Epoch 1: 4 mistakes**, ending at $w=(-2,3,3)$.

Every update of the run. Epoch 3 visits all eight points with no mistake, so training stops at w = (−5, 1, 1).

| Epoch | Point | y | score s (before) | y·s | w after update |
| --- | --- | --- | --- | --- | --- |
| 1 | 1 (1, 0) | −1 | 0 | 0 | (−1, −1, 0) |
| 1 | 3 (5, 5) | +1 | −6 | −6 | (0, 4, 5) |
| 1 | 4 (0, 1) | −1 | 5 | −5 | (−1, 4, 4) |
| 1 | 6 (1, 1) | −1 | 7 | −7 | (−2, 3, 3) |
| 2 | 1 (1, 0) | −1 | 1 | −1 | (−3, 2, 3) |
| 2 | 4 (0, 1) | −1 | 0 | 0 | (−4, 2, 2) |
| 2 | 6 (1, 1) | −1 | 0 | 0 | (−5, 1, 1) |
| 3 | none |  |  | all > 0 | (−5, 1, 1), converged |

**Reading off the result**

1. **Boundary.** $-5+x_1+x_2=0$, i.e. **pass when $x_1+x_2>5$**. The final scores of the eight points are $-4,-5,5,-4,2,-3,2,3$, all with the correct sign.
2. **Predict a new student** with $x=(4,2)$: $s=-5+4+2=1>0$, so $\hat y=+1$ (pass). For $(3,1)$: $s=-5+3+1=-1$, fail.
3. **Check the bound.** The largest augmented norm is $\lVert(1,5,5)\rVert=\sqrt{51}=7.14$. The best margin through the origin in augmented space is $\gamma=0.530$ (from $u\propto(-1.8,0.4,0.4)$). So Novikoff allows at most $(7.14/0.530)^2=181.6$ updates. The run needed **7**. The bound is a worst case, not a prediction.
4. **Points 5 and 7** end closest to the line, at $y\,s=2$, a distance $2/\sqrt2=1.41$ from it. The perceptron stopped at the **first** separating line it found, not the widest one.

> Figure: The worked example, one point visit per step. The violet arrow is the normal (w₁, w₂) drawn from the origin. On a mistake the dashed grey arrow is the old normal and the rose arrow is the added y·x, so you can see the vector sum turn the boundary. Points with a rose outline are currently misclassified. Separable data: 4, 3, then 0 mistakes per epoch, ending at w = (−5, 1, 1) after 7 updates. Switch to '+ mislabelled (4, 4)': every epoch ends with that point flipping w (to (−9, −1, −2) after 6 epochs, 4 errors), while the pocket keeps (−6, 3, 2) with 1 error.

> **The answer depends on the order:** Run the same data in reverse order (point 8 first) and the perceptron converges after 5 updates to $w=(-3,0,2)$, i.e. the horizontal line $x_2=1.5$, a completely different separator. Both are "correct" on the training set. The perceptron finds *a* separating hyperplane, and which one depends on the visiting order. A hard-margin SVM on the same points finds the unique widest one, $x_1+x_2=4.5$, with half-width 1.77 against the perceptron's 1.41. That is the subject of **Support Vector Machines**.

## The algorithm, step by step

**Perceptron(X, y, epochs)**

1. **Prepare.** Append a constant feature 1 to every $x_i$ (or keep a separate $b$ and update it by $\eta\,y_i$). Encode labels as $\pm1$. Standardize features if their scales differ a lot.
2. **Initialize** $w=0$.
3. **For each epoch**, optionally shuffle, then for each $(x_i,y_i)$ compute $s=w\cdot\tilde x_i$. If $y_i s\le0$, set $w\leftarrow w+\eta\,y_i\tilde x_i$ and count a mistake.
4. **Stop** when an epoch makes no mistakes (converged), or after `max_epochs`, or when the training loss stops improving (`tol`, `n_iter_no_change`).
5. **Predict** $\hat y=\operatorname{sign}(w\cdot\tilde x)$ for new points.

**Complexity**

- **Per update:** $O(d)$: one dot product plus one vector addition (for sparse inputs, $O(\text{non-zeros})$)
- **Per epoch:** $O(n\,d)$
- **Total (separable):** at most $(R/\gamma)^2$ updates, plus the final clean epoch
- **Memory:** $O(d)$. It never needs more than one example at a time, so it works online and out of core

## When the data are not separable

Add a single mislabelled point, $(4,4)$ with $y=-1$, sitting inside the pass region. Now no line can be perfect. In the run above (switch the figure to the second tab), every epoch's last update is that point, which flips the normal around. After 6 epochs the weights are $w=(-9,-1,-2)$, a line that gets **4** of the 9 points wrong. Meanwhile the run passed through $w=(-6,3,2)$, which gets only the mislabelled point wrong. The plain perceptron just returns whatever $w$ it holds when the epochs run out, and that can be any point in its cycle.

Variants of the perceptron, and what each one fixes.

| Variant | Change to the rule | What it fixes |
| --- | --- | --- |
| **Pocket** (Gallant 1990) | keep a copy of the w with the fewest training errors seen so far | non-separable data: returns (−6, 3, 2), 1 error, instead of the last w |
| **Averaged / voted** (Freund & Schapire 1999) | predict with the average of w over all steps (voted: weight each w by how long it survived) | noise and order sensitivity; generalizes close to an SVM, at the same cost |
| **Margin perceptron** | update when y·s ≤ τ for some τ > 0, not just ≤ 0 | the boundary hugging the data: forces a gap of at least τ/‖w‖ |
| **Kernel perceptron** | store mistake counts αᵢ; s = Σ αᵢ yᵢ k(xᵢ, x) | non-linear boundaries (XOR, circles) via a kernel |
| **Multiclass** | one wᶜ per class; predict argmax wᶜ·x; on a mistake add x to the true class, subtract it from the predicted one | more than two classes in one model |
| **Structured** (Collins 2002) | the same update on feature vectors of whole output sequences | tagging and parsing with averaged updates |
| **Multi-layer perceptron** | stack layers with smooth activations, train with backpropagation | anything non-linear, at the price of convexity and guarantees |

**Practical tuning (scikit-learn's Perceptron)**

- **max_iter:** the number of epochs. On non-separable data this decides where the cycle stops, so prefer early stopping or averaging
- **shuffle:** on by default. It reshuffles every epoch, so set `random_state` for reproducibility; the result depends on the order
- **tol, n_iter_no_change:** stop when the loss has not improved by `tol` for that many epochs; `tol=None` runs all `max_iter` epochs
- **eta0:** the learning rate. From a zero start it only rescales w (see the math), so leave it at 1
- **penalty, alpha:** optional L2/L1/elastic-net shrinkage. Here η does matter, because the penalty is scaled by it
- **early_stopping:** hold out `validation_fraction` of the data and stop when validation accuracy stops improving: a cheap guard against non-separable cycling
- **class_weight:** scales the update for each class. Use 'balanced' for imbalanced labels

> **No convergence without separability:** On non-separable data the plain perceptron never stops on its own, and the weights it ends with depend on where the last epoch happened to stop. Real data is almost never perfectly separable. Always cap the epochs and use the pocket or the averaged perceptron, `early_stopping=True`, or switch to logistic regression or a linear SVM.

> **Scale your features (and mind the bias):** The bound $(R/\gamma)^2$ grows with the largest input norm. One feature measured in thousands makes $R$ huge, so convergence takes many more updates and that feature dominates every step. Standardize first. Also note that the bias coordinate of the augmented input is the constant 1. If the data sit far from the origin, $w_0$ moves by only 1 per update while the other weights move by the full feature values, so centring the data helps too.

> **Scores are not probabilities:** The perceptron's `decision_function` is an uncalibrated score, and there is no `predict_proba`. Its loss is zero for every correctly classified point, however close to the line, so nothing pushes the scores toward meaningful confidences. If you need probabilities, use **Logistic Regression**, which replaces the hard step with a sigmoid and the perceptron criterion with log-loss. If you want a generative linear classifier with a closed-form fit, see **Linear Discriminant Analysis**.

## In code

```python
import numpy as np

def perceptron(X, y, eta=1.0, max_epochs=100):
    Xa = np.c_[np.ones(len(X)), X]          # prepend x0 = 1 so w[0] is the bias
    w = np.zeros(Xa.shape[1])
    for epoch in range(1, max_epochs + 1):
        mistakes = 0
        for xi, yi in zip(Xa, y):
            if yi * (w @ xi) <= 0:          # wrong side (or on the line)
                w += eta * yi * xi           # w <- w + eta * y * x
                mistakes += 1
        print(f"epoch {epoch}: {mistakes} mistakes, w = {w}")
        if mistakes == 0:                    # a full clean pass: converged
            return w, epoch
    return w, None                           # not separable (or too few epochs)

def predict(w, X):
    return np.sign(np.c_[np.ones(len(X)), X] @ w)

X = np.array([[1, 0], [0, 0], [5, 5], [0, 1], [2, 5], [1, 1], [4, 3], [3, 5]], float)
y = np.array([-1, -1, 1, -1, 1, -1, 1, 1])
w, epochs = perceptron(X, y)
print("converged after", epochs, "epochs; w =", w)
print("predict (4, 2):", predict(w, np.array([[4, 2]])))

# epoch 1: 4 mistakes, w = [-2.  3.  3.]
# epoch 2: 3 mistakes, w = [-5.  1.  1.]
# epoch 3: 0 mistakes, w = [-5.  1.  1.]
# converged after 3 epochs; w = [-5.  1.  1.]
# predict (4, 2): [1.]
```

From scratch, on the worked example. Prints 4, 3, then 0 mistakes per epoch, converges to w = [-5, 1, 1], and predicts +1 for (4, 2).

```python
import numpy as np
from sklearn.linear_model import Perceptron

X = np.array([[1, 0], [0, 0], [5, 5], [0, 1], [2, 5], [1, 1], [4, 3], [3, 5]], float)
y = np.array([-1, -1, 1, -1, 1, -1, 1, 1])

clf = Perceptron(eta0=1.0, shuffle=False, max_iter=100, tol=None).fit(X, y)
print("w0 =", clf.intercept_, " w1, w2 =", clf.coef_)
print("training accuracy:", clf.score(X, y))
print("predict (4, 2):", clf.predict([[4, 2]]), " score:", clf.decision_function([[4, 2]]))

# w0 = [-5.]  w1, w2 = [[1. 1.]]
# training accuracy: 1.0
# predict (4, 2): [1]  score: [1.]

# Equivalent: SGDClassifier(loss="perceptron", learning_rate="constant", eta0=1, penalty=None)
```

scikit-learn, same data and order (shuffle=False, eta0=1). It finds the same w, because Perceptron is SGD on the perceptron loss.

**Strengths**

- You need a very fast, tiny, online linear classifier: one dot product per prediction and O(d) memory, and it updates from a stream one example at a time.
- The data are (close to) linearly separable, e.g. high-dimensional sparse text features, where the averaged perceptron is competitive with linear SVMs.
- You want a transparent baseline or a teaching model: every weight change has a one-line explanation.
- You need a learner for structured outputs (tagging, parsing) with simple, mistake-driven updates.

**Limitations**

- You need probabilities or calibrated confidence: use logistic regression.
- The data are noisy or overlapping: the plain version cycles and its final weights are arbitrary.
- You want the best linear boundary: it stops at the first separator, with no margin. Use an SVM.
- The boundary is non-linear (XOR is the classic case): a single perceptron cannot represent it without kernels or hidden layers.

- **Mark I Perceptron (1958):** Rosenblatt's hardware: a 20×20 photocell retina wired to adjustable potentiometer weights, trained to recognize simple shapes and letters.
- **NLP tagging and parsing:** The averaged structured perceptron (Collins 2002) was the workhorse for part-of-speech tagging, chunking and dependency parsing before neural models.
- **Online and streaming classification:** Spam filtering, click and fraud filters on sparse hashed features: learn as data arrives, with no stored dataset.
- **The neuron in neural networks:** Every unit of a multi-layer perceptron is a perceptron with a smooth activation. The perceptron's limits on XOR (Minsky & Papert, 1969) are why hidden layers matter.

> **One family, three losses:** The perceptron, the linear SVM and logistic regression are all linear models $\operatorname{sign}(w\cdot\tilde x)$ trained by SGD. They differ only in the loss as a function of the margin $m=y\,s$: perceptron $\max(0,-m)$, hinge $\max(0,1-m)$, logistic $\log(1+e^{-m})$. Moving the hinge from 0 to 1 is what gives the SVM its margin. Smoothing it gives logistic regression its probabilities.

**Question:** w = (−2, 3, 3) (bias first). The point x = (1, 0) with y = −1 arrives, and η = 1. What is w after this step?

- A. (−2, 3, 3), since the point is correct
- B. (−1, 4, 3)
- C. (−3, 2, 3)
- D. (−3, 2, 2)

**Answer:** C. (−3, 2, 3) — $s=-2+3\cdot1+3\cdot0=1$, so $y\,s=-1\le0$, a mistake. $w\leftarrow w+y\tilde x=(-2,3,3)-(1,1,0)=(-3,2,3)$. This is the first update of epoch 2 in the worked example.

**Question:** Every augmented input has norm at most R = 5, and the data are separable with margin γ = 0.5. Novikoff's theorem guarantees the perceptron makes at most how many updates?

- A. 10
- B. 20
- C. 100
- D. It depends on the number of points n

**Answer:** C. 100 — $k\le(R/\gamma)^2=(5/0.5)^2=100$, whatever $n$ and $d$ are, and however many epochs that takes.

**Question:** Starting from w = 0, you change the learning rate from η = 1 to η = 0.1. What happens to the trained classifier?

- A. It converges 10× slower
- B. It makes the same mistakes in the same order and predicts identically; w is just 10× smaller
- C. It may fail to converge
- D. It finds a wider margin

**Answer:** B. It makes the same mistakes in the same order and predicts identically; w is just 10× smaller — Every update adds $\eta\,y\,\tilde x$, so $w$ is always $\eta$ times the $\eta=1$ weights. Signs of scores, and therefore mistakes and predictions, are unchanged. On the worked example, $\eta=0.1$ ends at $(-0.5,0.1,0.1)$.

**Question:** You train a perceptron on XOR: (0,0) and (1,1) are −1, (0,1) and (1,0) are +1. What happens?

- A. It converges to 100% training accuracy
- B. It never converges: no line separates XOR, so some point is always misclassified
- C. It converges once the learning rate is small enough
- D. It converges after (R/γ)² updates

**Answer:** B. It never converges: no line separates XOR, so some point is always misclassified — XOR is not linearly separable, so γ does not exist and the theorem does not apply. Any line gets at least one point wrong; scikit-learn's Perceptron with 1000 epochs reaches only 50% training accuracy here. Kernels or a hidden layer are needed.

**Key points**

- Model: $\hat y=\operatorname{sign}(w\cdot\tilde x)$, with the bias folded in as $w_0$ via $\tilde x=(1,x)$.
- Rule: only on a mistake ($y\,w\cdot\tilde x\le0$), set $w\leftarrow w+\eta\,y\,\tilde x$. This is SGD on the loss $\max(0,-y\,w\cdot\tilde x)$, and each update raises the point's margin by $\eta\lVert\tilde x\rVert^2$.
- Separable data: at most $(R/\gamma)^2$ updates (Novikoff). The worked example converged to $x_1+x_2=5$ in 7 updates, against a bound of 181.6.
- The result depends on the visiting order and has no margin guarantee. From w = 0 the learning rate is irrelevant.
- Non-separable data: it cycles forever, so use the pocket or averaged perceptron, early stopping, or logistic regression / SVM.
- No probabilities and no non-linear boundaries. It is the single neuron that multi-layer networks are built from.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
