A linear classifier labels an input by the side of a hyperplane on which it falls. The Fisher discriminant unit built one such hyperplane from class means and scatter matrices; the ridge regression unit fitted a linear score by least squares. Here we treat three other ways of choosing the hyperplane, each defined by a different loss: the perceptron, which only reacts to mistakes; logistic regression, which fits a probabilistic model by maximum likelihood; and the maximum-margin classifier, which chooses the separating hyperplane farthest from the data. All three are organized by one quantity, the margin.
Scores and margins
Definition 29.1.1
(Linear classifier, functional and geometric margin)
Let inputs be and labels . A linear classifier has parameters , , and , a score and prediction . For a labeled example the functional margin is , positive exactly when the example is classified correctly and strictly, and the geometric margin is . The set is the decision hyperplane.
Theorem 29.1.2
(Geometric meaning of the margin)
The Euclidean distance from to the hyperplane equals . Hence the geometric margin is the signed distance from the example to the hyperplane, positive on the correct side. It is unchanged when is multiplied by a positive constant.
Proof
(Distance to a hyperplane)
The point satisfies , so it lies on the hyperplane, and . For any on the hyperplane, , and the Cauchy–Schwarz inequality gives , so every point of the hyperplane is at least this far from . Scaling by multiplies numerator and denominator by .
The functional margin, by contrast, can be made arbitrarily large by scaling, so statements about margins must say which one is meant. In the perceptron analysis we absorb the bias by augmenting each input to and the parameters to , so that .
The perceptron
The perceptron starts from and repeatedly scans the examples in a fixed order. Whenever an example has (a mistake, counting a zero score as a mistake), it updates . It stops after a full pass with no mistake.
Concept lensAnalytic
The perceptron as a subgradient step
With margin , consider the loss . For its gradient in is , and at the vector is a subgradient. A step of size one against it is exactly the perceptron update, and for the loss is flat, so no update occurs.
Theorem 29.1.3
(Perceptron mistake bound)
Suppose for all , and there is a unit vector and with for all . Then the perceptron makes at most updates, for every scanning order, and therefore terminates with a separating hyperplane.
Proof
(Alignment grows linearly, norm grows like a square root)
Let be the parameter vector after updates, with . If the -th update uses then , so . Also, since the update was triggered by ,
so . By Cauchy–Schwarz, , which gives . Since every pass without termination makes at least one update, the number of passes is also finite.
Proof X-ray
Linear growth against square-root growth
The proof tracks two quantities along the sequence of updates. The alignment grows by at least per update; this is the only place the margin hypothesis enters. The squared norm grows by at most per update; this is the only place the perceptron rule enters, because the cross term is nonpositive precisely when the example is a mistake. The final Cauchy–Schwarz step, which uses , compares the linear lower bound with the square-root upper bound , and the two are compatible only for . Starting from makes both bounds start at zero. If updates were also made on correctly classified examples, the cross term could be positive and the norm bound would fail; if were allowed to be , the lower bound would say nothing.
The bound does not depend on the number of examples or on the dimension. If the data are not linearly separable, no such exists and the algorithm never stops.
Counterexample mode
Non-separable data: the perceptron cycles
It is tempting to believe that the perceptron always stops, since each update corrects the example that triggered it. Take the four points with label and with label . No hyperplane separates them strictly: for all four would give, from the two positive points, , and from the two negative points, . The algorithm stops only after a pass with for every example, that is, with a strictly separating hyperplane, so here it can never stop. Concretely, with augmented inputs scanned in this order from , the four updates give , , and then again, so the iterates repeat forever. The repaired statement is the theorem above: termination is guaranteed under linear separability with a positive margin .
Logistic regression
Logistic regression models with . Since , the model gives for . The negative log-likelihood of the training set is therefore
Theorem 29.1.4
(Gradient and convexity of the logistic loss)
and . Consequently
so is convex and every stationary point is a global minimizer. If the data are linearly separable, has no minimizer: as while everywhere.
The derivatives follow from the chain rule: , and differentiating again gives . The Hessian formula uses . Each term is positive semidefinite and its coefficient is positive. For separable data, every term of has , so , but each , so the infimum is never attained. This is why an unregularized logistic fit on separable data diverges, and why a penalty, as in ridge regression, is added.
The maximum-margin classifier
Definition 29.1.5
(Hard-margin classifier)
For linearly separable data with both labels present, scale the parameters so that the closest example has functional margin exactly . The hard-margin problem is
A pair satisfying the constraints is feasible.
Theorem 29.1.6
(Hard margin as maximal smallest geometric margin)
For linearly separable data with both labels present, the hard-margin problem has an optimal solution, and its is unique. The optimal hyperplane has the largest possible smallest geometric margin among all separating hyperplanes, and that margin equals .
Proof
(Maximizing the margin is minimizing the norm)
Any separating hyperplane with unit normal and smallest geometric margin yields the feasible pair of norm , so the feasible set is nonempty. Conversely, a feasible has , since would require for both labels, and its smallest geometric margin is at least . Hence the largest smallest geometric margin is the reciprocal of the least feasible .
The set of for which some makes feasible is the projection of a polyhedron, hence a nonempty closed convex set. On it is strictly convex, so there is exactly one element of least norm; choose a feasible for it. The resulting hyperplane has smallest geometric margin at least , and no hyperplane can exceed that value, so the margin equals .
Worked examples
Worked example 29.1.7
(Tracing the perceptron and checking the bound)
Take four points with labels , , , , augmented to , and scan in this order. Start with .
- Point 1: , update to .
- Point 2: score , no update.
- Point 3: , update to .
- Point 4: , update to .
- Second pass: point 1 has score ; point 2 has score , update to ; points 3 and 4 have margins and .
- Third pass: all margins equal , so the algorithm stops with four updates.
For the bound take , whose margins on all four points equal , so , and . Then , which equals the number of updates made.
Worked example 29.1.8
(One gradient step of logistic regression)
Use one-dimensional inputs and , with and . All margins are and , so . The gradient is . With step size the new parameters are . The margins become and , so , a decrease. The step trades a worse margin on the first example for a much better one on the second. A fixed step size does not guarantee a decrease in general; here the loss happens to fall.
Worked example 29.1.9
(An exact hard margin)
Take with label and with label . The constraints are and . Adding gives , so and , with equality for , , which satisfies both constraints with equality. The margin is , which is half the distance between the two points, and the hyperplane is .
Common mistakes and subtle points
Common mistake
(Which margin is meant)
Functional margins change under scaling; only the geometric margin is a distance. The perceptron bound uses a unit separator and augmented inputs, so must bound the augmented norms including the constant .
Common mistake
(A zero score is a mistake)
In the perceptron update a zero score counts as a mistake, so starting from the first example always triggers an update.
Common mistake
(A small loss or a separating solution is not enough)
The logistic loss is a smooth surrogate for the zero-one error, and a small loss does not mean a small error rate or a calibrated probability. A perceptron solution is some separating hyperplane and depends on the scanning order, whereas the maximum-margin one is unique in .
Exercises
Quick check
(Let , . Find the distance from to the hyperplane, and the geometric margin if its label is .)
Compute first.
Solution · Answer
and , so the distance is . With label the geometric margin is , so the example is misclassified.
Quick check
(Augmented inputs satisfy , and a unit vector separates them with . Give the bound on the number of perceptron updates. Does it change if the scanning order is changed?)
The bound involves only and .
Solution · Answer
. The bound is valid for every scanning order, though the actual number of updates and the final hyperplane can depend on the order.
Quick check
(Compute and for and for .)
Use .
Solution · Answer
At , and . At , and , so and .
Quick check
(Points with label and with label . Find the hard-margin and the geometric margin.)
Add the two constraints.
Solution · Answer
The constraints are and , that is . Adding gives , so and the smallest norm is attained at , , which satisfies both constraints with equality. The geometric margin is .