Wettbewerbslernen RBF-Netze, Learning Vector Quantisation, Kohonen-Karten

Wettbewerbslernen

RBF-Netze, Learning Vector Quantisation,

Kohonen-Karten

Fulda 2009 Soft Computing / Wettbewerbslernen

2

Funktionales Verhalten

• Die multi-layer Perceptronshaben die Eigenschaft, daßderselbe Input immer den-selben Output produziert.

• Man nennt dieses Verhalten funktional, und deshalb sind diese Netzwerke im Wesentlichen nur geeignet muli-dimensionale Funktionen zu modellieren.


3

nicht-funktional

• Was tut man, wenn man nichtfunktionale (widersprüchliche) Daten modellieren möchte?

• Gründe für nicht-funktionalität sind etwa:– Messungenauigkeiten– Unberücksichtigte Einflußparameter

(unbekannt oder nicht unmittelbar messbar)– Interne Zustände, die sich zeitlich oder

datengetrieben ändern– Datenfehler (Irrtum, Ausfall,..)


4

Mittelwert

• Unterstellt man Messungenauigkeiten, so kann man bei gleichen Eingaben sehr ähnliche Ausgaben annehmen.

• In diesem Fall kann man funktional modellieren, dabei entsteht eine Ausgabe, die einen Mittelwert (Kompromiss) zwischen den möglichen Ausgaben darstellt.

• Dieser Ansatz hat seine Grenzen, wenn die Distanz von Ausgaben mit sehr benachbarten Eingaben groß wird.


5

Keine Kompromisse

• Es gibt allerdings Situationen, in denen der Mittelwert das falscheste sein kann, das man als Ausgabe wählen kann.

• Ein Indiz für eine derartige Situation kann sein, daß in der Trainingsdatei zu einem Input bis auf kleine Schwankungennur wenige (z.B. 2) sehr unterschiedliche Werte vorkommen.


6

Klassifikation

• Ist eine funktionale Approximation nicht möglich, so bleibt nur übrig die Daten nicht als Input-Output Schema zu interpretieren, sondern insgesamt als Datenvektoren.

• Diese Datenvektoren kann man nun auf Ähnlichkeit untersuchen, das Resultat ist dann eine Klasseneinteilung auf dem Datenraum, wo 2 Datensätze in die selbe Klasse gruppiert werden, wenn sie einander sehr ähnlich (z.B. bzgl. euklidischen Abstand) sind.

• In diesem Abschnitt betrachten wir neuronale Netze, die derartige Klassifikationen erzeugen können.

Datenraum


7

1-Schichten-Netze

• In diesem Kapitel betrachten wir Netze, die im Prinzip nur eine Verarbeitungsschicht haben und nach der winner-take-all Strategie trainiert werden.

• Der Input x sucht entweder einen Abstand |x-ck| zu minimieren oder ein Skalarprodukt xck zu maximieren.

x1 x2 ... xn

s1 s2 s3 ... sm

Input-Schicht

Verarbeitungs-Schicht


8

Winner-Take-All-Strategie

Das Verhalten dieser Netzwerke in der verarbeitenden Schicht ist gekennzeichnet durch:

• Jeder (trainierte) Input aktiviert (im Wesentlichen) nur ein einzelnes Neuron, den "Gewinner".

• Das vom Input aktivierte Neuron ist gekennzeichnet durch den minimalen Abstand zum zugehörigen Gewichtsvektor (Zentrum) bzw. durch das maximale Skalarprodukt mit dem Gewichtsvektor.

• Das einzig aktive Neuron bestimmt allein das weitere Verhalten des Netzwerks.

deshalb spricht man hier von der winner-take-all-Strategie.


9

Die Aktivierung |x-w|2

• Sind alle Gewichts-Vektoren Vektoren w von derselben Länge r, so erhält man für die Distanz-Aktivierung der Neuronen mit Input-Vektor x : |x-w|2 = x2+w2 - 2xw = x2+r2 -2xw

• Die Aktivierung unterscheidet sich von der Skalarprodukt-Aktivierung nur durch denSummand r2+x2 und den Faktor -2 das Skalarprodukt.

• Die bedeutet, daß bei Eingabe x und beiden Aktivierungsarten derselbe Gewinner für x entsteht, denn minimaler Abstand von Zentrum w entspricht dem maximalen Skalarprodukt wx.

r

w1

w2Alle Gewichts-Vektoren w sind auf dieselbe Länge r normiert

0


10

Output-VerwaltungDiese 1-Schichten-Netze können auf zwei Weisen

mit Output versehen werden.• Eine weitere Output-Schicht wird angehängt und durch

