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

Kurzfassung

Das Sparse Distributed Memory (SDM) ist ein neuronaler Assoziativspeichers, der sich aus- zeichnet durch Generalisierungsf¨ ahigkeit, hochgradige Parallelisierbarkeit, Robustheit gegen Feh- ler im Speicher und Abstraktionsf¨ ahigkeit. Er erm¨ oglicht neben der Erkennung verrauschter oder teilweise verdeckter Muster die Repr¨ asentation von Sequenzen und beliebigen Graphen. In der vorliegenden Arbeit wurde eine parallele objektorientierte Klassenbibliothek f¨ ur SDM in Common-Lisp entwickelt, welche portierbar auf alle Parallelrechner ist, welche ¨

uber einen Compiler f¨ ur Paralation Lisp verf¨ ugen. Die Vorlage bildete die SDM-Bibliothek von Andreas Turk, in der Sprache *-Lisp, welche nur auf der Connection-Machine CM-2 l¨ auft. Ich habe die Software diversen Optimierungen unterzogen und um zus¨ atzliche Varianten des SDM erweitert. Die SDM-Bibliothek umfasst das Generalisierte Adressmodul von Turk, welches das ori- ginale Modell des SDM von Kanerva und die Varianten von Jaeckel (Selected-Coordinates- und Hyperplane-Design) subsumiert. Dar¨ uber hinaus wurde das Adreßmodul um das Karlsson- Modell erweitert, das Datenmodul um eine bin¨ are Matrix mit optionaler gradueller Vergesslich- keit und der SDM um die Modi Adreßverdichtung und Datenverd¨ unnung.

Inhaltsverzeichnis

1  Einleitung  1

1.1  Aufgabenstellung  1

2  Sparse Distributed Memory  2

2.1  SD-MModell nach Kanerva  2

2.1.1  Architektur  2

2.1.2  Eigenschaften und Voraussetzungen  4

2.1.3  Abstraktion  5

2.1.4  Repr asentation 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--MCodes und bin arer Datenmatrix  8

2.2.5  Karlsson-Design  11

2.2.6  Adressverdichtung  12

2.2.7  Datenverd unnung  12

2.2.8  Datenmodul mit Buckets  13

2.2.9  Multipler Bin arer Entscheidungsbaum  13

3  Verteilte Repr asentationen  17

3.1  Frames  17

3.2  Lokale und verteilte Repr asentationen  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 usselw orter  21

4.3  Vor- und Nachteile und Probleme  22

4.4  Wege zur Umgehung der Nachteile  23

5  SD-MKlassenbibliothek  24

5.1  Spezifikationen  24

5.2  Implementation  24

5.2.1  Topologie Hyperw urfel  25

5.2.2  Verteilung der Dimensionen auf die Kommunikationsphasen  25

5.2.3  Dom anenpartitionierung  26

  i  

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 asentation 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 SD-MKlassenbibliothek  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

  ii  

Abbildungsverzeichnis

2.1  Random Access Memory Kan92  2

2.2  Sparse Distributed Memory Kan92  3

2.3  Konvergenz im SDM Kan92  4

2.4  Autoassoziatives SDM: 9 verrauschte Versionen werden gespeichert und das  10.

  als Adresse eingegeben Kan92  6

2.5  Folded SDM: Eine Sequenz wurde gespeichert und mit dem verrauschten 1 Ele-  

  ment adressiert Die ausgegebene Sequenz konvergiert gegen die gespeicherte  

  Kan92  7

2.6  Selected Coordinates Aktivierungsmodell Gre00  8

2.7  Hyperplane Aktivierungsmodell  8

2.8  N-Of--MCode-SDM Tem02  9

2.9  Lesen an verrauschter Adresse: Wahrscheinlichkeitsverteilungen der Ereignisse  

  X 0 (gespeichertes Bit ist 0) und X 1 Optimaler Schwellwert im Schnittpunkt  

  Tem02  10

2.10  Informationsgehalt verschiedener Codes J B03  11

2.11  Informationsgehalt in Abh angigkeit von der Dichte J B03  11

2.12  N-Of--MCode-SDM: Kapazit at in Abh angigkeit von der Anzahl von Bitfehlern  

  J B03  12

2.13  N-Of--MCode-SDM: Kapazit at in Abh angigkeit von der Dichte J B03  13

2.14  N-Of--MCode-SDM: Kapazit at in Abh angigkeit von der Aktivierungswahrschein-  

  lichkeit J B03  14

2.15  N-Of--MCode-SDM: Kapazit at in Abh angigkeit von der Speichergr oße J B03  15

2.16  N-Of--MCode-SDM: Kapazit at in Abh angigkeit von der Datenwortbreite J B03  16

2.17  Karlsson-Aktivierungsmodell  16

3.1  Lokale Repr asentation Kan97  18

3.2  Binary Spatter Code nach Kanerva: Binding- und Chunking-Operator zur Kon-  

  struktion komplexer Datenstrukturen Kan97  20

5.1  Hyperw urfel  25

5.2  Kommunikationsmuster Schmetterling im Hyperw urfel  25

5.3  Dom anenpartitionierung von Adress- und Datenmatrix bei 16 Prozessoren  26

5.4  Austausch von Segmenten des Selektionsvektors  27

5.5  Akkumulation der Teilsummen der selektierten Zeilen der Datenmatrix pro Block  

  mit sukzessiver Intervallhalbierung  28

