Linear separability

In geometry, two sets of points in a two-dimensional space are linearly separable if they can be completely separated by a single line. In general, two point sets are linearly separable in n-dimensional space if they can be separated by a hyperplane.

In more mathematical terms: Let $X_{0}$ and $X_{1}$ be two sets of points in an n-dimensional space. Then $X_{0}$ and $X_{1}$ are linearly separable if there exists n+1 real numbers $w_{1},w_{2},..,w_{n},k$, such that every point $x\in X_{0}$ satisfies $\sum _{i=1}^{n}w_{i}x_{i}\geq k$ and every point $x\in X_{1}$ satisfies $\sum _{i=1}^{n}w_{i}x_{i}<k$, where $x_{i}$ is the $i$-th component of $x$.

Example

Three points in two classes ('+' and '-') are always linearly separable in two dimensions. This is illustrated by the following figure:

However, not all sets of four points are linearly separable in two dimensions. The following example would need two straight lines and thus is not linearly separable:

Linear separability of hypercubes in n dimensions

Number of linearly separable Boolean hypercubes in each dimension (sequence A000609 in the OEIS)

Dimension	Linearly separable Boolean hypercubes
2	14
3	104
4	1882
5	94572
6	15028134
7	8378070864
8	17561539552946
9	144130531453121108

Usage

Linear separability allows simple Classification in machine learning.

See also

• Vapnik–Chervonenkis dimension