|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-95-011
Classification
by Polynomial Surfaces
Martin
Anthony
London School of Economics and Political Science
Abstract
Linear threshold functions (for real and Boolean inputs) have received
much attention, for they are the component parts of many artificial
neural networks. Linear threshold functions are exactly those functions
such that the positive and negative examples are separated by a hyperplane.
One extension of this notion is to allow separators to be surfaces
whose equations are polynomials of at most a given degree (linear
separation being the degree-$1$ case). We investigate the representational
and expressive power of polynomial separators. Restricting to the
Boolean domain, by using an upper bound on the number of functions
defined on $\{0,1\}^n$ by polynomial separators having at most a given
degree, we show, as conjectured by Wang and Williams, that for almost
every Boolean function, one needs a polynomial surface of degree at
least $\left\lfloor n/2\right\rfloor$ in order to separate the negative
examples from thepositive examples. Further, we show that, for odd
$n$, at most half of all Boolean functions are realizable by a separating
surface of degree $\left\lfloor n/2\right\rfloor$. We then compute
the Vapnik-Chervonenkis dimension of the class of functions realized
by polynomial separating surfaces of at most a given degree, both
for the case of Boolean inputs and real inputs. In the case of linear
separators, the VC dimensions coincide for these two cases, but for
surfaces of higher degree, there is a strict divergence. We then use
these results on the VC dimension to quantify the sample size required
for valid generalization in Valiant's probably approximately correct
framework.
Download Compressed
Postscript
|