Baeume und Lernen

Wolfgang Merkle und Frank Stephan


Das Thema des Vortrages ist es, zentrale Lernbegriffe aus der Induktiven
Inferenz mit Hilfe von Baeumen oder Familien von Baeumen zu
charakterisieren.

Die Charakterisierungen ermoeglichen neue Beweise bekannter Resultate.
Im Folgenden die wichtigsten Lernkriterien und ihre Charakterisierung:

- Vehaltenskorrektes Lernen heisst, dass eine Maschine bei sukzessiver
  Eingabe der Funktionswerte eine Folge von Indizes generiert, von denen
  fast alle die gegebene Funktion berechnen.
  Eine Klasse S von Funktionen kann genau dann von einer berechenbaren
  Maschine verhaltenskorrekt gelernt werden, wenn es eine uniform
  berechenbare Folge T0, T1, ... von Baeumen gibt, so dass jede Funktion
  in S isolierter Ast auf einem Baum Tn ist und auf keinem weiteren Baum
  Tm vorkommt.

- Lernen im Limes heisst, dass eine Maschine bei sukzessiver Eingabe der
  Funktionswerte eine Folge von Indizes generiert, von denen fast alle
  gleich einem festen Programm fuer die gesuchte Funktion sind.
  Eine Klasse S von Funktionen kann genau dann von einer berechenbaren
  Maschine im Limes gelernt werden, wenn es eine uniform berechenbare
  Folge T0, T1, ... von Baeumen gibt, so dass jede Funktion in S
  einziger unendlicher Ast auf einem Baum Tn ist und auf keinem weiteren
  Baum Tm vorkommt.

- Endliches Lernen heisst, dass die zu lernende Maschine eine gewisse
  Zeit lang das Symbol "?" und danach die einzige und richtige Hypothese
  e ausgibt.
  Eine Klasse S von Funktionen kann von einer Maschine mit Orakel K
  endlich gelernt werden genau dann wenn es einen aufzaehlbaren Baum
  gibt, so dass jede Funktion auf diesem Baum ein vollstaendig
  isolierter Ast ist.  Dabei ist f auf einem Baum vollstaendig isoliert,
  wenn es oberhalb einem gewissen sigma auf dem Baum nur noch Knoten der
  Form f(0) f(1) ... f(n) gibt.
  
- Streng-monoton verhaltenskorrektes Lernen heisst, dass bei jedem
  Hypothesenwechsel von i nach j die Funktion phi_j eine Fortsetzung von
  phi_i ist, das heisst dass phi_j(x) = phi_i(x) fuer alle x im
  Definitionsbereich von phi_i gilt.
  Eine Klasse S kann streng-monoton gelernt werden genau dann wenn sie
  die Klasse aller isolierten Aeste eines berechenbaren Baumes ist (oder
  eine Teilklasse davon).

Weiter konnte gezeigt werden, dass zusaetzliche Information beim Lernen
im Limes selbst dann hilfreich ist, wenn diese zusaetzliche Information
nur in einem Index eines Baumes besteht, auf dem die zu lernende
Funktion ein isolierter Ast ist. Es wurde eine Klasse S konstruiert, die
nur mit dieser zusaetzlichen Information, aber nicht ohne sie, im Limes
gelernt werden kann.