Perceptron Algorithm for Halfspaces

The update condition is not checked on an arbitrary unlabelled input. The selected index i matters because the Perceptron adds the matching product yi xi.

Programming

Interactive lab

Try it: Perceptron (Batch)

How the Batch Perceptron learns a halfspace: it looks for an example with y⟨w,x⟩ ≤ 0 and adds y·x to w, until no mistakes remain — which happens only when the data is linearly separable.

How it works

Start with w = 0 (with a bias, each x is extended with a constant 1, so b is learned as a weight).
Scan the examples in order and take the first one with y⟨w,x⟩ ≤ 0 — a mistake.
Update w ← w + y·x; the separating line ⟨w,x⟩ + b = 0 moves towards classifying it correctly.
Repeat until a full pass finds no mistake (converged) or the update cap is reached.
If the data is not linearly separable (checked exactly), no w works and the Perceptron would cycle forever.

Default run (14 steps): Start with w = 0 (and b = 0: x is extended with a constant 1). Every example has y⟨w,x⟩ = 0 ≤ 0, so every one counts as a mistake. … A full pass finds no example with y⟨w,x⟩ ≤ 0 (smallest y⟨w,x⟩ = 1.25). Converged after 12 updates: w = (3, 3.5), b = -6.

Simplified: 2-D toy data (at most 12 points on a half-unit grid) and a deterministic 'first mistake in list order' rule; the textbook allows any example with y⟨w,x⟩ ≤ 0. The update cap stands in for 'run forever'.

Educational simulation

Loading the simulation…

The Learner’s Main Loop

The Perceptron is a learner that repeatedly checks labeled training examples against its current weight vector. It starts with a zero vector. If an example fails the required positive condition, the Perceptron changes its weights using that example. If no example fails, it stops and outputs the current weight vector.

What happens as the Perceptron initializes its weights, checks examples, updates on a qualifying example, and decides whether to stop?

Checking the Update Condition

At iteration t, the Perceptron looks for a training example (xi, yi) satisfying yi〈w(t), xi〉 ≤ 0. Here, w(t) is the current weight vector, xi is the selected feature vector, and yi is its label. Finding such an index means the current vector has not achieved the required strictly positive condition for that example, so an update is performed.

Key point

The update condition is not checked on an arbitrary unlabelled input. The selected index i matters because the Perceptron adds the matching product yi xi.

Formula, step by step

1
Compute the inner product 〈w(t), xi〉.
2
Multiply that value by the example's label yi.
3
If the result is at most zero, select that example for an update.
4
If no training example gives a value at most zero, stop.

When does the learner change its weight vector, and how does adding yi xi produce the next vector?

Tracing One Update

Worked example

Applying the update to a selected example

Suppose the current vector is w(t) = (1, 0), the selected input is xi = (1, 2), and its label is yi = -1. Determine whether the Perceptron updates and calculate w(t+1).

1
Check the signed inner product
The inner product is 〈(1, 0), (1, 2)〉 = 1. Multiplying by yi = -1 gives yi〈w(t), xi〉 = -1.
2
Test the condition
Because -1 ≤ 0, this example satisfies the update condition.
3
Add the labelled input
Compute yi xi = -1(1, 2) = (-1, -2).
4
Form the next vector
Use w(t+1) = w(t) + yi xi = (1, 0) + (-1, -2).

Result

w(t+1) = (0, -2), so the Perceptron updates.

Online Prediction Rounds

The Perceptron can also be viewed as an online learner. On round t, it first receives one input vector xt from R^{^d}. It uses the current weight vector w(t) to predict a label, and only afterward receives the true label yt. The true label is feedback after the prediction, not information used to produce that same prediction.

Formula

After the prediction, the learner compares pt with the revealed true label yt. A prediction mistake occurs when the predicted label does not match the true label. The current weight vector and the incoming input therefore determine the prediction, while the later label reveals whether that prediction was correct.

How do the current weight vector and input produce a prediction, and how is that prediction compared with the revealed label?

What information arrives on each round, and in what order does the Perceptron use the input, predict, receive the label, and possibly update?

When the Algorithm Converges

For separable data, the Perceptron converges within at most (RB)^{^2} iterations. The quantity R is the maximum norm of the feature vectors xi. The quantity B is the minimum norm of a vector w satisfying yi〈w, xi〉 ≥ 1 for every training example.

