Näherungsverfahren 2 SS09

Aus ProgrammingWiki

Kontakt:

Danny Rücker

Sten Major

Inhaltsverzeichnis 1 DNA Computing 1.1 Motivation 1.2 Grundlagen DNA 1.3 Anwendungsbeispiel 1.4 Vor - und Nachteile DNA - Computing 1.5 Zukunft 2 Evolutionäre Algorithmen 2.1 Biologische Grundlagen 2.2 Am Handelsreisenden Beispiel 3 Neuronale Netze 3.1 Einführung 3.2 Erstes Beispiel - Roboter 3.3 Geschichtlicher Hintergrund 3.4 biologische Grundlagen 3.5 Eigenschaften des KNN 3.6 Aufbau 3.6.1 Bestandteile 3.6.2 Beispielnetz : XOR 3.7 Netztopologien 3.7.1 Feedforward 3.7.2 Feedback 3.8 Arten des Lernens 3.9 Backpropagation 3.10 Kohonen Netze 3.11 Hopfield Netze 3.12 Anwendung Neuronaler Netze 4 Übungsaufgaben 5 Folien

DNA Computing

Motivation

NP – Probleme sind nur in exponentieller Zeit „lösbar“. Abhilfe könnte ein grundsätzlich anderer Berechnungsansatz schaffen. Als Beispiel: Supercomputer benötigen heut zu Tage für die Berechnung des kürzesten Weges einer beliebigen Rundreise durch 64 Städte, wobei jede Stadt nur ein Mal durchgangen werden kann, Jahrzehnte. Wird die Eingabe um eins erhöht, wird die Laufzeit mit Basis k der Zeitkomplexität multipliziert, dass heißt wenn k = 2 würde es zu einer Verdoppelung führen. Die Beschleunigung der Prozessorgeschwindigkeit um den Faktor 10000 würde praktisch keine Verbesserung herbeiführen.

Konventionelle Rechner arbeiten Rechenschritt für Rechenschritt(Prozessor). Durch die Gentechnik wird es möglich, gleichzeitig viele DNA Moleküle in einem Reagenzglas reagieren zu lassen. In der DNA sind Informationen kodiert. Man fasst das Reagenzglas als Computer mit zahlreichen parallel arbeitenden Prozessoren auf.

Heut zu Tage herrscht eine Beschränktheit der Miniaturisierung elektronischer Rechner. Irgendwann verlangsamt sich das exponentielle Wachstum der Rechenleistung, spätestens wenn die Transistoren auf die Größe von Atomen geschrumpft sind. Bisher verdoppelte sich die Komplexität elektrischer Systeme aller 24 Monate(Mooresche Gesetz). Daher die Idee, Berechnungen auf molekularer Ebene durchzuführen.

Auf der Suche nach neuen Wegen der Informationsverarbeitung erkennt man schon früh, an welcher Stelle die Natur überlegen ist. Obwohl die Schaltzeit von Neuronen im Bereich von einer ms derjenigen von Mikroprozessoren unterlegen ist, kann zum Beispiel ein potentielles Beutetier einen Angreifer blitzartig erkennen und entsprechend reagieren. Dies ist eine Fähigkeit, welche das Vermögen von Mikroprozessoren übersteigt und wird durch Parallelarbeit ermöglicht.

Grundlagen DNA

Grundidee

Die Grundidee besteht darin, die DNA als Datenspeicher zu verwenden. Der Aufbau der DNA ist vergleichbar mit dem Aufbau digitaler Datenträger, auf dem hintereinander veschiedene Daten abgespeichert sind. Dadurch sind Computer auf molekularer Ebene denkbar, welche die heutige Hardware an Speicherdichte, Energieausnutzung und der Anzahl der möglichen Rechenoperationen um mehrere Zehnerpotenzen übertreffen könnte.Desweiteren sollen Operationen möglich sein, dass heißt biochemische Reaktionen, die auf alle DNA Stränge wirken. Die Ausgabe wird mittels Testoperation geprüft. Die Algorithmen stellen demnach die Arbeitsvorschriften für Laboranten dar und die Hardware ist das molekularbiologische Labor mit der entsprechenden Ausrüstung.

Geht man einen Schritt weiter, kann man sagen, dass die Idee des Rechnens mit der DNA darin besteht, die durch die Evolution entstandenen Werkzeuge zu benutzen, um die davor in DNA kodierten Probleme durch Manipulation der Moleküle zu bearbeiten. Übertragen auf den Computer bedeutet dies die Manipulation von Zeichenketten. Im gewissen Sinne ist jedes Molekül ein Prozessor in einem gigantischen Parallelrechner.

Außerdem besteht die Idee das DNA Computing darin, mathematische Berechnungen auf Basis von Interaktionen zwischen organischen Molekülen an Stelle elektronischer Schaltkreise durchzuführen. Dabei werden zwei wesentliche Eigenschaften der DNA ausgenutzt. Zum einen die zuvor schon erwähnte Parallelität, da alle Reaktionen in einer Lösung nahezu gleichzeitig ablaufen. Zum anderen liefert die Watson – Crick – Basenpaarung ein leistungsfähiges Berechnungssystem. Auch zu erwähnen wäre die Verfügbarkeit. DNA ist als Rohstoff nahezu unbegrenzt verfügbar und im Vergleich zu Silizium bei gleichem Volumen 10⁹ mal energieeffizienter und die DNA stellt 10¹² mal mehr Speicher zur Verfügung und erlaubt 10¹⁵ mal so viele Operationen pro Sekunde.

Aufbau DNA

DNA kommt in allen Lebewesen vor und trägt deren Erbinformation und stellt somit den Bauplan für sämtliche Proteine eines Organismus dar. Die DNA kodiert Aminosäuresequenz der Proteine.

DNA besteht aus zwei Strängen welche umeinander gewunden sind(Doppelhelix). Jeder Strang besteht aus Desoxyribonucleotiden, welche über Phosphodidesterbindungen miteinander verbunden sind. Desoxyribonucleotid enthält eine organische Base, den Zucker Desoxyribose und Phosphatsäurerest. Durch die lineare Anordnung der Nucleotide entsteht ein Zucker – Phosphat Rückgrat(backbone) von welchem die organischen Basen abstehen(A – Adenin , T – Thymin , G – Guanin, C – Cytosin). Durch den parallelen Verlauf stehen sich immer zwei Basenpaare gegenüber, dazwischen befinden sich Wasserstoffbrückenbindungen. Mögliche Paare sind A und T,T und A,G und C,C und G (komplementäre Basen). Bildlich kann man sich die Doppelhelix als Strickleiter vorstellen, welche zu einer Spirale verdreht ist. Die Holme entsprechen den Zucker – Phosphat Backbones, die Sprossen entsprechen den gepaarten Basen.

Da verschiedene Nucleotide in beliebiger Reihenfolge verkettbar sind, können so auch die Aufgaben des molekularen Computers mit dem vierelementigen Alphabet in molekularer Schrift geschrieben und als DNA – Molekül gespeichert werden.

Operationen

