Linear separability

In Euclidean geometry, linear separability is a property of two sets of points. This is most easily visualized in two dimensions (the Euclidean plane) by thinking of one set of points as being colored blue and the other set of points as being colored red. These two sets are linearly separable if there exists at least one line in the plane with all of the blue points on one side of the line and all the red points on the other side. This idea immediately generalizes to higher-dimensional Euclidean spaces if the line is replaced by a hyperplane.

The problem of determining if a pair of sets is linearly separable and finding a separating hyperplane if they are, arises in several areas. In statistics and machine learning, classifying certain types of data is a problem for which good algorithms exist that are based on this concept.

Mathematical definition

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

Equivalently, two sets are linearly separable precisely when their respective convex hulls are disjoint (colloquially, do not overlap).

Examples

Three non-collinear points in two classes ('+' and '-') are always linearly separable in two dimensions. This is illustrated by the three examples in the following figure (the all '+' case is not shown, but is similar to the all '-' case):

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

Notice that three points which are collinear and of the form "+ ⋅⋅⋅ — ⋅⋅⋅ +" are also not linearly separable.

Linear separability of Boolean functions in n variables

A Boolean function in n variables can be thought of as an assignment of 0 or 1 to each vertex of a Boolean hypercube in n dimensions. This gives a natural division of the vertices into two sets. The Boolean function is said to be linearly separable provided these two sets of points are linearly separable. The number of distinct Boolean functions is ${\displaystyle 2^{2^{n}}}$where n is the number of variables passed into the function.[1]

Number of linearly separable Boolean functions in each dimension[2] (sequence A000609 in the OEIS)

Number of variables	Boolean functions	Linearly separable Boolean functions
2	16	14
3	256	104
4	65536	1882
5	4294967296	94572
6	18446744073709552000	15028134
7	3.402823669 ×10^38	8378070864
8	1.157920892 ×10^77	17561539552946
9	1.340780792 ×10^154	144130531453121108

Support vector machines

Main article: Support vector machine

H₁ does not separate the sets. H₂ does, but only with a small margin. H₃ separates them with the maximum margin.

Classifying data is a common task in machine learning. Suppose some data points, each belonging to one of two sets, are given and we wish to create a model that will decide which set a new data point will be in. In the case of support vector machines, a data point is viewed as a p-dimensional vector (a list of p numbers), and we want to know whether we can separate such points with a (p − 1)-dimensional hyperplane. This is called a linear classifier. There are many hyperplanes that might classify (separate) the data. One reasonable choice as the best hyperplane is the one that represents the largest separation, or margin, between the two sets. So we choose the hyperplane so that the distance from it to the nearest data point on each side is maximized. If such a hyperplane exists, it is known as the maximum-margin hyperplane and the linear classifier it defines is known as a maximum margin classifier.

More formally, given some training data ${\displaystyle {\mathcal {D}}}$, a set of n points of the form

${\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}$

where the y_i is either 1 or −1, indicating the set to which the point ${\displaystyle \mathbf {x} _{i}}$ belongs. Each ${\displaystyle \mathbf {x} _{i}}$ is a p-dimensional real vector. We want to find the maximum-margin hyperplane that divides the points having ${\displaystyle y_{i}=1}$ from those having ${\displaystyle y_{i}=-1}$. Any hyperplane can be written as the set of points ${\displaystyle \mathbf {x} }$ satisfying

${\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,}$

where ${\displaystyle \cdot }$ denotes the dot product and ${\displaystyle {\mathbf {w} }}$ the (not necessarily normalized) normal vector to the hyperplane. The parameter ${\displaystyle {\tfrac {b}{\|\mathbf {w} \|}}}$ determines the offset of the hyperplane from the origin along the normal vector ${\displaystyle {\mathbf {w} }}$.

If the training data are linearly separable, we can select two hyperplanes in such a way that they separate the data and there are no points between them, and then try to maximize their distance.

See also

• Perceptron
• Vapnik–Chervonenkis dimension

References

1. 1962-, Russell, Stuart J. (2016). Artificial intelligence a modern approach. Norvig, Peter 1956- (Third ed.). Boston. p. 766. ISBN 978-1292153964. OCLC 945899984.CS1 maint: numeric names: authors list (link)
2. Gruzling, Nicolle (2006). "Linear separability of the vertices of an n-dimensional hypercube. M.Sc Thesis". University of Northern British Columbia. Cite journal requires |journal= (help)