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 ⊂ R d {\displaystyle X\subset \mathbb {R} ^{d}} be a set of m {\displaystyle m} points and Y ⊂ R d {\displaystyle Y\subset \mathbb {R} ^{d}} be a set of n {\displaystyle n} points in a d {\displaystyle d} -dimensional Euclidean space. X {\displaystyle X} and Y {\displaystyle Y} are linearly separable if they can be "separated" by a d {\displaystyle d} -dimensional hyperplane such that every point in X {\displaystyle X} lies on one side of the hyperplane and every point in Y {\displaystyle Y} lies on the other side. The separating hyperplane is composed of points { z ∈ R d : w ⊤ z + k = 0 } {\displaystyle \left\{z\in \mathbb {R} ^{d}:w^{\top }z+k=0\right\}} , where w ∈ R d {\displaystyle w\in \mathbb {R} ^{d}} is the normal vector to the hyperplane and k ∈ R {\displaystyle k\in \mathbb {R} } is a scalar offset. X {\displaystyle X} and Y {\displaystyle Y} are linearly separable if there exists a normal vector w {\displaystyle w} and a scalar offset k {\displaystyle k} such that either every point x ∈ X {\displaystyle x\in X} satisfies w ⊤ x + k > 0 {\displaystyle w^{\top }x+k>0} and every point y ∈ Y {\displaystyle y\in Y} satisfies w ⊤ y + k < 0 {\displaystyle w^{\top }y+k<0} , or every point x ∈ X {\displaystyle x\in X} satisfies w ⊤ x + k < 0 {\displaystyle w^{\top }x+k<0} and every point y ∈ Y {\displaystyle y\in Y} satisfies w ⊤ y + k > 0 {\displaystyle w^{\top }y+k>0} . 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.
… excerpt ends here. Continue reading the full article.