• Anfertigung von Strängen(Synthese)
• Vervielfältigen von DNA : Die DNA kann durch Erwärmen in zwei einzelne Stränge aufgeteilt werden. Nach der Temperaturabsenkung kommt es wieder zur Ausbildung von Basenpaaren. Mit Hilfe der Polymerase Kettenreaktion können Einzelstränge wieder zu einem Doppelstrang ergänzt werden. Diese Verfahren beschreibt das wiederholte Denaturieren und das Ergänzen der Einzelstränge mit freien Nucleotiden. Somit kann die DNA Menge mit exponentieller Geschwindigkeit vervielfältigt werden.
• schneiden durch Restriktionsenzyme
• verbinden(Ligieren) zweier DNA - Ketten durch DNA - Ligase(ist ein Enzym, welches die Verbindung zweier hintereinanderliegender DNA - Stränge zu einer längeren DNA - Sequenz ermöglicht)
• gezieltes einsetzen von DNA - Stücken an definierten Stellen in ein anderes DNA - Molekül, dadurch wird die Möglichkeit gegeben neue Moleküle zu bilden(Rekombination)
• Bestimmung der Sequenz von DNA(Sequenzierung)

Anwendungsbeispiel

Hamilton Pfad Problem

Das HPP beschäftigt sich mit dem Finden eines Weges durch einen Graphen. Dabei wird jeder Knoten genau einmal durchschritten bzw. es müssen alle Knoten durchgangen werden. Adleman hat 1994 bewiesen, dass sich dieses Problem mit Hilfe von DNA Molekülen lösen lässt. Seit dem wurden auch andere Probleme mit dem Prinzip des DNA - Computing gelöst bzw. es wurde beschrieben, wie man es mit DNA lösen würde. Das HPP zählt zu den NP schweren Problemen. Dabei wird die Brute Force Methode angewandt. Alle Lösungen werden in einer chemischen Lösung in DNA codiert erzeugt und in einer Folge von parallelen Laborschritten auf Richtigkeit überprüft. Im Bestreben, ein allgemeingültiges Verfahren zu finden, wurden viele Modelle entwickelt. In den meisten Modellen werden zwei Phasen beschrieben:

• Initialisierungsphase: Die DNA Sequenzen werden erzeugt, welche die Lösungskandidaten für das zu lösende Problem codieren.
• Berechnungsphase: Schlechte Kandidaten, also diese, die keine gültige Lösung darstellen, werden aussortiert.

Schritt 1: DNA Synthese

Jede Stadt wird durch eine Abfolge von 8 Basen codiert. Städteverbindungen werden durch die komplementäre Abfolge der vier letzten Basen des Ausgangspunktes und der ersten vier Basen des Zielortes gebildet. Die DNA Sequenz wird maschinell erstellt(übersetzen des Problems auf DNA), da es ein zuverlässiges und kostengünstiges Verfahren ist.

Stadt	Stadtnamecode	Komplement
Zittau	ACTT GCAG	TGAA CGTC
Görlitz	TCGG ACTG	AGCC TGAC
Dresden	GGCT ATGT	CCGA TACA
Berlin	CCGA GCAA	GGCT CGTT

Weg	codierter Weg
Zittau - Görlitz	GCAG TCGG
Zittau - Berlin	GCAG GGCT
Görlitz - Dresden	ACTG GGCT
Görlitz - Berlin	ACTG CCGA
Görlitz - Zittau	ACTG ACTT
Dresden - Berlin	ATGT CCGA

Schritt 2: Nasschemie im Reagenzglas

Durch Ligase werden DNA Stränge verknüpft. Diese Reaktionsschritte werden wiederholt. In der Lösung befinden sich nun eine Vielzahl von Reiseverbindungen wobei viele falsch und wenige richtig sind. In der Ligasereaktion werden die Moleküle bausteinartig zu DNA – Doppelsträngen zusammengefasst, die den denkbaren Pfaden entsprechen. Um alle möglichen Lösungskandidaten zu erzeugen, müssen hinreichende Mengen von DNA – Molekülen zusammengegeben werden. Im Reagenzglas befinden sich einzelne Moleküle der Städte,aber auch die Stränge der Stadtverbindungen.

Schritt 3

Hier erfolgt eine Hydrolyse der Doppelhelix. Die Stränge, welche den richtigen Start - und Zielort haben, werden vervielfältigt. Durch eine Gelelektrophorese werden diese Städte herausgefiltert, welche die richtig Stadtanzahl besitzen. Zum Schluss folgt eine Affinitätsprüfung um festzustellen, ob jede Stadt tatsächlich nur ein mal besucht wurde. Mit diesen Verfahren ist sichergestellt, dass nur Pfade weiterbenutzt werden, welche den HPP - Regeln entsprechen.

Schritt 4

Hier erfolgt die Sequenzanalyse des durch Aufarbeitung isolierten DNA – Einzelstranges. (Bsp.: Zittau – Görlitz – Dresden – Berlin)

Algorithmus zum HPP

Eingabe: gerichteter Graph G mit n Knoten und dem Startknoten V_in und Endknoten V_out

1. Erzeuge Instanzen aller möglicher Pfade
2. Verwirf Pfade, die nicht mit V_in beginnen und/oder nicht in V_out enden
3. Verwirf Pfade, die nicht exakt n Knoten haben
4. Verwirf Pfade, die nicht jeden Knoten mindestens einmal enthalten

Ausgabe: verbliebene Pfade sind Hamilton Pfade

Anwendung des HPP

Bei der Herstellung von Leiterplatten, wo der Bohrer alle Lochpositionen nacheinander anfahren muss, wird die angewandt. Zur Verkürzung der Bohrzeit sollte ein möglichst minimaler Weg vorliegen. Dadurch werden auch die Kosten gesenkt. Ein weiteres Beispiel wäre zum Beispiel das Anfahren von Stationen in automatischen Lagern durch Roboter oder aber auch das Austragen der Post.

Vor - und Nachteile DNA - Computing

Vorteile

Durch die hohe und massive Parallelarbeit erreicht man eine sehr hohe Rechengeschwindigkeit. Desweiteren die schon erwähnte Energieffizienz. Mit einem Joule lassen sich 2*10¹⁹ Operationen durchführen.

Außerdem besitzt eine DNA - Lösung eine enorm hohe Speicherkapazität. In einem Liter DNA - Lösung, in der z.B. 6g DNA mit 6*10¹⁹ Molekülen mit jeweils 200 Basenpaaren enthalten sind, existiert eine Speicherkapazität von 3*10¹⁹ Terabyte.

Auch ist die Haltbarkeit der Daten wesentlich höher als bei digitalen Speichermedien. Die älteste identifizierte und analysierte DNA ist 125 Mio. Jahre alt(ein in Bernstein eingeschlossenes Insekt). Computerbänder aus den 50er Jahren sind heut schon zum größten Teil unlesbar.

Nachteile

Zu den Nachteilen gehört ganz klar die langwierige Aufarbeitung zur Ermittlung der Rechenergebnisse. Desweiteren ist DNA Computing fehleranfällig, da die DNA unveränderlich ist. Die Berechnungszeit zur Lösung eines Problems wächst in DNA Computern zwar nicht exponentiell, aber die Menge der benötigten DNA tut dies. Im Falle des obigen HPP Beispiels würde man für den Fall mit 200 Städten eine Menge von DNA benötigen, welche mit der Erdmasse vergleichbar ist. Aber auch selbst primitive Aufgaben können im Reagenzglas Stunden dauern, da die Aufarbeitung langwierig ist.

Zukunft

