Prof. Dr. Dr. J. Hansohm Neuere Entwicklungen è Globale Optimierung è Clusterverfahren è sonstige Ansätze è Ameisensysteme è Künstliche Neuronale Netze

Prof. Dr. Dr. J. Hansohm

NeuereEntwicklungen

NeuereEntwicklungen Globale Optimierung

Clusterverfahren sonstige Ansätze

Ameisensysteme Künstliche Neuronale Netze

Globale Optimierung Clusterverfahren sonstige Ansätze

Ameisensysteme Künstliche Neuronale Netze


Globale OptimierungGlobale Optimierung

Problemstellung:Problemstellung:

Lipschitz Bedingung:Lipschitz Bedingung:

Eindimensionaler Fall:Eindimensionaler Fall:

f: A , A n

Ges. xmin A mit f(xmin) = f* = min { f(x) | x A }

f: A , A n

Ges. xmin A mit f(xmin) = f* = min { f(x) | x A }

| f(x) - f(y) | L || x - y ||| f(x) - f(y) | L || x - y ||

| f(x) - f(y) | max { f‘(z) | z A } | x - y || f(x) - f(y) | max { f‘(z) | z A } | x - y |

Es lassen sich Intervalle ausschließen, dieaufgrund der Lipschitz Bedingung dasglobale Optimum nicht enthalten können.

Es lassen sich Intervalle ausschließen, dieaufgrund der Lipschitz Bedingung dasglobale Optimum nicht enthalten können.


Problem der globalen OptimierungProblem der globalen Optimierung

Existenz (Stetigkeit, Kompaktheit) Praktikabilität (Dichte des Gitters) Approximation (cos(x)-a*x für -4<x<4)

Existenz (Stetigkeit, Kompaktheit) Praktikabilität (Dichte des Gitters) Approximation (cos(x)-a*x für -4<x<4)

a > 0a > 0 a < 0a < 0


ClusterverfahrenClusterverfahren Idee A: gleichverteiltes Netz, lokale

Minimumsuche vom Punkt mit dem kleinsten Wert

Idee B: Jeweils von einem Zufallspunkt aus wird eine lokale Minimumsuche durchgeführt (Multistart Methode)

Idee C: Cluster Punkte eines gleichverteilten Netzes so, daß die Cluster um die lokalen Minima liegen. Lokale Minimumsuche vom Punkt mit dem kleinsten Wert in jedem Cluster

Idee A: gleichverteiltes Netz, lokale Minimumsuche vom Punkt mit dem kleinsten Wert

Idee B: Jeweils von einem Zufallspunkt aus wird eine lokale Minimumsuche durchgeführt (Multistart Methode)

Idee C: Cluster Punkte eines gleichverteilten Netzes so, daß die Cluster um die lokalen Minima liegen. Lokale Minimumsuche vom Punkt mit dem kleinsten Wert in jedem Cluster


Clusterverfahren - DistanzermittlungClusterverfahren - Distanzermittlung

Euklidischer Abstand allein vernachlässigt die Informationen, die durch die Funktionswerte der Punkte gegeben sind.

Abhilfe: Einen (oder mehrere) Gradientenschritte

durchführen Distanz aufgrund eines Dichtemaßes

festlegen Punkt und Gradient in die Distanz mit

eingehen lassen

Euklidischer Abstand allein vernachlässigt die Informationen, die durch die Funktionswerte der Punkte gegeben sind.

Abhilfe: Einen (oder mehrere) Gradientenschritte

durchführen Distanz aufgrund eines Dichtemaßes

festlegen Punkt und Gradient in die Distanz mit

eingehen lassen


Sonstige AnsätzeSonstige Ansätze

Genetische Algorithmen,

Evolutionsstrategien

Simulated Annealing ausgehend von einem lokalen Minimum

durch Zufallspunkte einen Punkt mit einem kleineren Funktionswert finden und so ein neues lokales Minimum ermitteln

Statistische Methoden (Wiener Prozeß)

Branch & Bound (Horst)

Genetische Algorithmen,

