Concepts / Empirical Risk Minimization for Linear Classifiers

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.

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.

evaluatesproducestriggersadds toCurrent vectorw_tSelected example(x_i, y_i)Signed scoreat most 0Correctiony_i x_iUpdated vectorw_t + y_i x_i
How does a selected training example reveal the failed classification and determine the next weight vector?

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.

Identify the failure: The signed score is -2, which is at most zero. Therefore, the current vector does not classify this selected example correctly.

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).

Carry the old vector forward: The Perceptron adds the correction to the current vector instead of replacing the current vector with the correction.

Compute the next vector: The new vector is (1, 0) + (-2, -1) = (-1, -1).

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.

evaluateyesnoInspect example(x_i, y_i)Signed scoreat most 0?Add y_i x_ichange vectorCurrent vectorkeep and stop if none fail
What prediction condition causes the Perceptron to keep its current weight vector versus update it?

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.

correctioncorrectioncorrections continuew_0all zerosw_1w_0 + y_i x_iw_2w_1 + y_j x_jw_Tno misclassified sample
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.

triggereventually reachesremoves triggerMisclassifiedsamplesat least one remainsPerceptron updatesadd y_i x_iSeparating vectorpositive score for everysampleStopno misclassified sample
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.

combines withcombines withRmaximum sample normBseparating-vector norm(RB)^2upper bound on T
How do the example-radius quantity R and separator-norm quantity B combine to bound the number of Perceptron updates?

T ≤ (RB)^2

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

  • Updating whenever an example is examined

    The Perceptron changes its vector when the selected example is misclassified, identified here by a signed score at most zero.

    Fix: Check the signed score before applying the update.

  • Using x_i instead of y_i x_i

    The label is part of the correction. A negative label reverses the example direction.

    Fix: Multiply the selected example by its label before adding it.

  • Replacing the current vector with the correction

    The Perceptron carries the current vector forward and adds the correction to it.

    Fix: Use the current vector plus y_i x_i.

  • Treating separability as optional to the stopping guarantee

    Separability is the condition under which the convergence guarantee applies.

    Fix: 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.

Practice Solution

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

Check the trigger: The score is -3, which is at most zero, so the Perceptron updates.

Calculate the correction: Because the label is 1, y_i x_i = (1, 2).

Add to the current vector: The next vector is (0, 1) + (1, 2) = (1, 3).

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.

Key Takeaways

  • 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.