Concepts / Linear Programming for Separable Classification

Linear Programming for Separable Classification

The important question is not only which separating vector is eventually obtained. It is also how each failed classification produces the next vector.

  • Programming

Learning by Correction

The Perceptron can be understood as a correction process. It starts with an all-zeros weight vector, examines training examples, and changes its current vector only when it finds an example that is not classified correctly. Each correction is caused by a particular example, so the learning history is a sequence of weight vectors connected to the examples that produced them.

Key point

The important question is not only which separating vector is eventually obtained. It is also how each failed classification produces the next vector.

From One Vector to the Next

Let the current weight vector be w. When a selected training example is classified correctly, the Perceptron keeps w unchanged. When the selected example is misclassified, the example contributes a correction. If the example has feature vector x_i and label y_i, the correction is y_i x_i, and the next weight vector is obtained by adding that correction to the current vector.

w₀all zerosy₁x₁selected examplew₁w₀ + y₁x₁y₂x₂selected examplew₂w₁ + y₂x₂add y₁x₁causesadd y₂x₂causes
What happens to the weight vector from one correction to the next, and which selected example causes each transition?
Key point

The old vector is not discarded. The Perceptron carries it forward and adds the labeled correction to it.

The Update Trigger

For a selected example, first inspect its signed classification score. If that score is at most zero, the example is not correctly classified and an update is required. If the score is positive, the Perceptron does not change the current vector for that example.

Signed scoreselected examplePositive scorekeep wCurrent vectorunchangedScore at most zeroupdate requiredLabeled correctionadd yᵢxᵢevaluateevaluatepositiveat most zero
How does the Perceptron decide whether the selected example is correctly classified or requires an update?

Tracing a Failed Example

Worked example

A Negative Example Produces a Reversed Correction

Suppose the current vector is w = (2, 1), and the selected example has xᵢ = (1, 2) with negative label yᵢ = −1. Its signed score is at most zero, so an update is required.

  1. 1
    Identify the selected example

    The example contributes xᵢ = (1, 2), and its label is yᵢ = −1.

  2. 2
    Apply the label

    The labeled correction is yᵢxᵢ = −(1, 2) = (−1, −2). The negative label reverses the direction.

  3. 3
    Add to the current vector

    The new vector is w′ = w + yᵢxᵢ = (2, 1) + (−1, −2) = (1, −1).

  4. 4
    Locate the source of the change

    The change came from this selected misclassified example and its labeled correction. The old vector was not replaced by the example vector.

Result

The Perceptron changes (2, 1) to (1, −1) by adding the negative-label correction (−1, −2).

w = (2, 1)current vectoryᵢxᵢ = (−1, −2)labeled correctionw′ = (1, −1)updated vectorxᵢ = (1, 2)selected exampleyᵢ = −1negative labelmultiply by labelsets directionadd correctionadd
How does a selected failed example lead to a specific change in the current weight vector?

When a trace seems wrong, check three points in order: the signed score, the multiplication by the label, and the addition to the previous vector. These checks identify whether the failure came from selecting the wrong update condition, forgetting that a negative label reverses the correction, or replacing the old vector instead of carrying it forward.

Why the Process Stops

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

Misclassifiedexamplecorrection neededWeight updateadd yᵢxᵢAll samples correctseparating vector reachedselectrepeat until none remain
How does the Perceptron’s state change when misclassified examples remain, and what changes when none remain?
Key point

Separability does not mean that every intermediate vector is already correct. It means that a vector satisfying all separation constraints exists, which gives the Perceptron a valid target and supports the eventual-stopping guarantee.

Reading the Iteration Bound

Formula

Here, T is the number of Perceptron updates, R represents the maximum norm of a sample, and B represents the norm of a separating vector. The bound says that the number of updates is limited by the square of their product.

Rmaximum sample normRBcombined scaleT ≤ (RB)²update limitBseparator normcombinecombinesquare
How do the maximum sample radius R and the separating-vector norm B combine to limit the number of Perceptron updates?

The proof’s structure explains why both quantities appear. Each correction increases alignment with a separating vector w⋆, while the current Perceptron vector is controlled using the maximum sample norm R. Combining the alignment lower bound with the norm upper bound yields the iteration limit. The result is a convergence guarantee, not a claim that every data set will require exactly that many updates.

Tracing Errors Correctly

  • Common mistake

    Using x_i instead of y_i x_i for the correction.

    What it looks like

    For a negative label, adding x_i points in the wrong direction.

    Why it fails

    The label determines whether the example contributes its own direction or the opposite direction.

    Do this instead

    Compute the labeled correction y_i x_i before updating the vector.

  • Common mistake

    Replacing the current vector with the correction.

    What it looks like
    Setting w′ = y_i x_i instead of w′ = w + y_i x_i.
    Why it fails

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

    Do this instead

    Start with the previous vector and add the labeled example to it.

  • Common mistake

    Updating whenever an example is selected.

    What it looks like

    Changing w even when the selected example has a positive signed score.

    Why it fails

    An update is triggered only when the signed score is at most zero.

    Do this instead

    Check the signed score before applying the correction.

  • Common mistake

    Treating the bound as an exact update count.

    What it looks like
    Assuming T must equal (RB)^2.
    Why it fails

    The expression is an upper bound on the number of updates.

    Do this instead

    Read the inequality as T being no greater than (RB)^2.

Practice the Trace

EASY

A current vector is w = (3, 2). The selected example has x_i = (2, 1), label y_i = −1, and a signed score at most zero. Determine the labeled correction and the next weight vector. Then state which part of the trace would be wrong if the next vector were computed as w + x_i.

Hints
  • Multiply the example vector by its label first.
  • Add the resulting correction to the current vector.
  • For a negative label, compare y_i x_i with x_i.
MEDIUM

Explain in your own words why the existence of a separating vector is important for the Perceptron’s stopping guarantee. Include the roles of the current corrections and the condition that ends the process.

Hints
  • Start with the meaning of separability.
  • Connect a nonpositive score to an update.
  • Describe what it means when no misclassified example remains.

Key Takeaways

  1. 1
    The Perceptron begins with an all-zeros vector and constructs a sequence of vectors through targeted corrections.
  2. 2
    A selected example triggers an update when its signed classification score is at most zero.
  3. 3
    The update adds y_i x_i to the current vector, so the label controls the correction direction.
  4. 4
    If the data is separable, the Perceptron eventually stops with every sample correctly classified.
  5. 5
    The bound T ≤ (RB)2 uses the maximum sample norm R and the norm B of a separating vector to limit the number of updates.

At a glance

  • The Perceptron learns by correcting one currently misclassified sample at a time.
  • The update is w′ = w + y_i x_i, and the label must be included.
  • Separability provides a valid target and guarantees eventual stopping.
  • The inequality T ≤ (RB)2 bounds the number of updates using sample size geometry and separator geometry.
  • Tracing the signed score, label multiplication, and vector addition reveals why a classification update occurred.

Related Topics

Related concepts

More concepts starting with L