überwachtes Lernen (-Regel) trainiert.– Das Ergebnis der Verarbeitungsschicht wird als Zwischenergebnis

benutzt und in einem weiteren Verarbeitungsschritt zum Output umgerechnet

• Die Input-Neuronen-Schicht wird zwei Teile aufgeteilt, den eigentlichen Input-Bereich und den Output-Bereich– Die Verbindungen von dem Outputbereich zur Verarbeitungsschicht

werden nach dem Training in umgekehrter Richtung zur Propagierung des Outputs genutzt.

• Im Lernverfahren können Input- und Output-Bereich im Wechsel oder völlig getrennt trainiert werden.


11

c1 c2 c3

Radiale Basisfunktionen

• Approximation von Funktionen als Linearkombination von Funktionen der Form (|x-c|2)

• F(x) = k wkk (|x-ck|2)


12

RBF-NetzwerkeRadial Basis Funktionen Netze

• Outputfinktionen im hidden Layer sind RBF (|x-ck|2)

• geänderte Aktivierungsfunktion im hidden Layer: |x-ck|2 .

• Aktivierungsfunktionen im hidden Layer meist vom Typ Gauss-Glocke: (x) = e -x / d .

• meist lineare Outputfunktionen im Output Layer.

• meist selbstorganisierte Anpassung der Zentren ck.

• Anpassung der Koeffizienten wk

nach der -Regel : wk = .(u-t). (|x-ck|

2).

y1 y2 y3 ...

u

yn

wn

w3w2w1

x1 x2 ... xm

cnmc12c11

. . .


13

Die Aktivierung |x-c|2

• Sind alle Input-Vektoren Vektoren von derselben Länge r, so erhält man für die Aktivierung des Neurons mit Zentrum c : |x-c|2 = x2 + c2 - 2xc = r2 + c2 -2cx

• Die Aktivierung ist also bis auf den konstanten Summand r2+c2 und den Faktor -2 das Skalarprodukt.

• Nimmt man Summand und Faktor in die Outputfunktion , so hat man wieder die übliche Aktivierung aus dem Skalarprodukt mit c.

• Minimaler Abstand von Zentrum centspricht dem maximalen Skalarprodukt cx.

r

x1

x2Alle Input-Vektoren x sind auf dieselbe Länge r normiert

0


14

Lernparadigma

• Ziel eines Lernvorgangs in einem solchen Netz ist es also, die Zentren (Gewichtsvektoren) so zu legen, daß im Mittel alle Inputs einen möglichst geringen Abstand von (großes Skalarprodukt mit) ihrem nächsten Zentrum haben.

• Die Zentren können dann als Prototypen ihrer Klasse (der Input mit diesem Zentrum als Sieger) gelten.

• Das Lernen ist ohne Lehrer (unsupervised), da vorab keine Klasse festgelegt ist, in die bestimmte Inputs zu liegen kommen sollen.


15

Winner-take-all-netze

• In einem solchen Netz repräsentiert jedes Neuron in der Ausgabeschicht ein Zentrum und damit eine Klasse von Inputs, die Anzahl der Klassen ist also durch die Netzkonstruktion festgelegt.

• Die Gewichte (Zentren) werden zunächst willkürlich festgelegt (oft als speziell ausgewählte Inputs) und dann im Trainingsverfahren (Zentrensuche) nach und nach so verändert, daß die Zentren optimal in ihren Klassen liegen.


16

Zentrensuche• Codebook Vektoren

– Zufällige Auswahl von Input-Vektoren– K-nearest-neighbour eliminiert sukzessive

wenig nötige Inputs

• Least Squares– Sukzessive Wahl von Codebook Vektoren

um die Minimalabstände möglicht klein zu machen

• K-Means Clustering– K Teilmengen und deren arithmetische

Mittel als Zentren

• Vektorquantisierung– Codebook Vektoren als Zentren und deren

Annäherung an Inputs kleinsten Abstands

• selbstorganisiertes Backpropagating– Training der ersten Schicht auf

Einheitsvektoren als Ausgabe

Datenraum, Meßpunkte


17

Vektor Quantisierung• Im ersten Schritt werden K Inputs als

Zentren ausgewählt.• Bei jedem Schritt wird für einen Input x

das Zentrum c mit minimalem Abstand aufgesucht und um ein Stück auf den Input x zubewegt: c := (x-c) .

• Die Rate muß nach jedem Durchgang durch die Eingabedaten reduziert werden.

• Das Verfahren endet, wenn die Rate auf dem Wert 0 angelangt ist.

• Dies kann auch als ein Lernverfahren im Netzwerk interpretiert werden

ck

x

ck+(ck-x)

ck-(ck-x)


18

selbstorganisierte -Regel

