Inhaltsverzeichnis

1  Einleitung  1

1.1   

Uberblick   1

1.2  Notation  3

1.3  Grundlagen  4

1.3.1  Dilatationen und Translationen  4

1.3.2  Hebb-Lernregel mit Dilatationen und Translationen  6

2  Theorie zu Hopfield-Netzen h oherer Ordnung  8

2.1  Die Neuronen  8

2.2  Die Topologie  10

2.3  Der Ausf uhr-Modus  12

2.4  Der Lern-Modus  17

2.4.1  Eine Lernregel vom Perceptron-Typ  21

2.4.2  Konvergenz des Perceptron-Lernalgorithmus  25

2.5  Beispiele zum Lernprozess  36

3  Implementierung von Hopfield-Netzen h oherer Ordnung  52

3.1  Die Wahl der Programmiersprache  52

3.2  Details zur Implementierung  53

3.2.1  Ideen, Ziele und Leistungen des L osungsansatzes  53

3.2.2  Entwurfsentscheidungen  56

3.3  Probleme bei der Implementierung  81

3.4  Anforderungen an Hard- und Software  82

3.4.1  verwendete Hardware  82

3.4.2  verwendete Software  82

4  Analyse der Perceptron-Lernregel f ur  

Hop  field-Netze h oherer Ordnung  88

4.1  Motivation der Anwendung und Analyse  88

4.2  Details der Anwendungs- und Analyseumgebung  90

4.2.1  Die Testdaten  90

i

4.2.2  Die Netzparameter  92

4.2.3  Die Programmoptionen  94

4.2.4  Der Testablauf (  

Ubersicht  )  94

4.3  Ergebnisse der Anwendung und Analyse  98

5  Zusammenfassung und Ausblick  111

A  Der Quellcode  116

A.1  Das Programm PercHop  116

A.1.1  Die Header-Datei PercHop.h  116

A.1.2  Das Haupt-Programm PercHop.c  122

A.1.3  Die Datei Windows.c  127

A.1.4  Die Datei Optionen.c  133

A.1.5  Die Datei Lernen.c  163

A.1.6  Die Datei Ausfuehren.c  171

A.2  Das Programm PattGen  179

A.2.1  Die Header-Datei PattGen.h  179

A.2.2  Das Haupt-Programm PattGen.c  181

B  Die Compiler-Optionen  191

C  Das Shell-Script Auswertung  193

D  Die Testergebnisse  195

D.1  Teil I - Training von Zufallsmustern  197

D.2  Teil II - Training von Buchstabenmustern  203

E  Die Buchstabenmuster  207

ii

Abbildungsverzeichnis   

2.1  Struktur eines Hopfield-Netzes mit vier Neuronen  11

2.2  Hopfield-Netz zum Standardbeispiel  36

3.1  Datenstruktur zu Γ, R Γ und w R (Beispiel)  59

3.2  Flussdiagramm zum Programm PercHop.c  61

3.3  Flussdiagramm zum Men upunkt Optionen  83

3.4  Flussdiagramm zum Men upunkt lernen  84

3.5  Flussdiagramm zum Men upunkt ausfuehren  85

3.6  Flussdiagramm zum Programm PattGen.c  87

4.1  Beispiel: Pattgen - Auswahl der Parameter  99

4.2  Beispiel: Pattgen - Erzeugung der Dateien  99

4.3  Beispiel: PercHop - Das Hauptmen u  100

4.4  Beispiel: PercHop - Optionen zum Training von KS06  101

4.5  Beispiel: PercHop - Trainingsphase zur Menge KS06  101

4.6  Beispiel: PercHop - Ausf uhrmodus zur Menge ABC  103

iii

Tabellenverzeichnis   

3.1  Die wichtigsten Variablen  56

3.2  Realisierung ausgew ahlter Operationen  60

3.3  Programmoptionen und Netzparameter  63

3.4  Struktur einer Trainingsdatei  72

3.5  Struktur einer Musterdatei  74

3.7  Der Parameter κ und zugeh orige Korrelationsverh altnisse  79

3.6  Struktur einer LogDatei  86

D.1  Ergebnisse: korrelierte Trainingsmuster, schwarz dominiert, Γ g3  197

D.2  Ergebnisse: korrelierte Trainingsmuster, weiß dominiert, Γ g3  198

D.3  Ergebnisse: unkorrelierte Trainingsmuster, Γ g3  199

D.4  Ergebnisse: korrelierte Trainingsmuster, schwarz dominiert, Γ g4  200

D.5  Ergebnisse: korrelierte Trainingsmuster, weiß dominiert, Γ g4  201

D.6  Ergebnisse: unkorrelierte Trainingsmuster, Γ g4  202

D.7  Ergebnisse: alle Buchstaben des Alphabets, Γ g3  203

D.8  Ergebnisse: alle Buchstaben des Alphabets, Γ g4  204

D.9  Ergebnisse: erste H alfte des Alphabets, Γ g3  205

D.10  Ergebnisse: erste H alfte des Alphabets, Γ g4  206

iv

Kapitel 1

Einleitung

1.1 ¨ Uberblick

Ein klassisches Anwendungsgebiet f¨ ur rekursive neuronale Netze stellen die sogenannten Assoziativspeicher dar. Sie geh¨ oren zu einem der Hauptforschungsgebiete im Bereich des Designs k¨ unstlicher neuronaler Netze. Eine Besonderheit von Assoziativ- oder inhaltsorientierten Speichern - im Gegensatz zu klassischen adress-orientierten Speicherkonzepten - ist, dass ¨ ahnliche Adressen zu gleicher oder zumindest ¨ ahnlicher Information f¨ uhren sollen. Durch dieses Konzept wird eine gewisse Fehlertoleranz geschaffen. Eine allgemeine Einf¨ uhrung zur Thematik der Assoziativspeicher findet sich z. B. bei Kamp und Hasler [14].

Untersucht wurden neuronale Assoziativspeicher u.a. von Grossberg [10], Anderson [1], Kohonen [15, 16], Cohen und Grossberg [6], Kosko [17, 18], Hassoun [11], Wang, Cruz und Mulligan [35, 36], Srinivasan und Chia [33], Shanmukh und Venkatesh [31], Zhang, Xu und Kwong [37], Leung [26, 27], Wang, Zhuang und Xing [34, 38], sowie Sommer und Palm [32]. Die gerade genannten Arbeiten befassen sich im wesentlichen mit dem allgemeinsten Fall von neuronalen Assoziativspeichern, den heteroassoziativen Netzen. In der vorliegenden Arbeit wollen wir uns speziell den autoassoziativen Speichern im Sinne von Hopfield [12, 13] widmen.

Die Standardaufgabe eines solchen autoassoziativen Hopfield-Netzes ist die Speicherung einer Menge von t bipolar codierten Trainingsmustern

Konkret soll das zu verwendende Hopfield-Netz so konstruiert werden, dass ein als Eingabe angelegtes Trainingsmuster x ^(s) aus der obigen Trainingsmenge zu einer Ausgabe desselben Musters x ^(s) f¨ uhrt. Trifft dies f¨ ur alle Muster der Trainingsmenge zu, so sagt man, das Netz arbeitet perfekt auf den Trainingsdaten. Idealerweise soll auch dann das Muster x ^(s) ausgegeben werden, wenn die Eingabe geringf¨ ugig verrauscht, d.h. fehlerbehaftet, war.

Neuronale Hopfield-Netze h¨ oherer Ordnung verf¨ ugen ¨ uber die genannten Eigenschaften und haben sich als besonders leistungsf¨ ahig erwiesen. Behandelt werden Netze dieses Typs u.a. von Chen, Lee, Maxwell, Sun, Lee und Giles [5], Baldi und Venkatesh [2], Giles, Griffin und Maxwell [8, 9], Psaltis, Park und Hong [28], Chao, Wang und Hung [4], sowie Fahner und Eckmiller [7]. Im Folgenden betrachten auch wir Hopfield-Netze h¨ oherer Ordnung. Zu deren Training bauen wir auf dem klassischen Perceptron-Lernalgorithmus von Frank Rosenblatt [29, 30] auf, wobei wir eine Variante f¨ ur Hopfield-Netze h¨ oherer Ordnung verwenden. Entsprechend der Verallgemeinerung der klassischen Hebbschen Lernregel durch Burkhard Lenze [20, 21], f¨ uhren wir Dilatationen und Translationen des Trainingsmuster-Raumes auch f¨ ur die Perceptron-Lernregel h¨ oherer Ordnung ein (vgl. Lenze [24]). Unser Ziel ist es, gegen¨ uber der klassischen Perceptron-Lernregel die Leistung und Flexibilit¨ at des Hopfield-Netzes im Ausf¨ uhr-Modus zu verbessern, ohne aber dessen Komplexit¨ at zu erh¨ ohen.