5.6  Gepackte Zahlen: Auf ein Hardware-Wort werden mehrere kleine W orter neben-  

  einander geschrieben  29

  iii  

Kapitel 1

Einleitung

Das Sparse Distributed Memory (SDM) ist ein neuronaler Assoziativspeichers, der sich auszeich- net durch Generalisierungsf¨ ahigkeit, hochgradige Parallelisierbarkeit, Robustheit gegen Fehler im Speicher und Abstraktionsf¨ ahigkeit. Er erm¨ oglicht neben der Erkennung verrauschter oder teilweise verdeckter Muster die Repr¨ asentation von Sequenzen und beliebigen Graphen. In der vorliegenden Arbeit wurde eine parallele objektorientierte Klassenbibliothek f¨ ur SDM in Common-Lisp entwickelt, welche portierbar auf alle Parallelrechner ist, welche ¨

uber einen Compiler f¨ ur Paralation Lisp verf¨ ugen. Die Vorlage bildete die SDM-Bibliothek von Andreas Turk, in der Sprache *-Lisp, welche nur auf der Connection-Machine CM-2 l¨ auft. Ich habe die Software diversen Optimierungen unterzogen und um zus¨ atzliche Varianten des SDM erweitert. Die SDM-Bibliothek umfasst das Generalisierte Adressmodul von Turk, welches das ori- ginale Modell des SDM von Kanerva und die Varianten von Jaeckel (Selected-Coordinates- und Hyperplane-Design) subsumiert. Dar¨ uber hinaus wurde das Adreßmodul um das Karlsson- Modell erweitert, das Datenmodul um eine bin¨ are Matrix mit optionaler gradueller Vergesslich- keit und der SDM um die Modi Adreßverdichtung und Datenverd¨ unnung.

1.1 Aufgabenstellung

Vorrangiges Ziel der vorliegenden Arbeit war eine effiziente Implementation einer hardwareun- abh¨ angigen SDM-Klassenbibliothek. Daf¨ ur bot sich die Portierung der Turkschen Implementati- on nach Paralation Lisp an, einer plattformunabh¨ angigen parallelen Common-Lisp-Erweiterung.

1

Kapitel 2

Sparse Distributed Memory

Es sollen zuerst einige theoretische Grundlagen zu diesem Speichermodell erl¨ autert werden.

2.1 SDM-Modell nach Kanerva

2.1.1 Architektur

Abbildung 2.1: Random Access Memory [Kan92]

2

3

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.2: Sparse Distributed Memory [Kan92]

Die Originalversion des SDM von Kanerva [Kan88, Kan92] ist ein 3-schichtiges neuronales Netz, aus Neuronen mit bin¨ arer Aktivierungsfunktion (Abb. 2.2). Die Eingabeschicht zerf¨ allt in

2 Gruppen f¨ ur Adresse und Eingabedatum.

Die erste Gewichtsmatrix zwischen Adresseingangsneuronen und Zwischenschicht wird Adress- matrix genannt. Ihre Eintr¨ age sind bin¨ ar, werden zuf¨ allig initialisiert und bleiben konstant (auch w¨ ahrend des Schreibens). Die Zwischenschicht heißt Selektionsvektor. Eine Komponente davon wird genau dann aktiviert (Wert 1), wenn der Hamming-Abstand zwischen der korrespondierende Zeile der Adressmatrix und dem Adressvektor einen Schwellwert R (Aktivierungsradius) nicht ¨ uberschreitet. Die Zwischenschicht besteht daher aus RBF-Neuronen (Radiale Basisfunktionen), wenn die Adressmatrixeintr¨ age unipolar (Werte 0 oder 1) sind. ¨ Aquivalent kann man auch eine bipolare (Werte -1 oder 1) Adressmatrix und lineare Neuronen verwenden.

Die 2. Gewichtsmatrix ist die Datenmatrix. Sie ist direkt mit den Eingangsneuronen f¨ ur Daten verbunden und mit den Ausgabeneuronen, welche die gelesenen Daten ausgeben. Ihre Eintr¨ age sind variabel und Elemente aus Z. Eine Zeile i der Datenmatrix wird als Lokation bezeichnet und wird aktiviert, wenn die i-te Komponente des Selektionsvektors gleich 1 ist. Das Schreiben erfolgt nach der Hebbschen Lernregel. Das Datenwort wird von unipolar nach bipolar konvertiert (0en werden durch 1en ersetzt) und dann auf jede aktivierte Lokation addiert. Beim Lesen werden alle selektierten Zeilen addiert und binarisiert, durch Vergleich mit Schwellwert 0. Datenmatrix und Adressmatrix kann man als Datenmodul bzw. Adressmodul auffassen, diese

4

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.3: Konvergenz im SDM [Kan92]

sind die Komponenten des SDM. Das Adressmodul bekommt als Eingabe einen Adressvektor x der Dimension N und gibt einen M -dimensionalen Selektionsvektor aus. Die Eing¨ ange des Da- tenmoduls sind der Selektionsvektor und ein D-dimensionaler Datenvektor y (zum Schreiben), der Ausgang ist ein Datenvektor (zum Lesen) mit ebenfalls D Dimensionen. Ein SDM ist autoassoziativ, wenn D = N ist und die Adresse selbst gespeichert wird (ξ = ζ), sonst heteroassoziativ.

