Künstliche Neuronale Netze
Peter Kroyer (0626190)
Algorithms and Data Structures Group186.169 Seminar (mit Bachelorarbeit)
27. Mai 2009
Gliederung
Einführung- Definition
- Aufbau
- Arten des Lernens
Hopfield-Netze- Erklärung
- Anwendung auf TSP
Self-Organizing Feature Maps- Erklärung
- Anwendung auf TSP
Weitere Anwendungen
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Einführung
Neuronale Netze versuchen den Lernprozess zu imitieren, der im Gehirn stattfindet
Keine Nachbildung, sondern eine Abstraktion von dieser Informationsverarbeitung
. Lernfähigkeit,� . Generalisierungsfähigkeit und� . Fehlertoleranz
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
http://scienceblogs.com/neurotopia/upload/2006/07/neuron.png
Definition
Neuronales Netz = Tripel(N,V,ω)
N = Menge der Neuronen
V = sortierte Menge {(i, j) | i,j Є N}
Funktion ω : V -> R
ω(i,j) = Gewichte vom Neuron i zum Neuron j (kurz: ωi,j)
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Definition
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Propagierungsfunktion
Die Propagierungsfunktion nimmt für ein Neuron j Ausgaben oi1…oin
anderer Neuronen i1…in entgegen.
Diese werden unter Berücksichtigung der Verbingungsgewichte ωi,j zur Netzeingabe netj verarbeitet
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Definition
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Aktivierungsfunktion
Jedes Neuron besitzt einen gewissen Aktivierungszustand aj(t)
Jedem Neuron ist ein eindeutiger Schwellenwert Θ zugewiesen. Dieser markiert die Stelle der größten Steigung der Aktivierungsfunktion.
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Binäre Schwellenwertfunktion Fermifunktion
Definition
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Ausgabefunktion
Die Ausgabefunktion eines Neurons j berechnet die Werte, die an andere Neuronen, falls Verbindungen zu diesen bestehen, weitergegeben werden
Meist ebenfalls global definiert
Oft wird einfach Identität weitergegeben.
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Definition
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Aktivierungsreihenfolge
Synchrone Aktivierung
- Alle Neuronen ändern ihre Werte synchron
Asynchrone Aktivierung
- Die Neuronen ändern ihre Werte zu verschiedenen Zeitpunkten
- z.B. zufällige Ordnung
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Arten des Lernens
Neuronale Netze haben die Fähigkeit, sich Problemen durch Training vertraut zu machen und, nach ausreichendem Training, Probleme derselben Klasse lösen zu können => Generalisierung
Meist lernt das Netz, indem es Gewichte verändert
1. Unüberwachtes Lernen
Die Trainingsmenge besteht nur aus Eingabemustern. Das Netz versucht selbst, Ähnlichkeiten herauszufinden und Musterklassen zu bilden.
z.B. Self Organizing Feature Maps (SOFM)
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Arten des Lernens
2. Bestärkendes Lernen
Die Trainingsmenge besteht aus Eingabemustern. Nach erfolgtem Durchlauf wird dem Netz ein Wert zurückgegeben, ob das Ergebnis richtig oder falsch war.
3. Überwachtes Lernen
Die Trainingsmenge besteht aus Eingabemustern mit jeweiliger korrekter Lösung, so dass dem Netz nach Ausgabe ein genauer Fehlervektor zurückgegeben werden kann.
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Das Hopfieldnetz
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Das Hopfieldnetz
Besteht aus einer Menge K von untereinander vollständig verknüpften Neuronen. Diese können 2 Zustände (-1,1) einnehmen (binäre Aktivierung)
Gewichte zwischen 2 Neuronen sind symmetrisch wi,j = wj,i
Der Netzzustand kann durch einen Binärstring z Є {-1,1}K dargestellt werden
Inputstrang ist ebenfalls ein Binärstring
=> Aus diesem Inputzustand wird versucht ein Minimum zu finden (dieses wurde durch Eingabe von Trainingsbeispielen definiert)
Bei Stillstand wurde ein Minimum gefunden und ausgegeben
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Definition
Das Hopfieldnetz
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Beispiel
Das Hopfieldnetz
Die Zustandsänderung von Neuronen basiert auf Gewichten zu anderen Neuronen
3 Möglichkeiten:
- wi,j positiv: Beide Neuronen werden zur Gleichheit gedrängt.
- wi,j negativ: Beider Neuronen werden zur Unterschiedlichkeit gedrängt.
- wi,j = 0: Die beiden Neuronen beeinflussen sich nicht
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Gewichte
Das Hopfieldnetz
Mit jedem Zeitschritt werden die Zustände xk nach dem Schema
geändert. (Schwellenwert normalerweise 0)
Je nach Vorzeichen nimmt das Neuron dann den neuen Zustand 1 oder -1 an
Asynchrones Update: Es wird zufällig ein Neuron k gewählt
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Funktionsweise
Das Hopfieldnetz
Man verwendet eine Menge P von Mustereingaben p Є {-1,1}K – Diese stellen die Minima unserer Energieoberfläche dar
=> Erzeugen der Gewichtsmatrix W
Jedes Gewicht wi,j wird mittels der Formel berechnet
=> Bei Übereinstimmung wird 1 addiert, andernfalls -1
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Training
Das Hopfieldnetz
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Beispiel
Trainingsmuster (p0 – p5) Auffinden eines Minimums
Lösung des TSP mittels Hopfieldnetz
Hopfield und Tank haben 1985 das
TSP gelöst
n Städte => n!/2n verschiedene Touren
=> Matrix aus n*n Werten
Man versucht, ein Minimum (also eine gute Lösung) zu erreichen, indem man eine definierte Energiefunktion minimiert.
1 2 3 4 5A 0 0 0 1 0B 0 1 0 0 0C 0 0 1 0 0D 1 0 0 0 0E 0 0 0 0 1
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Lösung des TSP mittels Hopfieldnetz
Anwendung von Hopfield und Tank auf ein Beispiel mit 10 Städten
Insgesamt gibt es 181.440 gültige Touren für eine Tour mit 10 Städten
Das Hopfield-Netz konvergierte in 16 von 20 Versuchen. Hierbei hatten 8 Lösungen eine Abweichung von unter 3% von einer optimalen Lösung.
Inzwischen gibt es eine Reihe von weiteren Ansätzen zur Lösung des Problems des Handlungsreisenden
Z.B. gibt es Vorgehensweisen, die Simulated Annealing mit dem Hopfieldnetz kombinieren, um so den lokalen Minima zu entgehen
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Lösung
Lösung des TSP mittels Hopfieldnetz
Wilson und Pawley behaupteten 3 Jahre nach dem Erscheinen von Hopfield‘s Artikel, dass die Lösungen nicht reproduzierbar wären
H-T Vorgehensweise nicht ideal. In den meisten Fällen werden ungültige Lösungen erreicht.
Energiefunktion besitzt verschiedene ‚penalty parameters‘. Das Auffinden von Werten für diese Parameter um gültige Lösungen zu erreichen ist äußerst schwierig
Nicht jedes Minimum ist eine gültige Lösung
Bei Anwendung auf 30 Städte war die beste Lösung etwa 40% von der optimalen Lösung entfernt
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Kritik
Self Organizing Feature Maps
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature Maps
SOFMs (oder kurz SOM) arbeiten in 2 Räumen:
- Der N-dimensionale Eingaberaum
- Das G-dimensionale Gitter, das die Nachbarschaftsbeziehungen der Neuronen wiedergibt => Netztopologie
- G <= N
Eine SOM ist eine Menge K von Neuronen. Bei Eingabe eines Eingabevektors wird genau dasjenige Neuron k Є K aktiv, welches dem Eingabemuster im Eingaberaum am nächsten liegt. (Winner Takes All-Schema)
Dieses (+ weitere Nachbarn) bewegen sich dann auf den Stimulus zu
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature Maps
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Beispiel
Self Organizing Feature MapsTraining
1. Initialisierung
Start des Netzes mit zufälligen Neuronenzentren ck Є RN aus dem Eingangsraum.
2. Anlegen eines Eingangsmusters
Es wird ein beliebiger Punkt p aus dem Eingangsraum gewählt (Stimulus)
3. Abstandsmessung
Für jedes Neuron k wird der Abstand |p-ck| bestimmt
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature MapsTraining
4. Winner takes all
Es wird ein Gewinnerneuron ermittelt, welches den geringsten Abstand zu p besitzt. Folgende Bedingung muss also erfüllt sein:
5. Adaption der Zentren
Die Zentren der Neuronen werden innerhalb des Eingangsraums nach folgender Vorschrift versetzt:
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature MapsAdaption der Zentren
Topologiefunktion h(i,k,t)
- i = Gewinnerneuron k = Index t = Zeitpunkt
- Größter Wert, wenn k = i. Kleinerer Wert, je weiter k weg von i
- Nicht auf dem Eingangsraum sondern auf dem Gitter definiert
Abstand (p - ck)
Lernrate η(t)
- Es sollte gelten h * η <= 1, da die Neuronen sonst am Ziel vorbeischießen
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature MapsBeispiel
Abstandsmessung:
Topologiefunktion:
η(t) = 0,5
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Self Organizing Feature MapsWeiteres Beispiel
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
0 Iterationen 100 Iterationen 300 Iterationen
5000 Iterationen 50000 Iterationen 70000 Iterationen
Lösung des TSP mittels SOFM
Eine ungefähre Route ist gegeben: Besteht aus einem Set aus Neuronen, die einen Ring bilden.
Alle Neuronen können sich frei bewegen.
Eine Iteration besteht aus der Präsentation einer Stadt
Der Knoten, der am nähesten ist und seine Nachbarn bewegen sich auf die Stadt zu.
Eine Tour wurde gefunden wenn jede Stadt von einem Neuron auf dem Ring „eingenommen“ wurde
Zusätzlich: Creation und Deletion Rule
Bei den Testsets der TSPs, die Hopfield und Tank verwendet haben, haben sie eine gute Lösung (3% größer als Optimum) innerhalb von 2s gefunden
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Angéniol et al. (AVL)
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k02080103020102.html
Lösung des TSP mittels SOFM
Die Anzahl an Städten und an Neuronen ist gleich
Keine Creation und Deletion Rule
Conscience element: Behindert Neuronen die zu oft gewinnen.
Dadurch ist schon bei frühem Abbrechen eine fast gültige Lösung vorhanden.
Ergebnisse schlechter als bei Angéniol
Jedoch hat das Guilty Net die Vorteile, dass weniger Iterationen notwendig sind, und der Algorithmus früher abgebrochen werden kann, um eine annähernde Lösung zu erhalten
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Burke und Damany (Guilty Net – GN)
Lösung des TSP mittels SOFM
Anzahl der Neuronen ist doppelt so groß wie die Anzahl der Städte: n=2m
40% der Neuronen werden als Nachbarn mitaktiviert – wird mit der Zeit weniger
Ein inhibitor index wird definiert – hält ein Neuron davon ab, in einem Zyklus ein zweites mal gewählt zu werden
Die Neuronen werden rhombusförmig etwas rechts von dem Zentrum aller n Städte platziert
Lernrate:
Varianz der Topologiefunktion:
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
The Modified Growing Ring SOM (MGSOM)
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
The Modified Growing Ring SOM (MGSOM)
•50 Städte
•Lösung nach 30 Iterationen
'Yanping et al. (2005)‘
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Vergleich verschiedener Neuronaler Netzwerke
'Yanping et al. (2005)‘
MGSOM wurde mit verschiedenen anderen SOMs verglichen (u.a. SETSP)
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Vergleich verschiedener Neuronaler Netzwerke
'Yanping et al. (2005)‘
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Vergleich verschiedener Neuronaler Netzwerke
'Yanping et al. (2005)‘
Lösung des TSP mittels SOFM
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Vergleich verschiedener Neuronaler Netzwerke
'Yanping et al. (2005)‘
Weitere Anwendungen
Die Mehrheit der Forschung konzentriert sich auf das TSP
Jedoch wurde bei fast allen COPs versucht, diese mittels Neuronaler Netzwerke zu lösen.
Viele der Ergebnisse können sich mit traditionellen Algorithmen messen
General Assignment Problem
- 1993, Cho et al.: Hopfieldnetz entwickelt , das weniger als 100 Iterationen benötigt, unabhängig von der Größe
Constraint Satisfaction Problems
- 1987, Tagliarini and Page: Hopfieldnetz entwickelt, welches das N-Damen Problem löst
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Weitere Anwendungen
Tree Problems
- Craig et al.: Hopfieldnetz entwickelt , das das ‚degree-constrained minmum spanning tree problem‘ löst.
- Findet nur in 56% der Fällen eine gültige Lösung, aber wenn eine gefunden wurde, ist diese meist sehr nah am Optimum
Multiple TSPs
Graph Coloring Problems
Vehicle Routing Problems
.
.
.
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Vielen Dank für die Aufmerksamkeit!
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘
Literaturverzeichnis
‚Neural Networks for Combinatorial Optimization: A review of more than a decade of research‘ – Kate A. Smith (1998)
‚A new self-organizing maps strategy for solving the traveling salesman problem‘ – Yanping Bai, Wendong Zhan, Zhen Jin (2005)
‚Ein kleiner Überblick über Neuronale Netze‘ – David Kriesel (2005)
‚Genetische Algorithmen und Neuronale Netze‘ – Radu Ion (2008)
‚http://cs.uni-muenster.de/Professoren/Lippe/lehre/skripte/wwwnnscript/strfx/hop_anwendungen.html‘
Alle Bilder, sofern nicht anders angegeben, entstammen von David Kriesel (2005)
Kroyer Peter (0626190), ‘Künstliche Neuronale Netze‘