Die Zukunft dieser Technologie ist noch recht ungewiss. Man ist heut zu Tage auf dem Stand der Entwicklung, verglichen mit der Geschichte der Rechentechnik, als die Transistoren erfunden wurden und damals wusste auch niemanden, was uns erwarten würde. Man strebt an, die Operationen, welche mit der DNA durchführbar sind, als Standardoperationen zur Verfügung zu haben. Besser wäre die Vermeidung der Nasschemie und die Reduktion des Aufarbeitungszyklus durch Chips mit DNA - Strängen, die selektiv die Rechenlösung binden. Praktisch ist die Idee des DNA - Computing bis heute noch nicht anwendbar.

Evolutionäre Algorithmen

Evolutionäre Algorithmen werden zur Optimierung von Problemen aus Forschung, Industrie und Wirtschaft genutzt. Sie orientieren sich dabei an unterschiedlichen Vorbildern der natürlichen Evolution. Durch unterschiedliche Schwerpunkte bezüglich der evolutionären Konzepte entstehen unterschiedliche Modelle der evolutionären Algorithmen. Sie entlehnen Begriffe und Vorgänge aus der Biologie um so in einem anderen Zusammenhang Verfahren zur Lösung von Optimierungsproblemen zu beschreiben. Im Vordergrund steht dabei der Begriff der Population, bei der es sich um eine Ansammlung von Lösungskandidaten handelt, welche als Individuen bezeichnet werden. Diese Population wird anschließend einer Evolution unterworfen, wobei sich nun durch Modifikation und Selektion bessere Individuen herausbilden. Das „beste Individuum“ steht hierbei für die „beste“ Lösung des Problems.

Biologische Grundlagen

• Gene

Ein Gen ist ein Abschnitt auf der Desoxyribonukleinsäure (DNA), der die Grundinformationen zur Herstellung einer biologisch aktiven Ribonukleinsäure (RNA) enthält

• Chromosomen

sind Strukturen, die Gene und damit Erbinformationen enthalten. Sie bestehen aus DNA, die mit vielen Proteinen verpackt ist.

• Individuen

Unter einem Individuum versteht man etwas Einzelnes in seiner Gesamtheit mit allen Eigenheiten und Eigenarten, die in ihrem Gesamtgefüge wiederum bestimmend sind für seine Individualität. Es bezeichnet also das räumlich und qualitativ einmalige Einzelwesen

• Kreuzung

Als Kreuzung wird die gezielte Auswahl von Individuen und Veranlassung der geschlechtlichen Fortpflanzung zwischen zwei verschiedenen Arten verstanden.

• Selektion

Die Selektion besteht in der Reduzierung des Fortpflanzungserfolgs bestimmter Individuen einer Population mit der Folge, dass andere Individuen, die im Rückblick als „überlebenstüchtiger“ erkennbar sind, sich stärker vermehren.

• Mutation

Eine Mutation ist eine Veränderung des Erbgutes eines Organismus durch Veränderung der Abfolge der Nukleinbasen oder durch Veränderung der Chromosomenzahl

• Population

Eine Population ist eine Gruppe von Individuen der gleichen Art, die aufgrund ihrer Entstehungsprozesse miteinander verbunden sind, eine Fortpflanzungsgemeinschaft bilden.

Am Handelsreisenden Beispiel

Problemstellung

Der Inhalt des Handlungsreisendenproblems ist, dass ein Handelsreisender viele Städte besuchen muss um seine Ware zu verkaufen. Er hat allerdings nur wenig Zeit und braucht daher den Kürzesten Weg durch all diese Städte ohne eine zweimal besuchen zu müssen. Es stellt sich also die Aufgabe, eine möglichst kurze Tour durch die gegebenen Städte zu finden.

• Wir verwenden im weiteren einen Evolutionären Algorithmus um dieses Problem gut zu lösen.

Gesucht ist in unserem Falle eine Reise durch 5 Städte, was ein relativ überschaubares Problem darstellt, aber zum Zwecke der Erläuterung gerade richtig ist.

Diese Städte sind untereinander alle frei ansteuerbar und jede dieser Stadt zu Stadt Verbindungen besitzt eine gegebene Länge.

Kante	Abstand	Kante	Abstand	Kante	Abstand
(v1,v2)	5	(v2,v3)	10	(v3,v5)	17
(v1,v3)	8	(v2,v4)	4	(v3,v6)	8
(v1,v4)	11	(v2,v5)	9	(v4,v5)	6
(v1,v5)	3	(v2,v6)	12	(v4,v6)	5
(v1,v6)	7	(v3,v4)	6	(v5,v6)	11

Daraus ergeben sich nun bereits bei nur 6 Städten 60 Möglichkeiten diese alle in einer Rundreise anzusteuern. Doch welche ist die Beste?

Verbindung der Biologie mit der Thematik

Um nun eine Verbindung zur Biologie herzustellen, bennenen wir die einzelnen Bestandteile genauer.

• Die einzelnen Städte werden durch die Gene verkörpert.

• Ein Individuum beschreibt eine einzige Rundreise die der Händler machen kann. (zb: v1-v3-v4-v5-v2-v6-v1)

• Jedes Individuum besitzt eine Fitness, welche in unserem Falle die Gesamtlänge einer Strecke ist.

• Mit der Population beschreibt man die Gesamtheit aller Rundreisen die absolviert werden können.

• Aus dieser Population wird versucht die beste Route zu ermitteln.

• Als Kreuzung wird es immer dann bezeichnet, wenn ein neuer Weg erstellt wird.

• Die Selektion bezeichnet die Auswahl der Individuen zur Kreuzung.

Das Indiviuum welches die größte Fitness besitzt, kann demzufolge eine Lösung für das Problem sein, oder aber auch die höchste Wahrscheinlichkeit besitzen, sich zu reproduzieren.

Ablaufplan für den Algorithmus

• Erzeugen einer Anfangspopulation, wobei eins der erstellten Individuen ein „Greedy-Individuum“ sein sollte.

• Anschließend werden diese Individuen bewertet. In unserem Falle also die Länge der Strecke betrachtet. Danach werden sie der Größe nach sortiert.

• Die Fitness der einzelnen Individuen ergibt sich direkt aus der Länge.

• Nun werden neue Individuen, also Strecken, durch Kreuzung erzeugt.

(Selektion und Mutation)

• Anschließend werden die nun neu erzeugten Individuen entsprechend ihrer Fitness in die sortierte Liste eingefügt und dementsprechend viele schlechtere gestrichen.

• Angeben einer Wahrscheinlichkeit, bei welcher es zur Mutation kommen kann. Das bedeutet, dass zufällig ein Gene bei einem Individuum getauscht wird, was zur folge hat, dass der Optimierungsprozess nicht in eine Schleifenbahn gerät und es auch selbst eine neue, bessere Lösung darstellen kann.

• Diese Vorgänge werden so oft wiederholt bis n-Generationen erzeugt wurden.

• Das daraus resultierende Ergebnis wird meist ein „gutes“ oder auch „sehr gutes“ Ergebnis sein, muss es aber nicht.

Neuronale Netze

Einführung

Es gibt Kategorien von Problemen, welche sich nicht in einen Algorithmus fassen lassen. Ein Beispiel dafür wäre das Problem der Bestimmung des Kaufpreises einer Immobilie. Dieser Preis ist von sehr vielen unterschiedlichen Faktoren abhängig. Ein Mensch kann den Preis ungefähr bestimmen, ein Computer jedoch mangels Algorithmus zunächst nicht. Der Unterschied in diesem Falle zwischen Computer und Mensch ist der Aspekt der Lernfähigkeit. Menschen lernen, um auf solche Fragestellungen eingehen zu können. Der Computer besitzt nur Recheneinheiten und Speicher, er kann komplizierteste mathematische Operationen ausführen, lernen kann er jedoch nicht.

