Transcription

Grundlagen und Aufbau von neuronalen Netzen Künstliche neuronale Netze (KNN) modellieren auf starkvereinfachte Weise Organisationsprinzipien und Abläufebiologischer neuronaler Netze Jedes KNN besteht aus einer Anzahl künstlicher Neuronen alselementare Informationsverarbeitungseinheit Künstliche Neuronen sind in bestimmter Art und Weiseangeordnet und miteinander verbunden (Netzarchitektur) Die Verbindungen dienen zum Austauschen von Nachrichtenund sind gewichtet, was die Intensität des Informationsflussesentlang dieser Verbindung zum Ausdruck bringen soll Mit Hilfe von Lernregeln können die Verbindungsgewichteverändert werden Ziel: Netz soll in Trainingsphase anhand von Beispielen und mitHilfe einer Lernregel, Abbildungen von Eingaben auferwünschte Ausgaben des Netzes lernen Vorteil von KNN: müssen für Lösung eines Problems nichtexplizit programmiert werden

Schematische Darstellung eines künstlichen NeuronsEingangssignale xi:Daten können von Umgebung oder Ausgang eines anderenNeurons stammenUnterschiedliche Netzwerkmodelle erlauben unterschiedlicheWertebereicheTypische Wertebereiche sind die reellen Zahlen, das Intervall[0,1] oder die diskreten Werte {0,1}.Gewichte wi:Jeder Verbindung in KNN ist häufig eine reelle Zahl alsGewicht zugeordnetGewicht beschreibt Stärke der VerbindungIn Verbindungsgewichten ist Wissen des KNN gespeichert

Netto-Input net:Netto-Eingabe entspricht Summe der gewichtetenEingangssignaleAktivierungsfunktion f(net):bestimmt, abhängig von Netto-Eingabe net, die Ausgabekann das Eingangssignal für anderes Neuron sein oderAusgangssignal des KNNSchwellwertfunktion:Sigmoide Funktion:

Die Netztopologie eines mehrstufigen Netzes Mehrstufige (mehrschichtige) Netze sind Netze, bei denendie Ausgabeschicht als Eingabe für eine weitereNeuronenschicht dientDiese Netztypen können alle möglichen Funktionen darstellenund seit 1985 gibt es einen geeigneten Lernalgorithmus, denBackpropagation-AlgorithmusBeispiel: Ein zweistufiges neuronales NetzDie mittlere Neuronenschicht ist Eingabe für diedarüberliegende Schicht von Neuronen, die den Output desgesamten Netzes bereitstelltDie Zwischenneuronen h1 und h2 bezeichnet man alsversteckte Neuronen (hidden neurons) und die gesamtemittlere Schicht als versteckte Schicht (hidden layer).

Probleme:1) Bestimmung der Gewichte Lange Trainingszeiten mit herkömmlichen Methoden Initialisierungsabhängig2) Bestimmung der Topologie Größe der Eingangs-/Ausgangsschicht steht festAnzahl der verdeckten Schichten ist variabel Größe der verdeckten Schichten ist variabel Entweder strenge Schichtenarchitektur oder beliebigevorwärtsgerichtete Schichtenarchitektur

Optimierung der KNNKünstliche neuronale Netzen werden mit folgenden Ansätzenoptimiert:1. Ansätze, die versuchen die Topologie eines neuronalenNetzes zu optimieren2. Ansätze, die die Gewichte eines neuronalen Netzesoptimieren3. Ansätze, die gleichzeitig eine optimale Netztopologie undoptimale Gewichte des neuronalen Netzes finden wollenArten der Codierung von KNN:1) direkte Codierung2) indirekte Codierung

Beispiel 1: direkte Codierung [Schöneburg]Idee: Schöneburg stellt einen Algorithmus vor, der nicht nachgeeigneten Topologien im Raum der Netzwerktopologien sucht,sondern im Raum formaler Repräsentationen von Netzwerktopologien.Übersicht des Algorithmus: Übersetzung des Neuronalen Netzes in mathematische Formeln Festlegung „akzeptabler“ Formeln durch Grammatik Codierung der Formeln in ein binäres Format Anwendung von GAs auf binär verschlüsselte Formeln, um „gute“Formeln zu erhalten „gute“ Formel haben wichtige Eigenschaften, z.B.:minimale Anzahl von Termen minimale Anzahl von Neuronen

