Norbert Klasner:

Lernen aus fehlerhafter oder unvollständiger Information

Die klassischen Lernmodelle, wie Valiants PAC Lernmodell, Angluins query Lernmodell und Littlestones on-line Lernmodell, verlangen, daß die Information, die der Lerner bzw. der Lernalgorithmus erhält, sowohl fehlerfrei als auch vollständig ist. Die Annahme der Fehlerfreiheit und Vollständigkeit der Information ist im allgemeinen jedoch unrealistisch.

Fehler in der Information können zum Beispiel durch Meßungenauigkeiten, Übertragungsfehler oder Sabotage auftreten. Wenn sich Lernalgorithmen auf exakte Information verlassen, können in ungünstigen Fällen bereits kleine "Rundungsfehler" große Wirkung erzielen.

In dieser Arbeit wird gezeigt, wie ein Lernalgorithmus, der fehlerfreie Information benötigt, in einen fehlertoleranten Lernalgorithmus verwandelt werden kann. Dieses geschieht durch "virtuelles" Entfernen der Fehler.

Information tritt oft auch unvollständig auf, da bestimmte Teilinformationen gar nicht oder nur durch enormen Aufwand oder Risiko zu ermitteln sind.

Betrachtet man beispielsweise ein sich zeitlich änderndes System, in dem man zu jedem Zeitpunkt nur eine echte Teilmenge aller Attribute messen kann (z.B. weil nur eine begrenzte Anzahl von Sensoren vorhanden ist), muß man sich mit unvollständiger Information begnügen. Hier hat der Lerner die Möglichkeit, die gemessenen Attribute selber auszuwählen und kann von Zeit zu Zeit die Auswahl dieser Attribute verändern. Der Lerner muß also bei "ausgeblendeten Attributen" lernen. Ein Lernmodell, welches das PAC Lernmodell entsprechend erweitert, ist das restricted-focus-of-attention (RFA) Lernmodell von Ben-David und Dichterman. In dieser Arbeit untersuchen wir das Lernen von Entscheidungslisten in diesem Modell.

Eine Erweiterung von Angluins query Lernmodell zum exakten Lernen Boolescher Funktionen bei unvollständiger Information ist das unspecified attribute value (UAV) Lernmodell von Goldman, Kwek und Scott. Hier kann, je nach Fragetyp, der Lehrer bei Antworten oder der Lerner bei Fragen Attribute unspezifiziert lassen. Wir beweisen scharfe allgemeine untere Schranken bezüglich der Vapnik-Chervonenkis Dimension und der Kapazitätsfunktion beim Lernen mit Fragen (insbesondere beim Lernen im UAV Lernmodell und in Angluins query Lernmodell). Desweiteren beweisen wir das UAV Sonnenblumen Lemma und leiten mit ihm die Nichtlernbarkeit einiger Konzeptklassen, wie z.B. read-twice DNF und monotone DNF, her. Dem stellen wir Lernalgorithmen für einige populäre Konzeptklassen, wie z.B. read-once DNF gegenüber. Schließlich wird eine vollständige Hierarchie der verschiedenen Fragetypen vorgestellt.

Desweiteren wird das sogenannte kombinatorische Gruppentest Problem untersucht. Mit einem Test einer Gruppe von Personen kann man feststellen, ob sich eine infizierte Person darunter befindet (ohne deren Identität zu erfahren). Gegeben, daß k aus n Personen infiziert sind, soll mit Hilfe von möglichst wenigen Tests die Teilmenge der infizierten Personen identifiziert werden. Da stets n-1 Einzeltests ausreichen, werden niemals mehr als n-1 Tests benötigt. Für den cut-off Punkt \alpha gilt, daß n-1 Tests genau dann notwendig sind, wenn 1 > k/n >= \alpha. In diesem Fall stellen Gruppentests keinen Vorteil gegenüber Einzeltests dar. Hu, Hwang und Wang haben vermutet, daß \alpha = 1/3. In dieser Arbeit wird nun für den Fall, daß nur Einzel- oder Zweiertests erlaubt sind, gezeigt, daß der cut-off Punkt tatsächlich 1/3 ist. Der Beweis erfolgt konstruktiv mittels einer Gegenspielerstrategie.
Last update: 2/10/99. Norbert Klasner, klasner@lmi.ruhr-uni-bochum.de.

Return to list of my publications.