Linear Separability

[Griff Bilbro]

The statistical mechanical theory of learning predicts  that
learning  linear  separability in the plane depends strongly
the location of samples.

I have applied theory of learning available in  the  litera-
ture  [Tishby, Levin, and Solla, IJCNN, 1989] to the problem
of learning  from  examples  the  line  that  separates  two
classes of points in the plane.

When the examples in the training set are  chosen  uniformly
in  a  unit  square bisected by the true separator, learning
(as measured by the average prediction  probability)  begins
with  the  first  example.  If the training set is chosen at
some distance from the line, even more learning occurs.   On
the  other  hand, if the training set is chosen close to the
line, almost no learning is predicted until the training set
size  reaches 5 examples, but after that learning is so fast
that it exceeds the uniform case by 15 examples.

Here learning is measured by the predictive ability  of  the
estimated  line  rather  than  its numerical precision.  The
line may be determined to more significant digits by 5 mali-
cious  points,  but  this  is not enough if the 6th point is
drawn from the same malicious  distribution.   This  doesn't
apply  to  the  case when the 6th point is drawn from a dif-
ferent distribution.

 Griff Bilbro.