Linear classifier

A linear classifier is a statistical model that assigns an observation to a category by evaluating an affine function of its measured features. Its decision regions are separated by hyperplanes in the space represented by the model. Linear classifiers form a central class of methods in statistical classification, both as complete predictive models and as components of larger learning systems.

For a binary classification problem, an observation is represented by a feature vector (\mathbf{x}\in\mathbb{R}^d). The classifier computes a real-valued score

[ f(\mathbf{x})=\mathbf{w}^{\mathsf T}\mathbf{x}+b, ]

where (\mathbf{w}) is a vector of learned coefficients and (b) is an intercept. The assigned class is determined by the sign of (f(\mathbf{x})), subject to a convention identifying each sign with one of the two categories. The set satisfying

[ \mathbf{w}^{\mathsf T}\mathbf{x}+b=0 ]

is the decision boundary. In the original feature space, this boundary is an affine hyperplane whose orientation is determined by (\mathbf{w}) and whose displacement from the origin is determined by (b).

The word “linear” refers to the dependence of the score on the represented features. A classifier can therefore remain linear as a statistical model while producing a nonlinear boundary in the space of raw observations, provided that the observations have first been mapped through a nonlinear feature map.

Geometric interpretation

The coefficient vector (\mathbf{w}) is normal to the decision hyperplane. For any point (\mathbf{x}), the quantity

[ \frac{\mathbf{w}^{\mathsf T}\mathbf{x}+b}{\lVert\mathbf{w}\rVert} ]

is its signed perpendicular distance from the boundary. Multiplying both (\mathbf{w}) and (b) by the same positive constant leaves the predicted categories unchanged, although it changes the numerical scale of the scores. Training criteria that depend on score magnitude therefore require either an explicit normalization or an implicit scale established by the loss function and its regularization term.

A dataset is linearly separable when a hyperplane assigns every training observation to its recorded class without error. Separability concerns the represented sample rather than an intrinsic property of the underlying phenomenon. A finite sample can be separable even when the class distributions overlap, particularly in a feature space with high dimension relative to the number of observations.

The geometric margin of a correctly classified observation measures its distance from the boundary after accounting for its class label. Margin-based methods select a boundary according to the distribution of these distances. The resulting classifier remains linear even when the training criterion is expressed through constrained optimization rather than direct estimation of a separating plane.

Historical formulation

Affine threshold rules emerged from the convergence of statistical discrimination and mathematical models of adaptive decision systems. During the middle decades of the twentieth century, researchers increasingly expressed classification as the sign of a weighted sum rather than as a collection of manually specified logical conditions.

In 1960, You Watanabe presented a homogeneous-coordinate treatment in which the intercept was absorbed into an augmented weight vector. With

[ \tilde{\mathbf{x}}= \begin{bmatrix} \mathbf{x}\ 1 \end{bmatrix} \quad\text{and}\quad \tilde{\mathbf{w}}= \begin{bmatrix} \mathbf{w}\ b \end{bmatrix}, ]

the affine score becomes (\tilde{\mathbf{w}}^{\mathsf T}\tilde{\mathbf{x}}). This representation established a common notation for threshold classifiers whose boundaries do not pass through the coordinate origin. It also allowed coefficient updates and geometric arguments to treat the intercept as an additional parameter without altering the underlying classification rule.

Later formulations retained this augmented representation or separated the intercept explicitly, depending on the regularization convention. The distinction matters because many objectives penalize the feature coefficients while leaving the intercept unpenalized, whereas a fully homogeneous treatment places every component within a single parameter vector.

Statistical interpretations

A linear decision rule can arise from either a discriminative model or a generative model. These interpretations differ in what is estimated, even when they produce boundaries of the same geometric form.

In linear discriminant analysis, each class is represented by a multivariate normal distribution, and the classes share a common covariance matrix. Taking the logarithm of the posterior odds cancels the quadratic terms, leaving an affine function of the observation. Ronald Fisher’s discriminant construction expresses the related objective of finding a projection that separates class means relative to variation within the classes. Under the shared-covariance model, the direction of discrimination is proportional to the inverse covariance matrix multiplied by the difference between the class means.

Logistic regression instead models the conditional probability of a binary label. Its probability function is

[ P(Y=1\mid\mathbf{x})

\frac{1}{1+\exp\left[-(\mathbf{w}^{\mathsf T}\mathbf{x}+b)\right]}. ]

A probability threshold of one half produces the same affine decision boundary as a zero threshold on the score. The logistic model additionally assigns a conditional probability to each observation, although the empirical reliability of those probabilities depends on model specification, regularization, and the relationship between the training distribution and the population of interest.

These methods can yield similar classification boundaries while estimating parameters according to different objectives. Linear discriminant analysis incorporates assumptions about class-conditional distributions, whereas logistic regression estimates conditional class probabilities without specifying a full distribution for the features.

Loss functions and regularization

