Linear separability explained

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

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

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

In simple 2D, it can also be imagined that the set of points under a linear transformation collapses into a line, on which there exists a value, k, greater than which one set of points will fall into, and lesser than which the other set of points fall.

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.

Number of linear separations

Let

T(N, K) be the number of ways to linearly separate N points (in general position) in K dimensions, then^[2] $$T(N,\; K)=\backslash left\backslash$$

Notes and References

1. Book: Boyd . Stephen . Convex Optimization . Vandenberghe . Lieven . 2004-03-08 . Cambridge University Press . 10.1017/cbo9780511804441 . 978-0-521-83378-3.
2. Book: MacKay, David . Information Theory, Inference and Learning Algorithms . 2003-09-25 . . 9780521642989 . 483 . David J. C. MacKay.