linear separability

[Tal Grossman]

The issue of verifying whether  a given set of vectors is linearly
separable or not was discussed time and again in this forum,
and it is certainly very interesting for many of us.
I will therefore remind here a few old refs. and add one
(hopefully relevant) insight and one new (surely relevant)
reference.

The basic geometrical approach is that of the convex hulls of the
two classes: if their intersection is non empty, then the two
sets are not linearly separable (and vice versa). This method is
really old (the Highleyman paper). Related methods can be found in
Lewis and Coates, "Threshold Logic" (Wiley 1967).
In terms of computational complexity these methods are not any
better than linear programming.

About the idea of using the distances among the vectors:
I suggest the following simple experiment -
For large N (say 100), create P random, N dimensional
binary vectors, and then
make a histogram of the hamming distance between all pairs.
Compare such histograms for P<2N (in this case the set is almost
always linearly separable) and for P>2N (and then it is almost
always non l.s.).
You will find no difference.  Which shows that as it is presented,
your approach can not help in verifying linear separability.

The last item is a new perceptron type learning algorithm by
Nabutovsky and Domany (Neural Computation 3 (1991) 604). It
either finds a solution (namely, a separating vector) to a given
set, or stops with a definite conclusion that the problem is
non separable.

and of course I would be glad to hear about any new idea -

Tal Grossman  (fegross at weizmann)
Electronics Dept.
Weizmann Inst. of Science
Rehovot 76100
ISRAEL