AG 1, AG 2, AG 3, AG 4   Info

AG Audience

-- Not specified --

Saarbrücken

Beim Algorithmischen Lernen gilt es, eine unbekannte Funktion oder
Teilmenge eines Universums - man nennt dies auch ein Konzept - zu
bestimmen, wobei das Konzept aus einer vorgegebenen Klasse derartiger
Objekte stammt. Der Lernalgorithmus erhält dazu eine Folge von
Beispielen für dies Konzept, wobei die Beispiele zufällig gemäß
einer bekannten oder unbekannten Verteilung generiert werden.
Beim exakten Lernen muß das Konzept genau bestimmt werden (Golds Modell)
- im Gegensatz zum approximierenden Lernen, bei dem nur eine
hinreichend gute Approximation des Konzeptes verlangt wird
(Valiants PAC-Model). In der Regel kann der Lernalgorithmus nicht
erkennen, wann er korrekt gelernt hat; falls dies doch möglich ist,
spricht man von finitem Lernen.

Wir stellen einen neue Ansatz vor, effiziente exakte Lernstrategien
zu entwerfen und zu analysieren. Ziel ist es, das durchschnittliche
Zeitverhalten zu minimieren. Am Beispiel des Lernens von Monomen
zeigen wir, daß eine sehr präzise Analyse des average-case Verhaltens
möglich ist und für die Praxis aussagekräftige Ergebnisse liefert.
Im Vergleich zur worst-case Komplexität ergibt sich eine exponentielle
Beschleunigung.

Für das Lernen von 1-Variable Pattern Sprachen stellen wir ein exaktes
Lernverfahren mit optimaler linearer totaler Lernzeit im Mittel vor.
Diese Konzeptklasse ist nicht finit lernbar. Unser Ansatz ermöglicht
es jedoch, average-case effiziente Lernstrategien in finite zu
transformieren, für die die Wahrscheinlichkeit, daß die Endhypothese
nicht korrekt ist, beliebig klein gehalten werden kann.


InteressentInnen sind zum Vortrag herzlich eingeladen.


Die DozentInnen des Fachbereichs Informatik


Die Kolloquiumsankündigungen können Sie auch unter folgender
Internetadresse lesen: http://www.cs.uni-sb.de/kolloquien/.

--email hidden

passcode not visible

logged in users only