Formale Betrachtungen

Um den Leser nicht zu langweilen, werden nicht alle formalen Einzelheiten angegeben. Es soll nur eine Vorstellung von der Art der Untersuchungen vermittelt werden.

Im folgenden wird davon ausgegangen, daß man immerhin von einer konstanten - allerdings unbekannten - Wahrscheinlichkeitsverteilung über alle potentiellen, verschiedenen Sinnesreizungen sprechen kann. (Die unterschiedlichen Sinnesreizungen werden auch formal als Objekte bezeichnet.) In Abbildung 8.6 ist in grau eine Menge von Objekten zu sehen, die dem System potentiell präsentiert werden könnten.

  

Abbildung 8.6: Die Klassifikationsfunktion f soll aufgrund der Menge Y von einem selbstorganisierenden System bestimmt werden.

Das Ziel des selbstorganisierenden Systems ist es, die Klassifikationsfunktion f selbst zu bestimmen, oder eine Approximation zu finden, die möglichst viele der im grauen Bereich liegenden Objekte genau nach f klassifiziert. Das selbstorganisierende System muß also nun aufgrund der nach einer unbekannten Wahrscheinlichkeitsverteilung zufällig vorkommenden Sinnesreizungen, eine `sinnvolle'^9.29 Klassifikationsfunktion f bestimmen, die möglichst von höherer Komplexität ist, als das System selbst. Nur durch einen solchen Schritt kann sich ein System durch Selbstorganisation zu einem komplexeren System entwickeln.

Das folgende Ergebnis sagt etwas darüber aus, inwiefern einfache selbstorganisierende Systeme in der Lage sind, bestimmte Klassifikationsfunktionen hoher Komplexität aus zufällig gezogenen Stichproben von unklassifizierten Objekten zu gewinnen oder wenigstens näherungsweise zu gewinnen. Der Leser, der sich nicht für den Formalismus interessiert, möge gleich hinter Theorem 4 springen.

Sei X eine unendliche Menge von Objekten und $X_{n}\subset X$diejenige Teilmenge von X, die die ersten n Objekte enthält. X_n sei die Menge von Objekten, die von dem sich selbstorganisierenden System S zu klassifizieren sind.

Definition 4   Gegeben sei für ein beliebiges n eine feste Teilmenge $Y_{n}\subseteq X_{n}$ und eine feste Wahrscheinlichkeitsverteilung P_n über Y_n. Dann sagen wir, daß eine Funktion f eine Zielfunktion f_t $\varepsilon$-approximiert, wenn gilt:

$$\sum_{x\in\{x\vert x\in Y_{n}\wedge (f(x)\not=f_{t}(x))\}}P_{n}(x)\leq\varepsilon$$

Eine $\varepsilon$-Approximation einer Klassifikationsfunktion f_tklassifiziert ein zufällig ausgesuchtes Objekt x höchstens mit der Wahrscheinlichkeit $\varepsilon$ anders als f_t.

Wenn eine wichtige Klassifikationsfunktion für lebenserhaltende Klassifikationen der Umweltsituationen nicht hinreichend gut durch das selbstorganisierende System approximiert wird, so ist die Wahrscheinlichkeit entsprechend groß, in Lebensgefahr zu geraten.

Das folgende Theorem gibt eine Obergrenze für die Komplexität von approximierbaren Klassifikationsfunktionen in selbstorganisierenden Systemen an. K_Yn(f_t) ist dabei grob gesagt^9.30 die Kolmogoroffkomplexität der zu bestimmenden Zielklassifikationsfunktion.

Theorem 4   Für alle $0<\varepsilon<\frac{1}{2}$ und $0<\delta<1$, eine beliebige aber feste Stichprobengröße sund einer beliebigen Zielfunktion f_t mit einer Komplexität von

$$K_{Y_{n}}(f_{t})>K(S)+3\log_{2} n+const,$$

gilt das Folgende:

Es gibt kein selbstorganisierendes System S, das für jede beliebige Wahrscheinlichkeitsverteilung P_n über X_neine Funktion faus einer zufällig nach P_n gezogenen Stichprobe der Größe s bestimmt, so daß f die Zielfunktion f_t mit einer Wahrscheinlichkeit von mindestens $1-\delta$ $\varepsilon$-approximiert.

Beweis: Siehe Freivalds & Hoffmann HoffmannFreivalds[FH92].

Das Theorem deutet an, daß es bestimmte Grenzen einer zuverlässigen Selbstorganisation gibt: daß ein System ohne hinreichende Vorinformation, nicht in der Lage ist, durch reine Beobachtung unklassifizierter Objekte zu einer zweckorientierten wesentlich komplexeren Struktur zu gelangen. Es beschränkt die Komplexität der approximierbaren Klassifikationsfunktionen im wesentlichen auf die Komplexität des Systems selbst ! Nur ein geringer Teil ( $const + 3\log_{2} n$) geht über die bereits vorher vorhandene Systemkomplexität K(S) hinaus.

Die Voraussetzungen, die in das obige Theorem eingehen, sind natürlich nicht immer erfüllt. Einerseits ist gefordert, daß eine konstante Wahrscheinlichkeitsverteilung über den Objekten besteht - sie könnte mit der Zeit Veränderungen unterworfen sein. Andererseits geht der Beweis des Satzes auf eine Betrachtung des schlechtesten Falls zurück, hier auf die jeweils ungünstigste Wahrscheinlichkeitsverteilung über die für eine gute Approximation wesentlichen Objekten. Es ist somit nicht ausgeschlossen, daß ein selbstorganisierendes System in der Praxis bessere Klassifikationsleistungen erbringt. Ein weiterer Einwand mag die Annahme betreffen, daß es nur eine Zielfunktion gibt, die approximiert werden soll. Es ist durchaus möglich, daß es eine ganze Reihe von unterschiedlichen aber gleichermaßen viablen Klassifikationsmöglichkeiten gibt, die wahlweise approximiert werden können sollten.