Database Reference
In-Depth Information
function
VS
Eingabe:
Konzeptlernaufgabe mit den Sprachen L
E
und L
C
und Folge von Trainingsbeispielen
Ausgabe:
Versionenraumreprasentation aller Konzepte, die vollstandig
und korrekt bzgl. der eingegebenen Beispiele sind
Initialisiere S zu der Menge der speziellsten Hypothesen aus L
C
Initialisiere G zu der Menge der allgemeinsten Hypothesen aus L
C
for each
neues Trainingsbeispiel e
do
•
if
e ist ein positives Beispiel
then
•
entferne aus G alle Hypothesen g mit g(e)=0
•
for each
h
∈
S mit h(e)=0
do
•
entferne h aus S
fuge zu S alle Hypothesen h
hinzu mit:
- h
ist
minimale Verallgemeinerung von
h
bzgl.
e und
- es gibt eine Hypothese g
•
G mit h
≤
∈
g
•
entferne aus S jede Hypothese, die (echt) allgemeiner als
eine andere Hypothese in S ist
•
if
e ist ein negatives Beispiel
then
•
entferne aus S alle Hypothesen s mit s(e)=1
•
for each
h
G mit h(e)=1
do
• entferne h aus G
•
∈
fuge zu G alle Hypothesen h
hinzu mit:
- h
ist
minimale Spezialisierung von
h
bzgl.
e und
- es gibt eine Hypothese s
h
∈
S mit s
≤
•
entferne aus G jede Hypothese, die (echt) spezieller als
eine andere Hypothese in G ist
Abbildung 5.13
Versionenraum-Lernverfahren
VS
Der Algorithmus fur das Versionenraum-Lernverfahren abstrahiert noch von
einigen Aspekten wie z.B. der Bestimmung einer minimalen Verallgemeinerung einer
Hypothese h bzgl. eines (positiven) Beispiels e. Dabei ist die Hypothese h zu speziell
und muss verallgemeinert werden, allerdings nur “so weit wie notwendig”, dass e
gerade noch mit abgedeckt wird. Die genaue Spezifikation dieser Operationen hangt
naturlich von der konkreten Reprasentation von Beispielen und Konzepten ab. Das
Verfahren in Abbildung 5.13 ist aber so fur jede Konzeptlernaufgabe verwendbar.
5.4.7
Anwendungsbeispiel
Wir wenden das Versionenraum-Lernverfahren auf die Trainingsbeispiele aus Ab-
bildung 5.7 an. Als Initialisierung fur S erhalten wir S
0
=
{ ∅
,
∅
,
∅
,
∅
,
∅}
und fur