Evolutionsstrategien

Simulated Annealing ausgehend von einem lokalen Minimum

durch Zufallspunkte einen Punkt mit einem kleineren Funktionswert finden und so ein neues lokales Minimum ermitteln

Statistische Methoden (Wiener Prozeß)

Branch & Bound (Horst)


Testfunktion für globale MinimumsucheTestfunktion für globale Minimumsuche

f(x1,x2)=4 x12 - 2,1 x1

4 + 1/3 x16 + x1x2 - 4 x2

2 + 4 x24f(x1,x2)=4 x1

2 - 2,1 x14 + 1/3 x1

6 + x1x2 - 4 x22 + 4 x2

4


AmeisensystemeAmeisensysteme

Ameisensysteme sind wie bei den genetischen Algorithmen der Versuch,durch Adaption natürlichen Verhaltens Optimierungsproblemeheuristisch zu lösen.

Ameisensysteme sind wie bei den genetischen Algorithmen der Versuch,durch Adaption natürlichen Verhaltens Optimierungsproblemeheuristisch zu lösen.

Beispiel:Beispiel:

AA

BB

AA

BB BB

AA


Ameisensysteme Ameisensysteme

Ameisen hinterlassen auf ihrem Weg ein Pheromon

andere Ameisen gehen mit höherer Wahrscheinlichkeit einen Weg je höher der Pheromon Anteil ist, den sie wahrnehmen

Dadurch verstärkt sich der Anteil an Pheromon auf diesem Weg

Ameisen hinterlassen auf ihrem Weg ein Pheromon

andere Ameisen gehen mit höherer Wahrscheinlichkeit einen Weg je höher der Pheromon Anteil ist, den sie wahrnehmen

Dadurch verstärkt sich der Anteil an Pheromon auf diesem Weg



Beispiel Traveling Salesman ProblemBeispiel Traveling Salesman Problem

n Orte sind so zu durchlaufen, daßdie Gesamtlänge des Weges minimalwird („Rundreiseproblem“).

n Orte sind so zu durchlaufen, daßdie Gesamtlänge des Weges minimalwird („Rundreiseproblem“).

Ameise wählt einen nächsten Ort mit einer Wahr-scheinlichkeit in Abhängigkeit der Distanz zumnächsten Ort und dem Grad an Pheromon

Ameise wählt einen nächsten Ort mit einer Wahr-scheinlichkeit in Abhängigkeit der Distanz zumnächsten Ort und dem Grad an Pheromon

Ein schon durchlaufener Ort ist Tabu, es sei denn,die Tour würde damit zur RundreiseEin schon durchlaufener Ort ist Tabu, es sei denn,die Tour würde damit zur Rundreise

Wenn eine Ameise eine Rundreise geschafft hat, so hinterläßt sie Pheromon an jeder Kante, die sie durchlaufen hat

Wenn eine Ameise eine Rundreise geschafft hat, so hinterläßt sie Pheromon an jeder Kante, die sie durchlaufen hat

Jeder Knoten desGraphen wird miteiner Anzahl vonAmeisen versehen

Jeder Knoten desGraphen wird miteiner Anzahl vonAmeisen versehen

55

3322

11 1144

11



Menge an Pheromon abhängig von der Güte der Rundreise Parameter Q (cycle)

„altes“ Pheromon verflüchtigt sichParameter

Distanz zum nächsten Ort und Pheromon-intensität werden unterschiedlich gewichtet Parameter (Ort) und

Pheromon wird sofort ausgeschüttet unabhängig von der Distanz (quantity, density)

Menge an Pheromon abhängig von der Güte der Rundreise Parameter Q (cycle)

„altes“ Pheromon verflüchtigt sichParameter

Distanz zum nächsten Ort und Pheromon-intensität werden unterschiedlich gewichtet Parameter (Ort) und

Pheromon wird sofort ausgeschüttet unabhängig von der Distanz (quantity, density)

Parameter:Parameter:


Ameisensysteme Ameisensysteme Ergebnisse:Ergebnisse:

