Empirical Risk Minimization for Linear Classifiers

The Perceptron learns by correcting one currently misclassified sample at a time.

Programming

Learning Through Corrections

The Perceptron is easiest to understand as a correction process. It begins with an all-zeros weight vector, which represents no preference for any direction. It then searches for a training example that the current vector does not classify correctly. When it finds one, that example changes the vector. When no misclassified example remains, the algorithm stops.

Key point

The central object is a sequence of weight vectors: the initial vector, followed by one new vector for each correction.

Tracing One Misclassification

To trace a Perceptron correction, follow four pieces of information: the current weight vector, the selected training example, its label, and its signed classification score. If the signed score is at most zero, the selected example is misclassified or lies at the decision boundary, so the current vector must be changed. The correction is y_i x_i, and the new vector is the old vector plus that correction.

How does a selected training example reveal the failed classification and determine the next weight vector?

Worked example

A Negative Example Supplies the Opposite Direction

Suppose the current vector is (1, 0), the selected example is x_i = (2, 1), and its label is y_i = -1. The selected example has a signed score of -2, so it requires an update.

1
Identify the failure
The signed score is -2, which is at most zero. Therefore, the current vector does not classify this selected example correctly.
2
Apply the label
The correction is y_i x_i. Because y_i is -1, the example vector is reversed: (-1)(2, 1) = (-2, -1).
3
Carry the old vector forward
The Perceptron adds the correction to the current vector instead of replacing the current vector with the correction.
4
Compute the next vector
The new vector is (1, 0) + (-2, -1) = (-1, -1).

Result

The failed example changes the vector from (1, 0) to (-1, -1). The negative label is essential because it reverses the direction of the correction.

The Update Trigger

The Perceptron has a simple decision at every iteration. It checks whether the selected training example is classified correctly by the current vector. If the signed score is at most zero, the vector changes by adding y_i x_i. If no such misclassified example remains, the Perceptron keeps the current vector and stops.

What prediction condition causes the Perceptron to keep its current weight vector versus update it?

Key point

The update is targeted, not arbitrary. The selected example contributes in the direction y_i x_i, so the next vector is guided toward classifying that particular example more correctly.

The Sequence of Corrections

Each correction produces a new member of the weight-vector sequence. The algorithm does not discard its history: it carries the current vector forward and adds the next selected example's correction. A positive label contributes x_i, while a negative label contributes the opposite direction, −x_i.

How does the current weight vector change from one iteration to the next as misclassified examples are corrected?

The sequence ends when the current vector correctly classifies every training example. At that point there is no selected misclassified example left to trigger another correction.

Why Separability Ends the Process

Separability is the condition that makes the Perceptron's stopping guarantee possible. If a suitable separating vector exists, then there is a valid target: a vector that gives every sample a positive classification score. The Perceptron theorem states that in this realizable case, the algorithm eventually stops with every sample correctly classified.

How does finding a separating weight vector cause the sequence of updates to terminate?

Reading the Iteration Bound

For separable data, the Perceptron iteration bound is T ≤ (RB)^{^2}. Here, T is the number of Perceptron updates. R represents the maximum norm of a training sample, so it captures the scale or radius of the examples. B captures the norm, or geometric size, of a separating vector. The bound says that both the sample scale and the geometry of a separator affect how many corrections may be required.

How do the example-radius quantity R and separator-norm quantity B combine to bound the number of Perceptron updates?

Formula, step by step

1
T counts the number of Perceptron updates.
2
R describes the maximum norm of a training sample.
3
B describes the norm or geometric size of a separating vector.
4
The product RB is squared to give the stated upper bound.

The proof compares two effects. Each correction increases alignment with a separating vector, while the current vector's norm is controlled using the maximum sample norm R. Combining the alignment lower bound with the norm upper bound produces the iteration limit. The bound is therefore a geometric explanation of convergence, not merely a count of training examples.

Mistakes in Update Traces

Common mistake
Updating whenever an example is examined
What it looks like
Changing the vector even when the selected example has a positive signed score
Why it fails
The Perceptron changes its vector when the selected example is misclassified, identified here by a signed score at most zero.
Do this instead
Check the signed score before applying the update.
Common mistake
Using x_i instead of y_i x_i
What it looks like
Applying the same correction direction to positive and negative examples
Why it fails
The label is part of the correction. A negative label reverses the example direction.
Do this instead
Multiply the selected example by its label before adding it.
Common mistake
Replacing the current vector with the correction
What it looks like
Setting the next vector equal to y_i x_i
Why it fails
The Perceptron carries the current vector forward and adds the correction to it.
Do this instead
Use the current vector plus y_i x_i.
Common mistake
Treating separability as optional to the stopping guarantee
What it looks like
Claiming that the theorem guarantees eventual stopping without a separating vector
Why it fails
Separability is the condition under which the convergence guarantee applies.
Do this instead
State the guarantee together with its separability condition.

Trace Practice

EASY

A current vector is (0, 1). A selected example is x_i = (1, 2) with label y_i = 1. Its signed score is -3. Determine whether an update occurs, calculate the correction, and find the next vector.

Hints

A signed score at most zero triggers an update.
Compute y_i x_i before adding it to the current vector.
Keep the current vector; do not replace it with the correction.

Your attempt (not saved)

Worked example

Practice Solution

Use the current vector (0, 1), example x_i = (1, 2), label y_i = 1, and signed score -3.

1
Check the trigger
The score is -3, which is at most zero, so the Perceptron updates.
2
Calculate the correction
Because the label is 1, y_i x_i = (1, 2).
3
Add to the current vector
The next vector is (0, 1) + (1, 2) = (1, 3).

Result

The update occurs, and the next weight vector is (1, 3).

Key Takeaways

1
The Perceptron starts with an all-zeros vector and constructs a sequence by adding corrections.
2
A signed score at most zero causes an update for the selected example.
3
The correction is y_i x_i, so the label determines its direction.
4
Separability guarantees eventual stopping with every sample correctly classified.
5
The bound T ≤ (RB)^{^2} connects the number of updates to sample radius R and separating-vector geometry B.

At a glance

The Perceptron learns by correcting one currently misclassified sample at a time.
Each update carries forward the current vector and adds the label-aware correction y_i x_i.
Tracing the signed score, label multiplication, and vector addition reveals the source of an update.
When the data is separable, the Perceptron eventually reaches a vector that correctly classifies every sample.
The iteration bound T ≤ (RB)^{^2} reflects both the scale of the samples and the geometry of a separating vector.

More concepts starting with E