Theoretisch gesehen müsste ein Computer leistungsfähiger sein. Er besitzt 10⁹ Transistoren mit einer Schaltzeit von 10^-9 Sekunden. Das Gehirn eines Menschen besitzt zwar 10¹¹ Neuronen, jedoch beträgt die Schaltzeit 10^-3 Sekunden. Der Unterschied zwischen Gehirn und Computer ist, dass der größte Teil des Gehirns durchgehend arbeitet, beim Computer sind unter Umständen einige Bestandteile passiv. Das Gehirn arbeitet also massiv parallel. Der Computer ist ein statisches Objekt, das Gehirn gesehen als biologisches Neuronales Netz kann sich umstrukturieren und lernen.

Die einzige Folge dessen ist, dass man sich die Eigenschaften des Gehirns zu nutzen macht, und eine ähnliche Struktur im Computer verwendet. Künstliche Neuronale Netze(KNN) sind also motiviert durch die Ähnlichkeit zu erfolgreichen biologischen Systemen. Das heißt man übernimmt die sehr einfachen aber massiv prallel arbeitenden Neuronen und die Lernfähigkeit.

Ein neuronales Netz muss nicht explizit für eine bestimmte Aufgabe programmiert werden. Es kann zum Beispiel aus verschiedenen Trainingsbeispielen lernen und aus diesen generalisieren bzw. assoziieren(dazu später mehr). Nach dem Training dieser Beispiele kann das KNN ähnliche Probleme derselben Klasse lösen, ohne dass diese explizit trainiert wurden. Dies ermöglicht unter anderem eine große Fehlertoleranz, auch gegenüber vertauschten Eingabedaten.

Kommen wir noch einmal zur Fehlertoleranz zurück. Der Mensch besitzt 10¹¹ Neuronen welche sich kontinuierlich umstrukturieren oder durch Einflüsse von außen umstrukturiert werden. Zum Beispiel verliert man bei einem „Vollrausch“ 10⁵ Neuronen, trotzdem wird die Kognitionsfähigkeit nicht wesentlich beeinträchtigt. Das Gehirn ist also tolerant gegenüber inneren Fehlern und gegen Fehlern von außen. Zum Beispiel kann man eine schlechte Handschrift auch noch lesen, selbst wenn man einige Buchstaben nicht erkennen kann. Moderne Technologie ist nicht automatisch Fehlertolerant. Zum Beispiel gibt es keinen PC, wo ein Festplattencontroller fehlt und die Grafikkarte dessen Aufgabe übernimmt.

Wichtig noch einmal zu erwähnen wäre, dass das neuronale Netz nur eine Art Inspiration darstellt. Man versucht nicht ein neuronales Netz exakt biologisch nachzubauen, sondern man abstrahiert von der biologischen Informationsverarbeitung.

Erstes Beispiel - Roboter

Anhand der oben gegebenen Einführung möchte ich sofort ein kleines Beispiel anbringen. Der gegebene Roboter(siehe Abbildung 3.1) besitzt zwei Motoren, zwei hintere Sensoren und sechs vordere. Aus den 8 Sensoren werden die Eingabedaten gewonnen. Sie liefern immer einen reellen Zahlenwert, also es existiert immer ein Input . Der Roboter soll einfach nur fahren und anhalten wenn ein Hindernis im Weg steht. Der Output ist also binär, das Haltesignal für Stopp und für weiter fahren. Es gibt also eine Funktion

Der klassische Weg

Man entwickelt eine Schaltung oder schreibt ein kleines Computerprogramm, welches die oben gegebene Abbildung realisiert(bei diesem Beispiel wäre dies ohne weiteres möglich). Man studiert die technischen Referenzen der Sensoren, nimmt sich die Kennlinien um zu wissen was für Werte bei welchen Hindernisentfernungen ausgegeben werden und bindet diese Werte in das Regelwerk ein. Dies ist der Weg der klassischen künstlichen Intelligenz. Wenn die Abbildung bekannt ist, ist dies auch ein guter Weg.

Der Weg des Lernens

Diesen Weg sollte man einschlagen, wenn Abbildungen oder Probleme nicht auf Anhieb erfassbar sind. Wir zeigen dem Roboter verschiedene Situationen in denen er sich befinden kann und er soll selbst lernen, was er zu tun hat(siehe unten). Dabei wird der Roboter einfach in die Landschaft platziert, damit er Sensorwerte für die verschiedenen Situationen liefern kann. Die Ausgabe geben wir selbst hinzu(H). Er soll praktisch lernen, wann er anzuhalten hat und wann nicht. Man stellt sich das neuronale Netz als Blackbox vor. Man kennt nicht den Aufbau sondern man betrachtet es rein in seinem Verhalten nach außen. Also wir wissen nur, dass die 8 Sensoren Inputwerte liefern und diese werden auf einen binären Ausgabewert abgebildet. Die Situationen wo wir den Roboter in die Landschaft setzen und ihm das H angeben nennt man Trainingsbeispiele. Demnach besteht ein Trainingsbeispiel aus einem beispielhaften Input und dem dazugehörigen gewünschten Output.

Wie transportiert man die Informationen in das neuronale Netz?

Die Lern – bzw. Trainingsbeispiele lassen sich durch einfache Lernverfahren einen KNN beibringen. Ein Lernverfahren ist ein einfacher Algorithmus bzw. eine mathematische Formel. Nach diesen soll das Netz lernen, für eine vorgegebene Eingabe eine gewünschte Ausgabe zu produzieren. Hier wird dann das KNN, wenn wir alles richtig gemacht haben und die richtigen Beispiele ausgewählt haben, aus den Beispielen generalisieren und eine allgemeingültige Vorschrift finden, wann anzuhalten ist. Die Beispiele sind beliebig erweiterbar, man könnte zum Beispiel die Motoren separat ansteuern wodurch Roboter Hindernissen ausweichen könnte.

Das Ziel hinter der ganzen Sache ist nicht das Auswendiglernen der Beispiele, sondern dass Erkennen eines Prinzips hinter der ganzen Sache. Der Roboter soll das KNN im Idealfall in beliebigen Situationen anwenden und Hindernissen ausweichen. Insbesondere soll der Roboter das Netz während des Fahrens kontinuierlich bzw. oft direkt hintereinander befragen können um ständig Hindernissen ausweichen zu können. Es existiert also ein ständiger Kreislauf: Der Roboter befragt das Netz, fährt in eine Richtung, die Sensorwerte verändern sich, er befragt wieder das Netz, verändert die Position, Sensorwerte werden wieder verändert usw. Das System lässt sich auch auf dynamische Hindernisse adaptieren, also auch auf bewegliche Hindernisse.

Geschichtlicher Hintergrund

Die Geschichte der Neuronalen Netze beginnt bereits in den frühen 1940er Jahren und damit fast zeitgleich mit der Geschichte der programmierbaren elektronischen Computer.

• 1943 waren es Warren McCulloch und Walter Pitts, welche eine Art neurologischer Netzwerke beschrieben. Außerdem bauten sie Schwellwertschalter durch Neuronen nach und zeigten, dass selbst einfache Netze dieser Art praktisch jede logische oder auch arithmetische Funktion berechnen können.

