Dipl.-Inform. Martin Lösch Labor Wissensrepräsentation
kurze Wiederholung der letzten Stunde: Neuronale Netze
Dipl.-Inform. Martin Lösch
[email protected] (0721) – 608 45944
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Übersicht • Neuronale Netze
– Motivation – Perzeptron – Multilayer Neural Networks
• Grundlagen für praktische Übungen
• Aufgaben der letzten Stunde
2
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
NEURONALE NETZE
3
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Motivation • menschliches Gehirn und PC-Rechner komplementär in
ihren Stärken und Schwächen • Rechner sollen Vorteile des menschlichen Gehirns
ebenfalls nutzen – hohe Parallelisierung – Robustheit – etc.
• Gehirn besteht aus einzelnen Gehirnzellen (Neuronen), die durch Vernetzung erst Macht gewinnen
4
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufbau Perzeptron • einzelne künstliche Nervenzelle • verarbeitet Eingabesignale zu einzelnem Ausgabesignal • Aufbau:
5
. . .
x1
xn
x0=1 w1
x2 w2
wn
w0
Σ
€
o = { 1 wixi ≥θi=1
n
∑−1 sonst
x – Eingabevektor t – Target (Soll-Ausgabe)
w – Gewichtsvektor o – Output (Ist-Ausgabe)
Bias – Trick
€
x0 =1w0 = −θ
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Perzeptron verstehen • geometrische Interpretation: Trennhyperebene (in R2:
Gerade) • Gewichte definieren genaue Lage der Ebene (Gewichte =
Normale der Ebene) • Gewichtete Summe = Skalarprodukt aus Eingaben und
Gewichtsvektor
6
p1 • Gewichtsvektor > 0p2 • Gewichtsvektor > 0n1 • Gewichtsvektor < 0n2 • Gewichtsvektor < 0
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Lernen - Geometrische Interpretation
€
Hilfsmenge′ N = ′ x | ′ x = −x,∀x ∈ N{ }
Neues Lernproblemxw > 0 ,∀x ∈ ′ N ∪ P Im Beispiel: alle xi aus P
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Perzeptron – Lernalgorithmus
Start: Gegeben Lerndatenmenge P ∪ N Der Gewichtsvektor w(0) wird zufällig generiert. Setze t:=0.
Testen: Ein Punkt x in P ∪ N wird zufällig gewählt. Falls x ∈ P und w(t)⋅x > 0 gehe zu Testen Falls x ∈ P und w(t)⋅x ≤ 0 gehe zu Addieren Falls x ∈ N und w(t)⋅x < 0 gehe zu Testen Falls x ∈ N und w(t)⋅x ≥ 0 gehe zu Subtrahieren
Addieren: Setze w(t+1) = w(t)+x. Setze t:= t+1. Gehe zu Testen.
Subtrahieren: Setze w(t+1) = w(t)-x. Setze t:=t+1. Gehe zu Testen.
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Multi Layer Neural Network (MLNN) • Netzaufbau: mehrere versteckte (innere) Schichten
• Lernverfahren: Backpropagation-Algorithmus [Rumelhart86, Werbos74]
• Neuronenaufbau: nichtlineare Aktivierungsfunktion -1
i1
i2
i3
i4
i5
-1
-1
9
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
. . .
x1
xn
x0=1 w1
x2 w2
wn
w0
Σ
Aufbau der Neuronen
• xij = i-te Eingabe des Neurons j • wij = das Gewicht zwischen Neuron i und Neuron j • netj = ∑iwijxij Propagierungsfunktion • oj = Ausgabe des Neurons j • tj = Zielausgabe (target) des Ausgabeneurons j • f(x) = Aktivierungsfunktion
• output = Menge der Ausgabeneuronen • Downstream (j) = direkte Nachfolger des Neurons j
10
nichtlinear, wichtig für Lernalgorithmus
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Backpropagation Algorithmus I • Vorgaben
– Menge T von Trainingsbeispielen (Eingabevektor/Ausgabevektor)
– Lernrate η – Netztopologie
• Anzahl und Ausmaße der Zwischenschichten • Schichten sind vollständig vorwärts gerichtet
verbunden
• Lernziel – Finden einer Gewichtsbelegung W, die T korrekt
wiedergibt
11
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Backpropagation Algorithmus II • Initialisieren der Gewichte mit kleinen zufälligen Werten
• Wiederhole… – Auswahl eines Beispielmusters d – Bestimmen der Netzausgabe – Bestimmen des Ausgabefehlers (bzgl. Sollausgabe) – Sukzessives Rückpropagieren des Fehlers auf die einzelnen
Neuronen
– Anpassen der Gewichtsbelegung um
• … solange ein gewähltes Abbruchkriterium nicht erfüllt ist!
12
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Topologieauswahl • Zusammenhang zwischen Anzahl der (hidden) layer und
Zielfunktion? – 3 Layer (1 hidden Layer - sigmoid):
• jede Boolsche Funktion • jede kontinuierliche beschränkte Funktion
[Cybenko 1989, Hornik et al. 1989] – 4 Layer (2 hidden Layer -sigmoid)
• beliebige Funktionen mit beliebiger Genauigkeit [Cybenko 1988]
• Schon eine geringe Tiefe ist ausreichend
13
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Lernverhalten - Topologieauswahl • Anzahl der Neuronen pro Schicht im Bezug zu der Anzahl
von (stochastisch unabhängigen) Lerndaten ist wichtig • Aber: allgemeine Aussage nicht möglich
• Beispiel: gestrichelte Kurve soll eingelernt werden
wenig Neuronen
viele Neuronen wenig Lerndaten
14
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Auswahl repräsentativer Trainingsbeispiele • Lerndaten
– für die Anpassung der Gewichte • Verifikationsdaten
– für das Testen der Generalisierung
• gute Verteilung der Beispiele – Klassifikation: Daten aus allen Klassen – Regression: gesamter Definitionsbereich
• Beispiele insbesondere aus komplexen Regionen – Klassifikation: Randregionen zwischen Klassen – Regression: Verlaufsänderungen
15
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Overfitting • Fehler auf Verifikationsdaten steigt ab einer Anzahl von
Lernzyklen
• Mögliches Abbruchkriterium für Lernvorgang
16
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
GRUNDLAGEN FÜR PRAXIS-ÜBUNGEN
17
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
C++-Library Flood • Open Source Neural Networks Library in C++
• verfügbar unter http://www.cimne.com/flood/download.asp
• Bietet – Perzeptronen – Multi-layer Netzwerke – verschiedene Trainingsalgorithmen – weitere Utilities
• Verwendbar zur Lösung der folgenden Aufgaben
18
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
AUFGABEN AUS LETZTER STUNDE
19
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 1: Einrichtung • Einrichtung der Library für die weitere Verwendung
– Download – Entpacken – in Visual C++ geeignet einbinden
• von allen erfolgreich beendet?
20
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 2: Perzeptronen (1) a) Verwende die Klasse Perceptron der Flood-Library, um
von Hand einen logischen AND-Operator zu programmieren (2 Eingänge, 1 Ausgang, 1&1=1, 1&0=0, 0&1=0, 0&0=0).
• von allen erfolgreich beendet? • mögliche Lösung:
21
AndOp = new FL::Perceptron(2); FL::Vector<double> weights(2); AndOp.set_activation_function(FL::Perceptron::Linear); … AndOp->set_bias(-0.75); weights[0] = 0.5; weights[1] = 0.5; AndOp->set_synaptic_weights(weights);
FL::Vector<double> inputs(2); inputs[0] = INPUT1; inputs[1] = INPUT2; double outputsignal = AndOp->calculate_output(inputs);
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 2: Perzeptronen (2) • Wie kommt man zu den Parametern?
– Ausprobieren
– Grafisch überlegen (Gewichtsvektor = Normalenvektor)
– Gleichungssystem aufstellen:
22
1 · w1 + 1 · w2 = w1 + w2 > !
0 · w1 + 1 · w2 = w2 < !
1 · w1 + 0 · w2 = w1 < !
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 2: Perzeptronen (3) b) Erweitere die Lösung von Teilaufgabe a), so dass
– der Benutzer die Anzahl der Eingaben auswählen kann und
– neben dem AND-Operator auch ein OR-Operator realisiert wird.
• alle erfolgreich? • mögliche Lösung für AND:
23
AndOp = new FL::Perceptron(numberOfInputSignals); FL::Vector<double> weights(numberOfInputSignals); … double andInputWeight = 1.0 / numberOfInputSignals; double andThreshold = 1.0 – (andInputWeight / 2.0);
AndOp->set_bias(-andThreshold); for (int i=0; i<numberOfInputSignals; i++){
weights[i] = andInputWeight; } AndOp->set_synaptic_weights(weights);
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 2: Perzeptronen (4) • mögliche Lösung für AND:
• mögliche Lösung für OR:
24
AndOp = new FL::Perceptron(numberOfInputSignals); FL::Vector<double> weights(numberOfInputSignals); … double andInputWeight = 1.0 / numberOfInputSignals; double andThreshold = 1.0 – (andInputWeight / 2.0);
AndOp->set_bias(-andThreshold); for (int i=0; i<numberOfInputSignals; i++){
weights[i] = andInputWeight; } AndOp->set_synaptic_weights(weights);
double orInputWeight = 1.0 / numberOfInputSignals; double orThreshold = orInputWeight / 2.0);
OrOp->set_bias(-orThreshold); for (int i=0; i<numberOfInputSignals; i++){
weights[i] = orInputWeight; } OrOp->set_synaptic_weights(weights);
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Aufgabe 2: Perzeptronen (5) c) Für den Fall von genau 2 Eingängen: Realisiere einen
XOR-Operator unter Einsatz mehrerer Perzeptronen.
• alle erfolgreich? • mögliche Lösung:
• Normalisierung der jeweiligen Ausgaben
25
FL::Perceptron xorUL(2), xorLR(2), xorOut(2);
double threshold = 0.25; FL::Vector<double> xulWeights(2), xlrWeights(2), xoroutWeights(2);
xulWeights[0] = 0.5; xulWeights[1] = -0.5;
xlrWeights[0] = -0.5; xlrWeights[1] = 0.5;
xoroutWeights[0] = 0.5; xoroutWeights[1] = 0.5;
Dipl.-Inform. Martin Lösch Labor Wissensrepräsentation
Fragen?
26
Dipl.-Inform. Martin Lösch Labor „Wissensbasierte Systeme“ Wiederholung Neuronale Netze
Literatur • Tom Mitchell: Machine Learning. McGraw-Hill, New York,
1997. • M. Berthold, D.J. Hand: Intelligent Data Analysis. • P. Rojas: Theorie der Neuronalen Netze – Eine
systematische Einführung. Springer Verlag, 1993. • C. Bishop: Neural Networks for Pattern Recognition.
Oxford University Press, 1995. • Vorlesung „Neuronale Netze 2006“: http://isl.ira.uka.de/ • siehe auch Skriptum „Ein kleiner Überblick über
Neuronale Netze“: http://www.dkriesel.com/