Übersetzung eines KNN in eine Formel:Mit der Sigmoidfunktion TF als Aktivierungsfunktionfür alle Neuronen folgt:o( x) o( x1 , x2 ) TF ( w54TF ( w41 x1 w42 x 2 ) w53TF ( w31 x1 w32 x2 ))

Grammatik, die akzeptable Formeln bestimmt:1. Seien wi Gewichtungsvariable, xj Inputvariable, dannnennt man wi xj . wn xn basic expression2. Sei Φ ein basic expression, dann heißt fTi(Φ) neuronalerTerm3. Wenn Φ ein basic expression ist und β1, . , βn neuronaleTerme, dann heißt fTi ( Φ w1β1 . wn βn )terminaler Ausdruck4. Wenn Φ ein basic expression ist, β1, . , βn neuronaleTerme und Ω1, . , Ωk terminale Ausdrücke, dann ist fT i(Φ w1β1 . wn βn wj Ωj . αk Ωk ) ebenfallsterminaler Ausdruck.5. DEFINITION: Eine Folge von Termen Ω1, . , Ωk isteine akzeptable Formel, wenn alle Ωi terminaleAusdrücke sind und jedes xj mindestens einmal in einemder Ωi auftritt.

Ableitung einer Netzwerktopologie aus einerFormelSchritt 1: Man zeichne eine Linie. Auf diese Linie zeichne man für jedenTerm der Formel, der für eine Transferfunktion steht, einen Knoten(Kreis). In jeden Knoten zeichne man das entsprechende Symbol derTransferfunktion (die Reihenfolge des Auftragens der Knoten auf derLinie ist im Prinzip gleichgültig)Schritt 2: Man zeichne eine zweite Linie von Knoten unterhalb der ersten,wobei jeder Knoten dieser Linie für ein Eingabe-Symbol (EingabeVariable) steht (die Reihenfolge ist gleichgültig)Wiederhole für alle Ω (Ω)Schritt 3: analysiere das Argument Ω Da Ω die FormΩ Φ αβ α β α Ω α Ω hat, ist jeder Teilausdruck Φ von Ω in dieser Summe nach Definitionentweder ein basic expression, ein neuronaler Term oder ein terminalerAusdruck. Arbeite nun Ω von links nach rechts ab. Das weitereVorgehen hängt davon ab, welcher Art der jeweils betrachteteTeilausdruck von Ω ist.

Schritt 3.1: Angenommen Φ ist ein nicht leerer basic expression. Er hat . α * . In diesem Falldann nach Definition die Form: Φ α * zeichnet man für jeden Teilausdruck α * α von Φ eine Verbindungvon dem Knoten der unteren Linie, der die Eingabe-Variable repräsentiert, zu dem Knoten der darüber liegenden Schicht, der dieTransferfunktion repräsentiert. Beschrifte diese Verbindung mit αm,da αm die Gewichtung dieser Verbindung darstellt.Schritt 3.2: Wenn Φ von der Form α * (β ) ist und βn ein basicexpression, so zeichnet man eine Verbindung von dem Knoten, der repräsentiert zum Knoten und beschriftet diese Verbindung mit α .Dann fahre man mit dem Argument β rekursiv wie in 3.1 fort.Schritt 3.3: Wenn Φ von der Gestalt α * (Ω ) und Ω ein terminalerAusdruck ist, zeichnet man eine Verbindung von dem Knoten, der repräsentiert zu dem Knoten, der repräsentiert und beschriftet dieseVerbindung mit dem Gewicht α . Man beginnt den Aufbauprozessrekursiv mit (Ω ) wie bei Schritt 3, indem durch und Ω durchΩ ersetzt wird.

Codierung der Formeln Codierung auf Chromosom mit Alphabet aus 256 Buchstaben Chromosom ist in Abschnitte aufgeteilt Anzahl der Abschnitte entsprecht Anzahl der Ausgabe-Neuronen In Abschnitt ist Graph (Baumstruktur) zu Neuron codiert Abschnitt enthält Unterabschnitt, der aus 3 Buchstaben besteht Erster ist Aktivierungsfunktion, Zweiter und Dritter deren Parameter

