Home Up Mail an Joachim Pimiskern Impressum

Herleitung der Kapazität des Arbeitsgedächtnisses

Joachim Pimiskern, 29.12.2001

Wir können uns spontan Symbol-Tupel von maximal ca. 7+-2 Symbolen merken, z.B. 3b59fh oder p1mv1kp9d, aber nicht Folgen von wesentlich mehr als 7 Symbolen, wie z.B. 8mzk1wj614241pkn5. In diesem Dokument soll der Grund hierfür ausgearbeitet werden.


Um es kurz zu machen: der Grund ist, daß in einem Assoziativspeicher mindestens ca. 10% der Speicherelemente mit dem gewünschten Zielmuster belegt sein müssen, damit sich das Muster gegen Rauschen durchsetzen kann.

Biologische Ausgangssituation

Erinnern bedeutet, daß ein bestimmter Gehirnzustand hergestellt wird. Der Gesamtzustand eines Gehirns wird bestimmt durch die Kombination der Zustände der Komponenten, also der Neuronen. Der Erinnerungsprozeß besteht darin, daß ein Teil der Neuronen mit einem Teilmuster initialisiert wird. Anschließend stellt das Gehirn aus diesem Teilmuster ein Gesamtmuster her.

Ab irgendwann im Verlaufe der Evolution begann das symbolische Denken. Wir Menschen können uns Symbol-Tupel merken, z.B. cdefg. Ist nur ein Teil des Tupels bekannt, so kann daraus durch Assoziation der Rest des Tupel aus dem Gedächtnis abgerufen werden, z.B. xy -> xyz.

Definition: Ein Symbol ist diejenige Teilmenge eines Datensatzes, die genügen würde, um aus einem Assoziativspeicher den kompletten Datensatz abzurufen.

Das Langzeitgedächtnis kann keine Tupel mit mehr Symbolen speichern, als das Arbeitsgedächtnis speichern kann, denn sonst würden beim Abruf Informationen verloren gehen. Man kann z.B. Tausende von Ziffern der Zahl Pi auswendig lernen, aber abrufen kann man Pi immer nur portionsweise.

Umgekehrt sollte das Arbeitsgedächtnis nicht größere Tupel speichern können, als im Langzeitgedächtnis verankert werden können, denn sonst könnte man nicht häppchenweise lernen, ohne daß dabei Informationen verloren gehen.

Grundannahme für die folgenden Überlegungen: man hat einen Assoziativspeicher vorliegen, der aus gleichartigen Units bzw. Neuronen besteht. Jedes Neuron ist mit einigen der anderen Neuronen verbunden. Während der Erinnerungsphase trifft ein Neuron die Entscheidung aufgrund des Outputs der anderen Neuronen, ob es selbst den Ausgang mit 1 oder mit 0 belegen soll. Das heißt in anderen Worten, jedes Neuron klassifiziert das Gesamtkollektiv der anderen Neuronen. Wenn kein Neuron mehr seinen Ausgabezustand ändert, ist der Erinnerungsvorgang abgeschlossen.

Die Aufgabenstellung lautet also nun: in wieviele Teile kann man bei einem (oBdA binären) Assoziativspeicher die Muster zerlegen, damit ein einzelner dieser Teile genügt, um das Komplettmuster abzurufen?

Satz 1) Die Wahrscheinlichkeit dafür, daß ein Neuron sich einem von mehreren konkurrierenden Mustern anschließt, ist proportional zur Anzahl der Neuronen, die sich bereits diesem Muster angeschlossen haben. Beweis: die einzige Unterscheidungsmöglichkeit der Muster sind die Verhältnisse der Neuronenzahlen.

Daraus kann man ein Verfahren zur Simulation der Dynamik eines Assoziativspeichers gemäß der oben genannten Architektur ableiten. Man belegt m von n Neuronen mit einem Teil des Zielmusters. Die restlichen Neuronen belegt man mit einem Zufallsmuster, bei dem jedes Neuron mit einer Wahrscheinlichkeit von 50% 0 und mit 50% 1 ist. Auf diese Weise ist garantiert, daß in der Betrachtungsweise von Tupeln zu jeglichem anderen bereits gespeicherten Tupel ungefähr derselbe Hamming-Abstand besteht (Anmerkung: würde man die restlichen Neuronen z.B. alle mit 0 initialisieren, so würde der Zustand "alle Neuronen sind 0" zu einem Attraktor, der immer gewinnt) . Greift man ein Neuron zufällig heraus, so sind die Chancen m/n, daß man dabei eines erwischt, das sich bereits dem gewünschten Zielmuster ansgeschlossen hat. Die Chance ist (n-m)/n, daß es sich dabei um ein zufällig gesetztes Neuron handelt.

