Vom Neuron bis zur Boltzmann Maschine Miguel Domingo & Marco Block Seminar : Maschinelles Lernen und Markov KettenSommersemester 2002

Vom Neuron bis zur Boltzmann Maschine

Miguel Domingo & Marco Block

Seminar : Maschinelles Lernen und Markov Ketten Sommersemester 2002

von der Nervenzelle bis zum "in silico" Neuron


x1, x2, x3, ... ,xn, y {0,1}

w1, w2, w3, ... ,wn, R

Axon

DendritenZellkörper

x1

x2

xn

y

Input Output

w1

w2

wn

i=1

n

wi xi y 1 , wenn

y 0 , sonst

Erregung :

Neuron kann auch über f(x1,x2,...)Erregung berechnen

Interaktion zwischen Neuronen


Vorwärtsgerichtete Netze

x1

x2

xn

y1

y2

y3

yn

Rekursive Netze

t (Zeit)

W1 (nk) W2 (kl)

n

k

l

Assoziativspeicher


Recollection

unvollständig

verrauscht

wenige Repräsentantenwerden gespeichert

hier gibt es 256(256256) Möglichkeiten

konvergieren

Hopfieldnetz


- bidirektional- Rekursives Netz

-1/1- bipolar

Wunsch: Input-Konfiguration stabile Netzkonfiguration

- symmetrisch (wij wji) - wii 0

HopfieldnetzArbeitsprinzip


1

1 -1

0,5 0,5

0,5

23 mögl. Zustände

(-1, -1, -1)(-1, -1, 1)(-1, 1, -1)

( 1, 1, 1)...

N1 N2

N3

-1 1

1

KonfigurationN1, N2, N3

(-1, 1, 1)0,5

Erregung (N1) (11 + 11) 2

1

( 1, 1, 1)

HopfieldnetzEnergiefunktion


... ... 16 16 Bildmatrix256 dim. Vektor

12

4

256 dim. Raum

i=1

n

wij xi xj +E = ½

Energiefunktion

j=1

n

i=1

n

i xi

Analogie zu lokaler Suche

HopfieldnetzEnergiefunktion : Beweis der Konvergenz


Wir betrachten den Fall, dass xk x´k

E´ – E = (x´k– xk) ( – )wkj xj +jk

k < 0

Fall 1 : 1 – 0 <0 Fall 2 : 0 – 1 >0

• Veränderung Energie fällt• konvergiert gegen lokales Minimum stabile Konfiguration

jkE´ = ... wkj x´k xj + k x´k –

ik

wij xi xj +E = ½ jk i

k

i xi wkj xk xj +jk

k xk –

HopfieldnetzArbeitsprinzip


1

1 -1

0,5 0,5

0,5

-1 1

1

N1 N2

N3

KonfigurationN1, N2, N3

(-1, 1, 1)0,5

( 1, 1, 1)

E(t) ½[(1(-11))+(-1(11))+(1(-11))] ( 2) + (-0,5+0,5+0,5) 3,5

t

t+1

E(t+1) ½[(1(11))+(-1(11))+(1(11))] ( 2) + (0,5+0,5+0,5) 0,5

1

HopfieldnetzVeranschaulichung


3,5

0,5

Energieniveau

Attraktoren (stabile Konfigurationen)

HopfieldnetzLernen


gegeben: Vektoren x1, x2, ..., xm

Aufgabe: Finde Gewichte, für die diese Vektoren Attraktoren sind

?

0 0

0

1 1

1

N1 N2

N3

?

?

das ist ein seperater Vortrag ...

HopfieldnetzVeranschaulichung


Energieniveau

2n Konfigurationen möglich, da bipolaralso im Zahlenbeispiel 2256 !

1 2 3

aber nur 10 Attraktoren speichern ...(Aufwand : 1028 = 2560 bit)

Boltzmann - Maschine


Energieniveau

Start

Hopfield-Netz undsimulated annealingkombiniert

Boltzmann - Maschine Umschaltregel


Neuron schaltet auf xi=1 mit Wahrscheinlichkeit

E = wij xj - i j=1

n

P = 11+e-(E/T)

und auf xi=0 mit Wahrscheinlichkeit 1-P

Eine Boltzmann-Maschine mit T=0 ist gerade ein Hopfieldnetz.

Boltzmann-Maschine

0

simulated annealing

0

nur xj für jN(i) werden benötigt

Update von xi ist lokal entscheidbar!

Boltzmann - MaschineOptimierung


Problem : Boltzmann-Maschine ist zu langsam.Idee : Parallelisierung

Diagonalen sind unabhängig




Diagonalen sind unabhängig




Diagonalen sind unabhängig Zufälliges Neuron - „Updaten“









Konvergenz nicht beweisbar,aber experimentell bestes Verfahren.

Simulation


Lösung des 8-Dame Problems anhand einer Boltzmann-Maschine.

Zusammenfassung


i=1

n

wij xi xj +E = ½

Energiefunktion :

j=1

n

i=1

n

i xi

1. lokale Suche = Hopfield Netz2. simulated annealing = Boltzmann-Maschine

S = {0,1}n Konfigurationen für n Neuronen

N(u) = {u´ : u, u´ an einer Stelle unterschiedlich}

x1

x2

xn

y

w1

w2

wn

Neuron :

Literatur


Rojas: Theorie der Neuronalen Netze. Springer, 1996 Rojas: „Was können neuronale Netze?“ Artikel, 1994 Patterson: Künstliche Neuronale Netze. Pearson Education, 1997 Duda, Hart, Stork: Pattern Classification. Wiley Interscience, 2001 Korst, Aarts: Simulated Annealing and Boltzmann Maschines. John Wiley & Sons, 1990

und das Internet

sehr zu empfehlen

Documents

Vom Neuron bis zur Boltzmann Maschine Miguel Domingo & Marco Block Seminar : Maschinelles Lernen und Markov KettenSommersemester 2002