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

pix
 
Das Siegel
Naturwissenschaften Ingenieurwissenschaften Geisteswissenschaften Medizinische Einrichtungen Zentrale Einrichtungen
pix
 
pix Lehrstuhl Mathematik & Informatik
Identification Criteria and Lower Bounds for Perceptron-Like Learning Rules
 
 
 
Unser Angebot: Mitarbeiter | Forschung | Lehre   
pix
Startseite » Mitarbeiter » M. Schmitt » Identification Criteria and Lower Bounds for Perceptron-Like Learning Rules

pix pix Identification Criteria and Lower Bounds for Perceptron-Like Learning Rules
Perceptron-like learning rules are known to require exponentially many correction steps in order to identify Boolean threshold functions exactly. We introduce criteria that are weaker than exact identification and investigate whether learning becomes significantly faster if exact identification is replaced by one of these criteria: PAC identification, order identification, and sign identification. PAC identification is based on the learning paradigm introduced by Valiant and known to be easier than exact identification. Order identification uses the fact that each threshold function induces an ordering relation on the input variables which can be represented by weights of linear size. Sign identification is based on a property of threshold functions known as unateness and requires only weights of constant size. We show that Perceptron-like learning rules cannot satisfy these criteria when the number of correction steps is to be bounded by a polynomial. We also present an exponential lower bound for order identification with the learning rules introduced by Littlestone. Our results show that efficiency imposes severe restrictions on what can be learned with local learning rules.

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