Begriffe ermöglichen die Charakterisierung von Teilklassen in einem
Universum von Objekten. So charakterisiert der Begriff einer
``schwarzen Zahlkarte'' in unserem Kartenbeispiel genau eine bestimmte
Teilmenge im Kartenstoß; auf alle anderen Karten des Stoßes trifft der
Begriff nicht zu. Die Bildung von Begriffen ist eine (spezielle) induktive
Problemstellung, wie unser
Kartenbeispiel bereits illustriert.
Während wir diese Problemstellung in den voranstehenden beiden Unterabschnitten in einem logischen Rahmen prädikatenlogischer Formeln besprochen haben, wird Begriffsbildung oft innerhalb eines Raumes von Relationen, dem sogenannten Versionsraum behandelt [Mit78]. Wir wollen diesen Zugang in diesem Unterabschnitt kurz erläutern.
Ein Begriffsbildungsproblem ist ein Tupel .
und
sind die vorher eingeführten
positiven und
negativen Beobachtungen zum Begriff, den wir bilden
wollen. Der Einfachheit halber wollen wir
annehmen.
ist die im letzten Unterabschnitt eingeführte
Basismenge von Begriffen.
ist die durch die ebenfalls im letzten
Unterabschnitt besprochene Formeleinschränkung definierte Sprache, in der
die Begriffsdefinition formuliert werden kann.
Ein Begriffsbildungsproblem heißt akzeptabel, wenn
sich der Begriff mittels der Begriffe in in der Sprache
bilden läßt. Eine Relation heißt
charakteristisch, wenn sie von allen
Beobachtungen in
erfüllt wird; sie heißt
diskriminierend, wenn sie von allen
Beobachtungen in
nicht erfüllt wird; sie heißt
zulässig,
wenn sie charakteristisch und diskriminierend ist.
In unserem Kartenbeispiel ist die Relation charakteristisch, aber
nicht diskriminierend, da sie alle positiven Beispiele, aber auch ein
negatives Beispiel erfüllt. Die Relation, daß die Farbe Kreuz ist, ist
diskriminierend, aber nicht charakteristisch, da sie keines der negativen
Beispiele, aber auch ein positives Beispiel nicht erfüllt. Unsere
Lösungsrelation
ist charakteristisch und diskriminierend, also
zulässig.
Der Versionsraum eines
Begriffsbildungsproblems ist die Menge aller zulässigen Relationen. Ein
Versionsgraph ist ein gaG. Seine Knoten sind die
Elemente des Versionsraumes. Vom Knoten gibt es eine auf den Knoten
gerichtete Kante, wenn die folgenden beiden Bedingungen erfüllt
sind.
Abbildung 4.1: Der Versionsgraph für das Kartenproblem mit
und
Abbildung 4.2: Der Versionsgraph für das Kartenproblem mit
und
Abbildung 4.3: Der Versionsgraph für das Kartenproblem mit
und
Abbildung 4.4: Der Versionsgraph für das Kartenproblem mit
und
Abbildung 4.5: Der Versionsgraph für das Kartenproblem mit
und
verschiedenen Beispielmengen. steht dabei für die universelle
Relation, während die übrigen Zeichen die bisherige Bedeutung haben. Wir
sehen, wie mit jedem zusätzlichen Beispiel eine Reihe von Knoten des Graphen
entfallen, bis schließlich nur ein einziger Knoten als zulässige
Relation übrigbleibt.
Wenn man einen Einfluß auf die Auswahl der Beispiele ausüben kann, dann läßt sich mit einer geschickten Reihenfolge der Lösungsprozeß beschleunigen, wie man an den gezeigten Abbildungen auch sehen kann. Es handelt sich hierbei um die Generierung von Experimenten, wie sie auch in der Wissenschaft zur Theoriebildung in großem Maßstab durchgeführt wird. Zur Theoriebildung selbst und insbesondere ihre Anwendung auf die Programmierung siehe [Sha83].
Der Versionsgraph ist in praktischen Problemen außerordentlich groß. Man muß ihn jedoch zur Eingrenzung der Lösungsrelation nicht vollständig generieren. Vielmehr genügt die Fokussierung auf eine untere und obere Grenzmenge von Knoten. Beim Eintreffen neuer Beispiele werden dann nur diese Grenzmengen und nicht der gesamte Graph auf den diese zusätzlichen Beispiele berücksichtigenden, neuesten Stand gebracht.
Christoph Quix, Thomas List, René Soiron