|
NeuroCOLT
Technical Report NC-TR-00-068
VC
Dimension Bounds for Higher-Order Neurons
Michael
Schmitt
Abstract
We
investigate the sample complexity for learning using higher-order
neurons. We calculate upper and lower bounds on the Vapnik-Chervonenkis
dimension and the pseudo dimension for higher-order neurons that allow
unrestricted interactions among the input variables. In particular,
we show that the degree of interaction is irrelevant for the VC dimension
and that the individual degree of the variables plays only a minor
role. Further, our results reveal that the crucial parameters that
affect the VC dimension of higher-order neurons are the input dimension
and the maximum number of occurrences of each variable. The lower
bounds that we establish are asymptotically almost tight. In particular,
they show that the VC dimension in super-linear in the input dimension.
Bounds for higher-order neurons with sigmoidal activation function
are also derived.
Download
Compressed Postscript
|