Share Email Print

Proceedings Paper

Combinatorial geometry and V-C dimension
Author(s): Martha Alvey Carter; Mark E. Oxley
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 11 November 1996
PDF: 8 pages
Proc. SPIE 2824, Adaptive Computing: Mathematical and Physical Methods for Complex Environments, (11 November 1996); doi: 10.1117/12.258134
Show Author Affiliations
Martha Alvey Carter, National Air Intelligence Ctr. (United States)
Mark E. Oxley, Air Force Institute of Technology (United States)

Published in SPIE Proceedings Vol. 2824:
Adaptive Computing: Mathematical and Physical Methods for Complex Environments
H. John Caulfield; Su-Shing Chen, Editor(s)

© SPIE. Terms of Use
Back to Top