( = gute Lösungen)( = gute Lösungen)(jeweils 10 Durchläufe)(jeweils 10 Durchläufe)

(8 einfache Heuristiken ohne Verbesserung)(8 einfache Heuristiken ohne Verbesserung)

(AS =Ameisensystem TS=Tabu Search SA=Simulated Annealing)

(AS =Ameisensystem TS=Tabu Search SA=Simulated Annealing)


o

Künstliches NeuronKünstliches Neuron

Summations-funktion

net

Transfer-funktion

F

Output-funktion

o

x1

x2

...

xn

w1

w2

wn

...

net(...wi...xi...)

a=F(a, net)o(a)

net= wi*xi

a=1/(1+e-g*net)i=1

n

o=a


Formen von Neuronalen Netzen (NN)Formen von Neuronalen Netzen (NN)

SelbstorganisierendeNetzeSelbstorganisierendeNetze

„Feed Forward“ Netze„Feed Forward“ Netze

EingangsschichtEingangsschicht

AusgangsschichtAusgangsschicht


Backpropagation NetzwerkBackpropagation Netzwerk

Fehler-korrektur(Lernregel)

Gewichte

Eingangs-muster

Ausgangs-muster

Schicht


Delta LernregelDelta Lernregel

Fehler definiert als E = ½ (zi - oi)2, wobei oi der tatsächliche und zi der gewünschte Output ist

Fehler definiert als E = ½ (zi - oi)2, wobei oi der tatsächliche und zi der gewünschte Output ist

Hierauf wird ein Gradientenverfahren angewandt, welches ergibt:Hierauf wird ein Gradientenverfahren angewandt, welches ergibt:

wij(t+1) = wij(t) + i

oj

wij(t+1) = wij(t) + i

oj

ist hierbei die Lernrate, bzw. die Schrittweite beim Grad.-Verfahrenist hierbei die Lernrate, bzw. die Schrittweite beim Grad.-Verfahren

i = F‘(neti) * (zi - oi) für die Outputschichti = F‘(neti) * (zi - oi) für die Outputschicht

i = F‘(neti) * h whi über alle h Nachfolgeschichten sonsti = F‘(neti) * h whi über alle h Nachfolgeschichten sonst

F(neti) ist hierbei die Transferfunktion des Neurons iF(neti) ist hierbei die Transferfunktion des Neurons i


Delta Lernregel - VorgehensweiseDelta Lernregel - Vorgehensweise

Initialisierung: Alle Gewichte erhalten zufällige kleine Werte von -0,1 bis +0,1

Anlegen der Inputdaten, ermitteln der Outputdaten, Fehler feststellen, mit Deltaregel lernen. Vorgang wiederholen.

Stop bei ausreichend geringem Fehler Verbesserung der Lernregel mit Momentum

Initialisierung: Alle Gewichte erhalten zufällige kleine Werte von -0,1 bis +0,1

Anlegen der Inputdaten, ermitteln der Outputdaten, Fehler feststellen, mit Deltaregel lernen. Vorgang wiederholen.

Stop bei ausreichend geringem Fehler Verbesserung der Lernregel mit Momentum

wij(t) = i oj + wij(t-1) und wij(t+1) = wij(t) + wij(t)wij(t) = i oj + wij(t-1) und wij(t+1) = wij(t) + wij(t)


Lineare Diskriminanzanalyse mit NNLineare Diskriminanzanalyse mit NN

net = w0 + wi*xii=1

n

1

x1

xn

w0

w1

wn

...

1 = solvent

0 = insolvent


NN und KursprognoseNN und Kursprognose

Beispiel: Eingabe - 20 fortlaufende TageskurseBeispiel: Eingabe - 20 fortlaufende Tageskurse

Ausgabe - 3 darauf folgende TageskurseAusgabe - 3 darauf folgende Tageskurse

Lernen jeweils an alten DatenreihenLernen jeweils an alten Datenreihen

Transferfunktionen: sigmoid und sinusTransferfunktionen: sigmoid und sinus2020