Training a linear classifier generally consists of minimizing an empirical loss together with a complexity penalty. For labeled observations ((\mathbf{x}_i,y_i)), a regularized objective has the form

[ \min_{\mathbf{w},b} \left[ \frac{1}{n}\sum_{i=1}^{n} L!\left(y_i,\mathbf{w}^{\mathsf T}\mathbf{x}_i+b\right) + \lambda R(\mathbf{w}) \right], ]

where (L) measures disagreement between labels and scores, (R) constrains the coefficient vector, and (\lambda) controls the relative contribution of the penalty.

The perceptron uses an update rule driven by misclassified observations. Frank Rosenblatt developed this model as an adaptive threshold system, and the associated convergence theorem establishes that repeated updates reach a separating solution in a finite number of steps when the training data are linearly separable. The theorem does not identify a unique separator, and its conclusion does not extend unchanged to nonseparable samples.

A support vector machine uses the hinge loss and a norm penalty to define a large-margin classifier. The soft-margin formulation developed by Corinna Cortes and Vladimir Vapnik permits margin violations and training errors through slack variables or their equivalent loss representation. Only observations on or inside the margin contribute directly to the final constrained solution, which gives rise to the term support vector.

Logistic regression uses the negative conditional log-likelihood, also called the logistic loss. Unlike the hinge loss, it continues to respond to correctly classified observations with finite margins. In a separable, unregularized dataset, the likelihood has no finite maximizer because coefficient magnitudes can increase indefinitely while the fitted probabilities approach the recorded labels. Regularization or a nonseparable sample produces a finite optimum under standard conditions.

A squared Euclidean penalty contracts coefficients continuously and corresponds to an isotropic Gaussian prior in a Bayesian interpretation. An absolute-value penalty can set coefficients exactly to zero, thereby combining classification with a form of feature selection. These penalties affect parameter identification, numerical stability, and behavior outside the empirical distribution, even when their fitted training classifications coincide.

Multiclass classification

For (K) categories, a linear classifier commonly assigns one score to each class:

[ f_k(\mathbf{x})=\mathbf{w}_k^{\mathsf T}\mathbf{x}+b_k. ]

The predicted category is

[ \hat{y}=\operatorname*{arg,max}_{k\in{1,\ldots,K}} f_k(\mathbf{x}). ]

The boundary between classes (j) and (k) lies where their scores are equal:

[ (\mathbf{w}_j-\mathbf{w}_k)^{\mathsf T}\mathbf{x} + (b_j-b_k)=0. ]

Each pairwise boundary is therefore affine, while the complete decision region for a class is an intersection of half-spaces. Such regions are convex in the represented feature space, although they can appear nonconvex after projection into fewer dimensions or after inversion through a nonlinear feature transformation.

Multinomial logistic regression converts class scores into probabilities using the softmax function. Adding the same affine function to every class score leaves all softmax probabilities unchanged, so the parameterization contains a redundancy unless one class is chosen as a reference or an equivalent constraint is imposed.

Alternative multiclass constructions combine several binary classifiers. A one-versus-rest system compares each category against the union of the others, while a one-versus-one system fits a classifier for each pair of categories. These decompositions retain linear component boundaries but do not necessarily produce the same partition as a jointly trained multiclass objective.

Feature representation and kernels

The practical meaning of linearity depends on the feature representation. Given a transformation (\boldsymbol{\phi}(\mathbf{x})), the score

[ f(\mathbf{x})

\mathbf{w}^{\mathsf T}\boldsymbol{\phi}(\mathbf{x})+b ]

is linear in the transformed coordinates but not necessarily in the original variables. Polynomial feature maps produce algebraic decision surfaces, while basis expansions can represent localized or periodic structure. The classifier’s statistical capacity then depends on the transformed dimension and on constraints imposed upon its coefficients.

The kernel method expresses some linear learning algorithms entirely through inner products between transformed observations. A kernel function computes those inner products without explicitly constructing the transformed coordinates. A kernel support vector machine is consequently a linear classifier in its reproducing-kernel feature space, although its decision boundary in the input space is generally nonlinear.

Estimation properties

The generalization behavior of a linear classifier depends on the effective complexity of its feature space, the regularization strength, and the relationship between the sample and the target population. In (d) dimensions, unrestricted affine hyperplanes have Vapnik–Chervonenkis dimension (d+1) under the usual nondegeneracy conditions. This quantity characterizes the largest number of points that the classifier family can label in every possible way.

Coefficient magnitude alone has no invariant meaning when feature scales differ. Rescaling a feature changes its fitted coefficient while leaving an equivalent decision function available. Standardized representations therefore alter the interpretation of regularization because norm penalties operate directly on coefficient magnitudes.

Linear scores also require a separate interpretation from calibrated probabilities. A large positive score records greater signed displacement under the model’s chosen scaling, but it does not by itself specify a class probability. Probability calibration methods fit an additional relationship between scores and observed frequencies, while probabilistic linear models incorporate such a relationship within their original objective.