• 1947 waren es erneut Walter Pitts und Waren McCulloch die die Entwicklung entscheidend voran brachten, in dem sie ein Praktisches Anwendungsgebiet nannten. Es handelte sich dabei um die Erkennung räumlicher Muster durch Neuronale Netze.

• 1949 formulierte Donald O. Hebb die klassische Hebb’sche Lernregel, welche in ihrer allgemeinen Form die Basis fast aller neuronalen Lernverfaren darstellt.

• 1950 vertrat der Neuropsychologe Karl Lashley die These, dass Informationen verteilt im Gehirn gespeichert werden. Begründet hat er diese These durch Versuchen an Ratten.

• 1951 begann die Blütezeit der Forschung über Neuronale Netze. Marvin Minsky entwickelte den Neurocomputer Snark, welcher seine Gewichte automatisch justieren konnte. Er wurde aber nie praktisch eingesetzt, da er zwar rechnete, aber niemand wirklich sagen konnte was.

• 1956 treffen sich auf dem Dartmouth Summer Research Project renommierte Wissenschaftler und aufstrebende Studierende und diskutieren darüber, wie man am besten ein Gehirn nachbilden könne. Dabei bilden sich Unterschiede zwischen Top-Down- und Bottom-Up-Forschung heraus. Die früheren Anhänger der Artificial Intelligence wollen die Fähigkeiten durch Software nachbilden. Im Gegensatz dazu die Anhänger der Neuronalen Netze, welche das Systemverhalten durch Nachbildng kleinster Systemteile, der Neuronen, erreichen wollen.

• 1957-1958 wurde der erste erfolgreiche Neurocomputer, der Mark I Perceptron, welcher mit einem 20x20 Pixel großen Bildsensor einfache Ziffern erkennen konnte, entwickelt.

• Von hier an beschleunigte sich die Entwicklung.

• 1959 beschrieb Frank Rosenbaltt verschiedene Varianten des Perceptrons.

• 1960 gab es bereits das wohl erste kommerziell verbreitete Neuronale Netz und zwar in fast jedem analogen Telefon zum Zwecke der Echtzeit-Echofilterung.

• 1961 stellte Karl Steinbuch Techniken zur assoziativen Speicherung vor.

• 1972 stellt Teuvo Kohonen ein Modell des linearen Assoziators, eines Assoziativspeichermodells vor.

• 1976 – 1980 stellt Stephen Grossberg viele Arbeiten vor, in denen eine Vielzahl von neuronalen Modellen mathematisch genau analysiert wurden.

• 1982 beschreibt Teuvo Kohonen die nach ihm benannten selbstorganisierenden Karten und John Hopfield die nach ihm benannten Hopfieldnetze.

• 1985 löst John Hopfield das Traveling Salesman Problem durch Hopfieldnetze.

Ab dieser Zeit gab es dann einen rapiden Anstieg der Forschungsgebiete welche bis heut immer weiter geführt werden.

An der Fülle dieser vielen Ereignisse in diesem nahezu kurzen Zeitraum und die Tatsache, dass viele der berühmtesten Vertreter dieser Verfahren und Theorien noch am Leben sind, sieht man gut die Aktualität und Präsenz dieses Themas.

biologische Grundlagen

Aufbau Neuronen

Das Nervensystem enthält alle Neuronen eines Systems. Die Funktionen eines Neurons sind die Aufnahme, die Verarbeitung und die Weiterleitung von Reizen. Sie bestehen aus Dendriten, Axon, Zellkörper und dem Zellkern sowie aus Synapsen(siehe Abbildung 3.2). Zur Erregungsleitung läuft das elektrische Signal durch das Axon. An den Synapsen wird das Signal chemisch weitergereicht. Die Synapsen sind mit anderen Zellen verbunden, entweder andere Neuronen und andere Empfängerzellen. Die Dendriten sind feine plastische Verästelungen des Zellkörpers die über die Synapsen Kontakt zu anderen Zellen herstellen und von diesen Erregungen empfangen. Sie empfangen also Aktionspotentiale von anderen Neuronen durch deren Axone. Das Axon ist also zuständig für die Übertragung des Aktionspotential einer Nervenzelle und leitet diese zu den Synapsen und damit an andere Zellen weiter(z.B. an andere Nervenzellen, Muskelnerven, Drüsenzellen etc.).

Erregung von Nerven

Zwischen dem Axon und der Umgebung besteht ein Spannungsunterschied von 70mV. Dies wird als Ruhepotential bezeichnet. Durch den Reiz erfolgt eine Spannungsänderung von 90mV. Das Aktionspotential entspricht der Erregung, diese wird von den Neuriten bis zum Endknöpfchen(Synapse) weitergereicht.

synaptische Übertragung

Die oben erwähnte Erregung geht durch die ganze Nervenzelle zur Synapse. Es wird eine Überträgersubstanz frei, welche über den synaptischen Spalt zur gegenüberliegenden Membran(bzw. Dendrite) strömt. Diese wird anschließend erregt(siehe Abbildung 3.3).

Eigenschaften des KNN

Ein künstliches Neuronales Netz kann man als Abbildungsvorschrift mit einer Menge von Ausgaben verstehen. Man verknüpft einzelne Prozessoren, welche einfache Rechnungen ausführen können. Die Verbindung zweier Prozessoren wird durch ein Gewicht bewertet. Das heißt, dass ein Gewicht die Stärke der Verbindung zwischen zwei Neuronen angibt. Ein positives Gewicht gibt an, dass das Neuron einen erregenden Einfluss auf das andere Neuron hat. Ist das Gewicht negativ, existiert ein hemmender Einfluss. Kein Einfluss existiert, wenn das Gewicht gleich null ist. Durch die wiederholte Eingabe der Trainingsmuster wird die Stärke der Verbindungen zwischen den Neuronen modifiziert. Das Wissen der KNN wird sozusagen in den Gewichten gespeichert. Durch das Lernen werden die Gewichte verändert, abhängig von den Lernregeln. Das heißt, dass bei der Lern – bzw. Trainingsphase die Gewichte korrigiert werden.

Die Modifikation des Gewichtes hat Einfluss auf das Ein – Ausgabeverhalten. Die schon erwähnte Lernfähigkeit ist anwendungsunabhängig bzw. es können anwendungsunabhängige Lernverfahren angewandt werden. Desweiteren gibt es die Möglichkeit, Trainingsdaten zu reproduzieren. Desweiteren verfügt das KNN über eine Robustheit gegenüber verrauschten Daten. Die schon erwähnte Fehlertoleranz hat zur Folge, dass Aufgrund der verteilten Informationsrepräsentation ein geeignetes Verhalten im Falle eines Ausfall einzelner Subkomponenten gefunden werden kann. Durch geeignete Trainingsbeispiele und den entsprechenden Lernstrategien können neuronale Netze Entscheidungsregeln bilden. Die Gültigkeit geht über Trainingsdaten hinaus was eine allgemeine Bedeutung(Generalisierungsfähigkeit)zur Folge hat. Die Performanz ist überaus hoch.

Aufbau

Bestandteile

Ein KNN besteht aus simplen Recheneinheiten(Neuronen) sowie gerichteten und gewichteten Verbindungen zwischen diesen.

