Projectile Learning - Entwicklung und Implementierung eines neuen Lernverfahrens für künstliche neuronale Netze mit dem Ansatz einer globalen Suche auf der Fehlerfunktion

Inhaltsverzeichnis

1 Einleitung

2 Einführung in die künstlichen neuronalen Netze
2.1 Biologisches Vorbild
2.2 Modellierung von Neuronen
2.3 Vernetzung der künstlichen Neuronen
2.4 Lernverfahren
2.5 Backpropagation

3 Probleme des Backpropagation Algorithmus
3.1 Lokale Minima
3.2 Flache Plateaus
3.3 Verlassen guter Minima

4 Modifikation von Backpropagation
4.1 Momentum Term
4.2 Weight Decay
4.3 Quickprop
4.4 δ − δ Lernregel

5 Lösungsansatz
5.1 Flight of a Projectile in the Conformational Space
5.2 Projectile Learning
5.2.1 Verwendetes Framework
5.2.2 Implementierung des Projektilfluges
5.2.3 Kollision des Projektils mit der Fehleroberfläche
5.2.4 Resultat des Lernverfahrens

6 Anwendung
6.1 Testfälle
6.1.1 Wirbelsäulenstörung
6.1.2 Brustkrebs Vorhersage
6.1.3 Parkinson
6.2 Auswertung der Testfälle

7 Fazit

8 Anlage

Abbildungsverzeichnis

1 Zwei verbundene Nervenzellen. [Lip06, S. 11]

2 Zwei idealisiert dargestellte Neuronen. [Lip06, S. 45]

3 Beispiele von Ausgabefunktionen. [Lip06, S. 50]

4 Beispiel eines künstlichen neuronalen Netzes aus H Schichten. [Lip06, S. 51]

5 Beispiel einer Fehlerkurve. [Lip06, S. 94]

6 Der Algorithmus landet in diesem Fall in einem lokalen Minimum, welches nicht dem globalen Minimum entspricht. [Lip06, S. 105] .

7 Flaches Plateau [Lip06, S. 106]

8 Ein gutes Minimum wird verlassen. [Lip06, S. 108]

9 Bewegung eines zweidimensionalen Objektes unter Einfluss der Gravitationskraft. [Har08, S. 415]

10 Vektor Analysis der zweidimensionalen Bewegung unter Einfluss der Gravitationskraft. [Har08, S.416]

11 Geschwindigkeit vor und nach einem elastischen Stoß. [Har08, S.416]

