Linear Separability

Linear separability is a property of two sets of points in Euclidean space: a single hyperplane can place every point of one set on one side and every point of the other set on the opposite side. In two dimensions the separator is a straight line; in three dimensions it is a plane. The concept connects geometry with machine learning, particularly binary classification in supervised learning. It describes whether a particular kind of decision boundary exists, rather than how that boundary is learned. (web.stanford.edu)

Mathematical definition

Let a finite collection of training examples be represented by pairs $(x_i,y_i)$, where $x_i\in\mathbb{R}^{d}$ and $y_i\in\{-1,+1\}$, with both labels present. The data are strictly linearly separable if there exist a nonzero vector $w\in\mathbb{R}^{d}$ and a scalar $b\in\mathbb{R}$ such that

The expression $w^\top x$ is the standard inner product. The hyperplane $w^\top x+b=0$ divides the space into two open half-spaces, and the sign of the expression determines the predicted class. (web.stanford.edu)

Although conventionally called “linear,” the score $w^\top x+b$ is an affine function when $b\neq0$. The intercept allows the boundary to lie away from the origin. If $b=0$, the separator is homogeneous and must pass through the origin. An affine score can be represented as an inner product in one additional dimension by replacing $x$ with $(x,1)$ and $w$ with $(w,b)$. (web.stanford.edu)

Strict separation excludes observations on the boundary. Weak separation instead permits non-strict inequalities, with a nonzero normal vector; it may leave points from both classes on the hyperplane and therefore does not necessarily provide an unambiguous classifier. For finite strictly separable data, the smallest signed score is positive, so rescaling $w$ and $b$ gives the equivalent constraints

Testing these constraints is a linear-programming feasibility problem. (stanford.edu)

Convex geometry and counterexamples

For two nonempty finite point sets, strict linear separability is equivalent to their convex hulls being disjoint. A convex hull is the smallest convex set containing a set, or equivalently the collection of its convex combinations. An affine score that is positive at every point remains positive at every convex combination; consequently, intersecting hulls make strict separation impossible. Conversely, disjoint finite hulls are compact convex sets, for which a strictly separating hyperplane exists. Finiteness matters: separation results for arbitrary infinite sets require more careful distinctions between strict separation and a uniform positive gap. (stanford.edu)

A standard counterexample is exclusive OR (XOR). Assign the positive label to $(0,1)$ and $(1,0)$, and the negative label to $(0,0)$ and $(1,1)$. Each class’s convex hull is a diagonal segment of the unit square. The segments intersect at $(1/2,1/2)$, so no straight line strictly separates the classes. This is a limitation of the model’s representational capacity, not a failure of an optimization procedure. (cs.toronto.edu)

Margins and learning algorithms

Separability alone does not specify a unique boundary. The geometric margin of a separating hyperplane on a finite dataset is

where $\|w\|_2$ is the Euclidean norm. It measures the smallest perpendicular distance from an observation to the boundary and is unchanged by multiplying both parameters by a positive constant. (cs.cornell.edu)

The perceptron updates its parameters after misclassified examples. Its convergence theorem guarantees that, for a finite strictly separable dataset, repeated presentation of the examples produces a separator after finitely many updates. In the homogeneous formulation, if $\|x_i\|\leq R$ and a unit-length separator achieves margin at least $\gamma$, the number of updates is bounded by $(R/\gamma)^2$. The affine case can be handled using augmented vectors. The guarantee does not imply that the perceptron finds the largest-margin separator. (cs.cornell.edu)

A hard-margin support vector machine instead selects a maximum-margin boundary through convex optimization:

The observations that determine the boundary are called support vectors. When the data are not separable, soft-margin formulations introduce nonnegative slack variables, allowing margin violations and potentially classification errors while penalizing them. (web.stanford.edu)

Dependence on representation

Linear separability depends on the chosen features. Feature engineering can transform nonseparable inputs into a separable representation. For XOR, the map

makes the four examples separable: the score $x_1+x_2-2x_1x_2-\tfrac12$ is positive exactly at the two positive examples. It is affine in the transformed features but nonlinear in the original coordinates. This explicit score illustrates the feature-map construction. (cs.toronto.edu)

Kernel methods implement related constructions through a function $K(x,z)=\langle\phi(x),\phi(z)\rangle$, permitting algorithms to use inner products in a feature space without explicitly constructing every transformed coordinate. A kernel does not automatically ensure separability; the result depends on the representation and the labeled observations. (cs.cornell.edu)

Statistical implications

Separability has a distinctive consequence for unregularized logistic regression. Under complete separation, increasing the magnitude of a separating parameter vector drives fitted probabilities toward the observed labels. The likelihood approaches its supremum without attaining it at finite parameters, so a finite maximum-likelihood estimate does not exist. Regularization can constrain this parameter growth. (stat.cmu.edu)

Finally, separation of a training sample does not establish separation of the underlying populations or reliable generalization to unseen examples. Zero training error concerns only the observed points; performance on a separate test set addresses a different question. (courses.cs.cornell.edu)

References

1. Margins and separating hyperplanes — STATS 202web.stanford.edu
2. Convex Optimization: Geometric Problemsweb.stanford.edu
3. The Perceptroncs.cornell.edu
4. Convex Optimization — Slidesstanford.edu
5. Convex Optimizationstanford.edu
6. CSC 311: Introduction to Machine Learningcs.toronto.edu
7. Support vector machines: The linearly separable casenlp.stanford.edu
8. Machine Learning for Intelligent Systems: Mistake Boundscs.cornell.edu
9. CS4787/5777 — Lecture 18cs.cornell.edu
10. Lecture 13: Kernelscs.cornell.edu
11. Linear Classifiers and Logistic Regressionstat.cmu.edu
12. The Implicit Bias of Gradient Descent on Separable Dataarxiv.org