Friedrich-Alexander-Universität Erlangen-Nürnberg
Lehrstuhl für Künstliche Intelligenz

Neuronale Informationsverarbeitung mit
SDM (Sparse Distributed Memory):
Klassenbibliothek zur Implementation des
Kernsystems (SDM-Klassen)

Studienarbeit im Studienfach Informatik
vorgelegt von Alexander Eslava

Beginn der Arbeit: 1. November 2004
Abgabe der Arbeit: 1. August 2005

Kurzfassung

Das Sparse Distributed Memory (SDM) ist ein neuronaler Assoziativspeichers, der sich auszeichnet durch Generalisierungsfähigkeit, hochgradige Parallelisierbarkeit, Robustheit gegen Fehler im Speicher und Abstraktionsfähigkeit. Er ermöglicht neben der Erkennung verrauschter oder teilweise verdeckter Muster die Repräsentation von Sequenzen und beliebigen Graphen. In der vorliegenden Arbeit wurde eine parallele objektorientierte Klassenbibliothek für SDM in Common-Lisp entwickelt, welche portierbar auf alle Parallelrechner ist, welche über einen Compiler für Paralation Lisp verfügen. Die Vorlage bildete die SDM-Bibliothek von Andreas Turk, in der Sprache *-Lisp, welche nur auf der Connection-Machine CM-2 läuft. Ich habe die Software diversen Optimierungen unterzogen und um zusätzliche Varianten des SDM erweitert. Die SDM-Bibliothek umfasst das Generalisierte Adressmodul von Turk, welches das originale Modell des SDM von Kanerva und die Varianten von Jaeckel (Selected-Coordinatesund Hyperplane-Design) subsumiert. Darüber hinaus wurde das Adreßmodul um das Karlsson- Modell erweitert, das Datenmodul um eine binäre Matrix mit optionaler gradueller Vergesslichkeit und der SDM um die Modi Adreßverdichtung und Datenverdünnung.

Inhaltsverzeichnis

1 Einleitung ...  1
1.1 Aufgabenstellung ... 1

2 Sparse Distributed Memory ...  2
2.1 SDM-Modell nach Kanerva ... 2
2.1.1 Architektur ... 2
2.1.2 Eigenschaften und Voraussetzungen ... 4
2.1.3 Abstraktion ... 5
2.1.4 Repräsentation von Sequenzen ... 5
2.2 Varianten des SDM ... 7
2.2.1 Selected Coordinates Design nach Jaeckel ... 7
2.2.2 Hyperplane Design nach Jaeckel ... 7
2.2.3 Generalisiertes Modell nach Turk ... 8
2.2.4 SDM mit N-Of-M-Codes und binärer Datenmatrix ... 8
2.2.5 Karlsson-Design ... 11
2.2.6 Adressverdichtung ... 12
2.2.7 Datenverdünnung ... 12
2.2.8 Datenmodul mit Buckets ... 13
2.2.9 Multipler Binärer Entscheidungsbaum ... 13

3 Verteilte Repräsentationen ...  17
3.1 Frames ... 17
3.2 Lokale und verteilte Repräsentationen ... 17
3.3 Neuronale Netze ... 19
3.4 Random Indexing ... 19
3.5 Binary Spatter Code nach Kanerva ... 19

4 Paralation Lisp ...  21
4.1 Programmierstil ... 21
4.2 Wichtige Schlüsselwörter ... 21
4.3 Vor- und Nachteile und Probleme ... 22
4.4 Wege zur Umgehung der Nachteile ... 23

5 SDM-Klassenbibliothek ...  24
5.1 Spezifikationen ... 24
5.2 Implementation ... 24
5.2.1 Topologie Hyperwürfel ... 25
5.2.2 Verteilung der Dimensionen auf die Kommunikationsphasen ... 25
5.2.3 Domänenpartitionierung ... 26
5.2.4 Propagierung des Selektionsvektors ... 27
5.2.5 Akkumulation und Sukzessive Intervallhalbierung und -Verdoppelung ... 27
5.2.6 Einsammeln des Ausgabevektors beim einfachen Lesen ... 27
5.2.7 Propagierung des Ausgabevektors beim iterativen Lesen ... 28
5.2.8 Gepackte Repräsentation von kleinen Ganzzahlen ... 28
5.2.9 Folded SDM ... 29

6 Zusammenfassung und Ausblick ...  30
6.1 Zusammenfassung ... 30
6.2 Ausblick ... 30

A Referenz der SDM-Klassenbibliothek ...  31
A.1 Paket SDM ... 31
A.1.1 Datentypen und Konstanten ... 31
A.1.2 Methoden und Klassen ... 31
A.1.3 Sparse Distributed Memory ... 32
A.1.4 Hilfsfunktionen ... 35
A.1.5 Adressmodule ... 36
A.1.6 Datenmodule ... 38
A.2 PROB ... 42
A.3 BIGSDM ... 42
A.4 FSDM ... 45

B Mathematische Grundlagen ...  48

Literaturverzeichnis ...  51

Abbildungsverzeichnis

[...]

Kapitel 1
Einleitung

Das Sparse Distributed Memory (SDM) ist ein neuronaler Assoziativspeichers, der sich auszeichnet durch Generalisierungsfähigkeit, hochgradige Parallelisierbarkeit, Robustheit gegen Fehler im Speicher und Abstraktionsfähigkeit. Er ermöglicht neben der Erkennung verrauschter oder teilweise verdeckter Muster die Repräsentation von Sequenzen und beliebigen Graphen. In der vorliegenden Arbeit wurde eine parallele objektorientierte Klassenbibliothek für SDM in Common-Lisp entwickelt, welche portierbar auf alle Parallelrechner ist, welche über einen Compiler für Paralation Lisp verfügen. Die Vorlage bildete die SDM-Bibliothek von Andreas Turk, in der Sprache *-Lisp, welche nur auf der Connection-Machine CM-2 läuft. Ich habe die Software diversen Optimierungen unterzogen und um zusätzliche Varianten des SDM erweitert. Die SDM-Bibliothek umfasst das Generalisierte Adressmodul von Turk, welches das originale Modell des SDM von Kanerva und die Varianten von Jaeckel (Selected-Coordinatesund Hyperplane-Design) subsumiert. Darüber hinaus wurde das Adreßmodul um das Karlsson- Modell erweitert, das Datenmodul um eine binäre Matrix mit optionaler gradueller Vergesslichkeit und der SDM um die Modi Adreßverdichtung und Datenverdünnung.

1.1 Aufgabenstellung

Vorrangiges Ziel der vorliegenden Arbeit war eine effiziente Implementation einer hardwareunabhängigen SDM-Klassenbibliothek. Dafür bot sich die Portierung der Turkschen Implementation nach Paralation Lisp an, einer plattformunabhängigen parallelen Common-Lisp-Erweiterung.

[...]