Boltzmann-Maschinen

Seminar: Neuronale Netze
Prof. Bernhard Lauth
Dimitri Thomas Ghouse
LMU München
Januar 2017
Dimitri Thomas Ghouse (LMU München)
Januar 2017
1 / 26
Gliederung
1
Generative Modelle
2
Stochastisches Hopfield-Netwerk
3
Boltzmann-Maschine
Dimitri Thomas Ghouse (LMU München)
Januar 2017
2 / 26
Gliederung
1
Generative Modelle
2
Stochastisches Hopfield-Netwerk
3
Boltzmann-Maschine
Dimitri Thomas Ghouse (LMU München)
Januar 2017
3 / 26
Motivation (1)
Ausgangssituation:
Wir besitzen einen sehr großen Fundus an (implizitem) Wissen über die Welt.
Z.B.: Intuitition über die Schwerkraft, Objekte in der Welt und wie diese sich
verhalten, komplizierte soziale Interaktionen, etc.
Langfristiges Ziel von AI & ML Forschungseinrichtungen ist es Algorithmen
zu entwickeln, die ebenfalls ein „Verständnis“ für dieses Wissen besitzen.
Großer monetärer Anreiz insbesonders für private Forschungseinrichtungen bei
Google, Facebook, Amazon, IBM, Apple
Wie soll das Ziel erreicht werden?
1) Bessere & schnellere Hardware
2) Bessere Modelle und Algorithmen
3) Größere Mengen an Daten
Dimitri Thomas Ghouse (LMU München)
Januar 2017
4 / 26
Motivation (2)
Daten:
Aktuell brauchen „Machine Learning“ Algorithmen sehr viele Daten - vor allem
„gekennzeichnete“ Daten (labeled) um trainiert zu werden.
Allerdings liegt der Großteil der Information und Daten - ob in physischer oder
digitaler Form - in nicht gekennzeichneter Form dar.
Lernform und Modell:
Supervised Learning:
- Braucht gekennzeichnete Datensätze
Z.B.: MNIST Datensatz
- Ziel: richtige Klassifikation von Bildern
nach Training
⇒ Diskriminitive Modelle: p(Y |X )
Vorteile & Nachteile:
Unsupervised Learning:
- Ungekezeichnete Datensätze → Vorteil
- Ziel: Modell lernt selbstständig Repräsentationen (Features) aus Daten
⇒ Generative Modelle: p(X )
(„2016 Jahr generativer Modelle“ &
„Unsupervised Learning: The Next Frontier in AI - Yann LeCun“)
Supervised Modelle sind (aktuell) performanter als unsupervised Modelle
Kennzeichnen von Daten ist aufwenig & teuer
Langfristig nicht der richtige Pfad zu besseren und anwendungsunabhängigen
Algorithmen
Dimitri Thomas Ghouse (LMU München)
Januar 2017
5 / 26
Grundlagen (1) - Diskriminitive Modelle
Modellierung der bedingten „Wahrscheinlichkeitsverteilung“ p(Y|X):
Gegeben X prognostiziere bzw. klassifiziere Y
Bsp.: Lineare Regression, SVM, ~Neuronale Netze:
Abbildung: Lineare Regression
Abbildung: Vanilla neuronales Netz
[https://de.wikipedia.org/wiki/Lineare_Regression]
[http://pille.iwr.uni-heidelberg.de/~ocr01/images2/nnet.png]
Dimitri Thomas Ghouse (LMU München)
Januar 2017
6 / 26
Grundlagen (2) - Generative Modelle
Ziel:Lernen der Wahrscheinlichkeitsverteilung p(X):
Boltzmann Maschinen (BM)
Probabilistische Graphische Modelle (PGM)
Generative Adversarial Network (GAN) - aktuelles Forschungsinteresse
Warum die (gemeinsame) Wahrscheinlichkeitsverteilung?
Modellierung des datengenerierenden Prozesses → Möglichkeit neue
(gekennzeichnete!) Datenpunkte generieren zu können
Evtl. bessere Generalisierung
Idee der Datenkompression / Feature Generierung → Hidden Units (später)
Dimitri Thomas Ghouse (LMU München)
Januar 2017
7 / 26
Grundlagen (3) - Generative Modelle
Abbildung: Intuition: Wahrscheinlichkeitsraum von Bildern:
[https://openai.com/blog/generative-models/]
^
p(x): gelernte Verteilung
p(x): wahre Verteilung
⇒ Wie lerne ich die Verteilung des „Bilderraums?
⇒ Wie lerne ich die Verteilung mit einer Boltzmann Maschine?
Dimitri Thomas Ghouse (LMU München)
Januar 2017
8 / 26
Gliederung
1
Generative Modelle
2
Stochastisches Hopfield-Netwerk
3
Boltzmann-Maschine
Dimitri Thomas Ghouse (LMU München)
Januar 2017
9 / 26
Wiederholung: Deterministisches Hopfield-Netz
Binärer Zustandsvektor: V S = [v1s , v2s , · · · , vNs ],
vi ∈ (0, 1) oder vi ∈ (−1, 1)
Anzahl der Units: N
Mögliche Zustandsvektoren: S = 2N
Globale Energie
P einer Konfiguration:
vi vj wij
E (v ) = −
i<j
Speicherung eines Zustandsvektors: wij = vi vj
für (−1, 1)
Energy Gap: 4Ei = Ei (−1) − Ei (+1) =
P
vj wij
j
Update-Regel für Unit vi : wenn
4Ei < 0 → vi = −1, sonst vi = 1
Abbildung: Hopfield-Netz mit fünf
Units
Festellung:
System deterministisch
Keine Veränderung des aktuellen
Zustandsvektors sobald Energieminimum
erreicht ist
Dimitri Thomas Ghouse (LMU München)
[https://1.bp.blogspot.com/-3htp4rq2460/uf8f0ddyzci
/aaaaaaaaadm/jlggxzf0cws/s1600/hopfieldarchitecture.png]
Januar 2017
10 / 26
Hopefield-Netzwerke - Optimierungsproblem
Feststellung: Hopfield-Netzwerke minimieren eine Energiefunktion.
Frage: Kann deswegen ein Hopfield-Netzwerk auf Optimierungsaufgaben
angewendet werden?
Abbildung: Problem des Handlungsreisenden
Dimitri Thomas Ghouse (LMU München)
[http://examples.gurobi.com/traveling-salesman-problem/screenshot.png]
Januar 2017
11 / 26
Hopefield-Netzwerke - Problem des Handlungsreisenden
Problem des Handlungsreisenden
Optimierungsproblem unter Nebenbedingungen:
Finde die kürzeste Route, die genau ein Mal durch jede Stadt verläuft
Für N Städte existieren (n−1)!
verschiedene Rundreisen
2
bei 18 Städten beträgt die Anzahl verschiedener Rundreisen > 177 Billionen
Optimierungsproblem gehört zu NP-Schwer
Idee:
Geeignete Gewichtsmatrix wählen:
1) Energiefunktion ist nur dann minimiert, wenn eine zulässige Route gefunden
ist
2) Gewichte kodieren Abstände zwischen Städten
N 2 Units
Bsp.: vier Städte
[David MacKay: Information Theory, Inference, and Learning Algorithms]
Dimitri Thomas Ghouse (LMU München)
Januar 2017
12 / 26
Stochastische Units (1)
Frage: Wie kann eine Wahrscheinlichkeitsverteilung mit Hilfe eines
Hopfield-Netzes generiert werden?
Idee: Stochastische Update-Regel für Unit vi :
pi (+1) =
1
1+e
,
−4E /T
i
X
4Ei = Ei (−1) − Ei (+1) =
vj wij
j
T: Temperatur, steuert das zufällige Wechsel
einer Unit von −1 zu 1 und umgekehrt
stochastisches Netzwerk ⇒ keine endgültige
Konfiguration des Zustandsvektors
vorhanden
Thermales Gleichgewicht: Verhältnis
zwischen eingeschalteten und
ausgeschalteten [v1s , v2s , · · · , vNs ] Units ändert Abbildung: Sigmoidfunktion für
sich nicht. ⇒ „stochastisches“
verschiedene Werte von T
Gleichgewicht
[http://www.beigebag.com/images/sigmoic/sigmoic_half1.jpg]
Dimitri Thomas Ghouse (LMU München)
Januar 2017
13 / 26
Stochastische Units (2) - Simulated Annealing
Problem: Algorithmus kann in lokalen Minima „stecken“ bleiben
Ausweg: Simulated Annealing (Kirkpatrick et al., 1983)
Idee:
1
2
3
Abbildung: Temperatur: Auswirkungen auf
Übergangswahrscheinlichkeiten [Coursera, Geoffrey Hinton, Neural
Nets for Machine Learning, Chapter 11]
Starte mit hoher
Temperatur
Netzwerk solange „laufen“
lassen, bis thermales
Gleichgewicht erreicht
wurde
Temperatur verringern und
Netzwerk wieder laufen
lassen
Für T = 0 ergibt sich das
(deterministische)
Hopfield-Netzwerk
Im Folgenden: T = 1
Dimitri Thomas Ghouse (LMU München)
Januar 2017
14 / 26
Energiefunktion (1)
Neues Paradigma - Energiebasiertes Modell:
Anstelle einer Speicheraufgabe wie im Hopfield-Netzwerk soll das
stochastische Netzwerk eine Verteilung generieren
Wahrscheinlichkeit für den Zustand V k :
P(V k ) =
k
e −E (V )
S
P
l
e −E (V )
l=1
Partitionsfunktion bzw. Normalisierungskonstante: Z =
S
P
e −E (V
l
)
l=1
Wahrscheinlichkeitsverteilung hängt alleine von der Energie eines Zustandes
V S ab
Energiefunktion hängt von den jeweiligen Gewichten wij ab
Dimitri Thomas Ghouse (LMU München)
Januar 2017
15 / 26
Energiefunktion (2)
Energiebasierte Modelle:
−E (V k )
e
Wahrscheinlichkeit für den Zustand V k : P(V k ) = P
S
e −E (V l )
l=1
Vk
1
2
3
4
5
6
7
8
v1
0
0
0
0
1
1
1
1
v2
0
0
1
1
0
0
1
1
v3
0
1
0
1
0
1
0
1
−E(VS )
0
0
0
1
0
1
1
3
S
e−E(V )
1
1
1
2, 718
1
2, 718
2, 718
20,
085
P
= 32, 240
p(Vk )
0,0310
0,0310
0,0310
0,0843
0,0310
0,0843
0,084
0,622
P
=1
Tabelle: Bsp.: stochastisches Hopfield-Netz mit drei Units mit den Gewichten w=1
Dimitri Thomas Ghouse (LMU München)
Januar 2017
16 / 26
Gliederung
1
Generative Modelle
2
Stochastisches Hopfield-Netwerk
3
Boltzmann-Maschine
Dimitri Thomas Ghouse (LMU München)
Januar 2017
17 / 26
Hidden Units (1)
Limitierung der Speicherkapazität eines Hopfield-Netzwerks
Bsp.: (deterministisches) Hopfield-Netzwerk mit drei Units:
Abspeicherung folgender vier Zustände:
v1 = (1, 1, −1), v2 = (1, −1, 1), v3 = (−1, 1, 1), v4 = (−1, −1, −1)




0 1 −1
0 −1 1
0 −1  w2 = 
0 −1 
w1 = 
0
0




0 −1 −1
0 1 1
0
1  w4 = 
0 1 
w2 = 
0
0

4
0
X
⇒W =
wi = 
i=1
Dimitri Thomas Ghouse (LMU München)

0 0
0 0 
0
Januar 2017
18 / 26
Hidden Units (2)
Die Ursache liegt in der Regel wie das Hopfield-Netzwerk trainiert wird:
wij = vi vj
Es können nur Korrelationen (Momente zweiter Ordnung) zwischen zwei
Units in das Netzwerk kodiert werden.
Korrelationen zwischen zwei Pixel kodieren
keine bzw. zu wenig relevante Information
Ausweg:
1. Möglichkeit: Korrelation höherer Ordnung
einführen:
P
E =−
vi vj vk wijk
2. Möglichkeit: Einführung von Hidden Units
Abbildung: MNIST Beispielzahl
Dimitri Thomas Ghouse (LMU München)
Januar 2017
19 / 26
Hidden Units (3)
Hidden Units: Erhalten keinen direkten Input
(Analogie zu neuronalen Netzen)
Idee der Datenkompression: Hidden Units sollen
sinnvolle Features über die Daten einfangen
„Datenkompression in Zeit, Raum, Energie“
Abbildung: Boltzmann-Maschine
mit drei visible und zwei hidden
Units
Abbildung: Beispiel: Autoencoder
http://nghiaho.com/wp-content/uploads/2012/12/autoencoder_network1.png
Dimitri Thomas Ghouse (LMU München)
Januar 2017
20 / 26
Boltzmann-Maschine (1)
Boltzmann-Maschine
Geoffrey Hinton & Terry Sejnowski 1985
Hopfield-Netzwerk + stochastische Units (+ hidden Units) ⇒ Boltzmann
Maschine
P
P
P
vi vj wij −
vi hk wik −
hk hl wkl
Neue Energiefunktion: E (v , h) = −
i<j
i,k
k<l
Marginale Wahrscheinlichkeitsverteilung für die visible Units:
X
1 e −E (v )
P(v ) =
P(v , h) =
Z
h
mit Z =
X
e −E (v ,h)
v ,h
Dimitri Thomas Ghouse (LMU München)
Januar 2017
21 / 26
Boltzmann-Maschine (2)
Abbildung: Bsp.: Boltzmann-Maschine
Dimitri Thomas Ghouse (LMU München)
[Coursera, Geoffrey Hinton, Neural Nets for Machine Learning, Chapter 11]
Januar 2017
22 / 26
Lernen der Gewichte (1)
„Neural-Networks or: How I Learned to Stop Worrying and Love the Weights“
Ursprüngliches Ziel: Wie kann das stochastische Hopfield-Netz dazu
gebracht werden einer Verteilung zu ähneln? → Verändere die Gewichte wij
zwischen den Units
Log-Likelihood Ansatz
P
Leite die Verteilung P(v ) = P(v , h) =
den Gewichten ab.
∂logP(v )
∂wij
h
1 e −E (v )
Z
bzw. die Likelihood nach
= hsi sj iDaten − hsi sj iModell
si bezeichnet hier eine Unit (egal ob visible oder hidden)
hi bezeichnet den Erwartungswert
Dimitri Thomas Ghouse (LMU München)
Januar 2017
23 / 26
Lernen der Gewichte (2)
Update-Regel für die Gewichte lautet: 4wij ∝ η [hsi sj iDaten − hsi sj iModell ]
Vorgehen:
1
Positive Phase hsi sj iDaten :
1
2
3
2
Initialisiere die hidden Units zufällig und „fixiere“ einen Zustandsvektor (aus
den Daten)
Warte bis thermales Gleichgewicht erreicht wurde (Anpassung der hidden
Units)
Berechne die Statistik: hsi sj iDaten
Negative Phase hsi sj iModell :
1
2
3
Initialisiere alle Units zufällig
Warte bis thermales Gleichgewicht erreicht wurde
Berechne hsi sj iModell → Einschätzung des aktuellen Modells
Festellung
Positive Phase ähnelt der Hebbian Regel
Dimitri Thomas Ghouse (LMU München)
Januar 2017
24 / 26
Literatur & weiteres Material
Dimitri Thomas Ghouse (LMU München)
Januar 2017
25 / 26
Information Theory, Inference, and Learning Algorithms, David MacKay
[Buch]
Neural Networks - Comprehensive Foundation, Simon Haykin [Buch]
Neural Networks - A systematic Introduction, Raul Rojas [Buch]
Boltzmann Machines, Sam Roweis [kurzer Übersichtsartikel]
Neural Networks for Machine Learning, Geoffrey Hinton [Coursera
Vorlesung]
Deep Learning, Ian Goodfellow and Yoshua Bengio and Aaron Courville
[Buch, vor allem weitere generative Modelle]
Vielen Dank für die Aufmerksamkeit!
Dimitri Thomas Ghouse (LMU München)
Januar 2017
26 / 26

Download Report