Die Fitness einer FormelDatensatz s Menge von Tupeln , , wobei die Eingabeund die jeweils dazu erwartete Ausgabe des Netzes ist.c sei ein Chromosom, d.h. eine verschlüsselte Formel undint(c, ) die Interpretation von c für das Argument . DieTauglichkeit von c, fit(c), wird durch ein Fehlermaß über demDatensatz s bestimmt.Wenn das Fehlermaß der mittlere quadratische Fehler ist, sowird z.B. fit(c) berechnet, indem die Interpretation von chintereinander auf alle als Argumente angewandt wird:Je kleiner der quadratische Fehler der Interpretation der Formelauf dem Trainingssatz ist, desto größer, ist die Tauglichkeit derFormel

Erweiterung der Fitnessfunktion Einfügen von Belohnungs- oder Bestrafungsterm für dieFitnessfunktion um zusätzlich kurze Formeln zu erhalten Identitätsfunktion f(x) x , um die Länge der Formel gleichmitzuoptimieren Wenn die Identitätsfunktion in verschlüsseltem Formelausdruckerscheint, wird sie übersprungen, da sie Wert nicht verändert Hinzufügen eines Belohnungsterm zur Fitnessfunktion für dask-fache Auftreten der Identitätsfunktionnfit (c) 1 /(1 / n * (int( c, xi ) y i ) 2 )) h(k )i 1 Die Funktion h kann im Prinzip jede sinnvolle Funktion von ksein, z.B. eine lineare oder exponentielle Funktion, wie z.B.h(k) α*kh(k) 2oderk in der Praxis wird noch eine kleine konstante Zahl β ( 2 10 oderähnlich) hinzugefügt, um eine potentielle Division durch 0 zuvermeiden (z.B. wenn Annäherungsfehler 0 ist)nfit (c) 1 /(1 / n * (int( c, xi ) yi ) 2 β )) h( k )i 1

Die automatische Erzeugung neuronaler NetzwerkeDie automatische Erzeugung Neuronaler Netzwerke läuft nunletztlich wie folgt ab:1. Erzeuge zufällig die anfängliche Population der Formeln (d.h.einen Satz binär verschlüsselter, akzeptabler Formel)2. Wiederhole bis die Abbruchbedingung erreicht ist (d.h. bis dieZeit abgelaufen ist oder bis kein weiterer Fortschritt in derPopulation errecht wurde)a. interpretiere jedes Chromosom und berechne seineTauglichkeit; wenn die Tauglichkeit zufriedenstellend ist,stoppe den Algorithmus und liefere die Formel mit derhöchsten Tauglichkeit als Ergebnis zurückb. ansonsten wähle Formeln durch passendes„Hochzeitsschema“ und gebe den Formeln eineMöglichkeit im Verhältnis zu ihrer Tauglichkeit Kinder zuerzeugen.c. rekombiniere die ausgewählten Formeln neu durchCrossoverd. nehme an den Formeln der neuen Generationentsprechende Mutationen vore. gehe zu 2.

Mit dieser Implementierung des Algorithmus wurde dasfolgende dargestellte Netz erzeugt. Dieses Netz erreichteinen mittleren quadratischen Fehler von 8% und wirddurch folgende automatisch generierte Formelnbeschrieben:

Nach weiteren 141 Generationen Optimierung erreicht dasNetz [Abbildung 2.8] einen mittleren Fehler von nur 0,2%.Die das Netz codierende, automatisch generierte Formellautete (i[x] steht hier für die Eingabeneuronen, dieTransferfunktion ist hier die Sigmoidfunktion f):

Beispiel 2: Indirekte Codierung [Kitano] grammatikalische Codierung Generierung einer Konnektionsmatrix eines KNN, indemer auf ein vordefiniertes Anfangselement (Axiom)rekursiv die Regeln einer deterministischen, kontextfreienGrammatik anwendet