Eingangs-schichtEingangs-schicht

HiddenLayersHiddenLayers

Ausgangs-schichtAusgangs-schicht


NN und ReihenfolgeproblemeNN und ReihenfolgeproblemeTrainiert mit durch anderen Algorithmuserrechneten optimalen Reihenfolgen (Johnson-Algor.)Trainiert mit durch anderen Algorithmuserrechneten optimalen Reihenfolgen (Johnson-Algor.)

Reihenfolge-nummerReihenfolge-nummer

Zeiten Produktionsstufe IZeiten Produktionsstufe IIZeiten Produktionsstufe IZeiten Produktionsstufe II

solange Aufträge vorhandensolange Aufträge vorhanden

ermittle kürzeste Bearbeitungszeit der Aufträgeermittle kürzeste Bearbeitungszeit der Aufträge

Auftrag eindeutig?Auftrag eindeutig?

streiche den eingeplanten Auftragstreiche den eingeplanten Auftrag

JJ NN

Auftragauf 1. freiePosition




Auftragauf letztefreiePosition

Auftragauf letztefreiePosition

Einer dieser Aufträgeauf 1. freiePosition

Einer dieser Aufträgeauf 1. freiePosition

Min. Bearbeitungszeitbei Prod. Stufe I ?Min. Bearbeitungszeitbei Prod. Stufe I ?

Min. Bearbeitungszeitbeim selben Auftrag?Min. Bearbeitungszeitbeim selben Auftrag?

JJ JJ NNNN


Problem des OverlearningProblem des Overlearning

Backpropagation Netz mit wenigerVerbindungenBackpropagation Netz mit wenigerVerbindungen

Baetge u.a.:„Früherkennung derUnternehmenskrise -NN als Hilfsmittelfür Kreditprüfer“

Baetge u.a.:„Früherkennung derUnternehmenskrise -NN als Hilfsmittelfür Kreditprüfer“

PrognoseproblemPrognoseproblem

Polynom n.ten Grades ist i.a.eine sehr schlechte Prognose,geht aber durch alle vorgegebenenPunkte.

Polynom n.ten Grades ist i.a.eine sehr schlechte Prognose,geht aber durch alle vorgegebenenPunkte.


ALS - AlgorithmusALS - Algorithmus

Skalierungenfest

Modellparameterfest

passe Skalierungen sukzessiv an beifesten Modellparametern (und beifesten anderen Skalierungen)

berechne Modellparameter bei festen(willkürlichen) Skalierungen


NN bei qualitativen DatenNN bei qualitativen Daten

schlecht mittel gut

0

0

1

0

1

1

w1

w2

nominalerInput

quantitativerInput

schlecht mittel gut

w1 w1+w20


Klassifikation mit Backpropagation NNKlassifikation mit Backpropagation NN

MerkmalsausprägungenMerkmalsausprägungen

„bottleneck“„bottleneck“

sollen reproduziert werdensollen reproduziert werden

Das NN soll die Merkmalsausprägungenwieder reproduzieren mit einer der Cluster-anzahl vorgegebenen verdeckten Schicht

Das NN soll die Merkmalsausprägungenwieder reproduzieren mit einer der Cluster-anzahl vorgegebenen verdeckten Schicht

Entspricht einer Art Haupt-komponentenanalyse mit an-schließender Festlegung zu denKlassen; z.B. das Objekt wirdder Klasse (blaues N) zugeordnet,die den höchsten Input des ent-sprechenden Datensatzes erfährt.

Entspricht einer Art Haupt-komponentenanalyse mit an-schließender Festlegung zu denKlassen; z.B. das Objekt wirdder Klasse (blaues N) zugeordnet,die den höchsten Input des ent-sprechenden Datensatzes erfährt.


Kohonen NetzKohonen Netz

Self Organizing Map (SOM)Self Organizing Map (SOM) Neuronen der SOM regen sich unter-einander an in Abhängigkeit ihrerLage im Raum.•nahe N werden angeregt•mittlere N werden gehemmt•weiter weg liegende N erhalten nichts

