Nächste Seite: 4.3.5 Lernen von Funktionen Vorige Seite: 4.3.3 Induktive Konzeptbildung

4.3.4 Begriffsbildung

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.

1. , dh. die Relation ist spezieller als .
2. Es gibt keine Relation mit .

Unter gewissen Bedingungen bildet der Versionsgraph einen Verband, den Begriffsverband [Wil87]. Die Abbildungen 4.1-4.5 zeigen die Versionsgraphen für unser Kartenproblem mit

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.