Der Aufbau dieser Arbeit im ¨ Uberblick:

Nach Einf¨ uhrung der verwendeten Notationen und Grundlagen beginnen wir in Kapitel 2 mit den theoretischen Betrachtungen zu Hopfield-Netzen h¨ oherer Ordnung mit Dilatationen und Translationen. Die Abschnitte 2.1 und 2.2 behandeln dabei den statischen Aufbau eines so erweiterten neuronalen Hopfield-Netzes. In Abschnitt 2.3 gehen wir auf die Dynamik dieser sog. verallgemeinerten Sigma-Pi-Hopfield-Netze ein, wobei wir zun¨ achst eine geeignete Wahl der Netzparameter voraussetzen werden. Die Bestimmung von Parametern, die zur L¨ osung eines gegebenen Assoziationsproblems geeignet sind, ist Gegenstand von Abschnitt 2.4. Dazu f¨ uhren wir zun¨ achst den Begriff der bedingt streng Γ-separierbaren Mengen ein, welcher die klassische Definition von streng linear separierbaren Mengen auf naheliegende Weise verallgemeinert. Danach lernen wir eine um Dilatationen und Translationen erweiterte Perceptron-Lernregel kennen, die wir zum Training von Hopfield-Netzen h¨ oherer

2

Ordnung verwenden werden. Ganz besonders werden wir uns der Frage widmen, unter welchen Bedingungen die vorgestellte Lernregel ¨ uberhaupt zu einer L¨ osung

f¨ uhrt. Wir werden zeigen, dass eine bedingt streng Γ-separierbare, bipolar codierte Trainingsmenge ein Terminieren des vorgestellten Perceptron-Lernalgorithmus zur Folge hat, was nach endlich vielen Lernschritten zu einer L¨ osung f¨ uhrt. Ein Ergebnis dieser Art kann als optimal im Sinne von Leung [27] bezeichnet werden. Als zentrale Ergebnisse der theoretischen Untersuchungen werden sich die Theoreme 2.3.1 und 2.4.1 erweisen. Abgeschlossen wird Kapitel 2 mit einigen von Hand nachvollziehbaren Beispielen in Abschnitt 2.5.

Kapitel 3 befasst sich mit der Implementierung der in Kapitel 2 vorgestellten Algorithmen f¨ ur die Ausf¨ uhr- und Lernphase und bereitet so eine heuristische Analyse der Problemstellung vor. Der zugeh¨ orige Quellcode ist in Anhang A zu finden.

Die Analyse der F¨ ahigkeiten und Grenzen unserer Perceptron-Lernregel mit Dilatationen und Translationen erfolgt in Kapitel 4. In Kapitel 5 fassen wir die erzielten Ergebnisse abschließend noch einmal zusammen.

1.2 Notation

In der vorliegenden Arbeit verwenden wir die Begriffe Hopfield-Netz h¨ oherer Ordnung und Sigma-Pi-Hopfield-Netz synonym. Beide Begriffe finden in der Literatur Verwendung. Aus schreibtechnischen Gr¨ unden verk¨ urzen wir diese Bezeichnungen gelegentlich weiter zu Hopfield-Netz oder einfach nur Netz. Solange nichts anderes angegeben ist, ist damit stets das in Kapitel 2 eingef¨ uhrte “verallgemeinerte Hopfield-Netz h¨ oherer Ordnung” gemeint.

Dar¨ uber hinaus f¨ uhren wir die folgenden Notationen ein:

#Γ f¨ ur eine endliche Menge Γ, bezeichne die Anzahl der Elemente in der

(w R ) R∈Γ verstehen wir dann stets einen Vektor

P(M ) bezeichne die Potenzmenge der Menge M . Die o. a. Menge Γ l¨ asst sich = Γ ⊂ P({1, 2, . . . , n}). damit auch schreiben als ∅

ubliche Euklidische Norm im IR ^γ . || · || 2 bezeichne die ¨

w ⁽²⁾ ∈ IR ^γ , bezeichne das ¨ w ⁽¹⁾ · w ⁽²⁾ f¨ ur zwei Vektoren w ⁽¹⁾ , ubliche, die Eukli-

a > 0 f¨ ur einen Vektor a ∈ IR ⁿ , ist komponentenweise zu verstehen als a k > 0 f¨ ur 1 ≤ k ≤ n.

| a| < b f¨ ur Vektoren a, b ∈ IR ⁿ , ist entsprechend komponentenweise zu verstehen als |a k | < b k f¨ ur 1 ≤ k ≤ n.

1.3 Grundlagen

Im Rahmen dieser Arbeit gehen wir davon aus, dass der Leser mit herk¨ ommlichen Hopfield-Netzen h¨ oherer Ordnung bereits vertraut ist (vgl. [14, 23] f¨ ur eine Einf¨ uhrung). Wir werden daher s¨ amtliche Definitionen und S¨ atze direkt in einer um Dilatationen und Translationen erweiterten Version formulieren und beweisen. Im n¨ achsten Abschnitt wollen wir die Idee der Dilatationen und Translationen kurz vorstellen.

1.3.1 Dilatationen und Translationen

Als Standardaufgabe werden wir ein autoassoziatives Hopfield-Netz h¨ oherer Ordnung betrachten, in dem wir eine Menge von t bipolar codierten Trainingsmustern

x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t, n ∈ IN , (1.3)

speichern und korrekt wieder abrufen wollen. Dazu haben wir innerhalb einer Lernphase geeignete sog. Sigma-Pi-Netzgewichte w R ∈ IR, R ⊂ {1, 2, . . . , n}, zu finden, mit deren Hilfe die Ausf¨ uhrphase des Netzes zum gew¨ unschten Ergebnis f¨ uhrt.

4

Um f¨ ur praktische Anwendungen die Komplexit¨ at in einem ¨ uberschaubaren Rahmen

zu halten, verwendet man nicht alle 2 ⁿ m¨ oglichen Netzgewichte w R , R ⊂ {1, . . . , n}, sondern beschr¨ ankt sich bei den Gewichten auf eine Teilmenge w R , R ∈ Γ, mit Γ ⊂ P({1, 2, . . . , n}). Diese Beschr¨ ankung bei der Wahl der Gewichte beschneidet das neuronale Netz allerdings in seiner Flexibilit¨ at und Speicherkapazit¨ at.

Verwendet man aber innerhalb des Lernprozesses und der Ausf¨ uhrphase des Netzes nicht nur die eigentlichen Trainingsvektoren

sondern f¨ uhrt zus¨ atzlich mittels

1 ≤ k ≤ n, 1 ≤ s ≤ t, eine Skalierung (Dilatation) und Verschiebung (Translation) des Trainingsraumes ein, so hat man durch die neu hinzugekommenen Dilatations-und Translationsparameter α k , d k ∈ IR, 1 ≤ k ≤ n, den Grad der Flexibilit¨ at wieder erh¨ oht, h¨ alt aber die Anzahl der Sigma-Pi-Gewichte, d. h. die Anzahl der multiplikativen synaptischen Verbindungen zwischen den Neuronen, konstant.

Diese Dilatations- bzw. Translationsparameter sind universelle, f¨ ur alle Neuronen des Netzes einheitliche Parameter, die f¨ ur konkrete Anwendungen ebenfalls geeignet zu bestimmen sind. Insbesondere werden wir noch weitere Bedingungen an die Parameter α k und d k stellen.

