A TEST FOR LINEAR SEPARABILITY AS APPLIED TO SELF-ORGANIZING MACHINES

Threshold logic elements are widely used in selforganizing machines, as a means of separating binary patterns into two categories. The question of whether or not two given sets of binary patterns can be separated with a single threshold logic element is of considerable interest, since training by weight adjustment can succeed only for those sets of patterns which are separable. In investigating this problem, it is convenient to consider the binary patterns as vertices of the unit n-cube. If an n-1-dimensional hyperplane can be passed through the cube in such a way that the two sets of vertices lie on opposite sides of the plane, the two sets are said to be linearly separable. The corresponding two sets of binary patterns can then, and only then, be distinguished by a single threshold logic element. This report presents a new test for linear separability. The two sets of binary patterns are combined in a matrix, and a sequence of reductions applied to this matrix to obtain a smaller matrix to be solved as a linear programming or game problem. Author