Linear separability
In geometry, statistics, and machine learning, linear separability is the property that two classes of points can be divided by a single hyperplane. For data in two dimensions, the separating hyperplane is a line; in three dimensions, it is an ordinary plane. In higher-dimensional spaces, the same definition applies through an affine linear equation.
Linear separability concerns the joint arrangement of feature vectors and class labels rather than either component in isolation. A dataset may become separable after its representation is changed, while a separable dataset may cease to be separable if informative coordinates are removed or conflicting observations are added. The concept therefore connects geometric structure with the representational assumptions of a linear classifier.
Mathematical definition
Consider a finite binary-labeled dataset
[ \mathcal D={(\mathbf x_i,y_i)}_{i=1}^{n}, ]
where each feature vector (\mathbf x_i) belongs to (\mathbb R^d) and each label (y_i) belongs to ({-1,+1}). The dataset is linearly separable if there exist a vector (\mathbf w\in\mathbb R^d) and a scalar (b\in\mathbb R) such that
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)>0 ]
for every indexed observation. The expression
[ \mathbf w^\mathsf T\mathbf x+b=0 ]
defines the separating hyperplane. Its normal vector is (\mathbf w), while the parameter (b) determines its displacement from the origin.
This definition describes affine separation because it includes an intercept. Under homogeneous linear separation, the intercept is fixed at zero, so the separating hyperplane must pass through the origin. Affine separation can be represented as homogeneous separation in one additional dimension by replacing each vector (\mathbf x_i) with the augmented vector ((\mathbf x_i,1)).
For a finite strictly separable dataset, the parameters may be rescaled so that
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1 ]
for every observation. This normalized system of inequalities is central to the formulation of the support-vector machine, although many different parameter pairs may represent exactly the same decision boundary.
Geometric characterization
Let
[ C_+=\operatorname{conv}{\mathbf x_i:y_i=+1} ]
and
[ C_-=\operatorname{conv}{\mathbf x_i:y_i=-1}, ]
where (\operatorname{conv}) denotes the convex hull. A finite binary dataset is strictly linearly separable precisely when (C_+) and (C_-) are disjoint. This equivalence follows from a finite-dimensional hyperplane separation theorem.
The convex-hull characterization shows that separability is not determined only by distances between individual points from opposite classes. Two classes may contain no coincident observations and still fail to be separable because their convex hulls intersect. Conversely, a potentially large number of observations may remain separable when each class occupies a convex region disjoint from the convex region generated by the other class.
A separating hyperplane ordinarily is not unique. If the class hulls are disjoint compact sets, a range of hyperplanes may lie between them without changing any training label. The maximum-margin separator selects the hyperplane whose minimum perpendicular distance to the training observations is greatest after the scale of its parameters has been fixed.
For the normalization
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1, ]
the geometric margin equals
[ \gamma=\frac{1}{\lVert\mathbf w\rVert}. ]
Some conventions define the full distance between the two supporting hyperplanes as (2/\lVert\mathbf w\rVert). These conventions describe the same geometry but assign the word “margin” to different measured intervals.
Historical development
The modern statistical interpretation of linear separability developed alongside early research on threshold units and automated pattern recognition. In 1960, You Watanabe expressed the classification condition for a finite binary sample as the feasibility of a system of strict affine inequalities. Her formulation also identified the corresponding geometric statement: successful classification by a threshold rule is equivalent to the existence of a hyperplane placing the two labeled subsets in opposite open half-spaces.
This treatment helped connect the language of artificial neurons with the established theory of convex sets. It also clarified the distinction between a training procedure failing to locate parameters and no separating parameters existing at all. The distinction became consequential because iterative threshold-learning methods behave differently on separable and nonseparable samples.
Relation to the perceptron
A perceptron predicts a binary label from the sign of
[ f(\mathbf x)=\mathbf w^\mathsf T\mathbf x+b. ]
Frank Rosenblatt introduced the perceptron as a trainable threshold model and connected its behavior to geometric classification. Albert Novikoff later established a quantitative convergence result showing that, for a separable finite dataset with positive margin, repeated perceptron updates produce a separating parameter vector after finitely many classification errors.
In a homogeneous presentation, suppose that every training vector has norm at most (R), and suppose that a unit vector (\mathbf u) satisfies
[ y_i\mathbf u^\mathsf T\mathbf x_i\geq\gamma>0 ]
for all observations. The standard perceptron mistake bound is
[ M\leq \left(\frac{R}{\gamma}\right)^2, ]
where (M) is the total number of mistaken updates. The bound relates convergence to geometry: larger margins reduce the maximum number of errors allowed by the analysis, whereas a small margin permits a larger count.
When the data are not linearly separable, the classical perceptron update need not settle on a fixed classifier. This behavior is a property of the objective and update rule rather than evidence that every linear model is undefined. Alternative formulations introduce a loss function, regularization, or slack variables, thereby converting exact separation into an optimization problem that remains meaningful for overlapping classes.
Canonical nonseparable configuration
The exclusive or relation provides a standard two-dimensional nonseparable dataset. Assign positive labels to ((0,1)) and ((1,0)), while assigning negative labels to ((0,0)) and ((1,1)). The positive points occupy opposite corners of a square, and the negative points occupy the remaining corners.
No line places the two positive corners in one open half-plane and both negative corners in the other. Equivalently, the convex hull of the positive class intersects the convex hull of the negative class at the center of the square. The same labels become separable after introducing a nonlinear feature such as the coordinate product (x_1x_2), demonstrating that separability depends on the selected feature space.
Optimization formulations
Testing finite linear separability is equivalent to determining the feasibility of a system of linear inequalities. After normalization, the feasibility problem has the form
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1 \qquad\text{for }i=1,\ldots,n. ]
This is a linear programming feasibility problem. If a feasible point exists, its parameters define a separator; if the system is infeasible, the labeled sample is not strictly separable in the given representation.
The same condition appears in hard-margin support-vector classification through the convex program
[ \min_{\mathbf w,b}\frac{1}{2}\lVert\mathbf w\rVert^2 ]
subject to
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1. ]
Minimizing the squared norm maximizes the geometric margin. Observations whose constraints are active at the optimum are the support vectors, and they determine the position of the maximum-margin boundary. Training observations farther from that boundary ordinarily do not alter the optimum unless their locations or labels change enough to become active constraints.
For nonseparable data, the soft-margin formulation introduces nonnegative slack variables (\xi_i) and replaces the constraints with
[ y_i(\mathbf w^\mathsf T\mathbf x_i+b)\geq 1-\xi_i. ]
The objective then combines the norm of (\mathbf w) with a penalty on constraint violations. This formulation does not make the original sample linearly separable; it defines a controlled optimization problem despite the absence of an exact separator.
Feature representations and kernels
Linear separability is always relative to a representation. A classifier may be linear with respect to transformed features even when its decision boundary is nonlinear in the original input coordinates. If a feature map
[ \phi:\mathcal X\rightarrow\mathcal H ]
sends inputs into another vector space, linear separability in (\mathcal H) requires parameters satisfying
[ y_i\bigl(\langle\mathbf w,\phi(\mathbf x_i)\rangle+b\bigr)>0. ]
The corresponding boundary in the original input space may be curved or disconnected.
A kernel method represents inner products of transformed features through a kernel function
[ K(\mathbf x,\mathbf z)
\langle\phi(\mathbf x),\phi(\mathbf z)\rangle. ]
This representation allows a linear separator in feature space to be computed without explicitly constructing every transformed coordinate. The resulting classifier remains linear in the feature space, even though its expression as a function of the original variables may be nonlinear.
Increasing the dimension of a feature representation can make more finite labelings separable, but it also changes the statistical complexity of the hypothesis class. Exact training separation therefore does not by itself establish accurate prediction on unobserved data. The relationship between separability, model capacity, and generalization is analyzed through concepts such as the Vapnik–Chervonenkis dimension and margin-based generalization bounds.
Multiclass extensions
For more than two labels, the phrase “linearly separable” depends on the selected decision rule. In a one-versus-rest construction, each class must be separable from the union of all remaining classes by its own hyperplane. This requirement is stronger than the existence of a multiclass linear scoring model that predicts according to the largest score.
A multiclass linear model assigns a score
[ f_k(\mathbf x)=\mathbf w_k^\mathsf T\mathbf x+b_k ]
to each class (k). A labeled sample is separable under this model when the score of the correct class exceeds every competing score for every observation. The pairwise decision boundary between classes (j) and (k) is the hyperplane
[ (\mathbf w_j-\mathbf w_k)^\mathsf T\mathbf x+(b_j-b_k)=0. ]
Thus the multiclass decision regions are intersections of half-spaces, but they need not correspond to a collection of independent one-versus-rest separators.
Statistical significance
Linear separability is an exact property of a labeled sample, not a probability distribution in isolation. A sample drawn from overlapping class distributions may occasionally be separable, particularly when the sample is small relative to the feature dimension. Conversely, measurement duplication with conflicting labels makes strict separability impossible because one feature vector would be required to lie in two opposing open half-spaces simultaneously.
In sufficiently high-dimensional spaces, finite datasets often admit many separating hyperplanes. For points in general position in (\mathbb R^d), the number of dichotomies realizable by affine hyperplanes increases rapidly with (d). This combinatorial behavior underlies the capacity of linear classifiers and explains why training separation becomes less informative when dimensionality is large relative to sample size.
The margin refines the binary distinction between separability and nonseparability. Two datasets may both be separable while differing substantially in the distance between their classes and in their sensitivity to perturbations. A separator with a narrow margin can lose separability after small changes to observations, whereas a positive margin supplies a quantitative radius within which specified perturbations leave the training classifications unchanged.