Stochastischer Prozeß, der einen Erinnerungsvorgang beschreibt

Wird ein Neuron gewählt, das sich bereits garantiert dem Zielmuster angeschlossen hat, so ist die Chance m/n, daß das Neuron seinen Zustand beibehält, denn gemäß 1) ist die Wahrscheinlichkeit so groß, sich dem gewünschten Zielmuster anzuschließen. Mit einer Wahrscheinlichkeit von (n-m)/n wird sich das Neuron irgendeinem anderen Muster anschließen, was bedeutet, daß dann m mit einer Wahrscheinlichkeit von 50% gleichbleibt und mit einer Wahrscheinlichkeit von 50% um 1 erniedrigt wird. Wird ein Neuron gewählt, das außerhalb dieser m Musterneuronen liegt, so ist die Wahrscheinlichkeit m/n, daß sich dieses Neuron dem Zielmuster anschließt und m also um 1 erhöht wird. Mit einer Wahrscheinlichkeit von (n-m)/n schließt sich das Neuron irgendeinem anderen Muster an, was bedeutet, daß m mit 50% Wahrscheinlichkeit um 1 erhöht wird und mit 50% Wahrscheinlichkeit gleich bleibt.

Zufällige Auswahl eines Neurons aus n.
m Neuronen sind mit einem Teilmuster initialisiert,
der Rest zufällig.

Musterkonformes Neuron, Wkt. m/n

Nicht musterkonformes Neuron, Wkt. (n-m)/n

Sich dem Zielmuster anschließen

Wkt. m/n

Sich irgendeinem Muster anschließen

Wkt. (n-m)/n

Sich dem Zielmuster anschließen

Wkt. m/n

Sich irgendeinem Muster anschließen

Wkt. (n-m)/n

Aktion: keine

Aktion: mit 50% Wkt. m := m - 1

Aktion: m := m + 1

Aktion: mit 50% Wkt. m := m + 1

Obiges Schema wurde alsDelphi-Programm realisiert. Das folgende Schaubild zeigt den Verlauf der Simulation. Für jeden Prozentsatz an Startmuster-Neuronen wurden 100 Simulationsschritte durchgeführt. Manchmal setzt sich das Startmuster durch, manchmal gewinnt die Drift gegen irgendwelche Zufallsmuster. Die blaue Kurve zeigt, wie oft sich das Startmuster durchsetzt, die rote Kurve, wie oft die Drift Oberhand gewinnt. Es ist deutlich zu sehen, daß die Fehlerquote ab ca. 10% belegter Neuronenzahl gegen 0 geht.

 

Schlußfolgerung

Nimmt ein Teilmuster weniger als ca. 10% der Neuronen eines Assoziativspeichers ein, so kommt es beim Erinnerungsvorgang zu gelegentlichen Fehlklassifikationen. Erst wenn das Teilmuster mindestens ca. 10% der Neuronen umfaßt, kann sich das gespeicherte Muster fast immer gegen die Drift durchsetzen. Um mit einem binären Assoziativspeicher einen Symbol-Tupel-Speicher zu realisieren, sollte man folglich je Tupel nicht mehr als ca. 10 Symbole verwenden.

Obige Überlegungen wurden unabhängig von einem bestimmten Modell von Assoziativspeicher angestellt. Lediglich wurde vorausgesetzt, daß die Muster, welche die einzelnen Symbole codieren, zufallscodiert sind. Dies scheint die am wenigsten aufwendige Methode zu sein, um zu gewährleisten, daß je zwei Muster den größtmöglichen Hamming-Abstand besitzen.

Speziell für das Hopfield-Modell erwähnen Schöneburg, Hansen und Gawelczyc [1]:

Wird die Hamming-Distanz zweier Muster klein (h<=N/5), verlagern sich die Minima der Energie-Funktion näher zueinander, so daß die stabilen Zustände nicht mehr den gelernten Mustern entsprechen, sondern etwas daneben liegen. Ist die Hamming-Distanz der Muster noch geringer (h<=N10), verschmelzen die Minima miteinander, es gibt nur noch einen stabilen Zustand für zwei Muster.

Wer sich für psychologische Experimente zur Begrenzung des Arbeitsgedächtnisses interessiert, sei auf [2] verwiesen.

Literatur

[1] E.Schöneburg, N.Hansen, A.Gawelczyk: Das Hopfield Modell, Chip Professional Programmieren, Ausgabe 9/1990, S.82

[2] George A. Miller: The Magical Number Seven, Plus or Minus Two: Some Limits on our Capacity for Processing, Information, 1956, http://psychclassics.yorku.ca/Miller/

Home Up Mail an Joachim Pimiskern Impressum