Concepts / Hard-SVM

Hard-SVM

Hard-SVM is concerned not only with whether a hyperplane separates the training set, but also with how far the closest training point is from that hyperplane.

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

Why Separation Needs Room

A hyperplane can separate a training set without telling us how much space lies between the training points and the boundary. That space matters. If the instances move slightly, a boundary with very little room may stop separating the classes, while a boundary with more room is more likely to continue separating them. Hard-SVM turns this idea of room into the margin.

Key point

Hard-SVM is concerned not only with whether a hyperplane separates the training set, but also with how far the closest training point is from that hyperplane.

The Closest Point Sets the Margin

The margin of a hyperplane with respect to a training set is the smallest distance from any training point to the hyperplane. The word smallest is essential: the margin is determined by the nearest training point, not by an average distance or by a typical point. If one point lies especially close to the boundary, that point limits the available room.

Rule

SeparatinghyperplaneboundaryMargindistance to nearest pointNearest trainingpointsmallest distanceAnother trainingpointlarger distancemeasure distancemeasure distancesmallest distance
Which training point is closest to the separating hyperplane, and how does its perpendicular distance determine the margin?
Worked example

Selecting the limiting distance

Suppose three training points have distances 4, 1.5, and 3 from a separating hyperplane. Which distance is the margin?

  1. 1
    List the distances

    The distances are 4, 1.5, and 3.

  2. 2
    Find the minimum

    The smallest distance is 1.5.

  3. 3
    Interpret the result

    The point at distance 1.5 is the closest training point, so it determines the margin.

Result

The margin is 1.5 in this generated example.

Why a Larger Margin Helps

A large margin means that even the closest training point is relatively far from the hyperplane. That point therefore has room to move before it reaches the boundary. More generally, if the instances are slightly perturbed, a larger gap makes it more likely that the same hyperplane will continue to separate the training set.

Small marginlittle roomLarge marginmore roomShifted pointnear boundaryShifted pointstill separatedslight perturbationslight perturbation
What happens when a training point shifts slightly, and why does a larger gap make a label change less likely?

This is a robustness argument, not a guarantee that every possible perturbation preserves separation. The claim is that a larger margin provides more room for slight changes. The closest point is the critical one because it has the least room available.

Margin and True Error

IdeaWhat it tells us
Training separationWhether the hyperplane separates the given training examples
MarginThe smallest distance from a training point to the hyperplane
True errorHow the halfspace performs beyond the observed training set
Margin-based relationshipThe margin provides a quantity in terms of which true error can be bounded

Separation, margin, and true error are related but are not identical quantities.

The margin does not directly report the exact true error of a halfspace. Instead, true error can be bounded using the margin. The important direction is that increasing the margin is associated with a smaller bound on true error. This relationship does not depend on the Euclidean dimension.

Smaller marginlarger boundTrue-error boundrelated quantityLarger marginsmaller boundassociated with a larger boundassociated with a smaller bound
How does increasing the margin affect the region of points that can be misclassified and the expected true-error bound?

The Hard-SVM Optimization

Formula, step by step
  1. 1
    The parameter pair contains w and b, which describe the hyperplane.
  2. 2
    The objective is to minimize ‖w‖₂.
  3. 3
    The constraint requires every training example to satisfy the classification requirement.
  4. 4
    The optimization chooses the smallest-norm parameters among the pairs that satisfy all of those constraints.
Candidateparametersw and bCheck every exampleclassification constraintFeasible pairall constraints holdMinimize ‖w‖₂choose among feasible pairsOptimization solutionseparating hyperplanetestall passthen optimizeselect
How does the optimization choose a separating hyperplane by minimizing parameter size while requiring every training example to satisfy the classification constraint?
Key point

The order matters: constraints first, objective second. Minimizing ‖w‖₂ without requiring the classification constraints would not express the Hard-SVM problem described here.

Why Every Example Matters

The constraint is applied to every training example because a separating hyperplane must classify the entire training set according to the required condition. It is not enough for most examples to be on the correct side. One example that violates its constraint prevents the parameter pair from being an acceptable Hard-SVM solution.

Training example 1constraint 1Feasible parameterpairsall constraints holdTraining example 2constraint 2Training example nconstraint nmust holdmust holdmust hold
How do the individual constraints for all training points combine to define valid separating hyperplanes?
Worked example

Filtering candidate parameter pairs

