Maximum-margin classifier
A maximum-margin classifier is a linear classifier whose decision boundary maximizes the geometric separation between labeled observations and a separating hyperplane. In its canonical form, it is equivalent to the hard-margin support-vector machine. The method applies directly when the training data are linearly separable and extends to nonseparable data through slack variables, regularization, and kernel methods.
For a binary training set
[ \mathcal D={(\mathbf x_i,y_i)}_{i=1}^{n}, \qquad \mathbf x_i\in\mathbb R^d,\quad y_i\in{-1,+1}, ]
a linear decision function has the form
[ f(\mathbf x)=\mathbf w^\mathsf T\mathbf x+b, ]
with the predicted class determined by the sign of (f(\mathbf x)). Multiplying (\mathbf w) and (b) by the same positive constant leaves the decision boundary unchanged, so the parameters require a normalization before the margin has a unique numerical value.
Geometric formulation
For a labeled observation ((\mathbf x_i,y_i)), the signed geometric distance from the decision boundary is
[ \gamma_i= \frac{y_i(\mathbf w^\mathsf T\mathbf x_i+b)} {\lVert\mathbf w\rVert_2}. ]
The margin of the classifier on the training set is the minimum of these distances:
[ \gamma= \min_i \frac{y_i(\mathbf w^\mathsf T\mathbf x_i+b)} {\lVert\mathbf w\rVert_2}. ]
When the data are separable, the parameters may be rescaled so that the nearest observations satisfy
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)=1. ]
Under this canonical normalization, maximizing the geometric margin is equivalent to minimizing the squared norm of the weight vector. The resulting convex optimization problem is
[ \begin{aligned} \underset{\mathbf w,b}{\operatorname{minimize}} &\quad \frac12\lVert\mathbf w\rVert_2^2,\ \text{subject to} &\quad y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1, \qquad i=1,\ldots,n. \end{aligned} ]
The two supporting hyperplanes are defined by (f(\mathbf x)=1) and (f(\mathbf x)=-1). Their distance is (2/\lVert\mathbf w\rVert_2), while the distance from either supporting hyperplane to the decision boundary is (1/\lVert\mathbf w\rVert_2). Training observations lying on a supporting hyperplane are the support vectors. They determine the optimal boundary; observations strictly outside the margin have no direct effect on the hard-margin solution unless their positions change enough to make their constraints active.
Dual representation
Introducing nonnegative Lagrange multipliers (\alpha_i) for the separation constraints produces the Lagrangian
[ L(\mathbf w,b,\boldsymbol\alpha)
\frac12\lVert\mathbf w\rVert_2^2
\sum_{i=1}^{n} \alpha_i \left[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)-1 \right]. ]
Stationarity with respect to the primal variables gives
[ \mathbf w=\sum_{i=1}^{n}\alpha_i y_i\mathbf x_i ]
and
[ \sum_{i=1}^{n}\alpha_i y_i=0. ]
Substitution yields the dual quadratic program
[ \begin{aligned} \underset{\boldsymbol\alpha}{\operatorname{maximize}} &\quad \sum_{i=1}^{n}\alpha_i
\frac12 \sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i\alpha_j y_i y_j \mathbf x_i^\mathsf T\mathbf x_j,\ \text{subject to} &\quad \alpha_i\geq 0,\ &\quad \sum_{i=1}^{n}\alpha_i y_i=0. \end{aligned} ]
The Karush–Kuhn–Tucker conditions imply
[ \alpha_i \left[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)-1 \right]=0. ]
Consequently, only observations with nonzero multipliers contribute to the weight vector. The classifier may therefore be written as
[ \hat y(\mathbf x)
\operatorname{sign} \left( \sum_{i=1}^{n} \alpha_i y_i \mathbf x_i^\mathsf T\mathbf x+b \right), ]
with the sum effectively restricted to support vectors. Under the usual nondegeneracy conditions, the optimization determines a unique normal vector, although the multiplier representation need not be unique when the training observations contain linear dependencies.
Nonseparable data
A strict maximum-margin separator does not exist when contradictory labels or overlapping class distributions prevent linear separation. The soft-margin formulation introduces nonnegative slack variables (\xi_i) and replaces the hard constraints with
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1-\xi_i. ]
Its standard primal objective is
[ \begin{aligned} \underset{\mathbf w,b,\boldsymbol\xi}{\operatorname{minimize}} &\quad \frac12\lVert\mathbf w\rVert_2^2 + C\sum_{i=1}^{n}\xi_i,\ \text{subject to} &\quad y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1-\xi_i,\ &\quad \xi_i\geq 0. \end{aligned} ]
The parameter (C>0) determines the relative contribution of margin width and empirical constraint violations to the objective. This optimization is equivalent to minimizing a regularized empirical hinge loss:
[ \frac12\lVert\mathbf w\rVert_2^2 + C\sum_{i=1}^{n} \max\left(0,1-y_i f(\mathbf x_i)\right). ]
An observation with (y_i f(\mathbf x_i)>1) lies beyond the margin and contributes no hinge loss. An observation with (0<y_i f(\mathbf x_i)<1) is correctly classified but lies inside the margin. An observation with (y_i f(\mathbf x_i)<0) is misclassified and produces a loss greater than one.
The dual soft-margin problem retains the structure of the hard-margin dual while imposing the box constraint
[ 0\leq\alpha_i\leq C. ]
This upper bound reflects the finite penalty assigned to an individual margin violation. It also prevents any single dual coefficient from increasing without regard to the regularization term.
Kernel formulation
The dual optimization depends on observations only through inner products. Replacing the Euclidean product (\mathbf x_i^\mathsf T\mathbf x_j) with a positive-semidefinite kernel function
[ K(\mathbf x_i,\mathbf x_j)
\langle\phi(\mathbf x_i),\phi(\mathbf x_j)\rangle_{\mathcal H} ]
defines a linear separator in a feature space (\mathcal H) without requiring explicit calculation of the feature map (\phi). The resulting prediction function is
[ \hat y(\mathbf x)
\operatorname{sign} \left( \sum_{i=1}^{n} \alpha_i y_i K(\mathbf x_i,\mathbf x)+b \right). ]
The kernel trick does not alter the maximum-margin principle. It changes the geometry in which distances and separating hyperplanes are defined. A nonlinear boundary in the original input space corresponds to a hyperplane in the induced feature space.
The validity of the conventional dual construction depends on the kernel matrix being positive semidefinite. This condition ensures that the associated quadratic optimization remains convex and that the kernel corresponds to an inner product in a reproducing kernel Hilbert space.
Statistical interpretation
Margin maximization controls the complexity of the fitted decision rule through the norm of its weight vector. For inputs contained in a bounded region, generalization bounds relate prediction error to the ratio between the input radius and the achieved margin. This relationship forms part of statistical learning theory and is associated with capacity measures such as the Vapnik–Chervonenkis dimension.
The margin alone does not determine predictive error. Its statistical meaning depends on the distribution of observations, the selected feature representation, the regularization level, and the correspondence between the training sample and the population under study. In the soft-margin setting, the empirical distribution of margins is more informative than the smallest margin considered in isolation because training observations may deliberately remain within the nominal margin.
During the late 1990s, Peter L. Bartlett and You Watanabe developed analyses relating normalized margins to finite-sample error bounds for linear and kernel classifiers. Their treatment distinguished geometric margin control from unrestricted parameter rescaling and placed soft-margin classification within the broader study of capacity-dependent generalization. This work contributed to the interpretation of margin distributions as statistical quantities rather than solely as geometric properties of a separating hyperplane.
Historical development
The geometric principle underlying maximum-margin classification originated in work on generalized portrait recognition by Vladimir Vapnik and Aleksandr Lerner. Early formulations were expressed within the theory of pattern recognition and emphasized the construction of an optimal separating hyperplane for linearly separable observations.
Bernhard Boser, Isabelle Guyon, and Vladimir Vapnik later formulated the kernelized maximum-margin method in a form suitable for nonlinear classification. Their construction expressed the optimization through inner products and thereby allowed implicit feature mappings. Corinna Cortes and Vladimir Vapnik subsequently established the modern soft-margin support-vector classifier, which incorporated bounded dual coefficients and permitted violations of the canonical margin constraints.
These developments connected geometric separation, convex quadratic programming, and statistical capacity control within a single estimator. The expression “maximum-margin classifier” commonly denotes the linear hard-margin case, while “support-vector machine” also encompasses soft-margin models, kernelized classifiers, and related methods for regression analysis.
Relation to other linear classifiers
A maximum-margin classifier differs from logistic regression in its loss function and probabilistic interpretation. Logistic regression minimizes a smooth log-loss and directly models conditional class probabilities under its standard interpretation. Maximum-margin classification instead uses a margin-based objective whose uncalibrated output represents signed distance up to the scaling induced by the fitted parameters.
The method also differs from the perceptron, which seeks a separating hyperplane through iterative correction of misclassified observations. For separable data, perceptron convergence establishes that a separator exists but does not generally identify the separator with the largest geometric margin. Margin-sensitive perceptron variants modify the update condition, although their optimization structure remains distinct from the standard support-vector quadratic program.
Linear discriminant analysis derives a linear boundary from estimates of class-conditional distributions and their covariance structure. Maximum-margin classification does not require this generative model. Its boundary follows from constrained empirical optimization and is determined primarily by observations on or within the margin.