2.1.2 Eigenschaften und Voraussetzungen

Es wird angenommen, daß die Komponenten sowohl der Adressvektoren x ∈ {0, 1} N als auch der Datenvektoren x ∈ {0, 1} D statistisch unabh¨ angig und mit Wahrscheinlichkeit p = 0, 5 den Wert 1 haben (Bitwahrscheinlichkeit, Dichte). Mit zunehmender Dimension verst¨ arkt sich die Tendenz zur Orthogonalit¨ at: W¨ ahrend der Erwartungswert der Differenz zweier zuf¨ alliger Vektoren 0,5 betr¨ agt, strebt die Varianz gegen 0.

Die Dimension des Selektionsvektors sollte sinnvollerweise wesentlich gr¨ oßer sein als die des Adressvektors. Der Zweck des Adressmoduls ist n¨ amlich die Transformation in einen h¨ oher- dimensionalen Raum, um die lineare Separierbarkeit der Adressen zu verbessern. Wenn N und M gen¨ ugend groß sind, werden von jeder Adresse etwa gleich viele Lokatio- nen aktiviert, in Abh¨ angigkeit vom Aktivierungsradius R. ¨

Ahnliche (kleiner Hammingabstand) Adressen haben eine große Schnittmenge der aktivierten Lokationen. Wenn zuerst ein Datenwort ζ an Adresse ξ gespeichert wird und dann an Adresse x gelesen wird, dann ist das Gewicht des Datums ζ in der Summe der aktivierten Lokationen desto gr¨ oßer, je kleiner |ξ − x| ist. Somit hat der n¨ achste Nachbar unter den Adressen der gespeicherten Daten die relative Mehrheit in der Summe. Die anderen vorkommenden Muster st¨ oren den Lesevorgang als Rauschen, auch ge- nannt Crosstalk. Da nach Voraussetzung der Erwartungswert dieses Rauschens gleich 0 und die Varianz klein ist, ist die Wahrscheinlichkeit p err , daß dieses Bit falsch rekonstruiert wird, kleiner als 0,5 (sehr klein, wenn |ξ − x| relativ klein ist und nicht zu viele Muster gespeichert sind). L¨ oschen ist m¨ oglich, indem das inverse Datenwort an die gleiche Adresse gespeichert wird. Gewichtung verschiedener Datenw¨ orter ist realisierbar durch mehrfache Speicherung desselben

Wortes. ¨

Uberlernen und graduelles Vergessen ist machbar, indem vor jeder Addition eines neuen Datenvektors auf eine Zeile der Datenmatrix die Eintr¨ age dieser zuerst um einen Faktor 0 < α < 1 skaliert wird, so dass alte W¨ orter weniger Einfluß haben und neue W¨ orter immer korrekt ausgelesen werden.

5

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Im autoassoziativen Fall hat der rekonstruierte Vektor y eine kleinere Hamming-Distanz zum gesuchten gespeicherten Vektor ξ als die eingegebene Adresse x (|ξ − x| ≥ |ξ − y|). Deshalb kann man das Ergebnis verbessern, indem man das Lesen iteriert, d.h., die Ausgabe y wird solan- ge als neue Adresse eingegeben, bis y = ξ gilt oder y i = y i+1 (Abb. 2.3). Diese Konvergenz tritt nur ein, wenn die Startadresse x sich im Attraktionsbecken um y = ξ befindet. Es gibt auch Di- vergenzzonen im {0, 1} M . Die Konvergenz-Eigenschaft macht die Fehlertoleranz des SDM aus. Im Gegensatz zu einem RAM darf die Leseadresse Fehler enthalten. Ein Anwendungsbeispiel ist die Erkennung verrauschter oder teilweise verdeckter Objekte in binarisierten Bildern. Als Software-Implementation auf einem massiven Parallelrechner bietet der SDM ein hohes Maß an Parallelisierbarkeit. Effizienter ist nat¨ urlich direkte Realisierung als Hardware. Eine positive Eigenschaft eines Hardware-SDM ist Robustheit gegen Hardwarefehler, wie bei jedem Neuronalem Netz. Wenn eine kleine Zahl von Eintr¨ agen der Daten- oder Adressmatrix fehlerhaft ist, dann nimmt nur die Kapazit¨ at ab, w¨ ahrend die Fehler maskiert werden und deshalb die Ausgabe nicht verf¨ alschen.

Diese Eigenschaften und sein Aufbau machen dieses Speichermodell biologisch plausibel, vor allem die Verschaltung des Kleinhirns weist starke ¨

Ahnlichkeiten auf.

Ein entscheidendes Kriterium zur Bewertung eines SDM oder einer Variante ist die Kapa- zit¨ at und ihrer Skalierbarkeit [Cho]. Erstere ist definiert als die maximale Anzahl von Daten, die gespeichert und korrekt gelesen werden k¨ onnen, wenn ein fester relativer Fehler := |ξ − x|/N zwischen Lese- und Schreibadresse vorgegeben ist. Die Skalierbarkeit charakterisiert, wie sich die Kapazit¨ at verh¨ alt, wenn die Anzahl der Lokationen zunimmt. Die Kapazit¨ at h¨ angt außerdem von M , N und R ab. Ein Maß f¨ ur die Kapazit¨ at ist der Signal-Rausch-Abstand. Kritisch ist die Wahl von R. R sollte auch in Abh¨ angigkeit der Anzahl T der gespeicherten Daten im voraus gew¨ ahlt werden. Ein zu kleiner Wert verkleinert die Attraktionsbecken (kleineres erlaubt), ein zu großer verschlechtert den Signal-Rausch-Abstand wegen den gr¨ oßeren ¨