F¨ ur eine detailierte Analyse, wie man durch Dilatations- und Translationsparameter die Kapazit¨ at von Hopfield-Netzen h¨ oherer Ordnung erh¨ ohen kann, ohne die Komplexit¨ at im Sinne der Anzahl verwendeter Sigma-Pi-Gewichte zu vergr¨ oßern, sei auf [20, 21] verwiesen. Eine Fallstudie hierzu findet sich auch bei Lenze [22]. Die Auswirkungen von Dilatationen und Translationen im Kontext bidirektionaler Assoziativspeicher (BAM) im Sinne von Kosko [17, 18] werden in [25] untersucht.

5

1.3.2 Hebb-Lernregel mit Dilatationen und Translationen

Die Verwendung von Dilatationen und Translationen im Trainingsprozess eines neuronalen Netzes ist zuerst anhand des klassischen Hebb’schen Lernalgorithmus f¨ ur Hopfield-Netze h¨ oherer Ordnung untersucht worden. Da wir im Folgenden darauf zur¨ uckgreifen werden, stellen wir hier die Definition einer Hebb-Lernregel mit Dilatationen und Translationen zur Verf¨ ugung (vgl. [21]).

Definition 1.3.1 (verallgemeinerte Hebb-Lernregel)

Sei n ∈ IN und Γ eine nichtleere Menge von Teilmengen von {1, 2, . . . , n}. Das um Dilatationen und Translationen erweiterte Sigma-Pi-Hopfield-Netz besitze n Neuronen, #Γ Sigma-Pi-Gewichte w R , R ∈ Γ, und jeweils n Dilatations- und Translationsgewichte α k , d k ∈ IR, α k > 0, k ∈ {1, . . . , n}. Ferner sei ein freier Lernparameter λ ≥ 0 gegeben, der entsprechend dem vorliegenden Problem geeignet zu w¨ ahlen ist. Pr¨ asentiert man nun dem Netz eine Menge von t bipolar codierten Vektoren

x ⁽¹⁾ , x ⁽²⁾ , . . . , x ^(t) ∈ {−1, 1} ⁿ , (1.6)

dann bezeichnet man die Berechnungsvorschrift

als verallgemeinerte Hebb-Lernregel.

Bemerkung 1.3.1 Falls λ = 0 oder d k = 0, 1 ≤ k ≤ n, gesetzt wird, reduziert sich die verallgemeinerte Hebb-Lernregel zur ¨ ublichen Hebb-Lernregel f¨ ur Hopfield-Netze h¨ oherer Ordnung.

Die Arbeiten von Lenze (vgl. [21, 22]) haben gezeigt, dass der Ansatz mit Dilatationen und Translationen speziell bei solchen Netzen sinnvoll ist, wo die Anzahl der verwendeten Sigma-Pi-Gewichte - aus theoretischen oder praktischen Gr¨ undenvon vornherein beschr¨ ankt ist. Insbesondere gilt dies f¨ ur sog. unvollst¨ andige Netze (vgl. Def. 2.2.2).

6

Ferner hat sich ergeben, dass zumindest im Falle von stark korrelierten Eingabedaten durch eine geeignete Wahl der Dilatations- und Translationsgewichte eine deutliche Steigerung der Netzkapazit¨ at erzielt werden kann, ohne die Komplexit¨ at des Netzes uberm¨ aßig zu beeinflussen. ¨

In Kapitel 4 werden wir versuchen, ¨ ahnliche Resultate auch f¨ ur die entsprechend verallgemeinerte Perceptron-Lernregel f¨ ur Sigma-Pi-Hopfield-Netze zu erhalten.

7

Kapitel 2

Theorie zu Hopfield-Netzen

h ¨ oherer Ordnung

Ein klassisches, diskretes Hopfield-Netz im Sinne von [12, 13] ist ein rekursiv arbeitendes neuronales Netz, welches aus einer endlichen Anzahl von vollst¨ andig mit-einander verbundenen Neuronen oder Units besteht, die untereinander ¨ uber bidirektionale Verbindungen kommunizieren. In den folgenden Abschnitten werden wir den Ansatz von Hopfield verallgemeinern, indem wir Hopfield-Netze h¨ oherer Ordnung betrachten, die wir um Dilatationen und Translationen des Trainingsraumes erg¨ anzen werden. An dieser Stelle gehen wir davon aus, dass der Leser mit den herk¨ ommlichen Hopfield-Netzen h¨ oherer Ordnung bereits vertraut ist (vgl. [14, 23]).

Nach einer detailierten Beschreibung der einzelnen Komponenten eines so verallgemeinerten Hopfield-Netzes wenden wir uns der entsprechend verallgemeinerten Ausf¨ uhr-Phase des Netzes zu. Dabei orientieren wir uns an [20].

2.1 Die Neuronen

Ein einzelnes Hopfield-Neuron sammelt die Informationen an seinen Eing¨ angen, gewichtet sie, und gibt das mittels einer Transferfunktion bewertete Resultat ¨ uber seine

eigenen Ausg¨ ange weiter. Im Folgenden verwenden wir die Signum-Transferfunktion,

8

die definiert ist durch T S : IR → {−1, 0, 1}, mit 1

Wir geben nun eine formale Definition der Neuronen eines Hopfield-Netzes h¨ oherer Ordnung, wobei wir direkt die Erweiterung um Dilatationen und Translationen ber¨ ucksichtigen.

Definition 2.1.1 (verallgemeinertes Sigma-Pi-Hopfield-Neuron)

Sei n ∈ IN und Γ eine nichtleere Menge von Teilmengen von {1, 2, . . . , n}. Ein (formales) verallgemeinertes Sigma-Pi-Hopfield-Neuron ist eine Funktion κ,

κ : IR ⁿ → {−1} ⁿ ∪ {0} ⁿ ∪ {1} ⁿ , (2.2)

gegeben durch

• die Signum-Transferfunktion T S : IR → {−1, 0, 1},

• eine Menge von γ := #Γ Sigma-Pi-Gewichten w R ∈ IR, R ∈ Γ, aus welcher w = (w R ) R∈Γ ∈ IR ^γ gebildet wird, der Gewichtsvektor

• und jeweils n Dilatations- und Translationsparameter α k , d k ∈ IR, mit α k > 0, k ∈ {1, . . . , n}.

Konkret wird ein Vektor x = (x 1 , x 2, . . . , x n ) ∈ IR ⁿ durch das verallgemeinerte Sigma-Pi-Hopfield-Neuron mittels

auf den aus n identischen Komponenten bestehenden Vektor y = (y, y, . . . , y),

y ∈ {−1} ⁿ ∪ {0} ⁿ ∪ {1} ⁿ , abgebildet:

