A recursive method for the investigation of the linear separability of two sets

摘要

A recursive method for finding a hyperplane separating two given finite sets X1 and X2 in Euclidean space En is presented. It is unknown a priori if these two sets are linearly separable. According to the proposed method, a certain sequence (ai)i = 1m of nonzero vectors in En + 1 is generated, where m denotes the number of elements in the set X = X1 ∪ X2. If the sets X1 and X2 are linearly separable, then each of the members ai determines a hyperplane Hi ⊂ En separating the subsets Xji = XϵXj:XϵXqq = 1i, j = 1, 2, of the set X = xii = 1m, where (Xi)i = 1m denotes a sequence obtained by arbitrary ordering of X. Thus, to get the information as to whether the considered sets are linearly separable, it is sufficient to check if each of the hyperplanes Hi separates the sets X1i and X2i. If this is the case, then Hm separates X1 and X2. In the opposite case, the procedure of generation of the sequence (ai)i = 1m is stopped when any hyperplane Hi does not separate the sets X1i and X2i. Index i of the recently generated vector ai informs us as to how far the realization of the method is advanced.