formale Beschreibung

Ein KNN kann als sortiertes Tripel angegeben werden.

• N = Menge der Neuronen
• V = sortierte Menge , Elemente sind Verbindungen von Neuron i zu Neuron j
• W = Funktion , Diese Funktion definiert die Gewichte wobei w_(i,j) das Gewicht der Verbindung von Neuron i zu Neuron j definiert

Die Gewichtungen lassen sich in quadratischer Gewichtsmatrix implementieren(Hinton Matrix). Die Zeilennummern geben an von wo die Verbindung ausgeht. Die Spaltennummern geben an welches Neuron das Ziel ist.

Verbindungen

Über Verbindungen werden Daten zwischen Neuronen übertragen.

Propagierungsfunktion

Betrachtet man ein Neuron(j) findet man meist viele Neuronen, von denen eine Verbindung zu j ausgeht, die also Ausgaben an j weiterleiten. Die PGF nimmt für ein Neuron j die Ausgaben anderer Neuronen entgegen(von denen eine Verbindung zu Neuron j existiert) und verarbeitet diese unter Berücksichtigung der Verbindungsgewichte w_(i,j) zur Netzeingabe(Eingabeelement j) welche von der Aktivierungsfunktion weiterverwendet werden kann. Die PGF verarbeitet also Eingaben zu Netzeingaben.

, wobei i die Menge der Neuronen ist

Dies wird auch als gewichtete Summe bezeichnet. Man multipliziert die Ausgabe eines jeden i mit w_(i,j) und summiert dies dann auf.

Netzeingabe : Ist das Ergebnis der PGF.

Aktivierung : Nach dem Vorbild der Natur ist jedes Neuron zu jeder Zeit zu einem bestimmten Grad aktiv bzw. gereizt. Von diesem Aktivierungszustand hängt die Reaktion des Neurons auf die Eingabe ab. Je stärker das Aktivitätslevel der sendenden Einheit und je höher das Gewicht zwischen den Neuronen ist, desto größer ist der Einfluss auf die empfangene Einheit.

Definition: Sei j ein Neuron, a_j der Aktivierungszustand und ist j eindeutig zugeordnet(ist der Grad der Aktivität des Neurons und ergibt sich aus der Aktivierungsfunktion).

Schwellenwert : Um den Schwellenwert herum reagiert AWF empfindlich. Biologisch stellt der Schwellenwert die Reizschwelle dar, ab der ein Neuron „feuert“.

Definition: sei j ein Neuron, Schwellenwert S_j ist j eindeutig zugeordnet und markiert die Stelle der größten Steigung der Aktivierungsfunktion

Aktivierungsfunktion

Die Aktivierung a_j eines Neurons j zu einem bestimmten Zeitpunkt hängt davon ab, wie sehr das Neuron aktiviert war und welche Eingaben von außen erhalten wurden.

Die Funktion verarbeitet die Netzeingabe net_j und den alten Aktivierungszustand a_j(t-1) zu einem neuen Aktivierungszustand a_j(t). Diese Funktion wird auch als Transferfunktion bezeichnet.

Ausgabefunktion

Die Ausgabefunktion berechnet die Werte die an die anderen Neuronen weitergegeben werden.

Die Funktion berechnet den Ausgabewert o_j des Neurons j an dem Aktivierungszustand a_j.

Beispielnetz : XOR

Dieses Netz besteht aus 4 Zellen(siehe Abbildung 3.6). Für die Aktivierung werden die binären Werte 0 und 1 verwendet. Die Netzeingabe wird berechnet durch die PGF:

Die Aktivierungsfunktion stellt in diesem Fall die binäre Schwellenwertfunktion dar.

Die Ausgabe ist in diesem Fall die Identität: .

• i = empfangene Unit
• j = sendende Unit
• o_j = Ausgabe anderer Neuronen bzw. Eingabe
• a_j = Aktivitätslevel
• w_(i,j) = Gewicht zwischen i und j

Die dazu gehörige Hinton Matrix ergibt sich wie folgt:

Ausgabe Neuron 1 : o1	Ausgabe Neuron 2 : o2	Eingabe Neuron 3 : net3	SW Neuron 3 : S3	Ausgabe Neuron 3 : o3	Eingabe Neuron 4 : net4	SW Neuron 4 : S4	Ausgabe Neuron 4 : o4	XOR
0	0	net3 = 0*1+0*1=0	1,5	0	net4 = 0*1+0*1+0*(-2)=0	0,5	0	0
0	1	net3 = 0*1+1*1=1	1,5	0	net4 = 0*1+1*1+0*(-2)=1	0,5	1	1
1	0	net3 = 1*1+0*1=1	1,5	0	net4 = 1*1+0*1+0*(-2)=1	0,5	1	1
1	1	net3 = 1*1+1*1=2	1,5	1	net4 = 1*1+1*1+1*(-2)=0	0,5	0	0

Netztopologien

Unter diesem Themenkomplex sind alle hier vorgestellten Netztopologien als Beispiele aufgelistet. Die Hinton Matrix ist jeweils auch dazu angegeben.

Feedforward

Die Neuronen sind in Schichten eingeteilt. Das Feed Forward Netz besteht aus einer Eingabeschicht, n versteckten Verarbeitungsschichten sowie einer Ausgabeschicht. Von jedem Neuron sind Verbindungen nur zu Neuronen in der nächsten Schicht erlaubt(in Richtung der Ausgabeschicht). Die Verarbeitungsschicht ist nach außen nicht sichtbar und wird auch als hidden layer bezeichnet.

Feedforward mit Shortcut Connection

Es sind außerdem Verbindungen erlaubt, welche eine Schicht überspringen. Das heißt Verbindungen dürfen nicht nur in die nächste, sondern auch in die übernächste Schicht.

Feedback

Man spricht von Feedback bzw. Rückkopplung, wenn sich ein Neuron auf irgendeine Weise oder durch irgendeinen Verbindungsweg selbst beeinflussen kann.

direkte Rückkopplung

Es existieren Verbindungen von einem Neuron zu sich selbst. Die Neuronen können sich selbst hemmen oder stärken um so an die Aktivierungsgrenze zu kommen. In der Hinton Matrix: Diagonale darf nicht null sein.

indirekte Rückkopplung

Es sind Verbindungen in Richtung der Eingabeschicht erlaubt. Ein Neuron kann sich durch einen Umweg selbst beeinflussen. In der Hinton Matrix: unter Diagonalen nicht null.

laterale Rückkopplung

Es sind Verbindungen innerhalb einer Schicht bzw. Ebene erlaubt. Oft ist es so, dass jedes Neuron die anderen in der Ebene hemmt und sich so selbst stärkt, da nur das stärkste Neuron aktiv wird(Winner takes it all – Prinzip).

vollständig verbunden

Es sind Verbindungen zwischen allen Neuronen erlaubt, außer der direkten Rückkopplung. Außerdem müssen die Verbindungen symmetrisch sein. Jedes Neuron darf zu jedem anderen eine Verbindung unterhalten. Allerdings kann so jedes Neuron ein Eingabeneuron werden(dies ist der Grund warum direkte Rückkopplung nicht erlaubt ist). Es sind auch keine klar definierten Schichten mehr gegeben. In der Hinton Matrix:alles ungleich null außer die Diagonale.

Arten des Lernens

