Vapnik-Chervonenkis dimension of recurrent neural networks

Pascal Koiran, Eduardo D. Sontag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Most of the work on the Vapnik-Chervonenkis dimension of neural networks has been focused on feedforward networks. However, recurrent networks are also widely used in learning applications, in particular when time is a relevant parameter. This paper provides lower and upper bounds for the VC dimension of such networks. Several types of activation functions are discussed, including threshold, polynomial, piecewise-polynomial and sigmoidal functions. The bounds depend on two independent parameters: the number w of weights in the network, and the length k of the input sequence. In contrast, for feedforward networks, VC dimension bounds can be expressed as a function of w only. An important difference between recurrent and feedforward nets is that a fixed recurrent net can receive inputs of arbitrary length. Therefore we are particularly interested in the case k≫w. Ignoring multiplicative constants, the main results say roughly the following: - For architectures with activation σ = any fixed nonlinear polynomial, the VC dimension is ≈ wk. - For architectures with activation σ = any fixed piecewisepolynomial, the VC dimension is between wk and w2k. - For architectures with activation σ = H (threshold nets), the VC dimension is between w log(k/w) and min{wk log wk, w2+w log wk}. - For the standard sigmoid σ(x)=1/(1+e −x ), the VC dimension is between wk and w4k2.

Original languageEnglish (US)
Title of host publicationComputational Learning Theory - 3rd European Conference, EuroCOLT 1997, Proceedings
EditorsShai Ben-David
PublisherSpringer Verlag
Pages223-237
Number of pages15
ISBN (Print)3540626859, 9783540626855
DOIs
StatePublished - 1997
Event3rd European Conference on Computational Learning Theory, EuroCOLT 1997 - Jerusalem, Israel
Duration: Mar 17 1997Mar 19 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1208
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd European Conference on Computational Learning Theory, EuroCOLT 1997
Country/TerritoryIsrael
CityJerusalem
Period3/17/973/19/97

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Vapnik-Chervonenkis dimension of recurrent neural networks'. Together they form a unique fingerprint.

Cite this