Uberlappungen. Die

Kapazit¨ at nimmt rapide mit ab. Wenn = 0, dann nimmt sie mit steigender Gr¨ oße M des

SDM linear zu. Aber wenn > 0, dann w¨ achst die Kapazit¨ at nur noch sublinear mit M. Diese

schlechte Skalierbarkeit l¨ asst sich umgehen mit d¨ unnbesetzten Vektoren (siehe unten).

2.1.3 Abstraktion

Speichert man zu viele Daten an ¨

ahnlichen Adressen, dann ist korrektes Lesen, auch nach vielen Iterationen, nicht mehr gew¨ ahrleistet. Stattdessen ist das Leseergebnis ein Mittelwert der Daten. Dies kann man auch als Vorteil betrachten. Der Ausgabevektor ist eine Abstraktion, ein Prototyp einer Menge von Datenw¨ ortern. Dies entspricht einer intentionalen Beschreibung einer Konzept- klasse, d.h., eine Klasse wird durch die typischen (h¨ aufigen) Merkmale ihrer Mitglieder definiert. Beispielsweise f¨ uhrt das Speichern vieler verrauschter Versionen des gleichen (bin¨ aren) Bildes zu einer Elimination des Rauschens [Tur92].

2.1.4 Repr¨ asentation von Sequenzen

Eine naheliegende M¨ oglichkeit, Folgen von Mustern (Sequenzen) zu repr¨ asentieren, ist, jedes Element der Folge heteroassoziativ auf seinen Nachfolger abzubilden. Eine Sequenz ABCD best¨ unde so aus den Assoziationen A → B, B → C und C → D. Der Haken ist aber, daß kein Muster mehrfach in der Sequenz auftreten darf, weil sonst das nachfolgende Muster nicht eindeutig w¨ are. W¨ urde man einfach in der Sequenz ABCDBE sowohl C als auch E an der Adresse B speichern, dann w¨ urde beim Lesen an B weder C noch E ausgegeben. Abhilfe schafft das Vergr¨ ossern des Kontextes. Definiert man als Vorg¨ anger eines Zeichens eine n-stellige Teilsequenz, dann werden auch Sequenzen zul¨ assig, welche Teilfolgen der L¨ ange

6

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

auto.jpg

Abbildung 2.4: Autoassoziatives SDM: 9 verrauschte Versionen werden gespeichert und das 10. als Adresse eingegeben [Kan92]

n − 1 enthalten. Wenn z.B. n = 2, dann l¨ asst sich ABCDBE korrekt ausdr¨ ucken durch AB → C, BC → D, CD → B und DB → E. So kann man es noch nicht direkt im SDM speichern, da ja die Wortbreite der Adresse genau ein Symbol (N -dim. Vektor) betr¨ agt. Eine geeignete L¨ osung ist der sogenannte Folded SDM [Tur92, Kan92]. Er besteht aus n Teil-SDMs.

Das Lesen geht folgendermaßen vonstatten: Eine beliebige, vorher eingespeicherte Sequenz wird, beginnend an einer beliebigen Stelle, Symbol f¨ ur Symbol dem Folded SDM pr¨ asentert. Alle Teil-SDMs werden parallel mit dem gleichen Symbol adressiert. Die Ausgabe des i-ten Teil-

SDM wird um i Zeittakte verz¨ ogert. Die Ausgabe des Folded SDM ist der Mittelwert (Summe

und Schwellwertoperator) aller Ausgaben der Teil-SDMs.

Beim Schreiben wird das Nachfolgersymbol zu einer Teilsequenz in allen Teil-SDMs gespei- chert. Das i-te Symbol von hinten der Teilsequenz dient als Adresse f¨ ur den i-ten Teil-SDM. Beispiele sind in Abbildungen 2.5 und 2.4.

7

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

seq.jpg

Abbildung 2.5: Folded SDM: Eine Sequenz wurde gespeichert und mit dem verrauschten 1. Element adressiert. Die ausgegebene Sequenz konvergiert gegen die gespeicherte. [Kan92]

2.2 Varianten des SDM

2.2.1 Selected Coordinates Design nach Jaeckel

Jaeckel schlug eine Modifikation des Adressmoduls vor, das Selected Coordinates Design [Jae89a,

Jae89b] (Abb. 2.6): Die Neuronen des Selektionsvektors (Zwischenschicht) sind nicht vollst¨ andig uber k zuf¨ allig ausgew¨ ahlten Koordina- mit den Adresseingabeneuronen verbunden, sondern nur ¨ ten. Eine Lokation wird aktiviert, wenn die ausgew¨ ahlten Adressbits genau mit den Gewichten ubereinstimmen. Die Aktivierungswahrscheinlichkeit betr¨ agt daher P = 2 −k . ¨ Diese Sparsamkeit von Verbindungen ist sehr g¨ unstig sowohl f¨ ur HW- als auch SW-Implementationen. Zudem ist die biologische Plausibilit¨ at h¨ oher als beim Kanerva-Design. Die entsprechenden Zellen im Kleinhirn haben ebenfalls nur ein paar wenige Eing¨ ange. ¨ Uberraschend ist die etwa doppelte Kapazit¨ at, verglichen mit Kanervas SDM. Das h¨ angt damit zusammen, daß die gleiche Lokation von sehr verschiedenen Adressen aktiviert werden kann, so daß im autoassoziativen Fall der Crosstalk viel eher den Erwartungswert 0 besitzt als beim Kanerva-Design, wo nur ¨ ahnliche Daten in der gleiche Lokation summiert werden.

