Combinatorial geometry and V-C dimension

Martha Alvey Carter; Mark E. Oxley

doi:10.1117/12.258134

11 November 1996 Combinatorial geometry and V-C dimension

Martha Alvey Carter, Mark E. Oxley

Proceedings Volume 2824, Adaptive Computing: Mathematical and Physical Methods for Complex Environments; (1996) https://doi.org/10.1117/12.258134
Event: SPIE's 1996 International Symposium on Optical Science, Engineering, and Instrumentation, 1996, Denver, CO, United States

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.

Citation Download Citation

Martha Alvey Carter and Mark E. Oxley "Combinatorial geometry and V-C dimension", Proc. SPIE 2824, Adaptive Computing: Mathematical and Physical Methods for Complex Environments, (11 November 1996); https://doi.org/10.1117/12.258134

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
8 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Artificial neural networks

Virtual colonoscopy

Neural networks

Binary data

Analytical research

Laser induced fluorescence

Lutetium

Show All Keywords

Keywords/Phrases

Search In:

Publication Years