12 Basis Klassendiagramm für Neuroph (http://neuroph.sourceforge .net/images/uml/BasicClassDiagram.jpg)

13 Veranschaulichung einer Kollision des Projektils

14 Veranschaulichung einer Kollision des Projektils

15 Graphische Oberfläche, in der die Voreinstellungen des Algorith- mus eingestellt werden können

16 Parameterwahl für das ProjectileLearning

17 Ausgabe des ProjectileLearning

18 Parameterwahl für das ProjectileLearning

19 Ausgabe des ProjectileLearning

20 Parameterwahl für das ProjectileLearning

21 Ausgabe des ProjectileLearning

1 Einleitung

Das menschliche Gehirn ist zu faszinierenden Leistungen fähig. In manchen Be- reichen ist es jedem Computer überlegen. Zum Beispiel könnte heute kein Com- puter im Straßenverkehr ein Auto so sicher lenken wie ein Mensch. Andererseits löst ein Computer komplizierte Rechenaufgaben viel schneller als ein mensch- liches Gehirn. Mit künstlichen neuronalen Netzen versucht die Informatik, das Gehirn zu imitieren, um die Vorzüge beider Systeme zu vereinigen.

Künstliche neuronale Netze bestehen aus künstlichen Neuronen, die mitein- ander zu einem Netz verbunden sind. Dabei können die Verbindungen unter- schiedlich stark ausgeprägt sein. Damit ein solches Netz bestimmte Probleme lösen kann, muss es zunächst mit einem Lernverfahren trainiert werden. Dabei werden dem Netz Beispiele in Form von Eingabedaten und den dazugehörigen korrekten Ausgabedaten vorgelegt. Manche Lernverfahren arbeiten auch mit Trainingsdaten, die keine korrekten Ausgabedaten enthalten.

Bei den Lernverfahren handelt es ich um eine Minimierung der Fehlerfunk- tion des künstlichen neuronalen Netzes. Diese suchen ein lokales Minimum der Fehlerfuntkion. Dieses ist nicht optimal, da es nach dem Finden eines lokalen Minimums der Funktion noch kleinere Werte der Fehlerfunktion geben kann.

In dieser Arbeit entwickle und implementiere ich ein Lernverfahren für künst- liche neuronale Netze, welches ein globales Minimum der Fehlerfuntkion sucht. Als Grundlage benutze ich einen von Harkiolakis entwickelten Algorithmus zur globalen Optimierung eines nicht nichtlinearen Gleichungssystem durch den Flug eines Projektils. [Har08] Mithilfe dieses Verfahrens wurden in bekannten Optimierungsproblemen neue Minima gefunden. Dieses übertrage ich auf ein Lernverfahren für künstliche neuronale Netze mit dem Versuch bessere Netze zu finden als mit den standard Lernverfahren.

In Kapitel 2 gebe ich zunächst eine Einführung in die künstlichen neuronalen Netze, weil diese im Zentrum dieser Arbeit stehen. Dabei orientiere ich mich an den ersten beiden Kapiteln des Buches Soft-Computing von Wolfram Lippe. [Lip06] Ich gehe auf das biologische Vorbild der künstlichen neuronalen Netze ein. Dann behandle ich das Modellieren von Neuronen und ihre Vernetzung. Außerdem führe ich Lernverfahren ein und insbesondere den BackpropagationAlgorithmus. Als Quelle für die Einführung diente [Lip06] und wird in diesem Kapitel nicht mehr aufgeführt.

Ich beschränke mich in dieser Arbeit auf vollständig ebenenweise verbun- dene Feedforward-Netze, die klassisch mit einem Backpropagation-Algorithmus trainiert werden. Die Probleme dieses Lernverfahrens lege ich in Kapitel 3 dar. Dabei gehe ich auf lokale Minima, Flache Plateaus und Verlassen von guten Minima ein.

Im vierten Kapitel erörtere ich Modifikationen von Backpropagation, die versuchen diese Probleme zu lösen. Ich behandle in diesem Kapitel das Momentum Term, Weight Decay, Quickprop und δ − δ Lerverfahren.

Meinen Lösungsansatz stelle ich in Kapitel 5 vor. Zunächst gehe ich auf den Algorithmus von Harkiolakis [Har08] ein. Dann zeige ich auf, wie ich mit Hilfe von diesem das Lernverfahren Projectile Learning entwickelt und in Java implementiert habe.

In Kapitel 6 teste ich meinen Algorithmus mit Hilfe von drei verschiedenen Anwendungsfällen. Zunächst beschreibe ich die Anwendungsfälle und begründe dann die Wahl der Parameter. Ich gebe dann den resultierenden Fehler und die gebrauchte Laufzeit des Algorithmus an. Zum Vergleich führe ich bei den Testfällen auch klassische Backpropagation Lernverfahren aus. Im Anschluß werte ich die erhaltenen Resultate aus.

Schließlich ziehe ich in Kapitel 7 mein Fazit aus dieser Arbeit. Hier fasse ich meine Ergebnisse zusammen und bewerte diese. Ich weise auf Probleme hin und gebe einen Ausblick auf mögliche Verbesserungen meines Algorithmus.

2 Einführung in die künstlichen neuronalen Netze

Künstliche neuronale Netze, kurz KNN, sind Konstrukte aus dem Bereich der künstlichen Intelligenz. Der Ansatz ist dabei, ein System zu schaffen, welches nach dem Prinzip eines Gehirns arbeitet. Dieses besteht aus kleinen Einheiten, den Neuronen. Obwohl in diesen komplizierte biochemische Reaktionen ablau- fen, gelten sie aus der Sicht der Informationstechnik als einfache Objekte. Die große Leistungsfähigkeit des Gehirns entsteht erst durch die sehr hohe Anzahl der Neuronen, ihre starke Vernetzung und ihre schnelle Schaltzeit.

In einem künstlichen neuronalen Netz werden Neuronen als Knoten eines gerichteten Graphen modeliert. Nachdem man gewisse Lernalgorithmen auf ein solches Netz anwendet, soll das Netz Berechnungen durchführen können, für das es trainiert worden ist. Dann arbeitet das künstliche neuronale Netz wie eine Black Box. Es akzeptiert eine Eingabe und liefert ein entsprechendes Ergebnis. Es ist jedoch nicht nachvollziehbar, weshalb das Netz gerade so aufgebaut sein muss, um das gewünschte Verhalten zu erzeugen.

In dieser Arbeit entwickele ich einen neuen Lernalogorithmus für künstliche neuronale Netze. Dafür ist es wichtig die Funktionsweise eines solchen Net- zes zu verstehen. Deshalb werde ich in diesem Kapitel eine Einführung in die künstlichen neuronalen Netze geben. Zunächst gehe ich auf das biologische Vor- bild ein. Dann gehe ich auf die Modellierung von Neuronen ein, wie diese ein Netz bilden und wie dieses dann trainiert werden kann. Anschließend stelle ich das Backpropagtion Netz vor, welches in der Praxis am häufigsten vorkommt.

2.1 Biologisches Vorbild

Künstliche neuronale Netze sind nach dem Vorbild des Gehirns entwickelt worden. Ein Gehirn ist aus Nervenzellen, auch Neuronen genannt, aufgebaut. In Abbildung 1 sind zwei solcher Neuronen, die miteinander verbunden sind, dargestellt. Außerdem werden dort die Grundkomponenten benannt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Zwei verbundene Nervenzellen. [Lip06, S. 11]

Zunächst lässt sich in der Abbildung erkennen, dass das Neuron einen Zell- kern besitzt, in welchem sich die DNA, also die Erbinformation, befindet. Das Neuron ist von einer Zellmembran umgeben und außer dem Zellkern befinden sich im Neuron noch weitere, nicht in der Abbildung dargestellte, Organelle, die für das ÜberlebenderZellewichtigsind.Dazugehören beispielsweise die Mitochondrien, die für die Energieversorgung der Zelle zuständig sind.

Die länglichen, röhrenförmigen Fortsätze des Neurons werden als Dendriten bzw. Axone bezeichnet. Die Dendriten sind meistens stark verästelt und für das Empfangen von Eingangssignalen zuständig. Diese Signale werden vom Zellkern verarbeitet. In Abhängigkeit von diesen und anderen Randbedingungen werden dann Ausgangssignale generiert. Diese werden über das Axon, welches ebenfalls Verästelungen ausbildet, zum nächsten Neuron geleitet. Dabei befindet sich am Ende jeder Abzweigung des Axons eine Synapse, die auf einem Dendriten eines anderen Neurons aufliegen kann.

Der Aufbau und die Wirkungsweise der Neuronen ist im Detail sehr kompli- ziert. Deshalb habe ich nur eine grobe Übersicht über das biologische Vorbild der künstlichen neuronalen Netze gegeben. Abschließend gebe ich in diesem Abschnitt noch einige Größen des menschlichen Nervensystems an, welche in Tabelle 1 aufgeführt sind.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Größenordnungen des menschlichen Nervensystems. [Lip06, S. 53]

Eine weitere interessante Größe ist die Vernetzung der Nervenzellen. Je- de Nervenzelle bekommt Eingangssignale von durchschnittlich 10.000 anderen Nervenzellen und eine Nervenzelle gibt für 10.000 andere Nervenzellen Aus- gangssignale aus.

2.2 Modellierung von Neuronen

In diesem Abschnitt werde ich nun beschreiben, wie nach dem biologischen Vorbild aus dem letzen Abschnitt Neuronen modelliert werden. Es werden die drei wichtigsten Komponenten berücksichtigt. Die Dendriten, der Zellkörper und das Axon. In Abbildung 2 sind zwei idealisierte Neuronen zu sehen, zwischen denen eine Verbindung besteht.

Die Zellköper werden als Objekte a i modelliert, welche Eingangssignale verarbeiten und daraus ein Ausgangssignal o i generieren. Eine Verbindung über eine Synapse zwischen einem Axon eines Neurons a i mit einem Dendriten eines Neurons a j wird mit einer Verbindung w ij modelliert. Diese wird typischerweise durch eine reelle Zahl charakterisiert. Je höher diese Zahl ist, desto aktiver ist diese Verbindung. Das bedeutet in diesem Fall, dass das Ausgangssignal o i einen hohen Einfluss auf das Neuron a j ausübt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Zwei idealisiert dargestellte Neuronen. [Lip06, S. 45]

Ein künstliches Neuron ist also ein Gebilde, welches mehrere Eingangssignale von anderen künstlichen Neuronen empfangen kann. Die Eingangssignale werden darüber hinaus je nach Akitivität der entsprechenden Verbindung unterschied- lich gewichtet. Diese gewichteten Eingangssignale werden zunächst verarbeitet und dann wird aus diesem Ergebnis ein Ausgangssignal generiert. Somit kann ein künstliches Neuron auf folgende Weise formal beschrieben werden:

Definition 2.1 (künstliches Neuron) Ein k ü nstliches Neuron ist ein Tupel (x, w, f a , f o , o) bestehend aus:

- Eingabevektor [Abbildung in dieser Leseprobe nicht enthalten]
- Gewichtsvektor [Abbildung in dieser Leseprobe nicht enthalten]
- Aktivierungsfunktion f a mit f a[Abbildung in dieser Leseprobe nicht enthalten]
- Ausgabefunkion f o mit f o[Abbildung in dieser Leseprobe nicht enthalten]
- Ausgabewert des Neurons o mit o[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Beispiele von Ausgabefunktionen. [Lip06, S. 50]

Abbildung in dieser Leseprobe nicht enthalten

Die Ausgabefunktion eines künstlichen Neurons ist im einfachsten Fall eine binäre Schwellenwertfunkion. Diese gibt den Wert 1 aus, falls die Aktivierungs- funktion über einem gewissen Schwellenwert liegt. Ansonsten gibt sie 0 aus. Häufiger werden jedoch sigmoide Funkionen gebraucht, die wie folgt definiert sind:

Definition 2.2 (Sigmoide Funktion) Eine Funktion s c[Abbildung in dieser Leseprobe nicht enthalten] hei ß t sigmoide Funktion einer Neuronenzelle c, wenn sie monoton wachsend und differenzierbar ist und es gelte

Abbildung in dieser Leseprobe nicht enthalten

In Abbildung 3 sind einge Beispiele für Ausgangsfunktionen dargestellt. Die beiden unteren Funktionen werden am häufigsten gebraucht. Von diesen werde ich für die Netze in dieser Arbeit meist die logistische Funktion verwenden.

Das künstliche Neuron berechnet also den Ausgabewert o, welcher dann an ein weiteres Neuron weitergeleitet werden kann. Wie man nun künstliche Neuronen zu einem künstlichen neuronalen Netz zusammenschließen kann, werde ich im nächsten Abschnitt erläutern.

2.3 Vernetzung der künstlichen Neuronen

Zunächst gebe ich die formale Definition eines neuronalen Netzes an.

Definition 2.3 (Neuronales Netz) Ein neuronales Netz ist ein Paar (N, V) mit einer Menge N von Neuronen und einer Menge V von Verbindungen. Es besitzt die Struktur eines gerichteten Graphen, f ü r den die folgenden Einschr ä nk ungen und Zus ä tze gelten:

- Die Knoten des Graphen hei ß en Neuronen.
- Die Kanten hei ß en Verbindungen.
- Jedes Neuron kann eine beliebige Menge von Verbindungen empfangen, ü ber die das Neuron seine Eingaben erh ä lt.
- Jedes Neuron kann genau eine Ausgabe ü ber eine beliebige Menge von Verbindungen aussenden.
- Das Neuronale Netz erh ä lt aus Verbindungen, die der

” Au ß enwelt “ ent-

springen, Eingaben und gibt seine Ausgaben ü ber in der dende Verbindungen ab.

” Au ß enwelt “ en-

Die Neuronen im neuronalen Netz können in Schichten einteilt werden. Da- bei gehören die Neuronen, welche keine Eingabe von anderen Neuronen erhalten, zu einer Eingabeschicht. Diese erhalten eine Eingabe von außerhalb des Netzes.

Neuronen, dessen Ausgabe nicht zu anderen Neuronen weitergeleitet wird, werden zu einer Ausgabeschicht gezählt. Ihre Ausgabe ist das Ergebnis des Netzes. Zwischen diesen Schichten können noch beliebig viele verborgene Schichten vorhanden sein. Ein Beispiel eines künstlichen neuronalen Netzes, bestehend aus H Schichten, ist in Abbildung 4 zu sehen.

Abbildung 4: Beispiel eines künstlichen neuronalen Netzes aus H Schichten. [Lip06, S. 51]

Abbildung in dieser Leseprobe nicht enthalten

Die Verbindungen zu einem Neuron hin bilden seinen Eingabevektor, zu dem auch ein Gewichtsvektor gehört (Siehe Definition 2.1). Die Neuronen in der Eingabeschicht [Abbildung in dieser Leseprobe nicht enthalten] ermöglichen eine Eingabe in das Netz. Das vorliegende Netz besitzt n solcher Neuronen. Diese werden Eingabeneuronen genannt und haben jeweils nur einen Eingabewert mit dem Gewicht 1. Die letzte Schicht[Abbildung in dieser Leseprobe nicht enthalten] bestehend aus m Neuronen, ist die Ausgabeschicht, dessen Neuronen das Ergebnis des Netzes ausgeben. Dazwischen befinden sich noch [Abbildung in dieser Leseprobe nicht enthalten] verborgene Schichten.

Jede Verbindung des Netzes ist eine Komponente eines Gewichtvektors eines Neurons. Die Gewichte der Verbindungen werden in einer Matrix [Abbildung in dieser Leseprobe nicht enthalten] zusammengefasst. Dabei sind die Komponenten w ij der Matrix das Gewicht der Verbindung von Neuron i zu Neuron j. Da die Gewichte reelle Zahlen sind, können die Verbindungen bei positiven Werten eine anregende Wirkung, bei negativen Werten eine hemmende Wirkung, auf das folgende Neuron haben.

Wenn es in einem künstilchen neuronalen Netz einen Pfad gibt, der von einem Neuron zu demselben Neuron führt, dann zählt das Netz zu den Netzen mit Rückkopplungen, welche auch rekurrente Netze gennant werden. Der Graph, der das Netz beschreibt, ist dann ein zyklischer Graph. Diese Netze mit Rückkopplung werden in vier Kategorien eingeteilt.

1. Netze mit direkten Rückkopplungen: Neuronen können Verbindungen mit sich selbst haben.
2. Netze mit indirekten Rückkopplungen: Neuronen können Verbindungen in Richtung anderer Neuronen aus niederen Schichten haben.
3. Netze mit Rückkopplungen innerhalb einer Schicht: Neuronen können innerhalb einer Schicht zyklisch verbunden sein.
4. Vollständig verbundene Netze: Neuronen können beliebig verbunden sein.

Gibt es keinen Pfad, der von einem Neuron zu sich selbst zurück führt, dann zählt das Netz zu den Netzen ohne Rückkopplungen, auch Feedforward-Netze genannt. Der Graph, der das Netz beschreibt, ist dann ein azyklischer Graph. Diese Netze ohne Rückkopplung lassen sich ebenfalls in mehrere Kategorien einteilen.

1. Ebenenweise verbundene Feedforward-Netze Neuronen können nur Verbindungen zur nächsten Schicht haben.

2. Allgemeine Feedforward-Netze: Neuronen können auch Verbindungen zu Neuronen aus beliebig höheren Schichten haben. Verbindungen, die mehr als eine Schicht überspringen werden Shortcuts genannt.

3. Vollständig ebenenweise verbundene Feedforward-Netze: Jedes Neuron hat eine Verbindung zu jedem Neuron aus der nächsten Schicht. Es sind keine Shortcuts vorhanden.

2.4 Lernverfahren

Bisher habe ich nur dargelegt, wie ein künsliches neuronales Netz aufgebaut sein kann und wie dieses auf eine Eingabe eine Ausgabe produziert. Damit das Netz aber die erwünschten Ergebnisse liefert, müssen die Neuronen und Verbindungen in einer passenden Konstellation vorliegen. Um diese herzustellen, muss das Netz mit einem Lernverfahren trainiert werden.

Zunächst beschränke ich mich hier auf Netze mit nur einem Ausgabeneuron. Die Ausgabe o des Neztes soll dann bei der Eingabe der Werte x 1 , ..., x n die Ausgabe f (x 1 , ..., x n) erzeugen. Das heißt, das Netz soll die gewünschte Funktion f, die ich im weiteren Verlauf als Zielfunktion bezeichne, an der Stelle (x 1 ,...,x n) berechnen. Idealerweise soll die Ausgabe o genau gleich dem Funktionswert der Zielfunktion sein. Da dies jedoch meist nicht erreicht werden kann, wird versucht, die Abweichungen möglichst gering zu halten.

Dazu wird von einem Netz, mit für die Zielfunktion richtigen Anzahl von Eingabe- und Ausgabeneuronen, ausgegangen. Ein Lernverfahren führt dann wiederholt gewisse Änderungen am Netz durch, bis es zufriedenstellende Ergeb- nisse liefert. Was genau zufriedenstellend bedeutet, muss von dem Lernverfahren durch ein Abbruchkriterium realisiert werden. Folgende Änderungen können an einem Netz durchgeführt werden, wobei ein Lernverfahren einen oder mehrere dieser Punkte verwenden kann:

- Verbindungen hinzufügen oder entfernen
- Gewichte der Verbindungen ändern
- Neuronen hinzufügen oder entfernen
- Aktivierungsfunktion oder Ausgabefunktion ändern

Um das Obengenannte auf Netze zu verallgemeinern, die mehrere Ausga- beneuronen besitzen, fasst man ihre Ausgabe in einem Vektor zusammen. Die Ausgabe der einzelnen Neuronen ist Enrique Iglesias. Dann ist die Ausgabe des Net- zes Enrique Iglesias). Die Funktion, die das Netz dann berechnen soll, ist dannEnrique Iglesias.

Die Lernverfahren verfolgen einen iterativen Ansatz. Zunächst berechnet das Netz ein Ergebnis zu einer Eingabe, dann wird das Netz entsprechend des Lernverfahrens angepasst und der Vorgang wiederholt. Alternativ wird das Netz immer erst nach einer gewissen Zahl von Berechnungen modifiziert. Dabei kann das Lernverfahren in drei Kategorien eingeteilt werden.

1. ÜberwachtesLernen: Bei jeder Berechnung des Neztes wird dessen Ausgabe mit der korrekten Ausgabe verglichen. Dazu müssen die korrekten Ausgaben der jeweiligen Eingaben bekannt sein.
2. Bestärkendes Lernen: Bei jeder Berechnung des Netzes wird nur überprüft, ob die Ausgabe richtig oder falsch ist.
3. Unüberwachtes Lernen: Es gibt während des Lernens keine Information darüber, ob ein Ergebnis richtig oder falsch ist.

[...]