2.2.2 Hyperplane Design nach Jaeckel

Mit noch weniger Verbindungen kommt das ebenfalls von Jaeckel entwickelte Hyperplane De- sign [Jae89a, Jae89b] (Abb. 2.7) aus: Alle selektierten Koordinaten haben das Gewicht 1, und die

8

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.6: Selected Coordinates Aktivierungsmodell [Gre00]

Wahrscheinlichkeit p f¨ ur 1en in den Adressen ist viel kleiner als 0,5 (z.B. 0,1). Es handelt sich somit um einen d¨ unnbesetzten Code. Die Aktivierungswahrscheinlichkeit betr¨ agt P = p k . Ein weiterer enormer Vorteil: Wenn in die Datenmatrix auch solche d¨ unnbesetzten Vektoren (mit kleinem p) geschrieben werden, dann steigt die Kapazit¨ at dramatisch an. Z.B. bei p = 0, 1 um das 5-fache.

Dieses Modell ist eng verwandt mit dem N-Of-M-Modell (siehe unten).

Abbildung 2.7: Hyperplane Aktivierungsmodell

2.2.3 Generalisiertes Modell nach Turk

Turk vereinigte die oben genannten Modelle zum Generalisierten Modell [Tur92]: Es gibt k aus- gew¨ ahlte Koordinaten mit beliebigen bin¨ aren Gewichten, die H¨ aufigkeit f¨ ur 1en p ist beliebig und Aktivierung erfolgt, wenn die Anzahl ungleicher Koordinaten zwischen Adresse und Gewichten unterhalb der Schwelle R liegt.

Laut Turk legen Versuchsergebnisse den Schluss nahe, daß das Hyperplane Design immer noch der Spezialfall des Generalisierten Modells mit der h¨ ochsten Kapazit¨ at ist.

2.2.4 SDM mit N-Of-M-Codes und bin¨ arer Datenmatrix

Eine andere Art von d¨ unnbesetztem Code ist der N-Of-M-Code [Tem02], in dem exakt N 1en in M

einem M-dimensionalen Vektor vorkommen. Das erm¨ oglicht

N

wurde ein SDM-Modell untersucht, in dem die Vektoren an allen Ein- und Ausg¨ angen jedes

9

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.8: N-Of-M-Code-SDM [Tem02]

N

Moduls ausschließlich N-Of-M-Codes sind (Abb. 2.8). Das Adresswort ist ein D

und Ausgabe-Datenw¨ orter sind vom Typ

d m Das Adressmodul enth¨ alt wie beim Kanerva-Design eine Adressmatrix und verwendet als ¨

Ahnlichkeitsmaß zwischen einer Zeile und der Eingabeadresse das Skalarprodukt. Die Eintr¨ age der Datenmatrix sind bin¨ ar (Willshaw-Memory). Beim Schreiben wird jeder selektierte Zeilenvektor mit dem bin¨ aren Datenwort mit bitwei- sem OR verkn¨ upft. Dies ist sowohl f¨ ur SW als auch HW sehr g¨ unstig, da keine aufw¨ andigen Addierer und Integer-Z¨ ahler pro Eintrag ben¨ otigt werden. Theoretische und experimentelle Untersuchungen in [Tem02] bescheinigen diesem Modell eine exzellente Kapazit¨ at, die ann¨ ahernd linear mit der Anzahl der Lokationen skaliert, wenn die Dichte der Daten sehr klein ist (Abb. 2.12, 2.13, 2.14, 2.15, 2.16). Mit zunehmender Dichte der Datenvektoren nimmt die Kapazit¨ at ab, w¨ ahrend der Informationsgehalt nach Shannon zunimmt (Abb. 2.11). Der Informationsgehalt eines Codes ist qualitativ gesehen die Anzahl m¨ oglicher Codew¨ orter. Eine ¨

Ubersicht ¨

uber den Informationsgehalt verschiedener Codes steht in Tabelle 2.10.

Falls nur approximativ N von M 1en vorkommen sollen: Beim Lesen wird die positive Summe mit einem Schwellwert verglichen. Dieser kann fest sein, oder man verwendet eine Liste von Schwellwerten, f¨ ur jede Iteration beim konvergentem Lesen einen. Wenn der Erwartungswert der Bitfehler bekannt ist, kann der optimale Schwellwert als Schnittpunkt der Wahrscheinlichkeitsverteilungen der Ereignisse X 0 (gespeichertes Bit ist 0)

X 1 berechnet werden (Abb. 2.9) .

10

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.9: Lesen an verrauschter Adresse: Wahrscheinlichkeitsverteilungen der Ereignisse

X 0 (gespeichertes Bit ist 0) und X 1 . Optimaler Schwellwert im Schnittpunkt. [Tem02]

