11 November 1996 Combinatorial geometry and V-C dimension
Author Affiliations +
Abstract
This paper shows that the Vapnik-Chervonenkis (VC) dimension of a set of functions representing a single hidden-layer, feed-forward, single binary output processor artificial neural network (ANN) can be evaluated using the characteristic (Poincare) polynomial of the implied hyperplane arrangement. This is a significant result since it lays a mathematical foundation rooted in combinatorial geometry for measuring ANN capabilities. The ANN specified above, geometrically, is a hyperplane arrangement configured to dichotomize a signed set. Since it is known that he cut- intersection of the hyperplane arrangement is a semi- lattice, then the Poincare polynomial can be used to evaluate certain geometric invariants of this semi-lattice. One of these geometric invariants is the cardinality of the resultant chamber set of the arrangements, which this paper will show is the VC dimension. Given this connection, ANN capabilities can be characterized in more general terms of geometric invariants about the hyperplane arrangements and signed set configurations. In the case of the VC dimension, the invariant about the data is simply the cardinality of the set independent of the coloring or the geometric arrangement. Hence, VC dimension assumes a worst-case data configuration even though the requirements of an ANN architecture could vary dependent on the coloring and arrangement. With this relationship established between ANNs and combinatorial geometry, alternative geometric invariants can be investigated pacing the way for improving the capabilities and designs of ANN architectures for mathematical and physical systems.
© (1996) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Martha Alvey Carter, Mark E. Oxley, "Combinatorial geometry and V-C dimension", Proc. SPIE 2824, Adaptive Computing: Mathematical and Physical Methods for Complex Environments, (11 November 1996); doi: 10.1117/12.258134; https://doi.org/10.1117/12.258134
PROCEEDINGS
8 PAGES


SHARE
Back to Top