linear separability

[Karen Huyser]

There is one Hamming-type test I know of, and that's a test for summability.
For a function of N variables to be linearly separable, it must be asummable.
To be asummable, it must be 2-asummable, 3-asummable, ... , k-asummable, ... ,
N-asummable.  Any function is k-asummable if it is not k-summable.  
2-summability is described below.  

If a boolean function is 2-summable, there exists
the following relationship between its vertices.  	   100          101
Imagine the faces (2-D subspaces) of a cube (hypercube).      0 ------ 1
Assign one-bit output values to each corner of the cube.      |        |
(If multiple-bit output, make multiple hypercubes.)           |        |
If any face of the hypercube has an assignment like that      1 ------ 0
to the left, the problem is not linearly separable.        000          001
This "exor" relation between pairs of vertices corresponds
to the function being "2-summable".  Specifically, if we add the vectors that
label the 1-corners (000 + 101 = 101) and those that label the 0-corners
(100 + 001 = 101), they add together to the same vector value (they sum in
pairs, hence 2-summable).  Similar relationships between three,
four, etc. vertices corresponds to 3-summability, 4-summability, etc.

Any function that is 2-summable is not linearly separable.  A simple test of
2-summability is to form all possible sets of four training vectors and test
for this exor condition.  In a Hamming sense, each hypercube face will be
composed of a corner, two of its nearest neighbors (one bit different),
and the diagonal.  (Note each face represents changes in only two bits.)
The test is not likely to be efficient, but it will be local.

So how can it be used for general boolean functions?  Suppose you have an 
incomplete boolean function of N variables, and that the incomplete function
can be divided into subsets each of which is a complete boolean function 
of Ki variables, where Ki < N.  (It's okay if a vertex is in more than 
one subset, but each vertex must be in some subset.)  If each such subset 
of vertices represents a subspace of fewer than nine dimensions (nine
variables), and the subset is a complete boolean function of the variables,
then the 2-summability test is also a test for linear separabilty.
If the subset fails the test, it is not linearly separable.  If it passes 
the test, it is linearly separable.  This is because 2-asummability is the 
same as complete monotonicity, which has been shown to be a necessary and 
sufficient condition for linear separability for boolean functions of fewer
than nine variables.  (See Muroga, 1971)

The 2-summability test works well only for completely specified functions.
For incomplete boolean functions, (that is, when the subset of vertices to be
tested is incomplete), this method will require filling in values
for "don't care" vertices in an attempt to prevent the augmented subset 
from becoming summable.  Again, summability tests are generally not thought
of as efficient, whereas a linear programming approach will be.

(1)  Saburo Muroga, "Threshold Logic and its Applications", Wiley, NY, 1971
   This text is full of wonderful theory about summability, monotonicity, etc.
(2)  John Hopcroft, "Synthesis of Threshold Logic Networks", Ph.D. thesis, 
   Stanford Univ., 1964.  Hopcroft discusses the relationship between convex
   hulls and linear separability in his thesis.  He uses convex hulls to
   construct a network-building algorithm you might find useful.

Karen Huyser
Electrical Engineering
Stanford University