DIMACS TR: 96-44
Polynomial Bounds for VC Dimension of Sigmoidal and
General Pfaffian Neural Networks
Authors: Marek Karpinski, Angus Macintyre
ABSTRACT
We introduce a new method for proving explicit upper bounds on the
VC Dimension of general functional basis networks, and prove as an
application, for the first time, that the VC Dimension of analog
neural networks with the sigmoidal activation function
$\sigma(y) = 1/1+e^{-y}$ is bounded by a quadratic polynomial
$O((lm)^2)$ in both the number $l$ of programmable parameters, and
the number $m$ of nodes. The proof method of this paper generalizes
to much wider class of Pfaffian activation functions and formulas,
and gives also for the first time polynomial bounds on their VC
Dimension. We present also some other applications of our method.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-44.ps.gz
DIMACS Home Page