Concepts / Margin and Hard-SVM

Margin and Hard-SVM

Hard-SVM connects large-margin classification to a constrained optimization problem.

  • Programming
Interactive lab

Try it: Support Vector Machine: Maximum Margin

How hard-SVM picks, among all separating lines, the one whose closest training point is farthest away, which points become support vectors, and how soft-SVM trades margin for violations with λ.

How it works

  1. Hard-SVM: minimise ‖w‖ subject to y(⟨w,x⟩ + b) ≥ 1 for every point; the margin is 1/‖w‖.
  2. In 2-D the optimum is fixed by one point of each class (their perpendicular bisector) or by two points of one class and one of the other.
  3. Check every such candidate against all constraints and keep the feasible one with the largest margin; the points on the margin lines are the support vectors.
  4. Compare with the Perceptron's separator, which also separates but usually with a smaller margin.
  5. Soft-SVM: minimise λ‖(w, b)‖² + average hinge loss by SGD (step 1/(2λt)), outputting the average iterate.

Default run (3 steps): Hard-SVM: among all (w, b) with y(⟨w,x⟩ + b) ≥ 1 for every point, find the smallest ‖w‖ — equivalently the separator whose closest point is farthest away (margin 1/‖w‖). … Max margin: w = (0.435, 0.696), b = -1.783, ‖w‖ = 0.82; margin 1/‖w‖ = 1.219 (band width 2.438). Support vectors p_5, p_6, p_7 sit exactly on y(⟨w,x⟩ + b) = 1. Checked 64 candidate sets. The Perceptron's line also separates, but its closest point is only 0.271 away.

Simplified: 2-D, at most 12 points, exact candidate enumeration instead of a general QP solver. The soft-SVM SGD regularises the bias too (x is extended with a constant 1) and runs a fixed number of seeded steps.

Educational simulation

Loading the simulation…

From Separation to Optimization

Hard-SVM turns the search for a good separating hyperplane into a constrained optimization problem. The goal is not merely to find parameters that separate the classes. Among parameter pairs that satisfy the required classification constraint for every training example, Hard-SVM selects the solution associated with the largest margin by minimizing the norm of w.

Key point

The order matters: first identify which parameter pairs are acceptable through the constraint, then minimize ‖w‖₂ among those acceptable pairs.

The Closest Training Point

The closest training point is identified using the minimum value of |〈w,xᵢ〉 + b|. This minimum singles out the training example whose position is closest according to the expression used by the formulation. Because this point is the limiting point nearest the separating hyperplane, it determines the smallest separation that the classifier must maintain when considering the training data.

Training examplesall pointsClosest trainingpointminimum value|〈w,xᵢ〉 + b|one value per exampleevaluateselect minimum
How does the closest training point determine the separation relevant to the hyperplane?
Worked example

Comparing Candidate Closest Points

Suppose two training examples produce absolute values of 4 and 1 for |〈w,xᵢ〉 + b|. Which example is identified as the closest training point by the stated criterion?

  1. 1
    Evaluate the criterion

    The formulation compares the absolute values obtained from |〈w,xᵢ〉 + b| for the training examples.

  2. 2
    Take the minimum

    Between 4 and 1, the minimum is 1.

  3. 3
    Identify the point

    The example producing 1 is the closest training point according to this criterion.

Result

The training example with value 1 is the closest point under the minimum-|〈w,xᵢ〉 + b| rule.

Reading the Hard-SVM Problem

The Hard-SVM formulation has two logically different parts. Its objective is to minimize ‖w‖₂. Its constraint requires every training example to satisfy the classification condition. The objective chooses among acceptable parameter pairs; it does not define acceptability by itself.

minimizeobjective‖w‖₂size of wsubject torequirementClassificationconstraintfor every training exampleapplies toafter restricting candidatesrequires
How do the objective of minimizing the norm and the classification constraints combine in Hard-SVM?
Worked example

Choosing Between Feasible Candidates

Imagine that two parameter pairs both satisfy the classification constraint for every training example. Candidate A has ‖w‖₂ equal to 3, and Candidate B has ‖w‖₂ equal to 5. Which candidate does the Hard-SVM objective prefer?

  1. 1
    Check acceptability

    Both candidates are assumed to satisfy the constraint for every training example, so both are eligible.

  2. 2
    Compare the objective

    The objective minimizes ‖w‖₂, so compare 3 with 5.

  3. 3
    Select the smaller norm

    Candidate A has the smaller norm and is therefore preferred by the objective.

Result

Candidate A is selected among these two feasible candidates.

Why Every Example Matters

The classification constraint is applied to every training example rather than to only one representative point. Each example contributes a requirement that the parameter pair must satisfy. A parameter pair is acceptable only when all of those individual requirements hold simultaneously. The optimization then minimizes ‖w‖₂ within that jointly acceptable set.

Parameter paircandidateTraining example xᵢconstraintEvery trainingexampleall constraintsFeasible parameterpairsall requirements satisfiedtestrepeatretain if all pass
How does each training example contribute its own constraint, and what remains after all constraints are considered?
Parameter pairscandidate separatinghyperplanesConstraint for xᵢone exampleAll constraintsevery exampleFeasible parameterpairsacceptable candidatesmust satisfycombinedefines
What set of separating-hyperplane parameters satisfies all training-example constraints simultaneously?
  • Common mistake

    Checking the constraint for only one training example

    What it looks like

    A parameter pair works for one point, so it is treated as an acceptable Hard-SVM solution.

    Why it fails

    The Hard-SVM constraint must hold for every training example.

    Do this instead

    Treat each training example as contributing a requirement, then retain only parameter pairs that satisfy all requirements simultaneously.

  • Common mistake

    Treating the objective as the entire optimization problem

    What it looks like

    Choose the parameter pair with the smallest ‖w‖₂ without checking its classification constraints.

    Why it fails

    The objective chooses among acceptable pairs; it does not establish acceptability on its own.

    Do this instead

    Apply the constraint first and minimize ‖w‖₂ only within the resulting feasible set.

From Solution to Normalized Parameters

Solving the constrained optimization problem produces an optimization solution. Hard-SVM then transforms that solution into the stated normalized output parameters. The important distinction is between the parameters found while solving the optimization and the normalized parameters reported as the final separating-hyperplane description.

Optimizationsolutionselected parameter pairNormalizationstated transformationNormalized parametersfinal outputtransformproduce
How does the optimization solution become the normalized parameter output?
MEDIUM

In your own words, explain the difference between a feasible parameter pair, the optimization solution, and the normalized output parameters.

Hints
  • A feasible pair satisfies the classification constraint for every training example.
  • The optimization solution is chosen by minimizing ‖w‖₂ among feasible pairs.
  • The normalized output parameters are produced by transforming the optimization solution.

Summary

  1. 1
    The closest training point is identified by the minimum of |〈w,xᵢ〉 + b|.
  2. 2
    Hard-SVM minimizes ‖w‖₂, but only among parameter pairs satisfying the classification constraint.
  3. 3
    The constraint is applied to every training example, so acceptable pairs must satisfy all example-specific requirements simultaneously.
  4. 4
    The optimization solution is transformed into the stated normalized output parameters.
  5. 5
    The central reading strategy is constraint first, objective second.

At a glance

  • The closest training point is selected using the minimum of |〈w,xᵢ〉 + b|.
  • Hard-SVM finds a separating hyperplane through constrained optimization.
  • The constraint defines acceptable parameter pairs for every training example.
  • The objective minimizes ‖w‖₂ only within that feasible set.
  • The selected optimization solution is transformed into normalized output parameters.

More concepts starting with M