*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 16
Donnerstag, 21.09.2000, 16.00–16.20 Uhr, WIL C 307

Entschiedenes Lernen

Frank Stephan, Universität Heidelberg, Mathematisches Institut

Osherson, Stob und Weinstein (1986) nannten einen Lerner “entschieden” wenn er nie zu einer einmal verworfenen Hypothese zurückkehrt. Sie fragten, ob im Modell des Lernens von positiven Daten ein entschiedener Lerner genausoviel lernen kann wie ein Lerner, der beliebig oft zu verworfenen Hypothesen zurückkehren darf.

Die Induktive Inferenz kennt hierbei zwei wesentliche Konvergenzkriterien: das Lernen im Limes (Ex), wo der Lerner nur endlich oft seine Hypothese wechselt, und das verhaltenskorrekte Lernen (BC), wo der Lerner die Hypotheses unendlich oft ändern darf - in beiden Fällen muss der Lerner jedoch fast immer eine korrekte Hypothese ausgeben, die ein Programm darstellt, welches die zu lernende Sprache aufzählt.

1994 zeigten Fulk, Jain und Osherson, dass es Klassen von Sprachen gibt, welche von einem verhaltenskorrekten Lerner, aber von keinem entschiedenen verhaltenskorrekten Lerner gelernt werden.

Gemeinsam mit Baliga, Case und Merkle zeigte der Vortragende, dass ein paralleles Ergebnis für das Lernen im Limes gilt: Es gibt eine Ex-lernbare Klasse, die von keinem entschiedenen Ex-Lerner und auch von keinem entschiedenen BC-Lerner gelernt wird. Andererseits gibt es jedoch zu jeder Ex-lernbaren Klasse einen Lerner, der zu einer verworfenen Hypothese höchstens einmal zurückkehrt.