Falls exakt N von M 1en vorkommen sollen:

Um zu erzwingen, daß exakt m Lokationen aktiviert werden oder daß der ausgegebene Da- tenvektor genau d 1en enth¨ alt, muss jeweils eine Suche nach den m der Eingabeadresse n¨ achsten Lokationsadressen bzw. der d gr¨ oßten Komponenten des Summenregisters durchgef¨ uhrt werden. Diese Maximumsuche ben¨ otigt globale Information und verursacht daher sehr große Kommuni- kationskosten in Parallelrechnern, verglichen mit dem Schwellwertoperator, der allein mit lokaler Information auskommt. Die Maximumsuche kann aber effizient in Hardware realisiert werden mit Hilfe von Spiking Neurons [Tem02].

Eine weiter Abwandlung ist die Verwendung von Ordered-N-Of-M-Codes, in welchen ein Vektor als geordnete Menge von Indizes dargestellt wird. Der Informationsgehalt nach Shannon ist h¨ oher als beim ungeordneten N-Of-M-Code, wodurch die Kapazit¨ at sinkt. Daf¨ ur aber darf die Busbreite (Wortl¨ ange) kleiner sein.

Beim ¨ Uberladen, d.h. wenn die Anzahl gespeicherter W¨ orter die Kapazit¨ at ¨ uberschreitet, f¨ ullt

sich die Matrix immer mehr mit 1en, und auch die neuesten W¨ orter k¨ onnen allm¨ ahlich nicht mehr gelesen werden. Ein noch gr¨ oßerer Nachteil ist, daß man W¨ orter nicht l¨ oschen oder ¨ kann, wie beim SDM mit Ganzzahl-Z¨ ahlern.

Ich habe in der SDM-Bibliothek folgende L¨ osung f¨ ur graduelles Vergessen und ¨ Uberlernen implementiert: Vor dem ODERn des neuen Datums auf die selektierten Lokationen werden diese zuerst um den Faktor α ausged¨ unnt, und zwar durch Nullsetzen eines Intervalls einer Lokation, mit fester L¨ ange und zuf¨ alliger Startposition. Falls Startposition plus Intervalll¨ ange gr¨ oßer als Lokationsl¨ ange ist, dann wird der Rest des Intervalls am Anfang der Lokation fortgesetzt. Dies stellt sicher, daß alle Koordinaten mit gleicher Wahrscheinlichkeit gel¨ oscht werden. Die L¨ ange des Intervalls wird so austariert, daß eine gew¨ unschte Okkupanz (relative H¨ aufigkeit von 1en in der Matrix) konstant bleibt, und damit auch das Signal-Rausch-Verh¨ altnis. Der Extremfall α = 0 entspricht hartem ¨ Uberschreiben. Und weil die Startposition f¨ ur jede selektierte Lokation

11

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.10: Informationsgehalt verschiedener Codes [J.B03]

Abbildung 2.11: Informationsgehalt in Abh¨ angigkeit von der Dichte [J.B03]

verschieden ist, verteilt sich der Schaden, den das L¨ oschen verursacht (ein notwendiges Opfer) gleichm¨ assig auf alle Koordinaten. Dadurch werden benachbarte gespeicherte W¨ orter so wenig wie m¨ oglich degradiert.

2.2.5 Karlsson-Design

Ein besonders f¨ ur serielle Rechner und Parallelrechner mit (relativ zu M ) wenigen Prozessoren extrem schneller Aktivierungsmechanismus f¨ ur das Adressmodul wurde von Karlsson [Kar95] vorgestellt: Die Lokationen werden in A Gruppen eingeteilt, und von jeder Gruppe wird genau eine aktiviert. Der Index dieser Lokation ist ein Hash-Key, welcher mit einer sehr einfachen Hash- Funktion aus dem Adressvektor gewonnen wird: k ausgew¨ ahlte Koordinaten der Adresse werden zu einer k-stelligen Bin¨ arzahl zusammengefasst. Insgesamt gibt es M = A · 2 k Lokationen. Die Bitwahrscheinlichkeit p muss genau 0.5 betragen, damit die Aktivierungswahrscheinlichkeit aller Lokationen gleich ist und somit die Kapazit¨ at nicht absinkt.

Eine gute Eigenschaft ist, daß immer exakt A von M Lokationen aktiviert werden, mit Wahr- scheinlichkeit P = 2 −k .

Die Kapazit¨ at ist noch etwas gr¨ oßer als die des Selected-Coordinates-Design.

12

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.12: N-Of-M-Code-SDM: Kapazit¨ at in Abh¨ angigkeit von der Anzahl von Bitfehlern [J.B03]

2.2.6 Adressverdichtung

Das effizienteste SDM als Software ist die Kombination aus Karlsson-Adressmodul und bin¨ arem Datenmodul. Aber wenn man damit ein autoassoziatives SDM programmieren will, dann gibt es ein Problem: Das Karlsson-Adressmodul braucht dichtbesetzte Vektoren und das bin¨ are Daten- modul d¨ unnbesetzte.

Dazu habe ich mir 2 L¨ osungen ¨ uberlegt. Die erste L¨ osung ist f¨ ur den Fall, dass man im

autoassoziativem SDM d¨ unnbesetzte Vektoren (p 0.5) speichern will. Hier muss ein Vektor vor der Adressierung verdichtet werden.

