linear separability

[steve gallant]

It's not easy to tell whether a set of vertices is separable
or not even with perceptron learning, because you don't know whether the
set is nonseparable or whether you just haven't run enough iterations.
One approach is to cycle through the training examples and keep track of
the weights on the output cell.  Either perceptron learning will find a
solution (separable case) or a set of weights will reappear (nonseparable
case).  Another method is the Ho-Kashyap procedure (see Duda & Hart), but
there's still no good bound on how much work is required to determine
separability.

	Steve Gallant