linear separability

[Thomas M. Breuel]

|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.

To get a bound on the amount of work required to determined linear 
separability, observe that linear separability is easily transformed 
to a linear programming problem.