ML6.4 · LESSON 4 OF 6

Margins

Compare nearest-neighbor, naive Bayes and margin-based predictions using their actual assumptions.

THE IDEA

Many lines separate the data. Which one?

A linear classifier scores a point with f(x) = w·x + b and predicts the sign. For separable data there are infinitely many lines that get every training point right. A line that scrapes past one point will probably misclassify a slightly different point from the same source. The maximum-margin idea picks the line with the widest empty street around it.

Write the street edges as the planes w·x + b = +1 and w·x + b = −1. The distance between them is 2/‖w‖. For example w = (3, 4) has norm 5, so the street is 0.4 wide. A short w means a wide street, so "widest street" and "smallest ‖w‖ that still keeps every point outside" are the same goal. This formula assumes the edges sit at ±1 exactly.

Move the line, watch the street

Below you set the direction, the offset and the half-width h of the street yourself (so w = u/h, with u the unit normal). Points on the wrong side get a red ring; points inside the street get red dashes. Hinge loss charges each point max(0, 1 − y·f(x)): 0 if it is on its side and beyond the street, between 0 and 1 inside the street, above 1 if misclassified. Try to get the loss to 0 with the widest street you can.

Solid purple: the centre line. Dashed purple: the street edges, a distance h either side. Red ring: wrong side. Red dashes: inside the street. Click a point to delete it.

angle of the normal (degrees) = 90offset of the centre line = 4street half-width h = 1.5

w = (4.08e-17, 0.6667), b = -2.6667
||w|| = 0.6667 (= 1/h)
street width 2/||w|| = 3

wrong side: 2 | inside the street: 4
hinge loss (sum): 2.8667

C 0.5||w||² + C·hinge = 3.0889

Support vectors on the best street (type a number)

Show the best street to compare. Green rings mark support vectors. Click any point to delete it, and watch whether the best street moves.

Only the points on the edge matter

The best street for this data is 4.3902 wide and is held in place by just 3 points, the support vectors, which sit exactly on the edges. Delete any of the other 11 points and the best street does not move at all. Delete a support vector and the street can widen. That is why a trained SVM keeps only its support vectors, and why a far-away point does not influence the boundary.

Predict first. You delete a training point that is far from the street, on the correct side. What happens to the maximum-margin line?

Real data is rarely separable. The soft-margin SVM minimises ½‖w‖² + C · Σ hinge: a wide street (small ‖w‖) against violations (hinge). A large C punishes violations and gives a narrow street that bends to the points; a small C accepts some violations for a wider street. Change C in the lab to see the objective trade off.

The common mistake

Chapter context

Different model families turn different notions of similarity into predictions. A geometric distance, a conditional-independence assumption and a kernel are distinct modeling decisions rather than variations of the same formula.

TRY IT YOURSELF

Part 1. Do it on the plot

Start from the flat line that makes 2 mistakes. Every task is computed from the line and the points you leave on the plot.

Solid purple: the centre line. Dashed purple: the street edges, a distance h either side. Red ring: wrong side. Red dashes: inside the street. Click a point to delete it.

angle of the normal (degrees) = 90offset of the centre line = 4street half-width h = 1.5

w = (4.08e-17, 0.6667), b = -2.6667
||w|| = 0.6667 (= 1/h)
street width 2/||w|| = 3

wrong side: 2 | inside the street: 4
hinge loss (sum): 2.8667

C 0.5||w||² + C·hinge = 3.0889

Support vectors on the best street (type a number)

To do: Separate the classes: every point on its own side of the centre line
To do: Reach zero hinge loss: no point inside the street or on the wrong side
To do: Keep hinge loss at zero while making the street at least 90% as wide as the best possible
To do: Type how many support vectors the widest street has
To do: Delete some points that are not support vectors and see the best street stay the same width
To do: Delete one support vector and watch the best street get wider

Part 2. Do it in code

hinge_loss(w, b, X, y) returns the sum over rows of max(0, 1 - y_i * (w . x_i + b)). Labels y are +1 or -1.
margin_width(w) returns 2 / ||w||, the distance between the planes w.x + b = +1 and w.x + b = -1.
support_mask(w, b, X, y, tol=1e-6) returns a boolean array that is True for rows with |y_i * (w . x_i + b) - 1| < tol.
svm_objective(w, b, X, y, C) returns 0.5 * ||w||^2 + C * hinge_loss.

import numpy as np

def hinge_loss(w, b, X, y):
    pass

def margin_width(w):
    pass

def support_mask(w, b, X, y, tol=1e-6):
    pass

def svm_objective(w, b, X, y, C):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is maximizing training accuracy exactly the hard-margin objective?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

\|x-y\|_2^2=\sum_j(x_j-y_j)^2,\quad K(x,y)=\exp(-\gamma\|x-y\|^2),\;\gamma>0.

For SVM canonical boundary planes $w^Tx+b=\pm1$ , their separation is $2/\|w\|$ . A naive-Bayes posterior is proportional to $P(c)\prod_jP(x_j\mid c)$ .

A numerically convenient naive-Bayes decision rule is

\hat c=\arg\max_c\left[\log P(c)+\sum_j\log P(x_j\mid c)\right].

This avoids multiplying many small probabilities, but it does not remove the need to handle zero likelihoods or choose an appropriate feature distribution.

Worked example

For query [1,1], squared distances to [0,0], [2,1] and [3,3] are 2, 1 and 8. The nearest point is [2,1]. Separately, a canonical SVM with w=[3,4] has norm 5 and margin width 2/5=0.4.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import sqrt, isclose
q = [1,1]
points = [[0,0],[2,1],[3,3]]
distances = [sum((a-b)**2 for a,b in zip(q,p)) for p in points]
assert distances == [2,1,8]
assert distances.index(min(distances)) == 1
assert isclose(2/sqrt(3**2+4**2), .4)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Changing feature scale can change neighbors. Kernel similarity is not automatically calibrated probability. The SVM margin formula assumes a particular normalization of the separating planes.