Ruhr-Universität Bochum zum Inhalt Startseite der RUB pix
Startseite UniStartseite
Überblick UniÜberblick
A-Z UniA-Z
Suche UniSuche
Kontakt UniKontakt

Das Siegel
Naturwissenschaften Ingenieurwissenschaften Geisteswissenschaften Medizinische Einrichtungen Zentrale Einrichtungen
pix Lehrstuhl Mathematik & Informatik
On the Sample Complexity for Neural Trees
Unser Angebot: Mitarbeiter | Forschung | Lehre   
Startseite » Mitarbeiter » M. Schmitt » On the Sample Complexity for Neural Trees

pix pix On the Sample Complexity for Neural Trees
A neural tree is a feedforward neural network with at most one edge outgoing from each node. We investigate the number of examples that a learning algorithm needs when using neural trees as hypothesis class. We give bounds for this sample complexity in terms of the VC dimension. We consider trees consisting of threshold, sigmoidal and linear gates. In particular, we show that the class of threshold trees and the class of sigmoidal trees on $n$ inputs both have VC dimension $\Omega(n\log n)$. This bound is  asymptotically tight for the class of threshold trees. We also present an upper bound for this class where the constants involved are considerably smaller than in a previous calculation. Finally, we argue that the VC dimension of threshold or sigmoidal trees cannot become larger by allowing the nodes to compute linear functions. This sheds some light on a recent result that exhibited neural networks with quadratic VC dimension.

Zum Seitenanfang  Seitenanfang | Diese Seite drucken
Letzte Änderung: 03.02.2003 | Ansprechpartner: Webmaster