Die Vektorverdichtung verl¨ auft nach dem folgenden einfachen Algortihmus: Die Eingabe ist ein Vektor x mit Dichte p = 2 −k . Dann wiederhole k − 1 mal: Die 2. H¨ alfte von x wird ¨ uber die

1. H¨ alfte gelegt und dann mit bitweisem ODER verkn¨ upft. Dadurch verdoppelt sich nach jeder

Iteration die Dichte, und die L¨ ange halbiert sich.

2.2.7 Datenverd ¨

unnung

Die 2. L¨ osung f¨ ur das Problem der Inkompatibilit¨ at zwischen Karlsson-Adressmodul und bin¨ arem Datenmodul ist erstens f¨ ur den Fall, dass man im autoassoziativem SDM dichtbesetzte Vektoren (p = 0.5) speichern will. Zweitens kann auch die Kapazit¨ at von heteroassoziativen SDMs erh¨ oht werden.

Hier muss ein Vektor vor dem Speichern verd¨ unnt und nach dem Lesen verdichtet werden. Der Verd¨ unnungsoperator muss also invertierbar sein. Er muss aber nicht deterministisch sein. Im Gegenteil: mehrfaches Speichern desselben Wortes in ein bin¨ ares Datenmodul mit stochastischer Verd¨ unnung erh¨ oht die Lebensdauer einer Erinnerung, wenn graduelles Vergesslichkeit aktiviert ist, und ¨ uberspeichert oder verdr¨ angt nah benachbarte Daten.

Zur Vektorverd¨ unnung habe ich mir folgenden Algorithmus ausgedacht: Eingegeben werden Vektor x und gew¨ unschter Verd¨ unnungsfaktor 2 k . Dann wiederhole k mal: W¨ ahle einen zuf¨ alli- gen dichten Vektor m als Bitmaske. Dann wird ein neuer Vektor mit der doppelten L¨ ange von x erzeugt. Dessen 1. H¨ alfte ist die Verkn¨ upfung von x mit der Bitmaske mit bitweisem AND. Dies l¨ oscht die H¨ alfte der Einsen. Die 2. H¨ alfte des neuen Vektors entsteht durch AND mit der

13

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.13: N-Of-M-Code-SDM: Kapazit¨ at in Abh¨ angigkeit von der Dichte [J.B03]

inversen Bitmaske, damit die andere H¨ alfte der Einsen gel¨ oscht wird.

2.2.8 Datenmodul mit Buckets

Eine Alternative zum additiven und bin¨ arem Datenmodul sind Buckets (Arrays oder Listen). Die Daten und Adressen werden separat in einer Tabelle gespeichert, und in den Buckets werden Indices auf Zeilen der Tabelle gespeichert.

Beim Lesen wird das Datenwort zu dem h¨ aufigsten Index in allen aktivierten Buckets aus- gegeben. Die Sicherheit, daß der gefundene Nachbar auch wirklich der n¨ achste ist, kann erh¨ oht werden, indem die Entfernungen der Adressen zu den m h¨ aufigsten Indices ¨ uberpr¨ uft werden.

Beim Schreiben wird nicht immer zu jeder Adresse, welche ein bestimmtes Bucket akti- viert, auch deren Nummer darin eingetragen, sondern nur mit einer gewissen Wahrscheinlichkeit. Somit wird effizienterweise nur eine Stichprobe der Indices in einem Bucket gespeichert. Das uberschrieben, mit der ¨ Bucket wird zyklisch (¨ ahnlich Ringpuffer) ¨ Uberschreibwahrscheinlichkeit 1/(L + 1) (L: Anzahl der Eintragungsversuche). Dies reduziert die Raum- und Zeit-Komplexit¨ at um einen konstanten Faktor.

Die Laufzeit des Lesens (nur das Pooling, nicht der Aktivierungsmechanismus) liegt in der Gr¨ oßenordnung O(AT ) = O(AT ) mit T = cT : Stichprobe der Daten, A: Anzahl aktivierter Buckets. Der Schreibvorgang (nur das Eintragen in Buckets, nicht der Aktivierungsmechanis- mus) besitzt eine Laufzeit von O(A).

2.2.9 Multipler Bin¨ arer Entscheidungsbaum

Wenn die Eingabeadressen inhomogen im Adreßraum verteilt (korreliert) sind, sinkt die Ka- pazit¨ at des Kanervaschen SDMs, weil ein Teil der Lokationen besondes stark ¨ uberladen wird und sich der Signal-Rausch-Abstand verschlechtert. In diesem Fall w¨ are ein Clustering-f¨ ahiges Adreßmodul optimal. Ein solches schlage ich vor: den Multiplen Bin¨ aren Entscheidungsbaum. Zu jeder Aktivation gibt es einen eigenen bin¨ aren Entscheidungsbaum. Jeder Entscheidungs- baum w¨ ahlt genau eine Lokation aus einem Block aus (¨ ahnlich Karlsson-Adressmodul). An je- dem inneren Knoten eines bin¨ aren Baums wird gem¨ ass dem Wert einer Koordinate der Adresse

14

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.14: N-Of-M-Code-SDM: Kapazit¨ at in Abh¨ angigkeit von der Aktivierungswahr- scheinlichkeit [J.B03]

verzweigt.

