Database Reference
In-Depth Information
Hypothesenraumes realisieren.
Anstatt auf einzelne Varianten genauer einzugehen, wollen wir ein Verfahren
vorstellen, das beide Suchrichtungen gleichzeitig betreibt und als Ausgabe eine Re-
prasentation
aller
Hypothesen liefert, die konsistent mit der Trainingsmenge sind.
5.4.5
Versionenraume
Die Grundidee des Versionenraumverfahrens ist es, nicht einzelne Hypothesen aus-
zuwahlen und bei spateren Widerspruchen die getroffene Auswahl zuruckzunehmen,
sondern zu jedem Zeitpunkt die Menge
aller
bis dahin noch moglichen Hypothesen
zu reprasentieren.
Definition 5.20 (Versionenraum)
Sei B eine Menge von Trainingsbeispielen.
Dann ist die Menge
V
B
=
{
h
∈
L
C
|
h ist korrekt und vollstandig bzgl. B
}
der
Versionenraum
bzgl. der Beispielmenge B.
Bei einem Konzeptlernproblem besteht vor der Bearbeitung des ersten Trai-
ningsbeispiels der aktuelle Versionenraum aus der Menge L
C
aller Hypothesen.
Die prinzipielle Moglichkeit, diesen Suchraum zu reprasentieren und schrittweise
bei jedem neuen Beispiel alle inkorrekten und alle unvollstandigen Hypothesen
zu eliminieren, hatten wir oben
Kandidaten-Eliminations-Methode
genannt. Das
Versionenraum-Lernverfahren arbeitet nach diesem Prinzip, wobei die einzelnen
Hypothesen aber nicht direkt, sondern in kompakterer Form reprasentiert werden.
Ahnlich wie man z.B. die Menge aller reellen Zahlen zwischen 1 und 2 durch Angabe
der Intervallgrenzen [1,2] reprasentieren kann, wird der Versionenraum durch zwei
Begrenzungsmengen reprasentiert: die speziellsten und die allgemeinsten Hypothe-
sen.
Beispiel 5.21 (Versionenraum und Begrenzungsmengen)
Abbildung 5.11
zeigt einen Versionenraum fur das Sportsendungenbeispiel 5.13. Die (einelemen-
tige) Menge S enthalt die speziellste Hypothese des Versionenraumes, und die
zweielementige Menge G enthalt die beiden allgemeinsten Hypothesen. Die Pfeile
deuten die “Allgemeiner-als”-Beziehung zwischen Konzepten an. Der hier gezeigte
Versionenraum enthalt sechs verschiedene Hypothesen. Er kann aber durch die
beiden Mengen S und G reprasentiert werden, da es moglich ist, alle Hypothesen,
die bzgl. der “Allgemeiner-als”-Relation zwischen den Mengen S und G liegen, aus
S und G zu generieren und aufzuzahlen.
Selbsttestaufgabe 5.22 (Korrektheit und Vollstandigkeit)
Fur welche Teil-
menge der Trainingsbeispiele aus Abbildung 5.7 ist die Hypothese
?, Mannschaft,
?, national, Samstag
aus der Menge S (vgl. Abbildung 5.11) korrekt und
vollstandig?
Fur jede Menge von Beispielen konnen wir die Begrenzungsmengen wie folgt
definieren:
