Why maximise the margin?

Section of Support vector machines, part of Statistical learning

Type	Section
Taught in	Support vector machines
Part	Statistical learning

A large margin gives a training point some tolerance to perturbation along the normal before its classification changes. Learning theory also relates margins to the richness of a class of decision rules. A set is shattered if every binary labelling of it can be realised by the class. The VC dimension is the largest size of any shattered set. General position is not part of the definition. Affine half-spaces in \mathbb{R}^p have VC dimension p+1. Some smaller degenerate configurations fail to be shattered, which is compatible with that maximum. The four XOR corners are one such configuration: half-spaces in the plane have VC dimension 3, and those four points are not shattered.

The radius–margin bound uses a stronger requirement: each labelling of a set must be realisable with a prescribed geometric margin. State both the radius and the margin before applying it. The classical form uses full slab width \rho and enclosing-ball diameter D (Burges, 1998).

Theorem 1 (Vapnik’s radius–margin bound) For points in a fixed ball of diameter D in \mathbb{R}^p, let h be the largest number that can be shattered by affine separators while every labelling has full geometric margin at least \rho>0. The classical radius–margin bound is

h\le\min\Bigl\{\Bigl\lfloor\frac{D^2}{\rho^2}\Bigr\rfloor,\, p+1\Bigr\}.

Article: Vapnik’s radius–margin bound →

Here D/\rho is the same ratio as ball radius divided by distance from the boundary to the nearest class. This is a margin-restricted capacity statement. The ordinary class of all linear decision boundaries does not acquire a smaller VC dimension merely because one fitted boundary happens to have a large training margin.

For example, D=10, \rho=2 and p=1000 give h\le 26. Compare this with the ordinary half-space VC dimension 1001. The restriction to labellings attainable with that margin is doing the work. It motivates a preference for large margins. It does not by itself supply a numerical test-error guarantee for one observed training set.

Used in

Taught in Support vector machines
All 10 questions on Support vector machines

Used in

See also