• In diesem Fall wird als Aktivierungsregel das Skalarprodukt gewählt.

• Zufällige Codebook-Vektoren werden zur Initialisierung der Verbindungsgewichte ck in der oberen Schicht gewählt.

• Für jeden Input x wird als Soll-Output der Einheitsvektor ek=(0..0,1,0..0) gewählt, für den das Skalarprodukt xck maximal ist.

• Mit diesem (ggf. wechselnden) Soll-Output wird die Input-Schicht nach der -Regel trainiert.

• Dies ist ein Netzwerk-Lernverfahren


19

Trainingserfolg

• Man kann ein solches Netzwerk als um so besser trainiert ansehen, je geringer der mittlere Abstand der Inputs von ihren Zentren ist.

• Es ist offensichtlich, daß die Anzahl der Klassen einen großen Einfluß auf den mittleren Abstand hat.

• Es wird möglicherweise Klassen geben, in denen dieser Abstand im Vergleich zu anderen sehr groß ist, man spricht dann von Ausreißern (outlyers)

• Es kann auch sein, daß Klassen sehr unterschiedlicher Elementezahl entstehen, denn man kann nicht davon ausgehen, daß in der Trainingsdatei alle Inputs etwa gleich oft vorkommen.


20

Feature Maps• Die Neuronen werden in

einem topologischen Gitter angeordnet. (meist 2-dimensional)

• Jeder Gitterpunkt wird mit einem Input-Vektor als Zentrum zufällig initialisiert

• Zu jedem Input wird der Gitter-punkt mit dem nächsten Zentrum aufgesucht.

• Dieser Gitterpunkt und eine topologische Umgebung davon wird ins Training nach LVQ-Muster einbezogen

• Kette

• Gitter Umgebung


21

Kohonen-Netzwerk• Das Gewinnerneuron ck kann mit

Abstand (im Input-Raum) oder Skalarprodukt ermittelt werden.

• Auf dem Gitter wird eine Funktion h definiert, die mit zunehmendem Gitter-Abstand zu 0 konvergiert

• Das Lernen erfolgt nach der LVQ-Formel, wobei die Änderung sich aus Lernrate und Funktion h vom Gitterabstand des lernenden Neurons zum Sieger ck berechnet:

cj := -.h(|cj-ck|).(cj-x)

• Der Lernraten-Anteil wird mit der Zeit auf 0 gesenkt.

Die Netzstruktur

k

1 2 ... ... n

c1kc2k cnk

Input Schicht

Zentren

Verarbeitungs Schicht


22

Topologische Einbettung• Wir betrachten für jedes

Neuron die eingehenden Synapsengewichte als einen Vektor im Eingaberaum.

• Jeder dieser Vektoren hat als Einzugsgebiet alle Eingaben, die ihm am ähnlichsten sind (kürzester Abstand)

• Darum nennt man diese Vektoren auch Prototypen.

• Wenn man im Eingaberaum diese Vektoren miteinander verbindet, wenn sie im Gitter benachbart sind, erhält man ein Bild des Gitters im Eingaberaum.

• Vor dem Training ist dieses Gitter völlig ungeordnet, das Training erzeugt dann eine Entfaltung des Gitters.

• Damit entsteht eine topologische Einbettung des Gitters in den Eingaberaum, so dass die Trainingspunkte möglichst geringen Abstand von den Gitterpunkten haben.


23

Beispiel 1• Werden Punkte im

Parabelabschnitt zufällig den Gitterpunkten Zugeordnet, so entsteht ein chaotisches Bild, wenn man die Kanten Gitter-benachbarter Punkte einzeichnet

• Beim Training entfaltet sich das Gitter langsam immer mehr.

• Es füllt schließlich den Bereich der Trainingsdaten optimal aus

• Aus Ritter-Martinetz-Schulten : Neuronale Netzwerke


24

verschiedene Dichte

• Liegen in einem Bereich deutlich mehr Trainingsdaten als anderswo, so ergibt sich in diesem bereich eine deutlich dichtere Anordnung von Netzpunkten als im übrigen Eingangsraum.

• Man kann also durch gezielte Vervielfachung von Trainings-Datenpunkten die Auflösung in deren Bereich erhöhen.


25

Wege, 1-dim. Karten

• Erzeugt man 1-dimensionale Karten so stellen deren Urbilder die Punkte eines Weges im Datenraum dar.


26

Handlungsreisenden-Problem

• Zyklische 1-dim. Kartegeringe Neuronenzahl

• Zyklische 1-dim. Karteausreichende Neuronenzahl


27

Visualisierung

• Ein wichtiger Aspekt beim Einsatz von Kohonen Karten ist die Visualisierung der Nachbarschaftsbeziehung im Eingabe-Datenraum.

