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.