Database Reference
In-Depth Information
Tritt einer dieser beiden Falle fur eine Hypothese in den Begrenzungsmengen S oder
G auf, gehen wir fur jede Hypothese s
∈
S und jede Hypothese g
∈
G wie folgt vor:
1. e ist fur s falschlicherweise positiv: Das bedeutet, dass s zu allgemein ist.
Da S aber nur speziellste Hypothesen enthalt, konnen wir s nicht weiter spe-
zialisieren, ohne die Vollstandigkeit zu verlieren. s muss also aus S entfernt
werden.
2. e ist fur s falschlicherweise negativ: Das bedeutet, dass s zu speziell ist und
soweit verallgemeinert werden muss, dass e mit abgedeckt wird.
3. e ist fur g falschlicherweise positiv: Das bedeutet, dass g zu allgemein ist und
soweit spezialisiert werden muss, dass e nicht mehr mit abgedeckt wird.
4. e ist fur g falschlicherweise negativ: Das bedeutet, dass g zu speziell ist. Da
G aber nur allgemeinste Hypothesen enthalt, konnen wir g nicht weiter ver-
allgemeinern, ohne die Korrektheit zu verlieren. g muss also aus G entfernt
werden.
In Abbildung 5.13 ist der vollstandige Algorithmus
VS
fur das Versionenraum-
Lernverfahren angegeben, der insbesondere diese vier Punkte realisiert. Im nachsten
Abschnitt werden wir
VS
anhand eines ausfuhrlichen Beispiels erlautern.
Beachten Sie, dass das Ersetzen einer Hypothese s
S durch eine Menge von
minimalen Verallgemeinerungen immer so erfolgt, dass jede neue Hypothese h
in
S immer noch spezieller oder gleich einer Hypothese aus G ist; entsprechendes gilt
umgekehrt auch fur G.
∈
Selbsttestaufgabe 5.25 (VS und Begrenzungsmengen)
Begrunden Sie,
warum im Algorithmus
VS
nach der Bearbeitung eines Beispiels wieder gilt, dass
es zu jeder Hypothese s ∈ S ein g
s
∈ G mit s ≤ g
s
und zu jeder Hypothese
g
g gibt. Formulieren Sie dazu eine Invariante
Inv
(S, G)
und zeigen Sie, dass
Inv
(S
post
,G
post
)aus
Inv
(S
pre
,G
pre
) folgt, wenn S
pre
, G
pre
die Begrenzungsmengen
vor
und S
post
, G
post
die Begrenzungsmengen
nach
der
Bearbeitung eines Beispiels e sind. Gilt auch
Inv
(S
init
,G
init
), wenn S
init
, G
init
die
Begrenzungsmengen sind, die sich bei der Initialisierung in
VS
ergeben?
∈
G ein s
g
∈
S mit s
g
≤
Die Terminierung von
VS
ist sichergestellt. Wenn
VS
terminiert, liegt eine der
folgenden drei Situationen vor:
1. S ist leer und/oder G ist leer. In diesem Fall ist der Versionenraum ebenfalls
zur leeren Menge kollabiert. Das bedeutet, dass es keine konsistente Hypothese
fur die Trainingsbeispiele in dem vorgegebenen Hypothesenraum L
C
gibt.
2. S und G sind identische einelementige Mengen: S = G =
. Das bedeutet,
dass die Hypothese h das einzige Konzept aus L
C
ist, das konsistent bzgl. der
Trainingsmenge ist.
{
h
}
3. Alle Beispiele sind bearbeitet, S und G sind beide nicht leer und enthalten
unterschiedliche Hypothesen. In diesem Fall sind alle in dem durch S und G
bestimmten Versionenraum liegenden Hypothesen konsistent bzgl. der Trai-
ningsmenge.