• Die trainierte Karte stellt ein zweidimensionales topolo-gisches Abbild des hochdimen-sionalen Trainingsbereichs im Eingaberaum dar .

• Das Bild ist nicht metrisch(!), denn wo Trainingsdaten sehr dicht liegen haben benachbarte Prototypen viel kürzere Abstände als woanders.


28

Trainingserfolg

• Im Allgemeinen kann man keine hochdimensionalen Bilder mit vernünftiger Anschaulichkeit erzeugen, dennoch lässt sich aus der Reaktion des Netzes die Güte des Trainingserfolges ablesen, wenn man nicht nur die Aktivierung des Siegers darstellt.

gute Aktivierung schlechte Aktivierung


29

Behandlung von Outputs

• Obwohl diese Netzwerke nicht für die Produktion von Outputs gedacht sind, gibt es verschiedene Ansätze zue Erweiterung der Netze um eine Output-Komponente

• Radial-Basis-Funktionen-Netze(RBF-Netze)

• Motorische Karten


30

Distanzminimum• Für die Distanzen eines Inputs x von den Zentren ci

erhält man |x-ci|2 = x2 + ci2 - 2xci = x2 + ci

2 -2|ci||x|cos

• Haben alle Zentren ungefär dieselbe Länge, so hat x genau dann minimale Distanz von ci , wenn das Skalarprodukt xci maximal (der Zwischenwinkel minimal) ist.

• Wenn also im Lernalgorithmus die Länge der Zentren normiert wird (für die Verarbeitung kann ja die Länge des Zentrums in die Aktivierungs- oder Output-Funktion eingebunden werden), kann der Gewinner sowohl über die Distanzminimierung wie über die Maximierung des Skalarprodukts ermittelt werden.


31

Codebook-Vektoren

• Wähle zufällig K Inputs als Zentren (Codebook-Vektoren) aus.• K-nearest neighbour :

– Wähle zunächst alle Inputs als Zentren aus.

– Eliminiere Schrittweise jeweils das Zentrum, das am nächsten an einem anderen Zentrum liegt.

– Ende wenn die Abstände zu groß werden oder die gewünschte Anzahl K an Zentren unterschritten wird.

Beide Verfahren liefern Ergebnisse, die signifikant unter dem Optimum liegen.


32

Least Squares

• Wähle einen Input als Zentrum aus.• Wähle schrittweise aus den verbleibenden Inputs

denjenigen als neues Zentrum aus, der die größte Verkleinerung der Minimalabstände zu vorhandenen Zentren liefert

Dieser Algorithmus ist sehr rechenintensiv, kann aber bedeutend verbessert werden, wenn man jeweils den zu den vorhandenen Zentren orthogonalen Teilraum berechnet (orthogonal least squares).


33

K-Means-Clustering• Es wird zunächst zufällig der Input-Raum in K disjunkte

Teilmengen S1 ,...,Sk (Cluster) eingeteilt und als deren Zentren jeweils deren arthmetische Mittel

ci = .xSix

• Schrittweise wechseln Inputs x in andere Teilmengen über, wenn sie von deren Zentrum geringeren Abstand haben, dann werden jedesmal die betroffenen Zentren neu als arithmetische Mittel berechnet.

• Das Verfahren endet, wenn jeder Input zu dem Cluster gehört, zu dessen Zentrum er minimalen Abstand hat.

x |S i|


34

Durchmesser• Wenn die Zentren dicht zusammenliegen, kann es zu

einer schlechten Interpolation kommen, weil die Basisfunktionen einander stark überlappen.

• Eine bessere Leistung wird erzielt, wenn für jedes Zentrum ck ein individueller Durchmesser dk der zugehörigen radialen Basisfunktion gewählt wird:

(| x - ck |2 / dk) statt (| x - ck |2) • Als günstiger Wert bietet sich hier die

Standardabweichung des Abstands vom Zentrum über das Cluster des Zentrums an: Sk := {x| (x-ck)2 < (x-cj)2 für alle j = k}

dk := (xSk (x-ck)2 / |Sk|)1/2


35

Verallgemeinerte RBFN

Radiale Basis-Funktion Netzwerke können noch

in mehrer Hinsicht verallgemeinert werden:• individuelle Gewichtung des Abstands |x-c|

durch individuelle Durchmesser• Verwendung eines ellipsoiden

Skalarproduktes ggf. mit angepaßten Hauptachsen

(x-c)D(x-c)t

• Verwendung einer beliebigen nichteuklidischen Norm als Abstandsfunktion.

Documents

Wettbewerbslernen RBF-Netze, Learning Vector Quantisation, Kohonen-Karten