HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material

Ein Neuronennetz

(aus Hopcroft/Ullmann, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, S.47)

Historisch gesehen wurden endliche Automaten zuerst benutzt, um Neuronen-Netze zu simulieren. Suchen Sie einen endlichen Automaten, dessen Verhalten äquivalent zu dem Neuronen-Netz aus der Abbildung ist. Endzustände des Automaten entsprechen 1-Ausgaben des Netzwerkes. Jedes Neuron hat anregende (Kreise) und dämpfende (Punkte) Synapsen. Ein Neuron produziert eine 1-Ausgabe, wenn die Anzahl der anregenden Synapsen mit 1-Eingabe die der dämpfenden Synapsen mit 1-Eingabe um wenigstens die Wertigkeit des Neurons (Zahl innerhalb des Dreiecks) übersteigt. Zwischen der Änderung an der Eingabe verbleibe genügend Zeit für das Fortpflanzen der Signale und das Einpendeln in einen stabilen Zustand. Sie können davon ausgehen, dass die Werte von y1, y2 und y3 zu Beginn alle 0 sind.

Aufgabe

Es soll der Zustand des Systems durch die Zustände der Neuronen y1, y2 und y3 beschrieben werden, so dass z.B. der Zustand z101 zu y1=1, y2=0 und y3=1 gehört.
Eingabealphabet ist E = {0,1}, Ausgabealphabet ist A = {0,1}, Zustandsmenge ist Z = {z000, z001, z010, z011, z100, z101, z110, z111}, Anfangszustand ist z000.
Zur Aufstellung der Automatentafel ist es nötig, für jeden Zustand und für jede Eingabe das Verhalten des Netzes zu studieren. Dabei sind solange die Schritte
  • Ermittlung der Synapseneingaben
  • Ermittlung der Neuronenausgabe
zu wiederholen, bis sich ein stabiler Zustand eingestellt hat.

Das Delphi-Programm Neuron1 kann einerseits hierbei eine Hilfe sein, andererseits in seinem Quelltext als eine andere Sicht das Verständnis der Aufgabenstellung verbessern.
So zeigt folgender Programmausschnitt die Ermittlung der Ausgaben aus den Eingaben:
  if y1e1+y1e2+y1e3 >= 2 then y1 := 1 else y1 := 0;
  if y2e1+y2e3-y2e2 >= 1 then y2 := 1 else y2 := 0;
  if y3e1+y3e2-y3e3 >= 1 then y3 := 1 else y3 := 0;
  if y2+y3 >= 2 then aus := 1 else aus := 0;


Automatentafel

000 001 010 011 100 101 110 111
0 000 / 0 011 / 1 010 / 0 011 / 1 000 / 0 010 / 0 110 / 0 110 / 0
1 001 / 0 001 / 0 101 / 0 111 / 1 100 / 0 101 / 0 100 / 0 111 / 1


Ist die Automatentafel gefunden, so zeigt der Automatengraph durchaus weitere neue Erkenntnisse:

Die Zustände z101 und z010 liegen isoliert, dh. gewöhnlich werden sie nicht erreicht. Käme man - etwa durch einen Fehler - doch hinein, so gibt es keinen Weg zurück. Es zeigt sich außerdem, dass der Automat als Mealy-Automat begonnen, direkt zu einem Moore-Automaten reduziert werden kann. Die Ausgaben lassen sich nämlich - wie in obigem Graph geschehen - mit den Zuständen assoziieren.