TR available - classification of points in general position

[Eduardo Sontag]

SHATTERING ALL SETS OF k POINTS IN GENERAL POSITION REQUIRES (k-1)/2 PARAMETERS

	Rutgers Center for Systems and Control (SYCON) Report 96-01
			    Eduardo D. Sontag
		Department of Mathematics, Rutgers University

The generalization capabilities of neural networks are often quantified in
terms of the maximal number of possible binary classifications that could be
obtained, by means of weight assignments, on any given set of input patterns.
The Vapnik-Chervonenkis (VC) dimension is the size of the largest set of
inputs that can be shattered (i.e, arbitrary binary labeling is possible).
Recent results show that the VC dimension grows at least as fast as the square
n**2 of the number of adjustable weights n in the net, and this number might
grow as fast as n**4.  These results are quite pessimistic, since they imply
that the number of samples required for reliable generalization, in the sense
of PAC learning, is very high.

On the other hand, it is conceivable that those sets of input patterns which
can be shattered are all in some sense ``special'' and that if we ask instead,
as done in the classical literature in pattern recognition, for the shattering
of all sets in ``general position,'' then an upper bound of O(n) might hold.

This paper shows a linear upper bound for arbitrary sigmoidal (as well as
threshold) neural nets, proving that in that sense the classical results can
be recovered in a strong sense (up to a factor of two).  Specifically, for
classes of concepts defined by certain classes of analytic functions depending
on n parameters, it is shown that there are nonempty open sets of samples of
length 2n+2 which cannot be shattered.

============================================================================
The paper is available starting from Eduardo Sontag's WWW HomePage at URL:

		http://www.math.rutgers.edu/~sontag/

(follow links to FTP archive, file generic-vc.ps.gz)

or directly via anonymous FTP:

   ftp math.rutgers.edu
   login: anonymous
   cd pub/sontag
   bin
   get generic-vc.ps.gz

Once file is retrieved, use gunzip to uncompress and then print as postscript.

============================================================================
Comments welcome.