The stopping condition and the convergence statement describe the same successful outcome from two views. Algorithmically, the Perceptron stops when no example satisfies yi〈w(t), xi〉 ≤ 0. Equivalently, every training example then satisfies yi〈w(t), xi〉 > 0.

How are the input-radius quantity R, the separating quantity B, and the finite iteration guarantee connected?

Mistakes to Catch

Common mistake
Updating when the condition is not satisfied.
What it looks like
Changing the vector even though every example has yi〈w(t), xi〉 > 0.
Why it fails
The Perceptron updates only when some example satisfies yi〈w(t), xi〉 ≤ 0.
Do this instead
Check the inequality first, and stop if no example satisfies it.
Common mistake
Adding xi instead of yi xi.
What it looks like
```
Using w(t+1) = w(t) + xi.
```
Why it fails
The label determines the signed contribution of the selected example.
Do this instead
Use w(t+1) = w(t) + yi xi for the same selected index i.
Common mistake
Stopping immediately after an update.
What it looks like
Outputting w(t+1) without checking the examples again.
Why it fails
An update changes the current vector but does not establish that all examples now satisfy the positive condition.
Do this instead
Return to the checking step after every update.
Common mistake
Using the true label before making an online prediction.
What it looks like
Treating yt as available when computing pt.
Why it fails
In the online sequence, xt arrives first, the learner predicts, and yt is revealed afterward.
Do this instead
Compute pt from w(t) and xt, then use yt as feedback.

Limits of General Guarantees

The convergence guarantee for separable training data should not be confused with a finite mistake guarantee for every possible online sequence in the stated class. When the dimension d is at least 2, the Littlestone dimension is infinite, so few-mistake guarantees are unavailable for that class.

The source attributes this infinite Littlestone dimension to the density of the real numbers. It describes a shattered tree built from vectors including (1/2, 1, 0, ..., 0), (1/4, 1, 0, ..., 0), and (3/4, 1, 0, ..., 0). The hypotheses use parameter vectors of the form (-1, a, 0, ..., 0), where a ranges over [0, 1]. This construction supports the conclusion that no finite mistake bound applies generally when d is at least 2.

Practice Check

EASY

A Perceptron currently has w(t) = (2, 1). A selected example has xi = (1, -1) and yi = 1. Decide whether an update occurs. If it does, calculate w(t+1). Then state what the learner must do after this update.

Hints

First calculate 〈w(t), xi〉.
Multiply the result by yi and compare it with zero.
If an update occurs, add yi xi to w(t).
The learner checks again after updating.

Your attempt (not saved)

What do you think happens?

On an online round, the learner has received xt but has not yet received yt. Can it determine whether its prediction is a mistake?

Yes, because xt is enough to reveal the true label.
No, because the true label is revealed only after the prediction.
Only if the current weight vector is zero.

Reveal answer

Answer:

No, because the true label is revealed only after the prediction.

The Perceptron predicts from w(t) and xt first. It can evaluate whether a mistake occurred only after yt is revealed.

Key Takeaways

1
The Perceptron begins with a zero weight vector and checks whether any example satisfies yi〈w(t), xi〉 ≤ 0.
2
When such an example is found, the update is w(t+1) = w(t) + yi xi using the selected example's label and input.
3
The algorithm checks again after an update and stops only when every example satisfies yi〈w(t), xi〉 > 0.
4
For separable data, convergence occurs within at most (RB)^{^2} iterations, with R defined from the feature-vector norms and B from the separating-vector condition.
5
In online learning, the learner receives xt, predicts using sign(〈w(t), xt〉), then receives yt and checks for a mistake; when d is at least 2, infinite Littlestone dimension prevents a finite general mistake guarantee.

At a glance

The Perceptron alternates between checking examples and updating its weight vector.
An update occurs exactly when some example satisfies yi〈w(t), xi〉 ≤ 0, and the update adds yi xi.
Online prediction uses the current weights and input before the true label is revealed.
For separable data, the algorithm converges within at most (RB)^{^2} iterations.
When d is at least 2, infinite Littlestone dimension means that no finite mistake guarantee applies to every sequence in the stated class.

More concepts starting with P