Versionsraum

Als Versionsraum wird im maschinellen Lernen diejenige Teilmenge des Hypothesenraums bezeichnet, die bezüglich einer Menge $D$ von Lernbeispielen alle konsistenten und vollständigen Hypothesen enthält. Eine Hypothese heißt konsistent, wenn sie keine negativen Trainingsbeispiele positiv klassifiziert. Eine Hypothese heißt vollständig wenn alle positiven Beispiele von einer Hypothese richtig klassifiziert werden.

Beim Versionsraum-Lernverfahren (Mitchell 1982) handelt es sich um ein inkrementelles maschinelles Lernverfahren zum Lernen eines Konzepts. Für den Fall, dass die Trainingsbeispiele nicht verrauscht sind und das gesuchte Zielkonzept im Hypothesenraum enthalten ist, liefert das Versionsraum-Lernverfahren eine kompakte Repräsentation des Versionsraums.

Generalität im Hypothesenraum

Basis des Algorithmus ist eine Halbordnung, die eine Unterscheidung von Hypothesen nach Generalität erlaubt. Eine Hypothese $h_{k}$ wird als spezieller als $h_{\ell }$ bezeichnet, wenn für alle x aus der Menge der möglichen Zielkonzepte folgendes gilt:

$h_{k}(x)=1\;\;\Rightarrow \;\;h_{\ell }(x)=1$

Versionsraum-Lernverfahren

Das Versionsraum-Lernverfahren ist eine maschinelle Methode im Bereich der KI, um dem Rechner beizubringen, zuvor unbekannte Informationen richtig zu beurteilen.

Algorithmus

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.

Vorteile und Nachteile

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.

Beispiel

Das Beispiel demonstriert, wie ein konkreter Versionsraum durch Beispiele entsteht.

Bevor die Beispiele in den Versionsraum eingeordnet werden, erfolgt eine Startbelegung der Mengen $S_{0}$ und $G_{0}$.

Startbelegung

• $S_{0}=\{\}$
• $G_{0}=\{(?,?,?,?,?)\}$

Positives Beispiel

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

Erklärung

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

Positives Beispiel

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

Erklärung

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

Negatives Beispiel

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

Erklärung

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

Positives Beispiel

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

Erklärung

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

Negatives Beispiel

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

Erklärung

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

Literatur

• Tom M. Mitchell: Machine Learning, McGraw Hill. 1997. ISBN 0071154671
• Christoph Beierle, Gabriele Kern-Isberner: Methoden wissensbasierter Systeme: Grundlagen, Algorithmen, Anwendungen., 4. Aufl. Vieweg+Teubner Verlag, 2008, S. 128ff. ISBN 3834805041