Concepts / Linear Programming for Separable Classification

Linear Programming for Separable Classification

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

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

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.

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

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.

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

Tracing a Failed 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.

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

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

Add to the current vector: The new vector is w′ = w + yᵢxᵢ = (2, 1) + (−1, −2) = (1, −1).

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.

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

multiply by labelsets directionadd correctionaddw = (2, 1)current vectoryᵢxᵢ = (−1, −2)labeled correctionw′ = (1, −1)updated vectorxᵢ = (1, 2)selected exampleyᵢ = −1negative label
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.

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

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

T ≤ (RB)^2

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.

combinecombinesquareRmaximum sample normRBcombined scaleT ≤ (RB)²update limitBseparator norm
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

  • Using x_i instead of y_i x_i for the correction.

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

    Fix: Compute the labeled correction y_i x_i before updating the vector.

  • Replacing the current vector with the correction.

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

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

  • Updating whenever an example is selected.

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

    Fix: Check the signed score before applying the correction.

  • Treating the bound as an exact update count.

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

    Fix: 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. The Perceptron begins with an all-zeros vector and constructs a sequence of vectors through targeted corrections.
  2. A selected example triggers an update when its signed classification score is at most zero.
  3. The update adds y_i x_i to the current vector, so the label controls the correction direction.
  4. If the data is separable, the Perceptron eventually stops with every sample correctly classified.
  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.

Key Takeaways

  • 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

  • Linear Separability
  • Perceptron Convergence
  • Classification with Weight Vectors