In Konnektionsmatrix sind Verbindungen zwischenNeuronen gespeichert, wobei eine 1 für eine Verbindungund eine 0 für keine Verbindung steht Optimierung dieser Regeln mittels GA anstatt direkteÄnderung der Verbindungen entstehende KNN sind i.a. regelmäßiger strukturiert undzeigen bessere Generalisierungsfähigkeiten als beidirekter Codierung. linke Seite der Regel besteht aus einem Non-Terminalund ihre rechte Seite aus einer 2x2-Matrix von entwederTerminals oder Non-Terminals Terminals sind Endelemente, die Bestehen oder Fehleneiner Neuronenverbindung anzeigen Non-terminals werden durch rekursive Anwendung dergrammatischen Regeln weiter transformiert

Grammatik ist als String variabler Länge repräsentiert,auf dem eine Regelmenge codiert ist GA optimiert diese Regeln Ziel: Finden guter Netzarchitekturen über die GA-basierteOptimierung der grammatischen Regeln Jeder String enthält konstanten sowie einen variablen Teil Nur variabler Teil wird durch Crossover und Mutationverändert.

Fitness bei [Kitano] Fitnessermittlung durch Transformation des„Grammatikstring“ in KNN Verbindungsgewichte und Schwellwerte werdenstochastisch initialisiert im Intervall –1,0 bis 1,0 undanschließend mit BP trainiert Über Testdaten wird die Summe der quadrierten Fehler Eermittelt Fitnessmaß ist 1/E, d.h. höhere Fitness bessereNetzleistung

Beispiel 3: Direkte Codierung: Optimierung vonNetzarchitektur und Parametern [Dasgupta undMcGregor] Anstatt nur die Topologie zu optimieren und erzeugteKNN mit Lernverfahren, wie BP zu trainieren ( wie beiindirekter Codierung von Kitano), ist es auch möglichsimultan die Netzparameter mitzuoptimieren Dasgupta und McGregor verwenden eine hierarchischeLösungsrepräsentation Jeder String besteht aus zwei Teilen Im ersten Teil (high level) ist die Konnektionsmatrixzeilenweise binär repräsentiert Der zweite Teil (low level) codiert, ebenfalls binär,Verbindungsgewichte und weitere Parameter des KNN

Sind Verbindungen zwischen Neuronen deaktiviert (Wert0 in der Konnektionsmatrix), so bleiben diekorrespondierenden Gewichte Bestandteil des Strings undwerden im Rahmen des GA weitervererbt Diese sind jedoch nicht aktiv und beeinflussen nichtdecodierte Netzkonfiguration Durch eine Änderung im high level Abschnitt des Stringskönnen sie wieder aktiviert werden daher ziehen Änderungen auf der höheren EbeneKonsequenzen auf der niedrigeren Ebene nach sich

Fitness bei [Dasgupta und McGregor] Startpopulation ist stochastisch initialisiert. Bei der Fitnessbestimmung während GA-Optimierungmuss jedes Individuum anhand beider Stringabschnitte zueinem KNN decodiert werden In Fitnessberechnung gehen Gültigkeit und Komplexitätder gefundenen Netzarchitektur Dasgupta und McGregor verwenden 2-Punkt Crossover,verschiedene Mutationsformen und rangbasierteSelektion Ungültige Architekturen werden mit höhererWahrscheinlichkeit als gültige im high level Bereichmutiert

Übersicht direkte/indirekte Codierung:Direkte Codierung:maximale Netzgröße muss vorab definiert werdenbeschränkt Suchraum, aber gute Architekturenkönnen unabsichtlich ausgeschlossen werdendaher eignet sich direkte Codierung nur für kleineKNNStringlänge wächst mit Netzgröße überproportionalIndirekte Codierung:Vermeidet Probleme direkter Codierung durch hohenAbstraktionsgradNicht geeignet um Einzelheiten der Netzarchitekturzu optimieren (z.B. Gewichte)

Netzes zu optimieren 2. Ansä tze , die die Gewichte eines neuronalen Netzes optimieren 3. Ansä tze , die gleichzeitig eine optimale Netztopologie und optimale Gewichte des neuronalen Netzes finden wollen Arten der Codierung von KNN: 1) d i r e k t e Codierung 2) i n d