Wie schon weiter oben erwähnt, besteht ein interessantes Merkmal der KNN in der Fähigkeit sich Problemen durch Training vertraut zu machen und diese nach ausreichendem Training lösen zu können durch Generalisierung(auch bis dato unbekannte Probleme derselben Klasse). Grundsätzlich verändert sich NN mit Veränderung seiner Bestandteile. Ein KNN kann lernen in dem es:

• Neue Verbindungen entwickelt
• Vorhandene Verbindungen löscht
• Verbindungsgewichte ändert
• Schwellwerte von Neuronen ändert
• Funktionen abwandelt(PGF,AWF,AF)
• Neue Neuronen entwickelt
• Vorhandene Neuronen löscht

Das Verändern der Verbindungsgewichte stellt die meist benutzte Lernmethode dar. Wie schon oben beschrieben lernt ein KNN, indem die Verbindungsgewichte durch Lernverfahren modifiziert werden. Es gibt drei wesentliche Arten des Lernens:

unüberwacht

Dies stellt die biologisch plausibelste Lösung dar, ist allerdings nicht für alle Probleme geeignet. Gegeben ist nur das Eingabemuster und das Netz versucht ähnliche Muster zu erkennen und in ähnliche Kategorien zu klassifizieren.

bestärkt

Dem Netz wird nach erfolgtem Durchlauf ein Wahrheitswert oder ein reeller Wert geliefert, welcher definiert, ob das gelieferte Ergebnis mit dem gewünschten Ergebnis überein stimmt. Ist im Wesentlichen besser geeignet als unüberwachtes Lernen, da man dem KNN Anhaltspunkte zur Lösungsfindung liefert.

überwacht

Es existiert eine Trainingsmenge von Eingabemustern sowie deren korrekte Ergebnisse in Form der genauen Aktivierung sämtlicher Ausgabeneuronen. Für jedes in das Netz eingegebene Trainingsmuster kann so die Ausgabe direkt mit der korrekten Lösung verglichen werden und anhand der Differenz die Netzgewichtung geändert werden. Das Ziel hinter diesem Verfahren besteht darin, die Gewichte zu verändern, sodass das Netz nach dem Training nicht nur selbstständig Ein – und Ausgabemuster assoziieren kann, sodern auch zu bis dato unbekannte, aber ähnliche Eingabemuster , plausible Lösungen liefern kann.

Hebb - Lernregel

Die Hebbsche Lernregel stellt in allgemeiner Form fast alle neuronalen Lernverfahren dar. Je häufiger ein Neuron A gleichzeitig mit einem Neuron B aktiv ist, umso bevorzugter werden diese beiden Neuronen aufeinander reagieren. Hebb wies dies anhand von Veränderungen der synaptischen Übertragung nach. Im KNN wird diese Veränderung der synaptischen Übertragung als Gewichtsänderung des neuronalen Graphen abgebildet.

w_(i,j) = Veränderung des Gewichtes von Neuron j zu Neuron i, also die Veränderung der Verbindungsstärke der beiden Neuronen

n = Lernrate --> konstanter Faktor

a_i = Aktivierung von Neuron i o_j = Ausgabe von Neuron j das mit Neuron i verbunden ist

Delta Regel

Diese Regel beruht auf dem Vergleich zwischen dem gewünschten und dem tatsächlichen beobachteten Output.

–

Es gibt drei Möglichkeiten: Wenn die beobachtete Aktivität zu niedrig ist werden die Gewichte zwischen dem Sender/Empfänger erhöht. Ist die beobachtete Aktivität zu hoch werden Gewichte verringert, das heißt die Verbindungen werden geschwächt. Sind sie gar gleich groß, folgt keine Änderung, da der gewünschte Wert ausgegeben wird. Daraus ergibt sich die Formel:

a_j = die Gewichte stärker verändert, welche größeren Einfluss auf den Fehlerterm haben

Backpropagation

Backpropagation ist ein Verfahren, welches auch bei neuronalen Netzen mit Hidden-Units angewendet werden kann. Es stellt eine Rechenvorschrift dar, mit der die Gewichte zu den Hidden-Units modifiziert werden können.

Entwickelt wurde es in den 70er Jahren, wo es aber zunächst in Vergessenheit geriet. Ein Jahrzehnt später, im Jahre 1986, wurde der Backpropagation Ansatz besonders bekannt durch Rumelhart, Williams und Hinton, deren Verfahren eine Verallgemeinerung der Delta-Regel darstellt.

Problemstellung

Bei Netzen mit Hidden-Units ist das Problem, dass man keine direkten Fehler für die Neuronen der Hidden-Schicht bestimmen kann. Das kommt daher, da man nur den Output für die Output-Schicht kennt, nicht aber den für die Hidden-Schicht.

Modifikation

Um trotzdem eine Modifikation der Gewichte über die entstehenden Fehler vornehmen zu können, gibt es 3 Schritte in der Trainingsphase für jede Gewichtsveränderung.

• Forward-Pass

Wie in Trainings- und Testphase üblich, werden den Input-Neuronen Reize präsentiert und anschließend der Output des neuronalen Netzes berechnet.

• Fehlerbestimmung

In diesem Schritt werden die gewünschten Output-Werte mit denen im Forward-Pass ermittelten Werten abgeglichen. Sind diese Fehler größer als eine vorgegebene Güteschwelle, folgt der Backward-Pass. Überschreiten sie diese Schwelle nicht, wird die Trainingsphase abgebrochen.

• Backward-Pass

Dieser Schritt ist der innovative Kern des Backpropagation Verfahrens. Die Fehlerterme breiten sich hier nun in entgegengesetzter Richtung bis zur Input-Schicht aus. Auf diesem Weg werden nun mit Hilfe der Fehlerterme Schicht um Schicht die Gewichte des Netzes modifiziert, so dass diese Fehlerterme kleiner werden.

Gewichtsanpassung

Die Gewichtsanpassung erfolgt über das Gradientenabstiegsverfahren. Zuerst wird eine zufällige Gewichtskombination erstellt. Für diese wird anschließend der Gradient [7] bestimmt und nun um eine vorgegebene Länge hinabgestiegen, also die Gewichte verändert. Für die nun neu erhaltene Gewichtskombination wird der Vorgang nun wiederholt. Dies geht solange, bis ein lokales Minimum erreicht ist.

Kohonen Netze

Das Kohonennetz, oder auch Self-Organizing Maps, ist eine Erweiterung der kompetitiven Netze. Bei ihnen wird der korrekte Output nicht festgelegt und anschließend an das neuronale Netz zurückgemeldet, sondern sie arbeiten ohne einen externen Lehrer.

• Diese Netze können also in selbstorganisierender Weise lernen, Karten eines Inputraums zu erstellen. Sie clustern also den Inputraum.

Geschichte

Den Namen hat das Kohonennetz von dem finnischen Ingenieur Teuvo Kohonen, welcher in den 80er Jahren ein sehr bekanntes Kohonennetz konzipierte. Allerdings wurden auch schon in den 70er Jahren Ansätze durch Grossberg und Christoph von der Malsburg entwickelt.

Vorteil

Der Vorteil der Kohonennetze gegenüber anderen ist, dass sie im Vergleich zu konventionellen neuronalen Netzen biologisch plausibler sind, da der Mensch vermutlich auch Probleme in der Regel ohne externen Lehrer löst.

Aufbau eines Kohonennetz

