Hard-SVM
Margin measures the smallest distance from a training point to a hyperplane.
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.
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.
The closest training point is identified through the minimum of |〈w, xᵢ〉 + b|.Selecting the limiting distance
Suppose three training points have distances 4, 1.5, and 3 from a separating hyperplane. Which distance is the margin?
List the distances: The distances are 4, 1.5, and 3.
Find the minimum: The smallest distance is 1.5.
Interpret the result: The point at distance 1.5 is the closest training point, so it determines the margin.
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.
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
| Idea | What it tells us |
|---|---|
| Training separation | Whether the hyperplane separates the given training examples |
| Margin | The smallest distance from a training point to the hyperplane |
| True error | How the halfspace performs beyond the observed training set |
| Margin-based relationship | The margin provides a quantity in terms of which true error can be bounded |
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.
The Hard-SVM Optimization
minimize ‖w‖₂ subject to the classification constraint for every training example
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.
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.
Check candidate one: Reject it because at least one training example violates the required condition.
Check candidate two: Reject it for the same reason: satisfying some constraints is not enough.
Check candidate three: Keep it as feasible because every listed training example satisfies its constraint.
Apply the objective: Among feasible candidates, the Hard-SVM objective prefers the one with the smaller ‖w‖₂.
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.
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
Treating the average distance as the margin.
The margin is determined by the smallest distance.
Fix:
Locate the nearest training point and use its distance.Assuming separation alone describes robustness.
Slight perturbations may change the separation when the closest point has little room.
Fix:
Consider the margin as the available room around the closest training point.Confusing the margin with exact true error.
The margin provides a quantity in terms of which true error can be bounded; it does not directly report exact true error.
Fix:
Say that a larger margin is associated with a smaller true-error bound.Minimizing ‖w‖₂ without the constraints.
The constraints define which parameter pairs are acceptable.
Fix:
Read the constraint first, then the objective over the feasible pairs.Checking only some training examples.
Hard-SVM requires the classification constraint for every training example.
Fix:
Reject any candidate that violates even one required training-example constraint.
Check Your Understanding
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?
Reveal answer
Answer: The smallest distance, 0.9.
The margin is defined by the closest training point to the hyperplane.
Key Takeaways
- The margin is the smallest distance from a training point to the hyperplane.
- The nearest training point, rather than an average point, determines the margin.
- A larger margin provides more room for slight perturbations and is associated with a smaller bound on true error.
- Hard-SVM minimizes ‖w‖₂ only among parameter pairs satisfying the classification constraint for every training example.
- The optimization solution is transformed into normalized output parameters representing the resulting separating hyperplane.
Key Takeaways
- 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.