Neuronen der SOM regen sich unter-einander an in Abhängigkeit ihrerLage im Raum.•nahe N werden angeregt•mittlere N werden gehemmt•weiter weg liegende N erhalten nichts

N der SOM Schicht bildet aus den Outputs derEingabeschicht mit den Gewichten: wki*xi ,erregt, hemmt mit gauss‘scher Glockenkurvebenachbarte N.Vereinfachung: nur das am stärksten externerregte N wird betrachtet, xi =1 und wki für alle Neuronen k gleich.

N der SOM Schicht bildet aus den Outputs derEingabeschicht mit den Gewichten: wki*xi ,erregt, hemmt mit gauss‘scher Glockenkurvebenachbarte N.Vereinfachung: nur das am stärksten externerregte N wird betrachtet, xi =1 und wki für alle Neuronen k gleich.

Veränderung derGewichte mittels Delta-regel. Gewichte gleichensich den Outputs an.

Veränderung derGewichte mittels Delta-regel. Gewichte gleichensich den Outputs an.

EingabeschichtEingabeschicht

wkiwki

x1x1 x2x2


Kohonen Netz und Traveling Salesman Pr.Kohonen Netz und Traveling Salesman Pr.

SOM eindimensional (Ring, wie dargestellt)Eingabevektoren 2-dim (x1, x2) Ortskoord.

SOM eindimensional (Ring, wie dargestellt)Eingabevektoren 2-dim (x1, x2) Ortskoord.

Nach einer Reihe vonSchritten (z.B. 10000)gleichen die Gewichteder N den Ortskoord.Reihenfolge auf dem Ring ergibt Reihen-folge der Tour

Nach einer Reihe vonSchritten (z.B. 10000)gleichen die Gewichteder N den Ortskoord.Reihenfolge auf dem Ring ergibt Reihen-folge der Tour


Kohonen Netz und KlassifikationKohonen Netz und Klassifikation

Eingabeschichtentsprechend derDimension derMerkmalsvektoren

Eingabeschichtentsprechend derDimension derMerkmalsvektoren

SOM Schicht entsprechendder Anzahl der KlassenSOM Schicht entsprechendder Anzahl der Klassen

Netz soll bei Anlegen einerMerkmalsausprägung mitder Erregung eines „winner“Neurons reagieren. Dies ent-spricht dann der Klasse.

Netz soll bei Anlegen einerMerkmalsausprägung mitder Erregung eines „winner“Neurons reagieren. Dies ent-spricht dann der Klasse.

Teilweise besser als mit hierarchischenVerfahren gewonnene Klassen, benötigtauch keine Distanzmatrix. Aber langeRechenzeiten und kein Vergleich mitz.B. Austauschverfahren.

Teilweise besser als mit hierarchischenVerfahren gewonnene Klassen, benötigtauch keine Distanzmatrix. Aber langeRechenzeiten und kein Vergleich mitz.B. Austauschverfahren.


Vor- und Nachteile Neuronaler NetzeVor- und Nachteile Neuronaler Netze

adaptives Lernen sinnvolle Reaktion auch bei bisher nicht

berücksichtigten Problemen relativ stabil gegenüber logischen Widersprüchen keine Erklärungskomponente keine Verifizierung der Entscheidung sensibel gegenüber Veränderungen im

Datenmaterial Qualität abhängig von der Güte der Trainings-

daten und dem Typ des Neuronalen Netzes

adaptives Lernen sinnvolle Reaktion auch bei bisher nicht

berücksichtigten Problemen relativ stabil gegenüber logischen Widersprüchen keine Erklärungskomponente keine Verifizierung der Entscheidung sensibel gegenüber Veränderungen im

Datenmaterial Qualität abhängig von der Güte der Trainings-

daten und dem Typ des Neuronalen Netzes

Documents

Prof. Dr. Dr. J. Hansohm Neuere Entwicklungen è Globale Optimierung è Clusterverfahren è sonstige Ansätze è Ameisensysteme è Künstliche Neuronale Netze