Versionsraum

Anfangs enthält der Versionsraum alle möglichen Hypothesen, stimmt also mit dem Hypothesenraum überein. Durch die sequentielle Hinzunahme von positiven und negativen Trainingsbeispielen wird er immer weiter eingeschränkt, bis er im Idealfall nur noch aus einem Element besteht. Die Repräsentation des Versionsraums erfolgt durch zwei Mengen namens S und G ("specific" und "general"). S ist die Menge der speziellsten Hypothesen und enthält alle Hypothesen, die mit den Trainingsbeispielen konsistent sind, also diese richtig klassifizieren. Weiterhin darf keine der Hypothesen in S allgemeiner als eine andere Hypothese im Versionsraum sein. Analog enthält G die allgemeinsten Hypothesen, die mit den Trainingsdaten konsistent sind.

Anfangs enthält S die speziellste Hypothese, also diejenige Hypothese, die jedes Zielkonzept negativ klassifiziert, und G die allgemeinste Hypothese, also diejenige Hypothese, die jedes Zielkonzept positiv klassifiziert. Anschließend wird über die Menge aller Trainingsbeispiele iteriert und S und G jeweils so angepasst, dass die obigen Forderungen für S und G erfüllt sind.

Der erste Vorteil des Versionsraum-Lernverfahrens ist die implizite Darstellung des Versionsraums. Alte Beispiele müssen nicht gespeichert werden und dadurch besteht ein geringer Speicheraufwand zur Darstellung des Versionsraums. Ein weiterer Vorteil ist die Möglichkeit, eine ausreichend große Menge von Trainingsbeispielen selbständig zu erkennen (Abbruch, wenn S=G). Eine Steigerung der Lerngeschwindigkeit erhält man, wenn Hypothesen erzeugt werden können und zu S oder G hinzugefügt werden, zum Beispiel von Experten erstellt. In diesem Fall kann der Algorithmus Beispiele selektieren, die den Versionsraum in möglichst gleich große Teile trennen. Das Lernen eines solchen Beispiels sorgt für eine schnelle Reduzierung der Versionsraumgröße.

• ${\displaystyle h_{1}=}$(Fußball, Mannschaft, draußen, national, Samstag)
• ${\displaystyle S_{1}=\{(}$Fußball, Mannschaft, draußen, national, Samstag${\displaystyle )\}}$
• ${\displaystyle G_{1}=\{(}$?,?,?,?,?${\displaystyle )\}}$

${\displaystyle S_{0}}$ enthält das Beispiel ${\displaystyle h_{1}}$ nicht. ${\displaystyle S_{0}}$ verallgemeinert sich um ${\displaystyle h_{1}}$. ${\displaystyle G_{1}}$ lässt weiterhin alle Beispiele zu.

• ${\displaystyle h_{2}=}$(Hockey, Mannschaft, draußen, national, Samstag)
• ${\displaystyle S_{2}=\{(}$?, Mannschaft, draußen, national, Samstag${\displaystyle )\}}$
• ${\displaystyle G_{2}=\{(}$?,?,?,?,?${\displaystyle )\}}$

${\displaystyle S_{1}}$ enthält das neue Beispiel ${\displaystyle h_{2}}$ nicht. Deshalb wird ${\displaystyle S_{2}}$ so verallgemeinert, dass es ${\displaystyle h_{2}}$ enthält. Da sich ${\displaystyle h_{1}}$ und ${\displaystyle h_{2}}$ nur in der Sportart unterscheiden, ersetzt man Fußball durch das Platzhaltersymbol ?

• ${\displaystyle h_{3}=}$(Bodenturnen, Einzel, drinnen, Welt, Samstag)
• ${\displaystyle S_{3}=\{(}$?, Mannschaft, draußen, national, Samstag${\displaystyle )\}}$
• ${\displaystyle G_{3}=\{}$(?, Mannschaft, ?, ?, ?), (?, ?, draußen, ?, ?), (?, ?, ?, national, ?)${\displaystyle \}}$

${\displaystyle S_{2}}$ enthält das negative Beispiel nicht, deshalb bleibt ${\displaystyle S_{2}}$ unverändert. ${\displaystyle G_{2}}$ muss spezialisiert werden, indem es alle Fälle aufführt, die verhindern, dass ${\displaystyle h_{3}}$ als gültiges Beispiel anerkannt wird. Gleichzeitig muss ${\displaystyle G_{3}}$ so allgemein sein, dass es die bisherigen Beispiele zulässt.

• ${\displaystyle h_{4}=}$ (Handball, Mannschaft, drinnen, national, Samstag)
• ${\displaystyle S_{4}=\{(}$?, Mannschaft, ?, national, Samstag${\displaystyle )\}}$
• ${\displaystyle G_{4}=\{}$(?, Mannschaft, ?, ?, ?), (?, ?, ?, national, ?)${\displaystyle \}}$

${\displaystyle S_{3}}$ enthält das aktuelle Beispiel nicht und muss deshalb erweitert werden. ${\displaystyle G_{3}}$ würde das aktuelle Beispiel zurückweisen, deshalb muss ${\displaystyle G_{3}}$ spezialisiert werden.

• ${\displaystyle h_{5}=}$(Zehnkampf, Einzel, draußen, Welt, Sonntag)
• ${\displaystyle S_{5}=\{(}$?, Mannschaft, ?, national, Samstag ${\displaystyle )\}}$
• ${\displaystyle G_{5}=\{}$(?, Mannschaft, ?, ?, ?), (?, ?, ?, national, ?)${\displaystyle \}}$

Da ${\displaystyle S_{4}}$ das Beispiel zurückweist, ist ${\displaystyle S_{5}=S_{4}}$. Auch ${\displaystyle G_{4}}$ lässt das Beispiel nicht zu, das heißt ${\displaystyle G_{4}=G_{5}}$.