Ziele des Clusterings sind erstens m¨ oglichst gleiche Aktivierungswahrscheinlichkeit aller Buckets/Lokationen (2 −11 bei 2 11 Bl¨ attern pro Baum), und zweitens sollte der Baum ausbalan- ciert sein.

Dieses Adressmodul ist außerdem kombinierbar sowohl mit dem Kanerva- als auch mit dem Bucket-Datenmodul. Beim ersteren ist nur Offline-Training m¨ oglich, beim letzteren auch Online- Training.

N¨ aherungsweise konstante Aktivierungswahrscheinlichkeit k¨ onnte man folgendermaßen her- stellen: Wenn das System feststellt, dass in einem Bucket seit einer bestimmten Zeitperiode zu h¨ aufig geschrieben wird und in anderen zu selten, dann strukturiert sich der Baum neu, und die Datensatz-Nummern werden neu verteilt. Ein totaler Neuaufbau des optimalen Baumes kann sehr lange dauern, daher ist es ratsamer, mit suboptimalen, aber gen¨ ugend guten Strukturen Vorlieb zu nehmen, vor allem beim Online-Training.

F¨ ur das Offline-Training stelle ich zuerst einen noch nicht ausgereiften, relativ einfachen Algorithmus vor: Die bedingten Wahrscheinlichkeiten der Koordinaten werden f¨ ur jeden inneren Knoten einzeln abgesch¨ atzt. F¨ ur jeden Baum wird zuerst eine Stichprobe aus der Trainingsmenge (z.B. 100 − 1000) entnommen und evtl. auch aus der Koordinatenmenge 1, ..., n, wenn n zu gross ist (etwa > 1000). Daraus werden nun die a-priori-Wahrscheinlichkeiten berechnet und die Koordinaten nach Bias |p i − 0.5| aufsteigend angeordnet. Mit einer Roulette-Wheel-Selection wird eine Koordinate i zuf¨ allig ausgew¨ ahlt: Erzeuge q reell mit 0 ≥ q ≥ 0.5n , uniform zuf¨ allig, durchlaufe die Rangordnung von vorne nach hinten, dekrementiere q jeweils um 0.5 − |p i − 0.5| solange, bis q < 0.5 − |p i − 0.5|. Damit hat man den Wurzelknoten. Danach zerlegen wir die Trainingsmenge nach p i = 0 und p i = 1. Jetzt k¨ onnen wir aus diesen Teilmengen die bedingte Wahrscheinlichkeit (p j |p i ) sch¨ atzen und so rekursiv fortfahren, bis ein Knoten als Blattknoten

15

KAPITEL 2. SPARSE DISTRIBUTED MEMORY

Abbildung 2.15: N-Of-M-Code-SDM: Kapazit¨ at in Abh¨ angigkeit von der Speichergr¨ oße [J.B03]

geeignet ist (wenn nicht mehr als eine Maximalzahl von Daten in eine Lokation bzw. Nummern in ein Bucket geschrieben werden), bis die Maximalzahl von Buckets verbraucht ist oder eine vorgegebene maximale Tiefe des Baums erreicht ist, oder sonstige Terminierungsbedingungen erf¨ ullt sind.

Es sei darauf hingewiesen, dass es wichtig ist, jede Koordinate zuf¨ allig, aber gewichtet nach Bias, auszuw¨ ahlen und nicht die optimale Koordinate, weil sonst alle parallelen B¨ aume gleich w¨ aren.

Die Laufzeit dieses Clustering ist O(n T kA). Die Laufzeiten f¨ ur Lesen und Schreiben (nur Aktivierung) betragen O(Ah max ).

Obiger Clustering-Algorithmus hat noch ein paar Schw¨ achen, die sich ausmerzen lassen:

• Die ohnehin schon kleine Stichprobe der Trainingsmenge wird durch die rekursive Parti- tionierung immer kleiner, bis die bedingten Wahrscheinlichkeiten (pi|pk, pl, m, ...) nicht mehr sch¨ atzbar sind. Hinzuf¨ ugen weiterer Beispiel-Adressen f¨ ur jeden Knoten w¨ urde die Laufzeit exponentiell mit k wachsen lassen, und man muss schlimmstenfalls die ganze Trainingsmenge durchlaufen, um eine passende Stichprobe zu finden (O(2 k T T n A)). Ei- ne viel bessere L¨ osung ist, den originalen Algorithmus zu verwenden und T’ gen¨ ugend groß zu w¨ ahlen (2 k T , z.b. T = 100) , aber zur Berechnung der bedingten Wahrschein- lichkeiten immer nur die ersten T” heranziehen. Das senkt die Laufzeit auf O((T k + n T 2 k )A) = O((k + n )T 2 k A), was schon um einiges akzeptabler ist.

• Es entstehen sehr oft Blattknoten mit zu kleiner Aktivierungswahrscheinlichkeit und nat¨ urlich gleichzeitig andere mit zu hoher. L¨ osungsvorschlag: Opfere f¨ ur eine Teilung eines ¨

uber- vollen 1. Buckets ein 2. Bucket, und zwar das leerste, und verschiebe seinen Inhalt in ein

3. Bucket, indem noch genug Platz ist. Dabei setze den Zeiger, der noch auf das freige-

wordene Bucket 2 zeigt, auf das Bucket 3. Ersteres steht danach frei zur Verf¨ ugung, um Bucket 1 zu teilen.