Separating Hyperplanes and the Margin

Logistic regression fits a boundary by making the observed labels probable. This lesson takes a different starting point: among all boundaries that separate the classes, prefer the one that is furthest from every observation. That single idea produces a classifier with an unusual property, which is that almost all of the data turn out to be irrelevant to it.

A hyperplane is a decision rule

In $p$ dimensions a hyperplane is the flat, $(p-1)$-dimensional set

$$\beta_0 + \beta_1 x_1 + \beta_2 x_2 + \cdots + \beta_p x_p = 0 .$$

In two dimensions that is a line, in three a plane. A point not on it makes the left-hand side either positive or negative, so a hyperplane cuts the space in two and gives a classifier for free: write

$$f(x) = \beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p$$

and predict class $+1$ when $f(x) > 0$ and class $-1$ when $f(x) < 0$. Coding the labels as $\pm 1$ makes "correctly classified" compact: the prediction is right exactly when

$$y_i f(x_i) > 0 .$$

The magnitude of $f(x)$ is informative too. A point far from the boundary has $f(x)$ far from zero, and we can be confident about it; a point close to the boundary is close to a coin flip.

Which separating hyperplane?

If the classes can be separated at all, they can usually be separated in infinitely many ways: nudge or tilt a separating line slightly and it still separates. So "find a separating hyperplane" is not yet a well-posed problem.

The maximal margin classifier resolves it. Compute the distance from every training observation to a candidate hyperplane; the smallest of those distances is the margin. Then choose the hyperplane whose margin is largest. In words, it is the mid-line of the widest slab you can push between the two classes.

Worked example

Take six observations in the plane:

$$\begin{array}{ll} \text{class } +1: & (3,3),\ (4,4),\ (3,5) \\ \text{class } -1: & (1,1),\ (0,2),\ (2,0) \end{array}$$

The maximal margin hyperplane is

$$x_1 + x_2 - 4 = 0 ,$$

and the perpendicular distance from a point to it is $|x_1 + x_2 - 4| / \sqrt{2}$. Evaluating that at each observation:

$$\begin{array}{lll} (3,3) & +1 & \sqrt{2} \approx 1.4142 \\ (4,4) & +1 & 2\sqrt{2} \approx 2.8284 \\ (3,5) & +1 & 2\sqrt{2} \approx 2.8284 \\ (1,1) & -1 & \sqrt{2} \approx 1.4142 \\ (0,2) & -1 & \sqrt{2} \approx 1.4142 \\ (2,0) & -1 & \sqrt{2} \approx 1.4142 \end{array}$$

The margin is $\sqrt{2}$, and four observations achieve it: $(3,3)$, $(1,1)$, $(0,2)$ and $(2,0)$. These are the support vectors. They lie on the edges of the slab and they hold it in place - move one and the hyperplane moves.

The other two, $(4,4)$ and $(3,5)$, sit at $2\sqrt{2}$ and are irrelevant. You may move them anywhere on their side of the slab and the fitted classifier does not change at all. Note also that the support vectors are not evenly split between the classes: one positive, three negative.

Stating it as an optimisation

The problem is written

$$\max_{\beta_0,\dots,\beta_p,\,M} M \quad\text{subject to}\quad \sum_{j=1}^{p}\beta_j^2 = 1, \qquad y_i\big(\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip}\big) \ge M \ \ \forall i .$$

The second constraint says every observation is on its correct side and at least $M$ away. The first looks like a technicality and is not. Multiplying every coefficient by any $k \neq 0$ describes the same hyperplane, so without a scale convention the parameters are not determined. Fixing the coefficient vector to unit length pins them down, and it makes $y_i(\beta_0 + \beta \cdot x_i)$ equal the actual perpendicular distance - which is what makes "maximise $M$" mean "maximise the margin".

The canonical form. An equivalent convention scales so the closest points satisfy $y_i f(x_i) = 1$. Our hyperplane becomes $\beta = (0.5, 0.5)$ with $\beta_0 = -2$, giving $\lVert\beta\rVert = 0.7071$ and a margin of $1/\lVert\beta\rVert = 1.4142$, the same $\sqrt{2}$. Maximising the margin is then minimising $\lVert\beta\rVert$, which is the form most software solves.

Two ways it fails

The classes may not be separable. Then no hyperplane satisfies the constraints with $M > 0$ and the problem simply has no solution. Real data are frequently like this, and a method that returns nothing at all is not much use.

Even when it works, it is fragile. The solution is determined entirely by the few points nearest the boundary, so it inherits their instability. Add a single $+1$ observation at $(1.6, 1.6)$, tucked in near the negative cloud, and the best achievable margin falls from $1.4142$ to $0.4243$ - a factor of more than three, from one point. Since a narrow margin is precisely what generalises poorly, demanding perfect separation is self-defeating.

Both failures point the same way: the classifier should be allowed to get a few observations wrong. That is the next lesson.

Before the quiz

Be able to classify by the sign of $f(x)$, define the margin, pick out the support vectors and say why the others do not matter, explain what the normalisation constraint is for, and name the two failure modes.