Post on 05-Apr-2015
transcript
Adaptive
Systeme-2Prof. Rüdiger Brause
WS 2011
Organisation
„Einführung in adaptive Systeme“ B-AS-1, M-AS-1• Vorlesung Dienstags 10-12 Uhr, SR9
• Übungen Donnerstags 12-13 Uhr, SR 9
„Adaptive Systeme“ M-AS-2• Vorlesung Donnerstags 10-12 Uhr, SR9
• Übungen Donnerstags 13-14 Uhr, SR 9
Gemeinsames Übungsblatt, unterteilt in 2 Teile
Ausgabe: Dienstags, Abgabe: Dienstags
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 2 -
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 3 -
Vorschau Themen
1. Einführung und Grundlagen
2. Lernen und Klassifizieren
3. Merkmale und lineare Transformationen
4. Lokale Wechselwirkungen: Konkurrentes Lernen
5. Netze mit RBF-Elementen
6. Rückgekoppelte Netze
7. Zeitdynamik und Lernen
8. Fuzzy-Systeme, Evolutionäre und genetische Algorithmen
9. Simulationstechnik
Klassifizierung
Grundlagen
Modellierung
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 4 -
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 5 -
Das Vorbild: Gehirnfunktionen
Lineares Modell Zell-Potential ~ Eingabe-Spikefrequenz Ausgabe-Spikefrequenz ~ Zellstrom
Ausgabe-Freq. y ~ Eingabe-Freq. x
• Problem: Reizähnlichkeita) b) c)
Zeit
Ähnlich zu a) ?
Ähnlich zu a) ?
Das Vorbild: Gehirnfunktionen
Kodierungsbeispiel: Neuron Nr.12, Grashüpfer Creutzig et al, J.Neurosci., 29(8), 2575-2580, 2009
Zirp-Identifikation von Männchen einer Spezies Keine Konstanz von Pausen- und Silbenlänge, Verhältnis Silben / Pausen ist entscheidend
Lösung: Längere Intervalle produzieren mehr spikes, Verhältnis bleibt invariant
Temperatur 2
Temperatur 1
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 6 -
Klassifizierung
Grundlagen
Modellierung
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 7 -
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 8 -
Modellierung formaler Neuronen
x1 x2x3
w1w2 w3
y
z
Akti-vierung
Ausgabe (Axon)
Gewichte (Synapsen)
Eingabe (Dendriten)x = (x1, ... ,xn)
w = (w1, ... ,wn)
Dendriten
Axon
Zellkörper
Synapsen
i
n
1iixw
y = S(z) z = = wTxsquashing
function
radial basis function
Ausgabefunktionen
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 9 -
Modellierung eines Neurons
Input-Output Formalisierung X={x}, Y = {y}, W = {w}
DEF Transferfunktion F: X W Y F : X
DEF Lernfunktion
DEF formales Neuron
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 10 -
Modellierung von Netzen
DEF Neuronales Netz
Ein neuronales Netz ist ein gerichteter Graph G := (K,E) aus einer
• Menge von Knoten K = {v}, den neuronalen Einheiten, und einer
• Menge von Kanten E KxK, den Verbindungen zwischen den Einheiten.
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 11 -
Ausgabefunktionen
Binäre Ausgabefunktionen
z.B. Kodierung von qual.Merkmalen rot = 1, braun = 0
y = SB(z) :=
Heavyside-Funktion
0 z 0
0 z 1
z
S B (z )S B (z )S B (z )S B (z )S B (z )S B (z )1
0
S B (z )1
-1
0 z
0 z 1-
0 z 1+y = SB(z) :=
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 12 -
Formale Neuronen
Anwendung binäre Funktion: log. Gatter
x1 x2 z=x1/2 + x2/2 X1 OR x2
0 0 z=0 0
0 1 z=½>1/3 SB=1 1
1 0 z=½>1/3 SB=1 1
1 1 z= 1>1/3 SB=1 1w1 = ½ w2 = ½ w3 = -⅓
z = w1x1+w2x2+w3x3
x1 x2x3
w1w2 w3
y
z
Veränderung: w3 = -⅓ → -⅔ : log. Gatter = ?
Schwellwertveränderung: Wechsel der Funktionalität!
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 13 -
Ausgabefunktionen
Begrenzt-lineare Ausgabefunktionen
y = SL(z,s) :=
-sz 0
szs- kz/2z
s>z z
max
max
k=zmax/2s
S L (z)1
.5
0
-s sz
y = SL(z,s) :=max
max
z z>s
kz -s z s
z z -s
k=zmax/s
s
S L (z )
z0
1
-1
-s
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 14 -
Ausgabefunktionen
Sigmoidale Ausgabefunktionen
z
0,5-
SF(z)
Fermi-Funktion, logistische Funktion
ss
0,5 -
SC(z)
Kosinus-Quetschfunktion
SF(z) := kze1
1
sowie hyperb. Tangens
ST(z) := 2SF(z)-1 = kz
kz
e1
e1
= tanh(kz)
SC(z) :=
1
1 2 1 2
0
z / 2
- / 2 < z < / 2
z - / 2
/ ( cos( / ))z
K=const
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 15 -
Formale Neuronen
ZeitmodellierungAnn.: Abfluss der Ladung aus dem Zellkörper -z/t mit sinkender Spannung proportional geringer
-z/t ~ –z(t) oder -z/t = –z(t)
* Rechnung *
t t+1 t´
Visualisierung
z(t)
A0
A
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 16 -
DEF Schicht
Schichten
x = (x1 x2 xn)
neural layer
y = (y1 y2 ym)
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 17 -
lineare Schicht
Lineare Transformation mit NN
x = (x1 x2 xn)
neurallayer
y = (y1 y2 ym)
)w,...,(w=y
) w,...,(w =y
mnm1m
1n111
x
x
y = = W·x Matrix-Multiplikation
y
y
w w
w w
x
xn
n
m mn n
1 11 1
1
1
Affine Transformationen
Erweiterung des Eingaberaums (homogene Koordinaten)
w1x1 +w2x2 + … + wnxn w1x1 +w2x2 + … + wnxn + wn+11
wTx =(w1,…,wn)(x1…,xn)T (w1,…,wn,wn+1)(x1…,xn,1)T=wTx(Skalierung, Rotation) (Skalierung, Rotation, Verschiebung)
Verschiebung eines Vektors
=
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 18 -
1 1
2 2
1 0 s x
0 1 s x
0 0 1 1
1 1
2 2
x s
x s
1
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 19 -
Affine Transformation
Affine Transformation mit NN
x = (x1 x2 xn)
neurallayer
y = (y1 y2 ym)
1 2 1
1 2 2
cos sin
sin cos
0 0 1
c c s
c c s
W =
• Drehung
• Skalierung
• Shift
cos sin 0
sin cos 0
0 0 1
1
2
c 0 0
0 c 0
0 0 1
1 0
0 1
0 0 1
1
2
s
s
Wshift Wrot Wscal =
2-dimensional
Wshift =
Wrot =
Wscal =
Affine Transformation
Klassifizierung
Grundlagen
Modellierung
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 20 -
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2009 - 21 -
Klassenbildung heute
Objekte werden durch Merkmale beschrieben z.B. qualitativ Mensch = (groß, braune Augen, dunkle Haare, nett, ...)
quantitativ Mensch = (Größe=1,80m, Augenfarbe=2, Haarfarbe=7, ...)
Idee = Form = „Klassenprototyp“
Breite
Höh
e Muster eines Objekts (Breite, Höhe) = x
Breite
c2
Höh
e
c1
Trennung von Klassen Blütensorte 1 Blütensorte 2
Klassenprototyp
Klassifizierung = Ermitteln der Geradengleichung bzw Parameter c1,c2. Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 21 -
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 22 -
Klassentrennung
Breite x1
c2
Höh
e x
2
c1
Klassentrennung durch Trenngerade mit f(x1) = x2= w1x1+w3
z<0 z=0 bzw. z = w1x1+w2x2+w3x3 = 0
z>0 mit x3 := 1n
i ii 1
w xMit z = = wTx
Klassenentscheidung
y = S(z) =
2 Klasse aus 0z 1
1 Klasse aus 0z 0
x
x
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 23 -
Trennung mehrerer Klassen
DEF Lineare Separierung
Seien Muster x und Parameter w gegeben. Zwei Klassen 1 und 2
des Musterraums = 12 mit 12 =
heißen linear separierbar,
falls eine Hyperebene {x*} existiert mit g(x*) = wTx* = 0,
so daß für alle x1 gilt g(x)<0 und für alle x2 gilt g(x)>0.
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 24 -
Klassentrennung durch formales Neuron
Klassentrennung durch binäres Neuron
n
i ii 1
w xz = = wTx
Klassenentscheidung
y = SB(z) =
2 Klasse aus 0z 1
1 Klasse aus 0z 0
x
x
z = wTxSB(z) y = 0: Klasse 1
y = 1: Klasse 2
x1
x2
x3
xn-1
...
1
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 25 -
WIE erhalten wir die richtigen Gewichte,
d.h. die richtige Klassifizierung
?
Lernen !
Assoziativ-speicher
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 27 -- 27 -
Neuro-Modell des Assoziativspeichers
z 0
z 1
Funktion:
Jede Komp.ist lin. Summe
zi = wix
Nichtlin. Ausgabe:
yi = SB(zi) =
Lernen von W ?
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 28 -- 28 -
Lernen im Assoziativspeicher
Speichern aller N Muster mit Hebbscher RegelN N
k kij ij k i j
k 1 k 1
w w L x
0:0w ij
Auslesen eines Musters r
y = Wxr = z = r Lr(xr)Txr + r
rk
kkk
T
xxL
assoziierte Antwort + Übersprechen von anderen Mustern
Orthogonale Muster xr: Übersprechen = 0, exakte Reproduktion.
Nicht-orthogonale Muster: Schwellwerte nötig zum Unterdrücken des Übersprechens.
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 29 -- 29 -
Trennung mehrerer Klassen
Erinnerung: Lineare Separierung
xr
xp
xk
xq
x2
x1
(1,0)
(0,0)
(0,1)
(1,1)
1 Neuron: 1 Trennlinie(Ebene)
2 Neurone: 2 Trennlinien
(Ebenen)
Bereiche trennbar
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 30 -- 30 -
Trennung mehrerer Klassen
Problem: Klassenentscheidung über Korrelationsgröße
xp
xq
x2
x1
Entscheidung über x:
Klasse p: xxp > xxq
Klasse q: xxp < xxq
Frage: x = xp: In welche Klasse?
Antwort: in Klasse q !
Lösung(x-y)2 = x2 -2xy +y2 ist minimal xy ist maximalgenau dann, wennKonstante Länge c = |x|=|y| (normierte Musteraktivität)
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 31 -- 31 -
Trennung mehrerer Klassen
Erweiterung der Mustertupel
x X‘ = (x0 , x1, x2, ..., xn) mit |x‘| = const
weil x20 = c2 – |( x1, x2, ..., xn)|
2 > 0 (!) Einbettung in den Hyperraum Beispiel: 2-dim 3-dim
c
xa
x2
x1
x3
xr
xk
xq
xp
Entscheidung durch
cos (a) = = c–2 xTxr
cos(a) monoton fallend Winkel als Distanzmaß
min a max Korrelation
||||
T
r
r
xx
xx
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 32 -- 32 -
Assoziativspeicher: SpeicherkapazitätM Tupel (x,y) gegeben: Wie viele können zuverlässig gespeichert werden?
x1= x2 =...= xM: nur ein Muster speicherbar.
y1= y2 =...= yM: beliebig viele Muster speicherbar, da Antwort y immer richtig.
Problem der Kodierung der Muster ! Sei |x| = a.
Maximaler Musterabstandmax d(xp,xq) = min xpxq = 0 bei orthogonalen MusternReelle Komponenten: n Dimensionen n orthogonale BasisvektorenBinäre Komponenten:
Mmax = z.B. n=100, a=10, also max M=10
Mittlere Abstand maximal
z.B. n = 100 max M 2n/n-0.5 1029
a
n
0I
a
,d !
*aa
kr
xx
2n
n
*a
nM
Rüdiger Brause: Adaptive Systeme, Institut für Informatik, WS 2011 - 33 -- 33 -
Assoziativspeicher: Binärspeicher
Spärliche Kodierung Binäre MusterSpeichern: wij = Vp yi
pxjp = maxp yi
pxjp
Kapazität: HB = ln 2 = 0,693 Bit pro Speicherzelle Palm 1980vergleichbar mit CAM-Speicher Kodierung
k = ax = ld m
j = ay = O(log n)
CAM vs. Ass.matrix
Konstante Zahl von 1 durch eine Leitung pro Eingabecode