Ein Kohonennetz besteht aus zwei Schichten von Neuronen, der Inputschicht und der Outputschicht, wobei von jedem Input-Neuron eine Verbindung zu jedem Output-Neuron führt.

Berechnung

Die Berechnung findet in 5 Schritten statt.

1.Startwert festlegen:

Zuerst werden die Gewichte zufällig generiert, die Lernkonstante wird festgelegt, sowie die Nachbarschaftsfunktion und die maximale Anzahl an Durchläufen.

2.Auswahl eines Inputvektors

Hier wird ein Inputvektor ausgewählt oder auch zufällig generiert.

3.Aktivitätsberechnung und Auswahl

Nun wird die Aktivität der Output-Neuronen berechnet und die Unit mit der maximalen Erregung wird Ausgewählt. Das ist genau diese, welche den geringsten Abstand zum Inputmuster aufweist.

4.Gewichtsmodifikation

Jetzt werden die Gewichte modifiziert. Zuerst das der Gewinner-Unit, so dass sie dem Input-Vektor ähnlicher wird. Anschließend die der Nachbarschaft von eben dieser Gewinner-Unit. Zudem wird noch der Radius für die Nachbarschaft eingegrenzt und die Lernparameter reduziert, wodurch die Korrektur der Gewichte zu Beginn des Trainings größer ausfallen, als am Ende. Nun geht es wieder mit dem ersten Schritt weiter.

5.Abbruch

Abgebrochen wird wenn die maximale Anzahl der Durchläufe erreicht ist.

Beispiel für ein Kohonennetz

Hopfield Netze

Das Hopfield-Netz wurde nach dem amerikanischen Wissenschaftler John Hopfield benannt, welcher das Modell 1982 bekannt machte.

Struktur

Ein Hopfield-Netz ist ein Feedback-Netz, also ein Netz mit Rückkopplung. Des Weiteren existiert nur eine Schicht, welche Ein- und Ausgabeschicht zugleich ist. Jedes der Neuronen in diesem Modell ist mit jedem Anderen, ausgenommen sich selbst, verbunden. Diese Neuronen können die Werte 1 und -1 annehmen. Auch sind im Hopfield-Netz alle Gewichte symmetrisch. Das ist zwar biologisch nicht sinnvoll, erlaubt aber damit die Analyse der Netzwerke mit Methoden der Mechanik.

Anwendung

Hopfield-Netze können als Autoassoziativspeicher benutzt werden, zum Zwecke der Musterrekonstruktion. Dies geschieht in 3 Phasen.

• Trainingsphase

Hier wird dem Netz eine Anzahl von vorgegebenen Mustern eingespeichert. Dies realisiert man durch das Einstellen der Gewichte.

• Anlegen neuer Eingaben

Jetzt nach dem Lernen, werden die Knoten wieder in den Anfangszustand zurück versetzt und ein neues, vielleicht verrauschtes oder unvollständiges Muster zum Test initialisiert.

• Rechenphase

Nun wird Neuron für Neuron aktualisiert und geschaut ob der aktivierte Punkt nahe einem gelernten Muster liegt. Ist das der Fall, wird er auf 1 gesetzt. Falls nicht auf 0. Dies geschiet solange bis ein stabieler Endzustand erreicht ist, was dann gleichbedeutend der Assoziation ist.

Ergebnis

Das Ergebnis ist je nach Anzahl der Iterationsschritte ein mehr oder weniger verrauschtes Bild, oder konnte nicht erkannt werden, befindet sich aber in einem stabielen, "unechten" Endzustand.

Anwendung Neuronaler Netze

Steuerung

KNN werden effektiv für die Steuerung mobiler Roboter eingesetzt, unter anderem für fahrerlose Fahrzeuge(autonome Landfahrzeuge). Diese wurden so trainiert, dass sie die schwierige Aufgabe erlernt haben, einen Lastwagen mit minimalem Aufwand an eine Laderampe zu steuern. Außerdem werden KNN eingesetzt bei der Positionierung großer Elektroden in elektrischen Schweißöfen von Stahlwerken. Desweiteren werden sie eingesetzt um Prozesse in Chemiewerken zu steuern und zu optimieren. Es werden hohe Summen gespart durch die verbesserte Prozessteuerung und die optimierte Materialausnutzung.

Diagnostik

Im Bereich der Diagnostik werden KNN vor allem im Bereich der Medizin, im Ingenieurwesen und im Fertigungswesen eingesetzt. Man benötigt konkrete Assoziationen zwischen Eingabemustern(die z.B. irgendein Symptom oder regelgerechtes Verhalten beschreiben) und der entsprechenden Krankheit, dem Hardwarefehler bzw. anderen Fehlfunktionen.

Vorhersage

KNN sind für Vorhersagen sehr gut geeignet. Sie können sagen, ob etwas passiert oder nicht, wann ein Ereignis eintritt oder mit welcher Wahrscheinlichkeit. Einsatzgebiete sind vor allem Produktionsunternehmen, Meteorologen und Banken(für Kreditwürdigkeiten von Firmen). Für ein genaues Ergebnis müssen dem KNN ausreichend viele Beispiele in Form von Paaren(Muster/Ergebnis) trainiert werden. KNN muss dann von den Mustern generalisieren um assoziative Ergebnisse vorherzusagen. Viele Unternehmen im Finanzbereich verwenden bereits KNN für Aktienkäufe, Devisenhandel etc.

Mustererkennung

KNN sind gut geeignet Wahrnehmungsaufgaben zu lösen. Unter diese gehört auch die Erkennung komplexer Muster, visuellen Bildern von Objekten, gedruckte oder handschriftliche Zeichen und Spracherkennung. KNN sind den herkömmlichen Methoden zur Mustererkennung weit überlegen.

Übungsaufgaben

DNA Computing

Gehen Sie das in der Vorlesung angegebene Beispiel noch einmal durch und verinnerlichen Sie die Idee des DNA Computing. Nutzen sie auch folgende Quelle: Computing with DNA

Evolutionäre Algorithmen

Benutzen Sie das Applet auf Travelling Salesman um die Auswirkung verschiedener Kreuzungsmethoden auf die Zeit der Berechnung für das Travelling-Salesman-Problem zu testen.

Neuronale Netze

Sehen Sie sich noch einmal die Beispiele aus der Vorlesung bzw. im Wiki an und wenden Sie die Grundlagen auf folgende Aufgaben an.

1. Realisierung AND mit NN

Eingabe 1	Eingabe 2	AND
0	0	0
0	1	0
1	0	0
1	1	1

• Variieren Sie die Gewichte bzw. den Schwellenwert in der Abbildung so, dass die logische AND Verknüpfung als Ergebnis heraus kommt.

Dabei ist die Ausgabe gegeben durch:

2. Realisierung OR mit NN

Eingabe 1	Eingabe 2	OR
0	0	0
0	1	1
1	0	1
1	1	1

• Variieren Sie die Gewichte bzw. den Schwellenwert in der Abbildung so, dass die logische OR Verknüpfung als Ergebnis heraus kommt. Die Ausgabefunktion kann von Aufgabe 1 übernommen werden.

3. Würde sich mit dieser Darstellung auch die logische XOR Verknüpfung darstellen lassen?

4. Benutzen Sie das Applet auf Kohonen-Netz-Applet um die Auswirkung des Blockradius und der Lernrate im Kohonen-Netz zu testen.

Folien

ENA2.pdf (0.9 MB)