κ( x) := (T S (

¹ In der Literatur ist auch die Definition n.d. (nicht definiert) zu finden, falls ξ = 0 ist.

9

Bezeichnung: Wir nennen ein verallgemeinertes Sigma-Pi-Hopfield-Neuron auch ein verallgemeinertes Hopfield-Neuron h¨ oherer Ordnung oder ein Hopfield-Neuron h¨ oherer Ordnung mit Dilatation und Translation.

Bemerkung 2.1.1 F¨ ur α k = 1 und d k = 0, 1 ≤ k ≤ n, ergibt sich gerade das Standard-Hopfield-Neuron h¨ oherer Ordnung ohne Dilatation und Translation.

Wir kommen jetzt zum strukturellen Aufbau eines Hopfield-Netzes.

2.2 Die Topologie

Die eigentliche Struktur eines Hopfield-Netzes ist zun¨ achst einmal unabh¨ angig vom speziellen Aufbau der Neuronen. Insbesondere spielt es f¨ ur die Topologie des Netzes keine Rolle, ob Neuronen h¨ oherer Ordnung - mit oder ohne Dilatation und Translation - oder klassische McCulloch-Pitts Neuronen verwendet werden. Wir k¨ onnen die Topologie vorerst ganz allgemein definieren.

Die im Folgenden verwendeten Begriffe Knoten bzw. Vektor sind im Sinne der Graphentheorie zu verstehen. Andere ¨ ubliche Bezeichnungen hierf¨ ur sind Ecke bzw.

Kante. Abbildung 2.1 veranschaulicht, wie diese Begriffe zu deuten sind. F¨ ur eine genaue Definition sei z.B. auf [3, 23] verwiesen.

Definition 2.2.1 (Topologie eines Hopfield-Netzes)

Ein Hopfield-Netz ist ein neuronales Netz mit einer endlichen Anzahl von Knoten und Vektoren, die die folgenden Eigenschaften besitzen:

• Jeder Knoten ist sowohl Eingangs- als auch Ausgangsknoten.

• Jeder Knoten hat genau einen bidirektionalen Eingangs-/Ausgangsvektor.

• Jeder Knoten ist mit jedem anderen Knoten durch einen bidirektionalen Vektor verbunden.

• Weitere verbindende Vektoren gibt es nicht. Insbesondere besitzen die Knoten keine Verbindung zu sich selbst.

10

Abbildung 2.1: Struktur eines Hopfield-Netzes mit vier Neuronen

Konfiguriert man nun aber die Knoten der gerade eingef¨ uhrten Hopfield-Struktur mit den formalen verallgemeinerten Sigma-Pi-Hopfield-Neuronen, so gelangt man zu einem Hopfield-Netz im engeren Sinne.

Definition 2.2.2 (verallgemeinertes Sigma-Pi-Hopfield-Netz)

Ein Hopfield-Netz gem¨ aß Definition 2.2.1 mit verallgemeinerten Sigma-Pi-Hopfield-Neuronen als Knoten (nach Definition 2.1.1) nennen wir verallgemeinertes Sigma-Pi-Hopfield-Netz.

Ein verallgemeinertes Sigma-Pi-Hopfield-Netz heiße vollst¨ andig von der Ordnung r, r ∈ {1, 2, . . . , n − 1}, falls die Menge Γ aus allen Teilmengen von {1, 2, . . . , n} mit h¨ ochstens r + 1 Elementen besteht. Gibt es kein solches r, so heiße das Netz unvollst¨ andig.

Bezeichnung: Entsprechend Definition 2.1.1 nennen wir ein verallgemeinertes Sigma-Pi-Hopfield-Netz auch ein verallgemeinertes Hopfield-Netz h¨ oherer Ordnung oder ein Hopfield-Netz h¨ oherer Ordnung mit Dilatation und Translation.

Bemerkung 2.2.1 Setzt man in Definition 2.1.1 die Parameter α k := 1 und d k := 0, 1 ≤ k ≤ n, so ergibt sich gerade das Standard-Hopfield-Netz h¨ oherer Ordnung ohne Dilatation und Translation.

Wir widmen uns nun der Ausf¨ uhrphase des verallgemeinerten Hopfield-Netzes h¨ oherer Ordnung.

11

2.3 Der Ausf¨ uhr-Modus

Ein geeignet konstruiertes Hopfield-Netz mit n ∈ IN Neuronen sollte in der Lage sein, eine endliche Menge von t ∈ IN bipolar codierten Vektoren x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t, mit sich selbst zu assoziieren - selbst dann, wenn die zu erkennenden Eingabevektoren leicht gest¨ ort sind (vgl. [14, 23]). Dazu muss das Netz in seiner Ausf¨ uhr-Phase notwendigerweise f¨ ur jeden Vektor dieser Trainingsmenge einen stabilen Endzustand erreichen, die Ausf¨ uhr-Phase also terminieren.

Wir definieren nun den Ausf¨ uhr-Modus eines Hopfield-Netzes h¨ oherer Ordnung mit Dilatation und Translation, betrachten also, wie das Netz mit einem ihm ¨ ubergebenen Eingabevektor verf¨ ahrt. Dabei gehen wir zun¨ achst davon aus, dass bereits geeignete Netzparameter vorliegen, sehen also die Sigma-Pi-Gewichte, Dilatations-und Translationsparameter als gegeben an. Die folgenden Ausf¨ uhrungen basieren auf [20].

Definition 2.3.1 (verallgemeinerter Sigma-Pi-Hopfield-Ausf¨ uhr-Modus)

Sei n ∈ IN beliebig gegeben. Die Menge Γ sei nicht leer und bestehe aus #Γ = γ verschiedenen Teilmengen von {1, 2, . . . , n}. Das verallgemeinerte Sigma-Pi-Hopfield-Netz besitze n Neuronen, γ Sigma-Pi-Gewichte w R ∈ IR, R ∈ Γ, sowie jeweils n Dilatations- und Translationsparameter α k , d k ∈ IR mit α k > 0, k ∈ {1, 2, . . . , n}. Diese Gewichte bzw. Parameter des Netzes seien mit Hilfe irgendeines Lernprozesses erhalten worden (z.B. mit dem in Abschnitt 2.4.1 eingef¨ uhrten Perceptron-Lernalgorithmus).

Wird nun dem Netz im Ausf¨ uhr-Modus ein bipolarer Eingabevektor

^{[0] [0]} n ) ∈ {−1, 1} ⁿ x =: x ^[0] = (x 2 , . . . , x [0] 1 , x (2.5)

ubergeben, so erzeugt das Netz eine Folge von Vektoren ¨

^[u] f¨ ur 1 ≤ j ≤ n. Dabei bezeichne A

j

u-ten Iteration. Als Ausgabevektor liefert das Netz dann denjenigen bipolaren Vektor

x ^[v] ∈ {−1, 1} ⁿ , f¨ ur den erstmals

x ^[v] = x ^[v+1] (2.8)

f¨ ur ein v ∈ IN 0 gilt, also

^{[v] [v]} n ) ∈ {−1, 1} ⁿ . x := x ^[v] := (x 2 , . . . , x [v] 1 , x (2.9)

Bemerkung 2.3.1 F¨ ur α k = 1 und d k = 0, 1 ≤ k ≤ n, ergibt sich gerade der Standard-Hopfield-Ausf¨ uhr-Modus h¨ oherer Ordnung ohne Dilatation und Translation.

Bei der gerade beschriebenen Ausf¨ uhrdynamik des verallgemeinerten Sigma-Pi-Hopfield-Netzes werden die Neuronen zyklisch aktiviert. Dabei gehen die bereits statt-gefundenen Neuronen-Updates sofort mit in die Berechnung ein. In (2.6) wird der Faktor f¨ ur k = j ¨ ubersprungen, da die Neuronen keine Verbindung zu sich selbst unterhalten.

Definition 2.3.1 beinhaltet implizit die Behauptung, dass ¨ uberhaupt ein Index v ∈ IN 0 existiert, f¨ ur den x ^[v] = x ^[v+1] (2.10)

und damit auch

x ^[v] = x ^[v+u] , u ∈ IN , (2.11)

gilt. Dieser Behauptung gehen wir im folgenden Satz nach (vgl. [20]).

Satz 2.3.1 (Finitheit des verallgemeinerten Sigma-Pi-Hopfield-Ausf¨ uhr-Modus)

Es sei n ∈ IN und Γ eine nichtleere Menge von #Γ = γ verschiedenen Teilmengen von {1, 2, . . . , n}. Das verallgemeinerte Sigma-Pi-Hopfield-Netz besitze n Neuronen, γ Sigma-Pi-Gewichte w R ∈ IR, R ∈ Γ, sowie jeweils n Dilatations- und Translationsgewichte α k , d k ∈ IR mit α k > 0, k ∈ {1, 2, . . . , n}. Diese Netzgewichte seien mit Hilfe irgendeines Lernprozesses erhalten worden. Wird nun dem Netz im Ausf¨ uhr-Modus ein bipolarer Eingabevektor

ubergeben, dann gibt es eine Zahl v ∈ IN 0 , so dass f¨ ur die in Definition 2.3.1 ein¨

gef¨ uhrte Folge der im Hopfield-Ausf¨ uhr-Modus erzeugten Vektoren x ^[u] ∈ {−1, 1} ⁿ , u ∈ IN 0 , gilt x ^[v] = x ^[v+u] , u ∈ IN . (2.13)

Beweis:

Es sei x =: x ^[0] ∈ {−1, 1} ⁿ beliebig gegeben und die Folge

x ^[u] ∈ {−1, 1} ⁿ , u ∈ IN 0 , (2.14)

erzeugt gem¨ aß

mit

f¨ ur 1 ≤ j ≤ n.

F¨ ur einen beliebigen bipolaren Vektor x ∈ {−1, 1} ⁿ definieren wir das Energiefunktional E bez¨ uglich der Sigma-Pi-Gewichte w R , R ∈ Γ, und der Dilatations- und Translationsparameter α k , d k ∈ IR, α k > 0, k ∈ {1, . . . , n}, durch E : {−1, 1} ⁿ → IR, mit

Wir betrachten nun f¨ ur einen beliebigen Ausf¨ uhrzyklus u ∈ IN 0 speziell das j-te Neuron. Falls keines der Neuronen j ∈ {1, . . . , n} seinen (bipolaren) Zustand ¨ andert, dann ¨ andert sich auch nicht die Energie des Systems, d.h. es gilt E( x ^[u+1] ) = E( x ^[u] ). Insbesondere ist dann x ^[u+1] = x ^[u] und die Behauptung ist gezeigt.

Es sei also j ein Neuron, welches seinen Zustand wirklich ¨ andert, d.h. es gelte

^{[u+1] [u]} = x j . Die beiden Hilfsvektoren

j

^{[u+1] [u+1] [u] [u]} j+1 , . . . , x ^[u] y := (x , . . . , x j−1 , x j , x n ) (2.18)

1

und

unterscheiden sich dann nur in der j-ten Komponente. Ein Vergleich der Energien E( y) und E( z) liefert daher

E( z) − E( y)

= −

= −

= −

= −

= −α j

= −α j

^[u] Letzteres ergibt sich nach Definition von A j in (2.6).

Nach Voraussetzung hat sich die Aktivit¨ at des j-ten Neurons im Update-Schritt u

^{[u] [u+1] [u+1] [u] [u]} j = −x ge¨ andert, d.h. es ist x , und wegen (2.7) gilt x = T S (A j ), denn A

j j j

kann aufgrund des geforderten Zustandswechsels nicht Null sein. Ber¨ ucksichtigen wir noch, dass α j > 0 vorausgesetzt war, so erhalten wir schließlich

Damit ist E( z) < E( y) gezeigt, d.h. das Energieniveau hat sich bei einem einzelnen Neuronen-Update mit Zustandswechsel echt verringert. Betrachtet man nun jeweils gesamte Ausf¨ uhr-Zyklen f¨ ur alle Neuronen j ∈ {1, . . . , n}, so ergibt sich entsprechend

E( x ^[u+1] ) < E( x ^[u] ), u ∈ IN 0 , (2.22)

^{[u+1] [u]} falls mindestens ein Index j ∈ {1, 2, . . . , n} existiert, f¨ ur den x = x j gilt. Da die

j

Menge {−1, 1} ⁿ endlich ist, es also nur endlich viele Netz-Zust¨ ande gibt, kann das

15

Energiefunktional E auf den Vektoren x ^[u] ∈ {−1, 1} ⁿ , u ∈ IN 0 , aber nicht unendlich oft echt verringert werden. Es gibt also ein v ∈ IN 0 mit

Insbesondere ergibt sich daraus x

x ^[v] = x ^[v+1] , (2.24)

woraus unmittelbar auch

x ^[v] = x ^[v+u] , u ∈ IN , (2.25)

folgt.

Wir haben also gezeigt, dass der Ausf¨ uhr-Modus des Hopfield-Netzes stets in einen stabilen Endzustand m¨ undet, falls die Netzparameter den obigen Bedingungen gen¨ ugen. Diese Endzust¨ ande entsprechen den lokalen Minima des in (2.17) definierten Energiefunktionals E.

Bisher sind wir einfach von irgendwelchen, bereits bekannten Netzparametern ausgegangen. Die Sigma-Pi-Gewichte (w R ) R∈Γ und die Dilatations- bzw. Translationsparameter α k , d k , 1 ≤ k ≤ n, sind aber noch nicht auf das Erkennen einer konkreten Menge von t bipolar codierten Eingabevektoren

x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t , (2.26)

hin optimiert worden. In Abschnitt 2.4 befassen wir uns daher mit der Frage, wie man das Netz so trainieren kann, dass es im Ausf¨ uhr-Modus nicht irgendwelche, sondern m¨ oglichst nur die gew¨ unschten stabilen Zust¨ ande annimmt.

In [21] wurde dazu eine verallgemeinerte Hebb-Lernregel mit Dilatationen und Translationen verwendet (vgl. auch Abschnitt 1.3.2). Es hat sich gezeigt, dass die so trainierten verallgemeinerten Hopfield-Netze auf stark korrelierten Eingabemustern deutlich besser arbeiten als klassische Hopfield-Netze ohne Dilatationen und Translationen, die nur mit der Standard-Hebb-Lernregel trainiert wurden.

In dieser Arbeit soll eine entsprechende Verallgemeinerung der bekannten Perceptron-Lernregel untersucht werden (vgl. [29, 30]). Dazu f¨ uhren wir in Abschnitt 2.4.1 eine Perceptron-Lernregel h¨ oherer Ordnung mit Dilatationen und Translationen ein.

16

Vorher wollen wir uns aber den in Definition 2.3.1 gegebenen Ausf¨ uhr-Modus f¨ ur verallgemeinerte Hopfield-Netze h¨ oherer Ordnung noch in algorithmischer Form anschauen. Wir ¨ ubernehmen dazu die dort eingef¨ uhrten Bezeichnungen.

Algorithmus 2.3.1 (verallgemeinerter Sigma-Pi-Hopfield-Ausf¨ uhr-Modus)

u = -1

^[0] FOR i = 1 TO n DO x = x i

ⁱ DO BEGIN

END

WHILE x ^[u] = x ^[u+1] .

2.4 Der Lern-Modus

In diesem Abschnitt soll es darum gehen, wie man ad¨ aquate, zu einem Assoziationsproblem passende Netzgewichte finden kann, die f¨ ur eine perfekte Assoziationsleistung im Ausf¨ uhr-Modus sorgen. Außerdem m¨ ussen wir uns die Frage stellen, unter welchen Bedingungen solche Gewichte ¨ uberhaupt existieren. Hierzu sind einige Vor-

arbeiten n¨ otig. Wir beginnen mit einer zus¨ atzlichen Bedingung an die verwendete Grundmenge Γ. Der gesamte Abschnitt 2.4 basiert im Wesentlichen auf [24].

Definition 2.4.1 (zul¨ assige Menge)

Sei n ∈ IN. Die Menge Γ sei eine nichtleere Menge von Teilmengen von {1, 2, . . . , n}. Wir nennen Γ eine zul¨ assige Menge, falls gilt: F¨ ur alle j ∈ {1, 2, . . . , n} gibt es ein R ∈ Γ mit j ∈ R.

17

Diese zus¨ atzliche Bedingung an die Menge Γ macht Sinn, denn ein Neuron j ∈ {1, 2, . . . , n}, f¨ ur welches kein R ∈ Γ mit j ∈ R existiert, w¨ are ein isoliertes Neuron. Es h¨ atte keine Verbindung zu anderen Neuronen des Netzes, w¨ urde daher nicht am Lernvorgang teilnehmen und im Ausf¨ uhr-Modus nie seinen anf¨ anglichen Zustand ¨ andern k¨ onnen.

Wir greifen nun die Idee der streng linear separierbaren Mengen auf und verallgemeinern sie in unserem Sinne zur bedingten strengen Γ-Separierbarkeit, die wir nun definieren wollen.

Definition 2.4.2 (bedingte strenge Γ-Separierbarkeit)

Sei n ∈ IN, und Γ eine zul¨ assige Menge von Teilmengen von {1, 2, . . . , n}. Es bezeichne γ := #Γ die Anzahl der verschiedenen Teilmengen in Γ. Die Menge

x ⁽¹⁾ , x ⁽²⁾ , . . . , x ^(t) ∈ {−1, 1} ⁿ (2.27)

von bipolar codierten Vektoren heißt dann bedingt streng Γ-separierbar, falls es sog. w ^∗ ∈ IR ^γ gibt,

so dass f¨ ur alle j ∈ {1, 2, . . . , n} und alle s ∈ {1, 2, . . . , t} gilt:

Bemerkung 2.4.1 Offensichtlich kann man eine bedingt streng Γ-separierbare Menge von bipolar codierten Vektoren gem¨ aß (2.27) perfekt in einem verallgemeinerten Hopfield-Netz h¨ oherer Ordnung speichern. Mit anderen Worten: zu jeder bedingt streng Γ-separierbaren, bipolaren Trainingsmenge existieren L¨ osungsparameter, mit denen das verallgemeinerte Sigma-Pi-Hopfield-Netz im Ausf¨ uhr-Modus perfekt auf den Trainingsdaten arbeitet.

Wir verdeutlichen Definition 2.4.2 durch ein Beispiel.

Beispiel (bedingte strenge Γ-Separierbarkeit)

F¨ ur n = 3 sei eine Menge von t = 2 bipolar codierten Eingabemustern

x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t, gegeben durch

Ferner geben wir eine Menge Γ ⊂ P({1, 2, 3}) vor ² , verm¨ oge

Γ := {{1, 2}, {1, 2, 3}} . (2.30)

Offensichtlich ist die Menge Γ zul¨ assig im Sinne von Definition 2.4.1 mit γ := #Γ = 2. Zu pr¨ ufen ist, ob die Menge der Eingabemuster bedingt streng Γ-separierbar ist.

Gesucht sind also ein δ > 0, Dilatationsparameter α i > 0, 1 ≤ i ≤ 3, reelle Translationsparameter d 1 , d 2 und d 3 mit |d i | < α i , 1 ≤ i ≤ 3, sowie reelle Sigma-Pi-Gewichte w ∗ {1,2} und w ∗ {1,2,3} , so dass die folgenden Ungleichungen f¨ ur s = 1, 2 erf¨ ullt werden:

Wir geben hier nur eine m¨ ogliche L¨ osung vor und verifizieren deren G¨ ultigkeit ³ .

Dazu seien

√ 5 − 2 ≈ 0, 236 δ := (2.32)

und

d 1 := 0 ,

d 2 := 0 , d 3 := 2 ,

gegeben.

² Es bezeichnet P(M ) die Potenzmenge von M .

³ Diese Werte ergeben sich aus der Anwendung der verallgemeinerten Hebb-Lernregel h¨ oherer Ordnung, auf die in Abschnitt 1.3.2 kurz eingegangen wurde. Vgl. hierzu auch [21]. Der Wert f¨ ur δ wurde geeignet gew¨ ahlt.

19

Mit diesen Werten gilt f¨ ur:

j = 1, s = 1 :

j = 1, s = 2 :

j = 2, s = 1 :

j = 2, s = 2 :

j = 3, s = 1 :

j = 3, s = 2 :

Die Menge

2.4.1 Eine Lernregel vom Perceptron-Typ

Wir bauen im Folgenden auf der Idee von Frank Rosenblatt auf (vgl. [29, 30]) und f¨ uhren Dilatationen und Translationen f¨ ur eine Lernregel vom Perceptron-Typ ein, um verallgemeinerte Hopfield-Netze h¨ oherer Ordnung zu trainieren.

Definition 2.4.3 (verallgemeinerte Perceptron-Lernregel)

Es sei ein verallgemeinertes Sigma-Pi-Hopfield-Netz mit n ∈ IN Neuronen gegeben. Die Menge Γ sei eine zul¨ assige Menge von Teilmengen von {1, 2, . . . , n} mit α > 0

w ⁽⁰⁾ ∈ IR ^γ gegeben (Initialisierung).

Wir pr¨ asentieren nun dem Netz eine Menge von t bipolar codierten Vektoren

x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t , (2.34)

die wir formal durch die zyklische Fortsetzung

x ^(s) := x ((s−1)( mod ^t)+1) , s ∈ IN , (2.35)

zu einer unendlichen Menge von Trainingsdaten

x ^(s) ∈ {−1, 1} ⁿ , s ∈ IN , (2.36)

erweitern. Dann nennt man die Berechnungsvorschrift

f¨ ur s ∈ IN, verallgemeinerte Perceptron-Lernregel f¨ ur Hopfield-Netze h¨ oherer Ordnung.

21

Bemerkung 2.4.2

^(s) • Die Berechnung der ∆ j w R in Formel (2.37) hat f¨ ur alle R ∈ Γ und f¨ ur alle j aus der jeweiligen Menge R zu erfolgen. Es werden also s¨ amtliche Korrekturwerte vor dem Gewichtsupdate bestimmt. Das eigentliche Update kann dann synchron f¨ ur alle Gewichte durchgef¨ uhrt werden.

• F¨ ur α k = 1 und d k = 0, 1 ≤ k ≤ n, ergibt sich gerade die Standard-Version einer Perceptron-Lernregel f¨ ur Hopfield-Netze h¨ oherer Ordnung ohne Dilatation und Translation.

• Bei der gerade definierten Perceptron-Lernregel ist die Terminierung des Trainingsprozesses a priori nicht gew¨ ahrleistet. Unter welchen Bedingungen der Lernalgorithmus ¨ uberhaupt terminiert, und wann man den Lernprozess abbrechen kann, wird in Abschnitt 2.4.2 behandelt.

Was genau passiert nun bei einem Gewichts-Update? Wir betrachten dazu im

^(s−1) mit R ∈ Γ. Exemplarisch greifen wir uns nun s-ten Lernschritt ein Gewicht w

R

ein Neuron j ∈ R heraus, und beobachten, welche Auswirkung die durch j bewirkte ^{(s) (s)} ¨ Anderung ∆ j w R am Gewicht w R auf die Berechnung der Aktivierung

f¨ ur das j-te Neuron hat. Bei der Veranschaulichung dieses Lerneffektes wollen wir

ubrigen Neuronen i ∈ R, i = j, verzichten. Jedes bewusst auf die Betrachtung der ¨

Neuron tr¨ agt auf entsprechende Weise zum Gesamtupdate des Gewichtes w wobei sich die Updates aller Neuronen kumulieren. F¨ ur die folgenden Betrachtungen

^(s) R := 0, i = j, setzen. wollen wir also in (2.37) formal ∆ i w

^(s) • Gilt x j = x

x ^(s) . Alle Gewichte w R mit j ∈ R bleiben unver¨ andert, da wegen ∆ j w gilt:

^{(s) (s−1) (s) (s−1)} w R := w + ∆ j w R = w . (2.39)

R R

^(s) • Gilt x j < x

Das j-te Neuron klassifiziert falsch. Wegen x

22

^(s) Gewichts-Update der Einfluß der anderen Neuronen k ∈ R, k = j, auf A

j

uber das entsprechende Gewicht w R verringert ⁴ . F¨ ur den Summanden zur ¨

^(s) Menge R in A j gilt:

Hierbei geht ein, dass der Ausdruck (α k x

f¨ ur kein k ∈ R gleich Null werden kann.

^(s) • Gilt x j > x

Das j-te Neuron klassifiziert wieder falsch. Wegen x beim Gewichts-Update der Einfluß der anderen Neuronen k ∈ R, k = j, auf ^(s) A uber das entsprechende Gewicht w R erh¨ oht. F¨ ur den Summanden zur ¨

^{j (s)} Menge R in A j gilt jetzt entsprechend:

F¨ ur die verallgemeinerte Perceptron-Lernregel soll nun noch eine algorithmische Formulierung geben werden. Mit den Bezeichnungen aus Definition 2.4.3 erhalten wir

⁽⁰⁾ R , R ∈ Γ, also den folgenden Algorithmus. mit der Initialisierung w R := w

23

Algorithmus 2.4.1 (verallgemeinerte Perceptron-Lernregel)

FOR s = 1 TO t DO

BEGIN

END {for s}.

Bemerkung 2.4.3

• Der Algorithmus durchl¨ auft in seiner obigen Form jeden Index s der Trainingsmenge x ^(s) , 1 ≤ s ≤ t, genau einmal. Damit der Lernprozess vollst¨ andig abl¨ auft, muss man Algorithmus 2.4.1 iteriert auf die Trainingsmenge anwenden. Dies entspricht gerade der zyklischen Fortsetzung der Trainingsdaten im Sinne von Definition 2.4.3.

• Der iterierte Lernvorgang kann gestoppt werden, sobald f¨ ur t aufeinander folgende Update-Schritte s keine ¨ Anderung der Netzgewichte w R , R ∈ Γ, mehr erfolgt.

24

• Die Struktur des Algorithmus bietet es an, jeweils alle Prozesse innerhalb der drei markierten Bl¨ ocke zu parallelisieren, sofern eine geeignete Rechnerarchitektur zur Verf¨ ugung steht.

Im folgenden Abschnitt befassen wir uns mit der Frage, unter welchen Bedingungen das Perceptron-Lernverfahren terminiert. Dort werden wir auch sehen, dass das Netz mit den nach einer m¨ oglichen Terminierung erhaltenen Gewichten perfekt auf der Trainingsdatenmenge arbeitet.

2.4.2 Konvergenz des Perceptron-Lernalgorithmus

Wir wenden uns nun der wichtigen Frage zu, unter welchen Bedingungen der in Definition 2.4.3 gegebene verallgemeinerte Perceptron-Lernalgorithmus ¨ uberhaupt

terminiert. Dazu beweisen wir zun¨ achst das folgende Lemma, das wir mit einer Bemerkung einleiten wollen.

Bemerkung 2.4.4 In jedem Trainingsschritt s ∈ IN der verallgemeinerten Percep- ^(s−1) , R ∈ Γ, durch die Korrekturterme tron-Lernregel (2.37) wird ein Gewicht w

^{R (s)} R aller Neuronen j ∈ R ver¨ andert. Wir m¨ ochten an dieser Stelle noch einmal ∆ j w

^(s−1) betonen, dass ein vollst¨ andiges Update des Gewichtes w im s-ten Trainings- R

schritt des Perceptron-Lernalgorithmus also gegeben ist durch

Lemma 2.4.1 Mit den Bezeichnungen und Vorgaben von Definition 2.4.3 gilt f¨ ur alle Trainingsschritte s ∈ IN und alle R ∈ Γ die ¨ Aquivalenz

F¨ ur den Fall, dass die verallgemeinerte Perceptron-Lernregel terminiert, dass es also w ^(r) f¨ ur alle s ≥ r gibt, arbeitet das durch

das Training erhaltene Hopfield-Netz perfekt auf den Trainingsdaten (2.34).

^(s) Das Lemma besagt also unter anderem, dass ein Gewicht w R genau dann nicht

mehr ver¨ andert wird, wenn alle an diesem Gewicht beteiligten Neuronen j ∈ R ihre Assoziationen bereits korrekt beherrschen.

25

Beweis: w ^(r) f¨ ur alle s ≥ r

impliziert nach Bemerkung 2.4.4 auch

Da Γ als zul¨ assige Menge vorausgesetzt war, gibt es f¨ ur jedes j ∈ {1, 2, . . . , n} mindestens eine Menge R ∈ Γ mit j ∈ R . Daher gilt nach (2.43) f¨ ur alle j ∈ {1, 2, . . . , n}

Der verallgemeinerte Sigma-Pi-Hopfield-Ausf¨ uhrmodus findet also bereits nach einem Ausf¨ uhrschritt in der angelegten Eingabe einen stabilen Zustand, d.h. das Netz arbeitet perfekt auf den Trainingsdaten. Wir zeigen jetzt die ¨ Aquivalenz in (2.43). Dazu seien s ∈ IN und R ∈ Γ gegeben. Anhand der Kardinalit¨ at der Menge R unterscheiden wir 3 F¨ alle:

Im Fall #R = 0, also R = ∅, ist nichts zu zeigen.

Im Fall #R = 1, d.h. R = {j} f¨ ur ein j ∈ {1, 2, . . . , n}, reduziert sich (2.43) zu

Dies ist ebenfalls trivialerweise erf¨ ullt.

Wir betrachten nun den interessanteren Fall #R ≥ 2 . Dazu stellen wir fest, dass wegen α k > 0, |d k | < α k (1 ≤ k ≤ n) und

die einzelnen Faktoren (α k x

nen (vgl. (2.37)). Insbesondere haben die Terme x k ∈ {1, 2, . . . , n} dasselbe Vorzeichen, d.h. es gilt

^{(s) (s)} k · (α k x k − d k ) > 0 , 1 ≤ k ≤ n . x (2.47)

Wir benutzen dieses Ergebnis, um zu zeigen, dass auch s¨ amtliche (von Null ver- ^(s) R , j ∈ R, dasselbe Vorzeichen besitzen. Dazu gen¨ ugt es, schiedenen) Terme ∆ j

w diese Eigenschaft f¨ ur zwei beliebig gew¨ ahlte i, j ∈ R mit ∆ i w zu zeigen. Sollte es keine zwei Indizes i, j mit dieser Eigenschaft geben, so ist die Aussage trivialerweise erf¨ ullt.

26

Seien also i, j ∈ R mit ∆ i w ^(s) i = x

^{(s) (s)} R · ∆ j w ∆ i w

R

^(s) i − x = (x

= (x

> 0 .

^(s) k −d k ) = 0 f¨ ur 1 ≤ k ≤ n, Die einzelnen Absch¨ atzungen ergeben sich dabei aus (α k x der Ungleichung in (2.47) und der Eigenschaft

F¨ ur ein fest gew¨ ahltes R ∈ Γ, #R ≥ 2, haben also die Terme

f¨ ur alle j ∈ R dasselbe Vorzeichen oder sind (teilweise) gleich Null ⁵ . Letzteres ist f¨ ur das j-te Neuron genau dann der Fall, wenn es seine Assoziation bereits beherrscht,

^{(s) (s)} d.h. wenn x j = x j gilt. ^(s) Damit nun f¨ ur alle j ∈ R der Ausdruck ∆ j w R verschwindet, was ¨ aquivalent ist zu

ist es notwendig und hinreichend, dass x

Aussage (2.43) gezeigt.

Zum Beweis des n¨ achsten Satzes ben¨ otigen wir noch eine Absch¨ atzung, die wir in dem folgenden Lemma bereitstellen.

⁵ Die Updates aller Neuronen j ∈ R wirken also in derselben Richtung auf das Gewicht w R ein. Insbesondere wird ein einmal gemachtes Update nicht durch ebenfalls am Gewicht w R beteiligte “Partnerneuronen” r¨ uckg¨ angig gemacht.

27

Lemma 2.4.2 Sei n ∈ IN und R ⊂ {1, 2, . . . , n}. Gegeben seien ferner Komponen- α, ten x j ∈ {−1, 1}, x j ∈ {−1, 0, 1}, j ∈ R, sowie α.

Setzen wir noch ρ := max{1, (α k + |d k |) | 1 ≤ k ≤ n}, dann gilt die Absch¨ atzung

 



Beweis:

Wegen

 



j∈R

gen¨ ugt es,

zu zeigen.

Mit der Dreiecksungleichung, ρ ≥ 1 und #R ≤ n folgt dann

(x j − x j )

j∈R

Wir verf¨ ugen nun ¨ uber die ben¨ otigten Hilfsmittel und kommen damit zum angek¨ undigten Satz ¨ uber die Endlichkeit der verallgemeinerten Perceptron-Lernregel f¨ ur Hopfield-Netze h¨ oherer Ordnung.

Satz 2.4.1 (Hopfield-Netz mit verallgemeinerter Perceptron-Lernregel)

Gegeben sei ein verallgemeinertes Sigma-Pi-Hopfield-Netz mit n ∈ IN Neuronen. Die Menge Γ sei eine zul¨ assige Menge von Teilmengen von {1, 2, . . . , n} mit γ := #Γ. Die Trainingsmenge

x ^(s) ∈ {−1, 1} ⁿ , 1 ≤ s ≤ t , (2.56)

mit t bipolar codierten Vektoren sei bedingt streng Γ-separierbar mit Trennungs- w ^∗ ∈ IR ^γ . parametern δ > 0,

d f¨ ur das Training mit der verallgemeinerten

Perceptron-Lernregel gem¨ aß Definition 2.4.3, dann terminiert der Lernvorgang f¨ ur w ⁽⁰⁾ ∈ IR ^γ gibt es eine w ^(s) ∈ IR ^γ , s ∈ IN, gilt: w ^(r) f ¨ w ^(s) = ur alle s ≥ r . (2.57)

Das so trainierte Netz arbeitet nach diesen endlich vielen Lernschritten perfekt auf den Trainingsdaten.

Beweis:

Wie in Definition 2.4.3 eingef¨ uhrt, erweitern wir die Menge (2.56) durch zyklische Fortsetzung zu einer unendlichen Menge von Trainingsdaten

x ^(s) , s ∈ IN . (2.58)

Nach Voraussetzung ist diese Menge bedingt streng Γ-separierbar, d.h. es gibt Tren- d ∈ IR ⁿ mit w ^∗ ∈ IR ^γ , so dass f¨ ur nungsparameter δ > 0, d| <

alle j ∈ {1, 2, . . . , n} und alle s ∈ IN gilt:

α und F¨ ur diese Parameter

ρ := max{1, (α k + |d k |) | 1 ≤ k ≤ n} ≥ 1 . (2.60)

Wir betrachten nun - wegen der vorliegenden Abh¨ angigkeiten im Lernprozessgleichzeitig alle Gewichte des Netzes, und wir zeigen, dass diese Gesamtheit der Netzparameter h¨ ochstens endlich oft echt lernt. Dabei interessiert uns von allen m¨ oglichen Trainingsl¨ aufen s ∈ IN nur diejenige Teilfolge (s u ) u∈IN , s 0 := 0, f¨ ur die w ^(su) ∈ IR ^γ tats¨ achlich sich jeweils mindestens eine Komponente des Gewichtsvektors w ^(s u−1 ⁾ gilt. F¨ ur jedes u ∈ IN gebe es also ein Gewicht w ^(su) = ¨ andert, d.h. f¨ ur den

^(s u−1 ⁾ , R ∈ Γ, f¨ ur dessen Update w

R

im s u -ten Trainingsschritt gilt:

Wir werden nun zeigen, dass dies f¨ ur h¨ ochstens endlich viele u ∈ IN passieren kann. Es sei u ∈ IN beliebig gegeben und es bezeichne · 2 die Euklidische Norm im IR ^γ . Dann erhalten wir unter Ausnutzung von (2.61) und (2.37)

2 w ^(su)

2

Die Absch¨ atzung im letzten Summanden ergibt sich dabei direkt aus Lemma 2.4.2. Wir setzen unsere Berechnungen fort, und erhalten wegen #Γ ≤ 2 ⁿ weiter

w (su)

Man beachte, dass die Menge Γ als zul¨ assige Menge vorausgesetzt war. Daher gibt es f¨ ur jedes j ∈ {1, 2, . . . , n} ein R ∈ Γ mit j ∈ R , so dass beim Herausziehen

^(su) der Terme (x

^j Ausdruck

entspricht dabei gerade der Aktivierung des j-ten Neurons im s u -ten Trainingsschritt. Bei der Fallunterscheidung f¨ ur die obige Ungleichung muss man f¨ ur jedes Neuron j wie folgt argumentieren (vgl. Def. 2.4.3, (2.37)):

^{(su) (su)} • Lernt das j-te Neuron nicht, so ist insbesondere x − x = 0, d.h. der j-te

^{j j} Summand verschwindet.

^(su) • Gilt x = 1, und das j-te Neuron hat gelernt, dann musste folglich

j

31

^(su) • Gilt x

j

Insgesamt folgt induktiv aus der obigen Ungleichung

letzteres, da s 0 := 0 vorausgesetzt war.

Durch Ziehen der Wurzel ergibt sich daraus

¨ Uber die Cauchy-Schwarzsche Ungleichung erhalten wir schließlich als erstes wichtiges Ergebnis

Andererseits gilt jedoch wegen

siehe dazu (2.61), auch

w ^∗ =

Man beachte, dass beim Herausziehen der Terme (x

uber alle j ∈ {1, 2, . . . , n} l¨ auft, da Γ eine zul¨ assige Menge ist. Bei der Fallunter¨

scheidung muss man f¨ ur jedes Neuron j wieder ¨ ahnlich wie oben argumentieren. Zus¨ atzlich geht hier noch die bedingte strenge Γ-Separierbarkeit mit ein:

^(sv) • Lernt das j-te Neuron im Schritt s v nicht, so ist insbesondere x

j

d.h. der j-te Summand verschwindet. Man beachte aber, dass nach Voraussetzung in jedem Trainingsschritt s v mindestens ein lernendes Neuron j existiert.

^{(sv) (sv)} − x ∈ {±1, ±2}. F¨ ur dieses gilt dann x

j j

^(sv) • Gilt x

^j sein. Es ist dann x

Γ-Separierbarkeit der j-te Summand gr¨ oßer oder gleich δ wird.

^(sv) • Gilt x = −1, und das j-te Neuron hat gelernt, dann musste entsprechend

^{j (sv) (sv)} − x ∈ {−1, −2} sein. Mit der bedingten strengen Γ-Separierbarkeit x

j j

folgt aber wieder, dass der j-te Summand gr¨ oßer oder gleich δ wird.

Wir erhalten also als zweite wichtige Ungleichung

Aus (2.68) und (2.71) folgt nun insgesamt

Die letzte Ungleichung kann aber nur f¨ ur endlich viele u ∈ IN erf¨ ullt sein, was wir nun zeigen werden. Damit w¨ are dann die erste Aussage des Satzes bewiesen.

Formt man (2.72) unter Beachtung von u ≥ 1 und δ > 0 weiter um, so erh¨ alt man

√

bzw. (nach Division durch δ · u)

Wir unterscheiden nun zwei F¨ alle:

√

w ^∗ ≥ 0, so sch¨ atzen wir u weiter ab durch

√

√

w ^∗ < 0, so k¨ onnen wir u absch¨ atzen durch

√

In jedem Fall ist aber die rechte Seite der Ungleichungen (2.75) bzw. (2.76) endlich. Die Ungleichungen k¨ onnen daher nicht f¨ ur alle, sondern nur f¨ ur endlich viele u ∈ IN erf¨ ullt sein. Nach endlich vielen Lernschritten haben also alle Neuronen des Netzes ihren Lernvorgang beendet, d.h. die verallgemeinerte Perceptron-Lernregel f¨ ur Sigma-Pi-Hopfield-Netze terminiert.

Genauer: es gibt ein r ∈ IN, so dass f¨ ur alle s ≥ r und alle R ∈ Γ gilt:

w ^(r) ∈ IR ^γ .

Die zweite Aussage des Satzes folgt schließlich direkt mit (2.77) und Lemma 2.4.1. Das Netz arbeitet also nach endlich vielen Lernschritten perfekt auf den Trainingsdaten.

Mit dem gerade bewiesenen Satz verf¨ ugen wir also ¨ uber eine hinreichende Bedingung

f¨ ur die Terminierung des Perceptron-Lernalgorithmus mit Dilatationen und Translationen im Kontext neuronaler Hopfield-Netze h¨ oherer Ordnung. Dar¨ uber hinaus sichert der Satz - im Falle der Terminierung - eine perfekte Assoziationsleistung im verallgemeinerten Hopfield-Ausf¨ uhr-Modus, d.h. jedes Trainingsmuster x ^(s) , 1 ≤ s ≤ t, wird im Ausf¨ uhr-Modus korrekt stabilisiert.

Da der Perceptron-Lernalgorithmus nach Vorgabe von geeigneten, trennenden Dilatations- und Translationsparametern d stets eine L¨ osung findet, falls ¨ uberhaupt eine L¨ osung existiert, k¨ onnen wir die verallgemeinerte Perceptron-Lernregel als optimal im Sinne von Leung [27] auffassen.

Bemerkung 2.4.5 Wenn man bereits vor dem Training s¨ amtliche Trennungspara- w ^∗ ∈ IR ^γ f¨ur eine gegebene, bedingt streng Γ-separierbare Menge d ∈ IR ⁿ und meter

von Trainingsmustern kennt, so kann die Lern-Phase des Netzes entfallen, da man mit diesen Werten bereits ¨ uber eine L¨ osung des Assoziationsproblems verf¨ ugt.

In konkreten Anwendungen sind diese Parameter allerdings a priori nicht bekannt. Man kann einer Trainingsmenge h¨ oherer Dimension i. d. R. noch nicht einmal ihre bedingte strenge Γ-Separierbarkeit ansehen.

F¨ ur praktische Anwendungen ist daher folgendes Vorgehen erforderlich:

1. Abh¨ angig vom vorliegenden Problem ist eine geeignete zul¨ assige Menge Γ, mit Γ ⊂ P({1, 2, . . . , n}) und γ := #Γ, auszuw¨ ahlen.

2. Die Dilatations- bzw. Translationsparameter α,

w ⁽⁰⁾ ∈ IR ^γ sind mit Hilfe einer geschickten Strategie geeignet zu initialisieren.

35