Imagine three candidate parameter pairs. The first violates the constraint for training example 2, the second satisfies the constraints for examples 1 and 2 but violates the constraint for example 3, and the third satisfies the constraint for all three.

  1. 1
    Check candidate one

    Reject it because at least one training example violates the required condition.

  2. 2
    Check candidate two

    Reject it for the same reason: satisfying some constraints is not enough.

  3. 3
    Check candidate three

    Keep it as feasible because every listed training example satisfies its constraint.

  4. 4
    Apply the objective

    Among feasible candidates, the Hard-SVM objective prefers the one with the smaller ‖w‖₂.

Result

The feasible set contains only parameter pairs that satisfy every training-example constraint.

Normalized Output Parameters

After solving the optimization problem, the optimization solution is transformed into the stated normalized output parameters. These parameters are the normalized representation of the separating hyperplane produced by the solution. The important interpretation is that normalization is an output step applied to the solution; it does not replace the requirement that the original solution satisfy every training-example constraint.

woptimization weightNormalizationstated rescaling stepNormalized weightoutput parameterboptimization biasNormalized biasoutput parameterinputinputproducesproduces
How are the optimization parameters transformed into normalized parameters representing the same separating hyperplane?
Best practice

When reading a Hard-SVM derivation, separate three stages: identify the feasible parameter pairs, minimize ‖w‖₂ over those pairs, and then report the normalized parameters produced from the optimization solution.

Common Reading Errors

  • Common mistake

    Treating the average distance as the margin.

    What it looks like

    Several points are far from the hyperplane, but one point is very close.

    Why it fails

    The margin is determined by the smallest distance.

    Do this instead

    Locate the nearest training point and use its distance.

  • Common mistake

    Assuming separation alone describes robustness.

    What it looks like

    A hyperplane separates the observed training examples but leaves almost no room around the closest point.

    Why it fails

    Slight perturbations may change the separation when the closest point has little room.

    Do this instead

    Consider the margin as the available room around the closest training point.

  • Common mistake

    Confusing the margin with exact true error.

    What it looks like

    Concluding that a particular margin directly equals the classifier's true error.

    Why it fails

    The margin provides a quantity in terms of which true error can be bounded; it does not directly report exact true error.

    Do this instead

    Say that a larger margin is associated with a smaller true-error bound.

  • Common mistake

    Minimizing ‖w‖₂ without the constraints.

    What it looks like

    Reading the objective but ignoring the requirement for every training example.

    Why it fails

    The constraints define which parameter pairs are acceptable.

    Do this instead

    Read the constraint first, then the objective over the feasible pairs.

  • Common mistake

    Checking only some training examples.

    What it looks like

    Accepting a candidate because it satisfies the constraint for most examples.

    Why it fails

    Hard-SVM requires the classification constraint for every training example.

    Do this instead

    Reject any candidate that violates even one required training-example constraint.

Check Your Understanding

MEDIUM

A separating hyperplane has training-point distances 2.8, 0.9, 1.7, and 4.1. Identify the margin, identify the training point that controls it, and explain why a small perturbation is most relevant for that point. Then describe the two parts of the Hard-SVM optimization: the condition that candidates must satisfy and the quantity minimized among acceptable candidates.

Hints
  • The margin uses the smallest distance.
  • The limiting point is the one associated with that smallest distance.
  • The objective is ‖w‖₂, while the constraint must hold for every training example.

What do you think happens?

Which distance determines the margin when the distances are 2.8, 0.9, 1.7, and 4.1?

  • The average distance

  • The largest distance

  • The smallest distance

  • The distance of the last-listed point

Reveal answer
Answer:

The smallest distance, 0.9.

The margin is defined by the closest training point to the hyperplane.

Key Takeaways

  1. 1
    The margin is the smallest distance from a training point to the hyperplane.
  2. 2
    The nearest training point, rather than an average point, determines the margin.
  3. 3
    A larger margin provides more room for slight perturbations and is associated with a smaller bound on true error.
  4. 4
    Hard-SVM minimizes ‖w‖₂ only among parameter pairs satisfying the classification constraint for every training example.
  5. 5
    The optimization solution is transformed into normalized output parameters representing the resulting separating hyperplane.

At a glance

  • Hard-SVM measures the room between a separating hyperplane and its closest training point.
  • The margin is the minimum distance, so the closest point controls robustness.
  • A larger margin supports more robust separation under slight perturbations and is associated with a smaller true-error bound.
  • The optimization first requires every training example to satisfy its constraint and then minimizes ‖w‖₂ among the feasible parameter pairs.
  • The resulting optimization parameters are transformed into normalized output parameters.

Related Topics

Related concepts

More concepts starting with H