Zusammenfassung Neuronale Netze (c) 2002-08-19 F.M. Suchanek http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/nn.txt Dieses ist die Zusammenfassung des Kurses "Neuronale Netze" von Dr. Barbara Hammer an der Universitaet Osnabrueck im SS 2002 unter Einbeziehung des Kurses "Neuroinformatik" (s. neuroinf.txt). Durch das Weiterlesen akzeptiert der Leser, dass der Autor keinerlei Verantwortung fuer die Richtigkeit oder Vollstaendigkeit dieser Zusammenfassung uebernimmt. Wenn jemand einen Fehler gefunden hat, so waere ich fuer eine Mail dankbar. Nur so habe auch ich etwas von der Veroeffentlichung dieser Zusammenfassung. Meine E-Mail-Adresse ist f.m.suchanek@zweb.de, wobei das 'z' aus der Adresse geloescht werden muss. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Mathematische Grundlagen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ s. a. algebra.txt s. a. analysis.txt s. a. statistik.txt Raum, Menge: Eine ungeordnete Ansammlung nicht identischer Elemente. M = {x1, x2, ..., xn} ist die Menge dieser Elemente M = {x | f(x) } ist die Menge aller x, fuer die eine Bedingung f(x) gilt Teilmenge: Eine Menge T ist eine Teilmenge der Menge M, wenn jedes Element von T auch in M ist. Dieses gilt auch im Falle T=M. T < M Maechtigkeit: Die Maechtigkeit einer Menge ist die Anzahl ihrer Elemente. |M| = n Reelle Zahlenmenge: Die Menge aller rellen Zahlen, mit R bezeichnet. Natuerliche Zahlenmenge: Die Menge aller natuerlichen Zahlen, mit N bezeichnet. Intervall: Eine Zahlenmenge M, zu der es zwei Grenzen a und b gibt, sodass M={x | x >=a & x =< b} gilt. Man schreibt M=[a;b]. Sollen eine Grenze nicht dazu gehoeren, so dreht man die entsprechende Klammer nach aussen. // Was dann immer sehr unschoen nach Bracket-Mismatch aussieht... Funktion: Eine Abbildung, die jedem Element einer Definitionsmenge genau ein Element einer Bildmenge zuordnet. Schreibweise: Funktion:Definitionsmenge -> Bildmenge Damit ist der Begriff "Funktion" so allgemein, dass z.B. auch eine Saftpresse eine Funktion ist: Presse ich eine Zitrone, kommt Zitronensaft heraus, presse ich eine Orange, kommt Orangensaft heraus. // Diese Funktion ist also sogar injektiv! :-) Tupel: Geordnete Zusammenfassung von Objekten. v = (v[1], v[2], ... v[n]) Kartesisches Produkt: Das kartesische Produkt von n Mengen M[1],..M[n] ist die Menge aller Tupel (m[1], m[2], ... m[n]) aller m[1] aus M[1], aller m[2] aus M[2] etc. M * N = { (m1, n1), (m1, n2), ... } M^n = M * M * ... * M Beispiel: {1,2} * {a,b,c} = { (1,a), (2,a), (1,b), (2,b), (1,c), (2,c) } Boolsche Funktion: Eine Funktion f:{0,1}^n -> {0,1}, die zu einem Tupel aus Nullen und Einsen eine Null oder Eins liefert. Binaere Funktion: Eine Funktion, die nach {0,1} abbildet. Matrix: Ein Tupel aus gleichlangen Tupeln. M = ( (v[1][1], v[1][2], ... v[1][n]), ... (v[m][1], v[m][2], ... v[m][n])) Komponente: Eintrag eines Tupels. Vektor: Element einer Menge, welche die Axiome des Vektorraums erfuellt. Hier: Ein Tupel aus reellen Zahlen. v = (v[1], v[2], ... v[n]) mit v[i] aus R v aus R^n Vektorsumme: Ergebnis einer abelschen Verknuepfung von 2 Vektoren. Hier: Die Vektorsumme zweier Vektoren ist derjenige Vektor, der entsteht, wenn man zu jeder Komponente des einen die entsprechende Komponente des anderen addiert. v + w = (v[1]+w[1], v[2]+w[2], ... v[n]+w[n]) Vektorvielfaches: Das k-fache eines Vektors v ist derjenige Vektor, der entsteht, wenn jede Komponente von v mit k multipliziert wird. k*v = (k*v[1], k*v[2], ... k*v[n]) Vektorverlaengerung: Die Vektorverlaengerung eines Vektors und einer Komponente ist der Vektor, der dieselben Komponenten hat wie der Ausgangsvektor und noch die gegebene Komponente dazu. v = (v[1], v[2], ... v[n]) v _ z = (v[1], v[2], ... v[n], z) // Dieses ist keine mathematische Operation, sie wird aber fuer // den Tower-Algorithmus benoetigt Skalarprodukt: Eine positiv definite hermitesche Sesquilinearform. Hier: Das Skalarprodukt zweier Vektoren v=(v[1],v[2],...v[n]) und w=(w[1],w[2],...w[n]) ist die reelle Zahl r=v[1]*w[1]+v[2]*w[2]+...v[n]*w[n]. v*w = v[1]*w[1]+v[2]*w[2]+...v[n]*w[n] // Anmerkung: Der Stern '*' ist nun in diesem Text ueberladen // Zwischen reellen Zahlen bedeutet er Multiplikation // Zwischen reeller Zahl und Vektor Vielfaches // Zwischen Vektoren Skalarmultiplikation Das Skalarprodukt zweier Vektoren kann man als "gewichtete Summe" auffassen: Man summiert alle Komponenten des zweiten Vektors auf, und gewichtet dabei jede Komponente so stark, wie die entsprechende Komponente des ersten Vektors angibt. Betrag eines Vektors: Die Wurzel aus dem Skalarprodukt des Vektors mit sich selbst. Der Betrag entspricht der Laenge des Vektors im Anschauungsraum. | w | = sqrt(w[1]*w[1] + w[2]*w[2] + ... w[n]*w[n]) e: Die Naturkonstante e=2.718281828459045. pi: Das Verhaeltnis von Kreisumfang zu Kreisdurchmesser, pi=3.141592653589793238462. Cosinus: Eine Funktion cos:R->[0;1], die zu einem Winkel in einem rechtwinkligen Dreieck mit einer laengsten Seite von 1 die Laenge der dem Winkel gegenueberliegenden Seite angibt. // Fuer eine genauere Abhandlung auch von pi und e siehe analysis.txt Geometrische Bedeutung des Skalarproduktes: Interpretiert man Vektoren als Pfeile vom Ursprung zum durch den Vektor angegebenen Punkt im Koordinatensystem, so gilt v*w = cos(phi) * |w| * |v|, d.h. das Skalarprodukt ist relativ zum Winkel, der von den Vektoren eingeschlossen wird. Insbesondere ist v*w=0 genau dann wenn die Vektoren senkrecht aufeinander stehen, es ist negativ fuer Winkel zwischen 90 Grad und 270 Grad und positiv fuer Winkel zwischen 270 Grad und 0 Grad bzw. 0 Grad und 90 Grad. Es ist 1, wenn die Vektoren in dieselbe Richtung zeigen und -1, wenn sie in entgegengesetzte Richtung zeigen. Deshalb kann man das Skalarprodukt zweier Vektoren als ein Mass fuer ihre Aehnlichkeit verwenden. Arithmetisches IF: Eine Funktion f:{true, false} * R * R -> R mit f(true,x,y)=x und f(false,x,y)=y. Wird meist infix mit den Zeichen '?' und ':' geschrieben. Beispiel: maxvalue(a,b) = ( (a>b) ? a : b) // Diese Funktion dient hier lediglich zum Verfassen dieses Textes Relation: Eine Teilmenge des kartesischen Produktes zweier Mengen. Fuer "(a,b) ist Element der Relation r" schreibt man auch "r(a,b)" oder "a r b" oder "(a,b) Element von r". Beispiel: Die Relation ">" ist die Menge aller Paare von reellen Zahlen, bei denen die erste Komponente groesser ist als die zweite, es ist > = { (1,0), (27.3,12.5), (17,-12), ... } und man schreibt: >(3,2) oder 3 > 2 oder (3,2) Element von >. stetige Funktion: Eine Funktion f:M->R, fuer die man an jeder Stelle a aus M fuer ein vorgegebenes eps>0 ein delta>0 finden kann, sodass |f(a)-f(x)|< eps fuer alle x aus [a-delta;a+delta]. Mit anderen Worten: Die Funktion springt nicht. Steigung: Die Steigung einer Funktion f:R^n -> R fuer einen bestimmten Eingabewert x in eine bestimmte Dimension i ist der (Grenz-)Wert 1/h * ( f(x[1],x[2],...x[n]) - f(x[1],x[2],... x[i]+h, ... x[n]) ) fuer h gegen 0. Meist gibt man statt der Nummer der Dimension den Namen der i-ten Eingabe-Komponente an. Ableitung: Die Ableitung einer Funktion f nach einer Dimension i ist eine Funktion f', die zu jedem Eingabewert x die Steigung der Funktion f an dieser Stelle in die Dimension i berechnet. Ist statt der Dimension der Name der i-ten Eingabe-Komponente gegeben (z.B. "z"), so spricht man von der "Ableitung von f nach z" und schreibt df/dz. Fuer den berechneten Wert fuer einen Eingabewert x schreibt man df(x)/dz. Bildlich gesprochen sagt df(x)/dz aus, wie stark sich f(x) veraendert, wenn man an z ruettelt. Ableitungsregel: Eine Regel zur Berechnung der Ableitung einer Funktion nach einer Groesse. d(f(x)+g(x))/dx = df(x)/dx + dg(x)/dx d(f(g(x)))/dx = df(g(x))/dx * dg(x)/dz "Kettenregel" df(g1(x),...gn(x))/dx = df/dg1 * dg1(x)/dx + ... + df/dgn * dgn(x)/dx "mehrdimensionale Kettenregel" d(c*f(x))/dx = c*df(x)/dx fuer Konstanten c dg/dx = 0 fuer von x unabhaengige Terme g differenzierbare Funktion: Eine Funktion, zu der man an jeder Stelle x die Steigung in jede Dimension angeben kann. Gradient: Der Gradient einer Funktion f an einer Stelle x ist der Vektor der Steigungen an dieser Stelle x in alle Dimensionen: Df = (df(x)/dx1, df(x)/dx2, ... df(x)/dxn ) Minimum, lokales Minimum: Ein Eingabewert, fuer den eine Funktion niedrigere Werte liefert als fuer die Eingabewerte um das Minimum herum. Die Steigung in einem Minimum ist 0, da es zu beiden Seiten nach oben geht. Die Steigung der Ableitung im Minimum ist meist positiv, da die Steigung der Funktion meist zunaechst negativ ist und dann positiv. globales Minimum: Ein Eingabewert, fuer den die Funktion ihre kleinstmoegliche Ausgabe hat, also das beste Minimum. Summenzeichen: Das grosse Sigma, hier "SUM". Mit "SUM i aus M a(i)" ist die Summe aller a(i) gemeint, wobei i alle Elemente von M durchlaeuft. a ist dabei eine Funktion von M in die reellen Zahlen oder einfach ein mathematischer Ausdruck, in dem i vorkommen kann. Beispiel: SUM i aus {1,2,3,4} 3*i = 3*1 + 3*1 + 3*2 + 3*4. Ist M eine Folge natuerlicher Zahlen von m bis n, so schreibt man auch SUM i=m..n a(i). Zufallsvorgang: Nicht determiniert vorhersagbarer Prozess. Elementarereignis: Ein moeglicher Ausgang eines Zufallsvorganges. Zufallsergebnis: Menge aller Elementarereignisse, mit Omega bezeichnet. Wahrscheinlichkeit: Eine Funktion, die eine Menge von Elementarereignissen auf eine reelle Zahl abbildet, sodass gilt: * P(B)>=0 fuer alle Elementarereignismengen B * P(Omega)=1 * P(A[1] \/ A[2] \/ ... A[N]) = P(A[1])+P(A[2])+...P(A[N]), wenn A[i] != A[j] // Fuer eine umfangreiche Abhandlung siehe statistik.txt Zufallvariable: Eine Funktion vom Zufallsergebnis in die reellen Zahlen. X: Omega -> R Die Zufallsvariablen-Funktion bekommt ein Elementarereignis w, greift ein bestimmtes Merkmal von w heraus und bildet es auf die reellen Zahlen ab. Die Zufallsvariable dient also dem numerisch-Machen von Elementarereignissen, sie misst die Auspraegung des Merkmals X bei dem Elementarereignis w. Erwartungswert einer Zufallsvariablen: Mit den Einzelwahrscheinlichkeiten gewichtete Summe von Werten einer Zufallsvariablen X. E(X) = SUM i=1..Messanzahl x[i] * P({X=x[i]})) Der Erwartungswert ist mit dem Mittelwert verwand. Varianz einer Zufallsvariablen: Der Erwartungswert der quadrierten Abweichung einer Zufallsvariable von ihrem Erwartungswert. Var(X) = SUM( (x[i]-E(X))^2 ) * P({X=x[i]}) Var(X) = E( (X-E(X))^2 ) = E(X^2) - E(X)^2 Die Varianz ist mit dem Streuungswert von Daten verwand. dekadischer Logarithmus, Logarithmus: Eine Funktion, die zu einer positiven Zahl x denjenigen Exponenten liefert, mit dem man 10 potenzieren muss, um x zu erhalten. Beispiel: log(1000)=4, weil 10^4 = 1000 // Fuer eine genauere Abhandlung siehe analysis.txt Binaerer Logarithmus, Zweierlogarithmus: Eine Funktion, die zu einer positiven Zahl x denjenigen Exponenten liefert, mit dem man 2 potenzieren muss, um x zu erhalten. Beispiel: log2(1024)=10, weil 2^10 = 1024 Polynom: Eine Summe von Produkten aus reellen Zahlen und einer Variable x in verschiedenen Potenzen: p(x)=a[0]*x^0 + a[1]*x^1 ... + a[n]*x^n Die a[i] heissen Koeffizienten, n ist der Grad des Polynoms. Approximation: Naherungsweise Berechnung einer Funktion. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Komplexitaeten ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ s.a. infod.txt Algorithmus: Eine endliche Folge von Anweisungen. Konvergenz: Die Tatsache, dass sich bei einem Algorithmus die benutzen Werte nach und nach einem Zielwert annaehern. Komplexitaet: Die Komplexitaet einer Funktion f ist eine andere Funktion, die grob den Verlauf von f beschreibt. Beispiel: f(x)=2*x^2+3*x-10 verhaelt sich grob wie g(x)=x^2. Mathematisch gesprochen ist die Komplexitaet einer Funktion f eine andere Funktion g, sodass es eine Konstante c gibt und einen Startwert x0, sodass fuer alle x ab diesem Startwert x0 gilt: f(x) < c*g(x) Die Menge aller Funktionen einer bestimmten Komplexitaet g fasst man zusammen in der Menge O(g). Beispiel: O(x^2) = { x^2+2x+1, 3*x^2-20, 5*x^2-6*x, ... } Nach der Definition schliessen komplexere Komplexitaeten einfachere ein: Wenn f z.B. zu O(x^2) gehoert, dann gehoert es automatisch auch zu O(x^4). Hier sind einige Standard-Komplexitaeten, sortiert von einfach ("gut") nach komplex ("boese"): * 1 "konstant" * log(x) "logarithmisch" * x "linear" * x^2 "quadratisch" * x^3 "kubisch" * x*log(x) etc. "polynomiell" * x^a "polynomiell" * a^x "exponentiell" * x! "x Fakultaet" Laufzeit: Die Laufzeit eines Algorithmus ist eine Funktion, die die Anzahl der Schritte, die der Algorithmus benoetigt, in Abhaengigkeit von der Eingabe berechnet. Beispiel: Malt ein Algorithmus ein Schachbrett mit der Seitenlaenge n, so wird er n^2 Kaestchen malen. Wenn er pro Kaestchen 3 Schritte braucht, so wird der Ablauf 3*n^2 Schritte dauern. Also SchachbrettLaufzeit(n) = 3*n^2 Meist schaetzt man eine Laufzeit durch ihre Komplexitaet ab: SchachbrettLaufzeit ist Element von O(n^2) effizient loesbares Problem: Ein Problem, zu dem es einen Algorithmus gibt, der es in polynomieller Laufzeit loest. Entscheidungsproblem: Die Fragestellung, ob ein Sachverhalt fuer ein Objekt zutrifft. XXX-loesbares Problem: Ein Problem, zu dem es einen Algorithmus gibt, der es in XXXer Laufzeit loest. XXX ist dabei "konstant", "logarithmisch" etc. Aufgrund der Definition der Komplexitaet schliessen sich die XXX-loesbaren Probleme gegenseitig ein. Beispiel: Jedes konstant-loesbare Problem ist automatisch ein kubisch-loesbares Problem. Nichtdeterministisch polynomiell loesbares Problem, NP-Problem: Ein Problem, zu dem es einen Algorithmus gibt, der mit einer Hilfestellung in polynomieller Laufzeit eine Loesung findet. Damit schliessen diese Probleme die XXX-loesbaren Probleme ein. Entscheidbares Problem: Ein Problem, welches prinzipiell durch einen Algorithmus loesbar ist. Damit schliessen diese Probleme die NP-Probleme ein. Rekursiv aufzaehlbares Problem: Ein Entscheidungsproblem, zu dem es einen Algorithmus gibt, der bei der Antwort "Ja" terminiert und "Ja" liefert und bei der Antwort "Nein" nicht terminiert. // Sebastian B.'s Kommentar: Also wie jedes Prologprogramm Damit schliessen diese Probleme die entscheidbaren Probleme ein. NP-vollstaendiges Problem: Ein NP-Problem, dessen polynomielle Loesbarkeit ohne Hilfe die polynomielle Loesbarkeit jedes anderen NP-Problems ohne Hilfe nach sich ziehen wuerde. NP-vollstaendige Probleme sind bisher noch nicht effizient loesbar. Um zu zeigen, dass ein Problem NP-vollstaendig ist, zeigt man, dass sich ein als NP-vollstaendig bekanntes Problem auf dieses Problem reduzieren laesst, d.h. dass sich jede Instanz des NP-vollstaendigen Problems zu einer Instanz des neuen Problems in polynomieller Zeit transformieren laesst. Konjunktive Normalenform: Eine Zeichenfolge der Form "(X11 \/ X12 \/ X13...) /\ (X21 \/ X22 \/ X23 ...) ... ". Die Xij sind dabei sogenannte "Variablen" und koennen auch mehrfach auftauchen. // Fuer Details und Ueberblick siehe infod.txt Erfuellende Variablenbelegung: Eine Belegung fuer jede Variable einer konjunktiven Normalenform mit TRUE oder FALSE, sodass sich der Gesamtausdruck nach folgenden Rechenregeln zu TRUE auswertet: TRUE /\ TRUE = TRUE TRUE /\ FALSE = FALSE FALSE /\ TRUE = FALSE FALSE /\ FALSE = FALSE TRUE \/ TRUE = TRUE TRUE \/ FALSE = TRUE FALSE \/ TRUE = TRUE FALSE \/ FALSE = TRUE Satisfying-values-Problem, SAT-Problem: Die Frage nach einer erfuellenden Variablenbelegung fuer eine konjuktive Normalenform. Das SAT-Problem ist NP-vollstaendig. (Cook) s.a. ai.txt Travelling-Salesman-Problem, Travelling-Saleswoman-Problem, Travelling- Salesperson-Problem, TSP-Problem: Die Frage, ob man zu einer bestimmten Anzahl von Staedten eine Rundreise finden kann, die hoechstens k Kilometer lang ist. Das TSP-Problem ist NP-vollstaendig. Hitting-Set-Problem: Die Frage, ob es in einer Menge, in der mehrere Teilmengen angegeben sind, k Elemente gibt, sodass alle Teilmengen vertreten sind. Dieses Problem ist NP-vollstaendig, da es sich vom SAT-Problem reduzieren laesst. Formal: Gegeben eine Menge S={s[1],...s[n]} von Elementen, eine Menge C={c[1],...c[m]} von Teilmengen von S, also c[i] < S, und eine Zahl k. Finde eine Teilmenge CA, die benutzt wird, um zu einer reellen Zahl zu entscheiden, welche Ausgabe das Neuron liefert. Feuern: Zu einem spezifischen Eingabevektor eine positive Ausgabe haben. Neuron: Eine Zelle aus Zellkoerper, Dendriten und Axon, die elektrische Signale verarbeitet. Hier: Informationsverarbeitende Einheit, gegeben ist durch: * eine Eingabedimension n // und eine Eingabemenge E * einen Gewichtsvektor w * einen reellen Schwellwert/Biaswert theta * eine Aktivierungsfunktion f:R -> A // und damit eine Ausgabemenge A Sie berechnet zu einem Eingabevektor x aus E^n die Funktion neuron(x)=f(x*w - theta). Aktivierung: Der Wert x*w eines Neurons. Neuronales Netz, Netz: Gerichteter Graph von Neuronen, dessen Kanten Verbindungen von Ausgaben des einen Neurons zu einer Eingabe des anderen Neurons symbolisieren. Es ist gegeben durch: * eine Menge N = {0,1,2,... n} von Neuronen(-nummern) * eine Teilmenge I von N von "Eingabeneuronen" * eine Teilmenge O von N von "Ausgabeneuronen" * eine Relation "->" zwischen Neuronen Diese Relation bestimmt gleichzeitig die Eingabedimension n[i] eines jeden Neurons * eine Menge von Gewichten w[i,j] fuer jede Verbindung i -> j * eine Menge von Biaswerten theta[i] fuer jedes Neuron i * eine Menge von Aktivierungsfunktionen f[i] fuer jedes Neuron i Es berechnet eine Funktion f:R^|I| -> R^|O|, indem der Eingabevektor komponentenweise den Eingabeneuronen als Aktivierung gegeben wird. Dann laesst man sukzessive die Folgeneuronen ihre Ausgabe berechnen, bis der Ergebnisvektor der Vektor aus den Ausgaben der Ausgabeneuronen ist. Verbindung: Ein Element der Relation "->". Architektur: Die Architektur eines neuronalen Netzes ist das Tupel aus seiner Menge N der Neuronen, den Teilmengen I und O und der Relation "->". Die Architektur ist also die Struktur eines Netzes ohne Angabe ueber die Werte der Gewichte oder Schwellwerte. Spike: Die zeitlich-oertliche Struktur eines Aktionspotenzials. (s.a. neurobio.txt) Modellierung von biologischen Neuronalen Netzen: Neuronale Netze koennen in verschiedenen Abstraktionsebenen modelliert werden: * Modellierung der Ionenstroeme mit Differentialgleichungen Dieses ist die materialnaechste und zeitgetreueste Modellierung * Modellierung der elektrischen Signale mit Differentialgleichungen Hier beschraenkt man sich auf die Modellierung des Aktionspotenzials * Vernachlaessigung der feinen zeitlichen Struktur Hier wird ein Aktionspotenzial auf ja/nein reduziert * Vernachlaessigung der gesamten zeitlichen Struktur Hier wird die Information nur ueber die mittlere Rate der Spikes modelliert ("Ratencodierung") Single-Neuron-Doctrine: Die Idee, dass jeder Sachverhalt durch genau 1 Neuron im Netz repraesentiert wird. Vorteile: * Biologisch nicht unplausibel, es gibt "Grossmutterneuronen" * Sehr einfache Umsetzung fuer technische Systeme Nachteile: * Kombinatorische Explosion (jede Variante des eigentlich gleichen Sachverhaltes braucht ein neues Neuron) * Keine Generalisierung * Keine Kreativitaet * Keine Fehlertoleranz * Keine Analogieschluesse Distributed-Representation-Doctrine: Die Idee, dass ganze Muster von Neuronenkonfigurationen einen Sachverhalt repraesentieren. Vorteile: * Keine kombinatorische Explosion * Technisch gebraeuchliche Form der Eingabe * Kreativitaet ist moeglich Nachteile: * Binding Problem Binding Problem: Die Schwierigkeit, anhand einer Ratencodierung von Neuronen festzustellen, welche der jeweils repraesentierten Sachverhalte zusammen an einem Objekt aufgetreten sind (Kuh-Giraffe-Problem). Dieses Problem kann geloest werden, indem man die zeitliche Struktur mit einbezieht und Neuronen, die sich auf dasselbe Objekt beziehen, zeitgleich spiken laesst (bzw. indem man nicht nur Rate, sondern auch Phase codiert). Muster, Beispiel: Etwas, was eine Menge repraesentiert. Hier: Ein Tupel aus einem Eingabevektor und der erwuenschten Ausgabe. b=( (x[1],...x[n]), y) Trainingsmenge: Eine endliche Menge von Beispielen. Damit kann eine Trainingsmenge auch angegeben werden durch das Tupel der m n-dimensionalen Eingabe-Vektoren und der Soll-Ergebnisse: (x,f) := { ( (x[1][1],...x[1][n]), f(x[1]) ), ... ( (x[m][1],...x[m][n]), f(x[m]) ) } Widerspruechliche Trainingsmenge: Eine Trainingsmenge, die denselben Eingabevektor einmal mit positiver Soll-Ausgabe und einmal mit negativer Soll-Ausgabe enthaelt. Trainieren: Schritte durchfuehren, um eine Funktion so zu konfigurieren, dass sie eine Trainingsmenge korrekt abbildet. one-shot Training: Ein Algorithmus zum Trainieren, welcher ohne eine Wiederholung fuer alle Muster auskommt. Datenmenge: Eine Menge von Eingabevektoren x[i] aus R^n. Ueberwachtes Lernen: Das Lernen unter Vorgabe einer Trainingsmenge. Unueberwachtes Lernen: Das Lernen unter Vorgabe einer Datenmenge. Symbolischer Formalismus: Ein Formalismus, der Symbole benutzt, welche explizit Objekte repraesentieren. Beipiele: Mathematik (Zahlen), Informatik (Variablen) Subsymbolischer Formalismus: Ein Formalismus, der nicht symbolisch ist. Beispiel: Neuronale Netze ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Das Perzeptron ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Identitaet: Eine Funktion id:M->M mit id(x)=x fuer beliebige Menge M. Einfaches lineares Element, Adaline, Adaptive Linear Combiner, ADC: Ein Neuron, welches gegeben ist durch: * Eine Eingabedimension n * einen Gewichtsvektor w=(w1,w2,...wn) * den Schwellwert 0 * die Aktivierungsfunktion Identitaet Ein ADC ist dient also der einfachen linearen Funktionsapproximation, bei der die w[i] so gesucht werden, dass fuer jedes Beispiel (x;y) gilt adc(x) = SUM i=1..n w[i]*x[i] = y. Perzeptronaktivierungsfunktion: Die Aktivierungsfunktion H:R->{0,1} mit H(x)= (x>=0 ? 1 : 0). Die Funktion liefert also immer dann 1, wenn x groessergleich 0 ist. Relatives McCulloch-Pitts-Neuron: Ein Neuron, welches gegeben ist durch * eine Eingabedimension n und die Eingabemenge E={0,1,-1} * einen Gewichtsvektor w=(w1,w2,...wn) aus {0,1,-1}^n * einen Biaswert/Schwellwert theta aus R * die Perzeptronaktivierungsfunktion Ein solches Neuron erhaelt also ein Eingabe von Nullen, Einsen und Minuseinsen und liefert 0 oder 1. Die berechnete Funktion ist damit f:{0,1,-1}^n -> {0,1} mit f(x) = H(w*x - theta). Absolutes McCulloch-Pitts-Neuron: Ein Neuron, welches gegeben ist durch * eine Eingabedimension n und die Eingabemenge E={0,1,-1} * einen Gewichtsvektor w=(w1,w2,...wn) aus {0,1,-1}^n * einen Biaswert/Schwellwert Theta aus R * die Perzeptronaktivierungsfunktion * die zusaetzliche Bedingung, dass ein einziger negativer Eingang zu einer negativen Ausgabe fuehrt Ein solches Neuron erhaelt also ein Eingabe von Nullen, Einsen und Minuseinsen und liefert 0 oder 1. Sobald also ein Eingang negativ ist, hemmt dieser bereits das gesamte Neuron, die Ausgabe ist 0. Die berechnete Funktion ist also f:{0,1,-1}^n -> {0,1} mit f(x)=( (H(w*x - Theta)>0) & (x[1]*w[1]>0) & ... (x[n]*w[n]>0) ) ? 1 : 0. Perzeptron: Ein Neuron, welches gegeben ist durch * eine Eingabedimension n und die Eingabemenge E=R * einen Gewichtsvektor w=(w1,w2,...wn) aus R^n * einen Biaswert/Schwellwert Theta aus R * die Perzeptronaktivierungsfunktion Die berechnete Funktion ist damit o:R^n -> {0,1} mit o(x) = H( w*x - theta ). Hebbsches Lernen: Verstaerken von Gleichem, Abschwaechen von Verschiedenem. Punkt: Ein Tupel aus n reellen Zahlen, wenn n die Dimension des umgebenden Raumes ist. Also kann man jeden Vektor und damit z.B. auch jeden Eingabevektor fuer ein Perzeptron als Punkt im Raum auffassen. "Grebene": Eine (n-1)-dimensionale Punktemenge im n-dimensionalen Raum, fuer die es keine (n-1)-dimensionale echte Obermenge gibt. Also im 2-dimensionalen eine Gerade, im 3-dimensionalen eine Ebene und im n-dimensionalen eine Hyperebene. // Dieser Begriff vereinfacht die Modellierung von Perzeptrons im // Anschauungsraum Linear trennbare Trainingsmenge: Eine Trainigsmenge zu der es eine Grebene gibt, die alle Eingabe-Punkte mit positiver Ausgabe von denjenigen mit negativer Ausgabe trennt. Ein Perzeptron kann genau die linear trennbaren Trainigsmengen korrekt verarbeiten. // Ich finde es schoener, den Begriff "linear trennbar" unabhaengig vom // Perzeptron zu definieren Linear trennbare Funktion: Eine Funktion f:R^n -> A, deren gesamte Trainingsmenge linear trennbar ist. Nur sehr wenige Funktionen sind linear trennbar, ihr Anteil an allen moeglichen boolschen Funktionen f:{0,1}^n -> {0,1} sinkt exponetiell mit steigendem n. Ein Perzeptron kann genau die linear trennbaren Funktionen berechnen. AND-Funktion: Eine boolesche Funktion AND:{0,1}^2 -> {0,1}, die nur dann 1 liefert, wenn beide Eingabekomponenten 1 sind. AND ist linear trennbar. OR-Funktion: Eine boolesche Funktion OR:{0,1}^2 -> {0,1}, die nur dann 0 liefert, wenn beide Eingabekomponenten 0 sind. OR ist linear trennbar. XOR-Funktion: Eine boolesche Funktion XOR:{0,1}^2 -> {0,1}, die nur dann 1 liefert, wenn beide Eingabekomponenten ungleich sind. XOR ist nicht linear trennbar. NOT-Funktion: Eine boolesche Funktion NOT:{0,1} -> {0,1}, die das Gegenteil der Eingabe liefert. NOT ist linear trennbar. Modellierung von Perzeptrons im Anschauungsraum: Ein Perzeptron mit der Eingabe-Dimension n laesst sich im n-dimensionalen Raum darstellen, indem alle eine positive Ausgabe hervorrufenden Eingabevektoren als weisse Punkte und alle anderen als schwarze Punkte eingezeichnet werden. Theta und w werden durch eine Grebene symbolisiert, die orthogonal zum Gewichtsvektor w ist und vom Ursprung Theta / |w| entfernt ist. Sie trennt genau die weissen und schwarzen Punkte, wobei w in Richtung der weissen (positiven) Punkte zeigt. Hintergrund zur Modellierung im Anschaungsraum: Es folgt der Beweis der Aequivalenz von graphischer Darstellung und Funktionalitaet des Perzeptrons. Sei die trennende Grebene gegeben durch einen Normalenvektor n und ihren dem Ursprung am naechsten liegenden Punkt p. Dann gilt nach Hessescher Normalenform fuer alle Punkte x der Grebene: n*(x-p)=0 <=> n*x - n*p = 0 <=> n*x = n*p // Waehle Theta=n*p, waehle w=n <=> w*x = Theta Fuer alle weissen (positiven) Punkte ist der Winkel zwischen n und (x-p) zwischen -90 Grad und +90 Grad, d.h. n*(x-p)>0 <=> n*x>n*p <=> w*x>Theta analog fuer alle schwarzen Punkte w*x Theta = |w| * |p| * cos(phi) // cos(phi)=1, da p und w parallel <=> Theta = |w| * |p| <=> |p| = Theta / |w| Entsprechend |p|=-Theta/|w|, wenn der Ursprung im weissen (positiven) Bereich liegt und p und w damit entgegengesetzt zeigen. // Selbstgestrickter Beweis Fehlersignal: Eine Funktion d: R^n * R^n * R -> {0,1,-1} mit d(w,x,y) = (y==1 & w*x=<0) ? 1 : (y==0 & w*x>=0) ? -1 : 0. Diese Funktion sagt also, ob das Skalarprodukt fuer die erwuenschte Ausgabe zu gross ist (-1), zu klein ist (+1) oder OK ist (0). // Diese Funktion wurde in der Vorlesung als d(w,x) definiert. Dann // allerdings handelt es sich nicht mehr um eine saubere Funktion, da ihr // Resultat noch von y abhaengt und y nicht gegeben ist Eliminieren des Schwellwertes: Das Hinzufuegen eines zusaetzlichen Gewichtes w[n+1]=theta und einer zusaetzlichen Eingabe x[n+1]=-1 ("on-Neuron"). Theta kann nun ignoriert werden. Perzeptronalgorithmus: Der folgende Algorithmus zum Trainieren eines Perzeptrons. Gesucht ist ein w=(w[1],...w[n]) aus R^n, sodass fuer alle Eingabevektoren x der Trainingsmenge gilt: x*w>=Theta genau dann wenn y=1. 1. Man initialisiere w mit Zufallswerten 2. Man eliminiere den Schwellwert 3. Wenn kein x aus der Trainingsmenge mehr existiert, fuer das d(w,x,y)!=0, so ist man fertig, andernfalls waehle dieses x aus. 4. Man addiere zu w das d(w,x,y)-fache von x hinzu 5. Weiter bei 3. Dieser Lernalgorithmus macht also Hebbsches Lernen: Wannimmer ein einzelner Eingabewert fuer die erwuenschte Ausgabe foerderlich ist (z.B. Eingabe 1 und auch erwuenschte Ausgabe 1), so wird das zugehoerige Gewicht verstaerkt. Ist ein Eingabewert hinderlich (z.B. -1 bei erwuenschter Ausgabe von 1), so reduziert sich das entsprechende Gewicht in Richtung 0. Soll der Biaswert beibehalten werden, so laesst man Schritt 2 weg und fuegt bei Schritt 4 hinzu: "Subtrahiere d(w,x,y) von Theta". Terminieren des Perzeptronalgorithmus': Ist die Trainingsmenge linear trennbar, so findet der Perzeptronalgorithmus eine Loesung. Beweis: 1. Sei w ein (unbekannter) Loesungsvektor Zunaechst verschiebt man die Grebene des Perzeptrons parallel ein kleines bisschen in Richtung der negativen Punkte, jedoch so, dass kein negativer Punkt auf die Grebene zu liegen kommt oder die Seite wechselt. Dies ist moeglich, da die Trainingsmenge endlich ist. Damit gilt w*x[i]!=0 fuer alle Eingabevektoren x[i]. Nun denkt man sich w so verlaengert (was die Loesung nicht aendert), dass w*x[i]>=1 fuer alle positiven x[i] und w*x[i]=<-1 fuer alle negativen x[i]. Sei im Folgenden x ein noch falsch abgebildeter Eingabevektor. 2. Sei w[k] der Gewichtsvektor des Perzeptrons nach der k-ten Iteration w*w[k]>=w*w[0]+k // w[k] wird also immer groesser Beweis durch Induktion ueber k Induktionsanfang k=0 w*w[0] >= w*w[0]+0 (OK) Induktionsschritt k->k+1 w*w[k+1]= w*(w[k]+d(w[k],x,y)*x) = w*w[k] + d(w[k],x,y)*w*x >= w*w[0]+k + d(w[k],x,y)*w*x // Nach Ind'Vorraussetzung >= w*w[0]+k + 1 // d() und w*x haben gleiches // Vorzeichen, |w*x|>1 3. Sei xmax der Betrag des laengsten Input-Vektors: xmax=max {|x[0]|,|x[1]|,...} |w[k]|^2 =< |w[0]|^2 + k*xmax^2 // |w[k]| bleibt beschraenkt Beweis durch Induktion ueber k Induktionsanfang k=0 |w[0]|^2 =< |w[0]|^2 + 0*xmax^2 0 =< 0*xmax^2 (OK) Induktionsschritt k->k+1 |w[k+1]|^2 = |w[k]+d(w[k],x,y)*x|^2 = (w[k]+d(w[k],x,y)*x)^2 // Nach Def. des Betrages = w[k]^2 + 2*w[k]*d(w[k],x,y)*x + x^2 // Nach Binom = |w[k]|^2 + 2*d(w[k],x,y)*w[k]*x + |x|^2 // Nach Betrag // Da w[k] noch falsch ist, // haben d() und w[k]*x // entgegengesetztes Vorzeichen =< |w[k]|^2 + 0 + |x|^2 =< |w[0]|^2 + k*xmax^2 + |x|^2 // Nach Ind'Vorr. =< |w[0]|^2 + k*xmax^2 + xmax^2 // Da xmax maximal =< |w[0]|^2 + (k+1)* xmax^2 4. Nun muessen also die Gleichungen 2 und 3 waehrend der Laufzeit des Algorithmus gelten. Das kann aber nicht fuer alle Schritte k sein: w*w[0]+k =< w*w[k] // Nach Gleichung 2 = cos(phi)*|w|*|w[k]| // Nach Skalarprodukt =< |w|*|w[k]| // Da cos(phi) in [-1;1] =< |w|*sqrt(|w[0]|^2 + k*xmax^2) // Nach Gleichung 3 Hier waechst w*w[0]+k linear mit k, die rechte Seite der Ungleichung hingegen linear mit sqrt(k). Irgendwann muss die linke Seite groesser als die rechte Seite werden, Gleichungen 2 und 3 waeren ab diesem k nicht mehr erfuellt. 5. Das kann nur heissen, dass die Vorraussetzung fuer das Gelten der Gleichungen, naemlich ein falsches x, nicht mehr erfuellt ist -- und der Algorithmus einen Loesungsvektor gefunden hat. Laufzeit des Perzeptronalgorithmus: Der Perzeptronalgorithmus laeuft soviele k Schritte, bis die Gleichung unter Punkt 4 bei "Terminierung des Perzeptronalgorithmus'" nicht mehr gilt. Dies ist fruehestens der Fall bei w*w[0]+k = |w|*sqrt(|w[0]|^2 + k*xmax^2) // Sei w[0]=(0,0,...) k = |w|*sqrt(k*xmax^2) // Wie soll das gehen (?) k = |w|*xmax^2 Mit dieser Gleichung und der Gleichung |w*x| >= 1 fuer alle x // Nach Konstruktion in Punkt 1 und ein paar Litern Mathematik gelangt man fuer eine Eingabedimension von n zu einer Einschaetzung von w[k], die schliesslich besagt: Der Perzeptronalgorithmus hat eine exponentielle Laufzeit. Durch eine Technik namens "linearen Programmierens" laesst sich jedoch eine polynomielle Laufzeit erreichen. Die Laufzeit wird aber mit groesserem |w| laenger. Bei zufaellig gewaehlten Mustern berechnet der Perzeptronalgorithmus auch bei nicht linear trennbaren Daten irgendwann mal eine optimale Teilloesung. Delta-Regel, Widrow-Hoff-Regel: Ein Algorithmus zum Trainieren eines ADCs. Er funktioniert aehnlich wie der Perzeptronalgorithmus, passt die Gewichte aber fuer das k-te Muster (x[k];y[k]) wie folgt an: w[i] := w[i] + my*e(k)*x[k][i] Dabei ist e(k) = adc(x[k]) - y[k] die Differenz aus tatsaechlicher Ausgabe fuer Eingabevektor x[k] und Sollwert y[k], also der Fehler. Die Delta-Regel kann als Gradientenabstiegsverfahren (s.u.) interpretiert werden: Sei o=adc(x) die Ausgabe des ADCs fuer Eingabe x, sei y Sollausgabe. Ziel: Minimiere den Fehler E(w)=0.5*(o-y)^2 w := w - my*DE(w) // von w wird der Gradient abgezogen w[i] := w[i] - my*dE(w)/dw[i] // Aufspaltung in Dimensionen w[i] := w[i] - my * dE(w)/do * do/dw[i] // Nach Kettenregel,E(w) als Funktion von o w[i] := w[i] - my * d(0.5*(o-y)^2)/do * (SUM j=1..n w[j]*x[j])/dw[i] // Nach Einsetzen von E(w) und o=adc(x) w[i] := w[i] - my * (o-y) * (SUM j=1..n w[j]*x[j])/dw[i] // Nach Kettenregel w[i] := w[i] - my * (o-y) * x[i] // Da die anderen w[j]*x[j] sind unabh. von w[i] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Perzeptron-Erweiterungen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Verrauschte Daten: Daten, die nicht genau dem wirklichen Sachverhalt entsprechen. Da Daten oft verrauscht sind, ist es geradezu notwendig, ein Perzeptron auch auf nicht linear trennbaren Daten lernen lassen zu koennen. Generalisierungsfaehigkeit: Die Faehigkeit, eine Funktion von den Beispielen auf den wirklichen Sachverhalt zu verallgemeinern. Oft spielt dabei Occam's Razor eine Rolle: Die Idee, dass die einfachste Erklaerung die beste ist. Beispiel: Die Faehigkeit, aus den Beispielen f(2)=1, f(4)=1, f(8)=1, f(16)=1 auch f(64)=1 zu vermuten. Overfitting: Die Tatsache, dass etwas nicht generalisierungsfaehig ist, d.h. nur die Beispiele samt Rauschen exakt abbildet, aber fuer unbekannte Eingaben keine sinnvollen Ausgaben hat. Als Folge werden z.B. Messfehler nicht als solche geoutet, die wahre Natur der Daten wird nicht erkannt, es wird nicht die "einfachste Erklaerung" gefunden und auf unbekannte Daten kann unsinnig geantwortet werden. Perzeptron-Zyklus-Theorem: Lernt der Perzeptronalgorithmus nur mit ganzzahligen oder rationalen Mustern, so geraet er im Falle einer nicht linear trennbaren Trainingsmenge in einen Zyklus. Die Laufzeit kann ueber die Anzahl der Muster und die Laenge des Gewichtsvektors abgeschaetzt werden. (Minsky & Papert) Perzeptronalgorithmus mit Zyklencheck: Der Perzeptronalgorithmus, versehen mit einer Abfrage, ob ein Gewichtsvektor frueher schon einmal erreicht wurde. In diesem Fall stoppt der Algorithmus. Fuer linear trennbare Trainingsmengen terminiert der Algorithmus also mit einer Loesung, fuer nicht linear trennbare Trainingsmengen muss er in einen Zyklus geraten. Dann stoppt der Algorithmus mit einer Teil-Loesung. Pocket-Algorithmus: Ein Perzeptronalgorithmus, der jedoch das jeweils beste Ergebnis zwischenspeichert. Dazu wird eine Menge P0 verwaltet, die zu Anfang alle Muster beinhaltet. Nun wird ein Muster (x;y) aus P0 gewaehlt. Wird (x;y) richtig gemacht (d(w,x,y)==0), so wird ein Zaehler erhoeht und (x;y) aus P0 herausgenommen. Andernfalls wird der Gewichtsvektor wie beim Perzeptronalgorithmus angepasst, P0 wird wieder auf die Menge aller Muster zurueckgesetzt und der Zaehler wird wieder 0. Jedesmal, wenn der Zaehler sein bisheriges Maximum ueberschreitet, wird der momentane Gewichtsvektor als bisher beste Teilloesung vermerkt. Konvergenz-Theorem des Pocket-Algorithmus: Werden die Trainingsmuster in jedem Durchlauf zufaellig gewaehlt, so findet der Pocket-Algorithmus auch bei nicht linear trennbaren Trainingsmengen eine optimale Teilloesung. Werden die Muster nicht zufaellig ausgewaehlt, so wird nicht unbedingt eine optimale Teilloesung gefunden. Beispiel dazu: Waehlt der Algorithmus die Muster immer in derselben Reihenfolge, so wird er fuer die folgende Trainingsmenge immer im oberen nicht loesbaren XOR-Teil haengen bleiben und keine optimale Teilloesung fuer den folgenden AND-Teil finden: 0,0,0,0->0 0,1,0,0->1 1,0,0,0->1 1,1,0,0->0 0,0,0,0->0 0,0,0,1->0 0,0,1,0->0 0,0,1,1->1 Laufzeit des Pocket-Algorithmus: Der Pocketalgorithmus benoetigt genau wie der Perzeptronalgorithmus exponentielle Laufzeit. Dieses kann durch lineares Programmieren umgangen werden. Trennproblem fuer Perzeptrons: Die Frage, ob es ein Perzeptron gibt, welches auf einer Trainingsmenge hoechstens k Fehler macht. Dieses Problem laesst sich vom Hitting-Set-Problem reduzieren und ist daher NP-vollstaendig. Zur Reduktion konstruiert man zu jedem Hitting-Set-Problem eine Trainingsmenge und ein Gewichtetupel, sodass das Perzeptron mit diesen Gewichten die Trainingsmenge genau dann bis auf k Fehler richtig macht, wenn es ein Hitting-Set gibt. Bis-auf-3-Fehler-Problem: Die Frage, ob es ein Perzeptron gibt, welches auf einer Trainingsmenge hoechstens 3 (oder irgendeine andere, konstante Anzahl) Fehler macht. Dieses Problem laesst sich effizient loesen, indem man aus der Trainingsmenge 3 Beispiele herausnimmt und das Perzeptron mit linearem Programmieren trainiert. War diese Teilmenge linear trennbar, so macht das Perzeptron auf der gesamten Menge hoechstens 3 Fehler. War die Teilmenge nicht linear trennbar, so ist auch die Gesamtmenge nicht linear trennbar. Praedikat, Maske: ... Hier: Eine Funktion f:{0,1}^(n*m) -> {0,1}. Diese Funktion kann also eine Matrix der Laenge n und Breite m aus reellen Zahlen auf 0 oder 1 abbilden. Feature-Extractor: Eine Maske, die bei einem bestimmten Muster in ihrem Eingabevektor 1 liefert und sonst 0. Rosenblatt-Perzeptron: Ein Perzeptron, dessen Eingaben von groessenbeschraenkten Masken vorverarbeitet werden. Als Eingabe bekommt das Rosenblatt-Perzeptron also eine Matrix aus reellen Zahlen. Die Masken bekommen Unter-Matritzen davon als Eingabe. Die Ausgaben der Masken gehen dann als Eingaben an das Perzeptron. Die Masken sind groessen- beschraenkt, d.h. die Unter-Matritzen duerfen (egal, wie gross man die grosse Matritze zoomt) eine bestimmt Kantenlaenge nicht ueberschreiten. Sind f1,... fn die Masken, so berechnet das Rosenblatt-Perzeptron f(x) = H( w*(f1(x),f2(x),...fn(x)) - Theta ) Die biologische Motivation fuer die Masken ergibt sich nach Rosenblatt beispielsweise durch die zufaellige Verknuepfung von Augenzaepfchen zu Ganglionzellen. s.a. sensphys.txt Maechtigkeit des Rosenblatt-Perzeptrons: Das Rosenblatt-Perzeptron ist kein universeller Problemloeser. Minsky & Papert zeigten, dass ein Rosenblatt-Perzeptron nicht erkennen kann, ob eine Figur auf der Eingabe-Matrix zusammenhaengend ist. Beweis: Man betrachte folgende Muster 1 2 3 4 L M R L M R L M R L M R ______ _____ _______ ______ _____| |_____| _____ |_____ |______ _______ |_____| ______| Muster 1 und 4 sind zusammenhaengend, Muster 2 und 3 nicht. Aufgrund der Groessenbeschraenktheit der Masken gibt es Masken, die ihre Eingabe nur aus dem Bereich L und dem Bereich M bekommen, nicht aber aus R. Das Perzeptron wird die Ausgaben dieser Masken gewichten und aufsummieren, sei l[i] diese Summe, wobei i die Nummer des Musters ist. Analog sei r[i] der Beitrag der rechten Masken und m[i] der Beitrag der mittleren Masken. Aufgrund der Aehnlichkeit der Muster gilt: m[1] = m[2] = m[3] = m[4] l[1] = l[3], r[1] = r[2], l[2] = l[4], r[3] = r[4] Annahme: Die Muster werden korrekt abgebildet. Dann gilt: l[1] + m[1] + r[1] >= Theta l[2] + m[2] + r[2] < Theta l[3] + m[3] + r[3] < Theta l[4] + m[4] + r[4] >= Theta Wegen der Gleichheiten gilt: l[1] + m[1] + r[1] >= Theta l[2] + m[1] + r[1] < Theta l[1] + m[1] + r[2] < Theta l[2] + m[1] + r[2] >= Theta Addiert man die erste und die letzte und die mittleren, so folgt: l[1] + l[2] + 2*m[1] + r[1] + r[2] >= 2*Theta l[2] + l[1] + 2*m[1] + r[1] + r[2] < 2* Theta Derselbe Wert soll also einmal groessergleich 2*Theta sein und gleichzeitig kleiner als 2*Theta. Das ist ein Widerspruch, das Problem kann nicht mit einem Rosenblatt-Perzeptron geloest werden. Aehnlich kann man zeigen, dass das Rosenblatt-Perzeptron nicht feststellen kann, ob die Anzahl der Einsen und Nullen in der Eingabe gleich ist. Dazu nimmt man folgende Eingabemuster: L M R 1 111000 0 -> 1 0 111000 1 -> 1 1 111000 1 -> 0 0 111000 0 -> 0 Perzeptron-Netz: Ein Neuronales Netz aus Perzeptronen. Ein Perzeptron-Netz (auch aus McCulloch-Pitts-Neuronen) kann beliebige boolsche Funktionen berechnen, da sich jede boolsche Funktion aus den Funktionen NOT und AND zusammensetzen laesst. Ebenso kann ein Perzeptron- Netz zu einer Eingabe entscheiden, ob der entsprechende Punkt in einer bestimmten (eckigen) Figur drin liegt. Dazu legt man Grebenen an die Grenzen der Figur, kreiert die zugehoerigen Perzeptrons und verknuepft deren Ausgaben entsprechend mit AND oder OR. Ein Perzeptron-Netz kann allerdings keine runden Formen erkennen. Bildet ein Perzeptron-Netz eine Trainingsmenge korrekt ab, so koennen Gewichte und Schwellwerte ganzzahlig gemacht werden, ohne dass dies sich aendert. Tower: Ein Perzeptron-Netz, das aus einer Folge von Perzeptronen besteht. Dabei bekommt jedes Perzeptron als Eingabe die Gesamteingabe und die Ausgabe seines Vorgaengers. Ist p[i](x) = H( w[i]*x - Theta[i]) die vom i-ten Perzeptron berechnete Funktion, so ist die vom Tower berechnete Funktion: tower(x) = p[n](x _ p[n-1](x _ ... p[1](x) ) ... ) Die Muster sind dabei aus {-1,1}^m x {0,1}. Tower-Algorithmus: Der folgende Algorithmus zum Trainieren eines Towers. Gesucht: Eine Folge von Perzeptrons, sodass alle Beispiel-Eingabe-Vektoren x[i] von diesem Tower korrekt auf ihre Soll-Ausgabe y[i] abgebildet werden. 1. Trainiere ein Perzeptron Nr. 1 auf den Trainingsdaten, bis eine bestimmte Anzahl von Schleifendurchlaeufen ueberschritten wurde. Hat das Perzeptron die Funktion gelernt, so ist der Tower dieses Perzeptron, fertig. Andernfalls weiter. 2. Setze k=1. Verlaengere alle Vektoren x[i] um eine Komponente 0. 3. Setze die letzte Komponente eines jeden Vektors x[i] auf die Ausgabe des Perzeptrons Nummer k von diesem Vektor, naemlich auf p[k](x[i]). 4. Erhoehe k. 5. Nimm ein neues Perzeptron Nr. k und trainiere es auf der so veraenderten Trainingsmenge, bis eine bestimmte Anzahl von Schleifendurchlaeufen ueberschritten wurde. 6. Hat das Perzeptron die Trainingsmenge gelernt, so ist der Tower fertig. Andernfalls weiter bei Schritt 3. Konvergenz des Tower-Algorithmus: Es gibt einen Tower-Algorithmus-Verlauf (d.h. eine Reihenfolge von Beispielen), der nach so vielen Schleifendurchlaeufen anhaelt, wie Beispiele in der Trainingsmenge sind, denn jedes hinzugefuegte Neuron kann so konfiguiert werden, dass es mindestens ein neues Beispiel korrekt klassifiziert. Beweis: Die y[i] seien aus {-1,1}. Sei x[i] ein noch falsch klassifizierter Beispielvektor. 1. Fall: x[i] ist positiv Waehle den Gewichtsvektor w des neuen Perzeptrons w = x[i] _ 2*|x[i]|^2, also als Komponenten die von x[i] und als zusaetzliche Komponente die Zahl 2*|x[i]|^2. Waehle als Bias |x[i]|^2. Ist f die Funktion, die von dem vorhergehenden Tower berechnet wird, so berechnet der neue gesamte Tower fuer einen Beispielvektor x[j] die Funktion tower(x[j]) = H( x[i]*x[j] + 2*|x[i]|^2*f(x[j]) - |x[i]|^2 ) Fuer x[i] kommt also heraus: tower(x[i]) = H( x[i]*x[i] + 2*|x[i]|^2*f(x[i]) - |x[i]|^2 ) = H( |x[i]|^2 + 2*|x[i]|^2* 0 - |x[i]|^2 ) = H( 0 ) = 1 Fuer alle anderen, bereits richtigen positiven Beispiel-Vektoren x[j] mit j= 0 >=0 >=0 =0 2. negative Eingabevektoren, die vom aktuellen Perzeptron richtigerweise auf negativ abgebildet werden. Dann aendert sich auch durch das Zusammenschalten nichts daran: w*x - Theta + lambda*p1(x) - lambda*p2(x) < 0 <0 =0 >=0 3. positive Eingabevektoren, die vom aktuellen Perzeptron faelschlicherweise auf negativ abgebildet werden. Dann wird dieser Fehler durch das Zusammenschalten behoben: w*x - Theta + lambda*p1(x) - lambda*p2(x) >=0 <0 =lambda =0 (wenn lambda gross genug gewaehlt wurde) 4. negative Eingabevektoren, die vom aktuellen Perzeptron faelschlicherweise auf positiv abgebildet werden. Dann wird dieser Fehler durch das Zusammenschalten behoben: w*x - Theta + lambda*p1(x) - lambda*p2(x) < 0 >=0 =0 =-lambda (wenn lambda gross genug gewaehlt wurde) Da die 2-elementigen Trainingsmengen ganz unten in der Rekursion auf jeden Fall von ihren Perzeptrons richtig klassifiziert werden, werden auch die Perzeptronen eine Ebene hoeher ihre Trainingsmengen richtig klassifizieren usw., bis folgt, dass das letzte Perzeptron die gesamte Trainingsmenge korrekt klassifiziert. Dazu braucht Upstart allerdings im Vergleich zu Tower exponentiell viele Neuronen. Zwar konvergiert der Upstart-Algorithmus, er muss aber aufgrund seiner Maechtigkeit nicht unbedingt generalisieren. Ensemble: Ein Perzeptronnetz, das aus einer Menge von Perzeptronen besteht, die ihre Ausgaben an ein einzelnes Perzeptron weitergeben. Die Gesamteingabe geht an alle Perzeptronen der Menge, die berechnete Funktion ist die Ausgebe des einzelnen Perzeptrons. Jede boolsche Funktion kann mit einem Ensemble berechnet werden. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Feed-Forward-Netze ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Covers Theorem: Die Wahrscheinlichkeit, dass eine Trainingsmenge linear trennbar ist, kann beliebig gross gemacht werden, wenn die Daten nicht-linear in einen genuegend hoch-dimensionalen Raum transformiert werden. Dieses geschieht durch eine Funktion f:R^n->R^m, die zu einem Vektor aus R^n einen m-dimensionalen anderen Vektor liefert, wobei m>n. Die Menge der so transformierten Vektoren f(x[i]) ist dann mit hoeherer Wahrscheinlichkeit linear trennbar. Beispiel: Vergleiche XOR-Problem, welches linear trennbar waere, wenn man die Moeglichkeit haette, einen Punkt in die dritte Dimension zu schieben. lineare Aktivierungsfunktion: Die Funktion lin:R->R mit lin(x)=a*x. Die lineare Aktivierungsfunktion kann verwendet werden, um einem Neuron Werte aus ganz R als Ausgabe zu ermoeglichen. Hat beispielsweise die Ausgabeschicht eines Neuronalen Netzes lin als Aktivierungsfunktion, so hat das Netz Vektoren aus R^|O| als Ausgabe. sigmoide Funktion: Eine Funktion f:R -> ]0;1[, die streng monoton steigend ist und fuer x -> -INF gegen 0 geht und fuer x -> +INF gegen 1. logistische Aktivierungsfunktion: Die sigmoide Funktion fl:R->]0,1[ mit fl(x)=1/(1+e^(-ax)) Ist a groesser, so ist fl um 0 herum steiler und stufenfoermiger, ist a kleiner, so ist fl flacher. Die Ableitung der logistischen Aktivierungsfunktion nach ihrem Eingabewert ist dfl(x)/dx = a*fl(x)*(1-fl(x)). Sigmoide Aktivierungsfunktion: Die sigmoide Funktion sgd:R->]0,1[ mit sgd(x)=1/(1+e^-x), also die logistische Aktivierungsfunktion mit a=1. Die Ableitung der sigmoiden Aktivierungsfunktion nach ihrem Eingabewert ist dsgd(x)/dx = sgd(x)*(1-sgd(x)). Sigmoides Neuron: Ein Neuron, welches gegeben ist durch * eine Eingabedimension n und die Eingabemenge E = R * einen Gewichtsvektor w=(w1,w2,...wn) aus R^n * einen Biaswert/Schwellwert theta aus R * die sigmoide Aktivierungsfunktion Die berechnete Funktion ist also f:R^n -> R mit f(x) = sgd(w*x - theta). Ein Sigmoides Neuron ist maechtiger als ein Perzeptron: Es kann alle Funktionen berechnen, die ein Perzeptron berechnen kann, da sgd sich fuer grosse |w| und |theta| wie H verhaelt. Es kann aber mehr Funktionen berechnen als das Perzeptron, weil es alle werte zwischen 0 und 1 als Ausgabe haben kann. Trennproblem fuer sigmoide Neuronen: Die Frage, ob es ein sigmoides Neuron gibt, welches auf einer Trainingsmenge hoechstens k Fehler macht. Dieses Problem laesst sich vom Trennproblem fuer Perzeptrons reduzieren und ist daher NP-vollstaendig. Sigmoides Netz: Ein Neuronales Netz aus sigmoiden Neuronen. Sigmoide Netze sind maechtiger als Perzeptron-Netze. Layer, Schicht: Eine groesstmoegliche Teilmenge von Neuronen, die so konstruiert ist, dass man von einem Neuron der Schicht nicht via "->" zu einem anderen (oder demselben) Neuron dieser Schicht kommen kann. Geschichtetes Netz: Ein neuronales Netz, dessen Neuronenmenge komplett in verschiedene Schichten zerfaellt. Das bedeutet, dass es von einer Schicht nur Verbindungen zur naechsten oder irgendeiner folgenden Schicht gibt. Vorwaertsgerichtetes Netz, Feed-Forward-Netz, FNN: Ein geschichtetes Netz, bei dem folgende Bedingungen erfuellt sind: * die Relation "->" ist azyklisch, d.h. man kommt nicht von einem Neuron via "->" wieder zum selben Neuron zurueck. Dieses geht mit der Schichtung einher. * I ist die Menge der Neuronen ohne Vorgaenger * O ist die Menge der Neuronen ohne Nachfolger Da die Ausgabe eines Netzes aus R^|O| ist, sind die Soll-Ausgaben der Beispiele einer Trainingsmenge fuer ein Netz stets reelle Vektoren. Die Aktivierungsfunktionen der verborgenen Neuronen sind nicht-linear, denn andernfalls wuerde ein einfaches Perzeptron ausreichen. Ein FNN wird auch "Multilayer-Perceptron" oder "MLP" genannt. Shortcut: Eine Verbindung von einer Schicht zur uebernaechsten oder einer darauf folgenden. Voll vernetztes FNN: Ein FNN, bei dem jedes Neuron einer Schicht Verbindungen zu jedem Neuron der darauf folgenden Schicht hat und bei dem es keine Shortcuts gibt. Eingabeschicht: Die Schicht aus Eingabeneuronen eines FNN. Ausgabeschicht: Die Schicht aus Ausgabeneuronen eines FNN. verborgene Schicht, hidden layer: Eine Schicht eines FNN, die weder Eingabeschicht ist noch Ausgabeschicht. // Den Begriff "hidden Schicht" finde ich unguenstig Neuronen der verborgenen Schichten: Die Neuronen der ersten Schicht dienen als "local feature detectors": Sie transformieren die Eingaben in einen Raum hoeherer Dimension, in der sie leichter trennbar sind (Covers Theorem). Die Neuronen der zweiten verborgenen Schicht dienen als "global feature detectors", die aus den Ergebnissen der local feature detectors das Gesamtergebnis formieren. n-m-n-Problem: Die Frage, ob ein FNN mit einer Eingabeschicht aus n Neuronen, einer verborgenen Schicht aus m Neuronen und einer Ausgabeschicht aus n Neuronen die Eingaben (1,0,0,...0), (0,1,0,...0) usw. korrekt auf dieselben Eingaben abbilden kann. Klassische Instanzen sind das 8-3-8-Problem und das 4-2-4-Problem, welche von einem sigmoiden Netz gut geloest werden koennen. Damit nehmen Schicht 1 und 2 eine Datenkompression vor. Die komprimierten Daten koennen abgegriffen werden und spaeter durch Schicht 2 und 3 des Netzes wieder entpackt werden. 2-Spiralen-Problem: Die Frage, ob ein FNN entscheiden kann, ob ein Punkt in einem Koordinatensystem auf der weissen oder schwarzen Spirale liegt. Die Spiralen liegen dabei ineinander gedreht. Das Netz hat 2 Eingaenge (x- und y-Koordinate) und 1 binaeren Ausgang. Es zeigt sich, dass das Netz nicht in Bereiche ausserhalb der Trainingsmenge abstrahieren kann, es funktioniert nur innerhalb der vorgegebenen Spirale. kompakte Menge: Eine Menge, die sowohl abgeschlossen ist (d.h. die "Grenzen" der Menge gehoeren mit dazu) als auch beschraenkt ist (d.h. alle Elemente liegen in einem abgesteckten Bereich). konstante Funktion: Eine Funktion, deren Ausgabe unabhaengig vom eventuell vorhandenen Eingabewert immer derselbe ist. Approximationsvollstaendigkeit: Die Eigenschaft, jede beliebige Funktion bis auf einen vorgegebenen Fehler berechnen zu koennen. Algebra: Eine Menge, auf der eine Addition, eine Multiplikation und eine Vervielfachung (skalare Multiplikation) definiert ist. Funktionsklasse: Eine Menge von Funktionen. separierende Funktionenalgebra: Eine Funktionenalgebra (d.h. eine Funktionsklasse mit Addition, Multiplikation und Vervielfachung), in der es zu zwei verschiedenen Werten x und y immer eine Funktion gibt, welche fuer x und y unterschiedliche Ausgaben hat: All x: All y: (x!=y => Ex f: f(x)!=f(y)) Satz von Stone-Weiertrass: Eine Algebra von Funktionen, die separierende ist und konstante Funktionen enthaelt, ist approximationsvollstaendig. Das heisst: Wenn ich eine Menge von Funktionen habe, die ich addieren kann, multiplizieren kann und vervielfachen kann, dann ist es moeglich, aus diesen Funktionen jede beliebige andere Funktion zusammenzusetzen. Cosinus-Squasher: Eine Funktion cossq:R->R mit cossq(x) = (x>pi/2) ? 1 : (x < -pi/2) ? -1 : cos(x). Diese Funktion ist also um 0 herum wie der Cosinus, ausserhalb aber konstant -1 bzw. 1. Approximationsvollstaendigkeit eines Netzes: Zu jeder beliebigen stetigen Funktion f:M -> [0;1] (M kompakt) (auch mit endlich vielen Unstetigkeitsstellen) gibt es ein vollvernetztes FNN mit 1 verborgenen Schicht, welches die Funktion bis auf einen beliebigen Fehler approximiert. Es genuegt also theoretisch eine einzige verborgene Schicht. In der Praxis nimmt man aber meist mehrere, sodass man insgesamt weniger Neuronen braucht. Beweis: Es genuegt zu zeigen, dass die Neuronalen Netze eine Funktionenalgebra sind, die separierend ist und Konstanten enthaelt: * Konstante Netze koennen sehr einfach gebastelt werden (1 Neuron, Gewichte auf 0, Schwellwert so gewaehlt, dass das gewuenschte Ergebnis herauskommt). * Separierung Man kann immer ein Netz finden, welches zu zwei Eingabewerten unterschiedliche Ausgaben hat. * Addition Zwei Netze koennen auch "addiert" werden. Dazu nimmt man zunaechst die Sigmoide aus den Ausgabeneuronen der beiden Netze heraus, sodass man lineare Ausgaben bekommt. Diese brauchen nur noch von einem Neuron aufsummiert zu werden. * Vervielfachung Die Vervielfachung kann aehnlich der Addition nachgebildet werden. * Multiplikation Man kann annehmen, dass die verborgene Schicht der Netze keine Sigmoide benutzt, sondern Cosinus-Squashers, da sich ein Cosinus-Squasher mit Sigmoiden approximieren laesst. Da sich aber der Cosinus durch Cosinus-Squashers approximieren laesst, kann man kann man annehmen, die verborgene Schicht benutze Cosinus-Funktionen. Wie bei der Addition kann man lineare Ausgabe annehmen. Dann berechnet das erste Netz SUM i aus N1 a1[i]*cos(...)+theta1[i] und das zweite ebenso SUM i aus N2 a2[i]*cos(...)+theta2[i]. Werden beide Netze multipliziert, so ergibt sich aufgrund eines Theorems, welches besagt, dass das Produkt zweier Cosinus-Funktionen die Summe zweier Cosinus-Funktionen ist, ein Ausdruck der Form SUM a[]*cos(...)+a[]*cos(...)+theta[], d.h. wieder ein Netz. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ FNN-Trainingsalgorithmen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Nettoinput-Funktion: Eine Funktion net[i]:R^n -> R, die zu einem Eingabevektor x des Neuronalen Netzes die Aktivierung des Neurons i liefert. Im Folgenden wird jedoch nur ein einzelner Eingabewert x betrachtet, daher ist net[i] die Aktivierung fuer diese Eingabe. Ausgabefunktion: Eine Funktion o[i]:R^n -> R, die zu einem Eingabevektor x des Neuronalen Netzes die Ausgabe des Neurons i liefert. Es gilt o[i](x)=f[i](net[i](x) - theta[i]), d.h. die Ausgabe des i-ten Neurons ist seine Aktivierung, die abzueglich seines Schwellwertes in seine Aktivierungsfunktion gesteckt wird. Im Folgenden werden jedoch nur Neuronen mit theta=0 und f[i]=sgd und nur ein einziger Eingabewert x betrachtet, daher gilt: o[i]=sgd(net[i]) Empirischer Fehler, Trainingsfehler, Fehler eines Netzes: Eine Zahl E, die zu einer Trainingsmenge fuer ein Netz die Guete der Berechnung abschaetzt. Der Fehler kann als Funktion aufgefasst werden, die zu einem Tupel von Kennwerten, die das Netz charakterisieren (z.B. die Gewichte und Biaswerte), die Guete-Bewertung berechnet. Daher kann man den Fehler nach allen Kennwerten des Netzes ableiten. Eine Fehlerfunktion sollte folgende Kriterien erfuellen: * Differenzierbarkeit (wird fuer den Gradientenabstieg benoetigt) * Minimal fuer richtige Ausgaben * Fehlergewichtung, d.h. falschere Werte sollen groesseren Fehler haben * Schnelle Berechenbarkeit Das Problem, das Minimum der Fehlerfunktion zu finden, ist NP-vollstaendig. Der empirische Fehler wird auch "Bias" genannt. Quadratischer Fehler eines Netzes: Fuer ein Neuronales Netz und eine Trainingsmenge P der Fehler E = 0.5 * (SUM p=1..|P| (SUM j aus O (y[p][j] - o[j](x[p]))^2)). Es wird also fuer jedes Muster p die tatsaechliche Ausgabe des j-ten Ausgabeneurons fuer die Eingabe x, naemlich o[j](x) von der gewuenschten Ausgabevektorkomponente y[p][j] abgezogen. Diese Zahl wird quadriert, um negative Eintraege positiv zu machen. Nun summiert man diese Zahlen fuer jedes Ausgabeneuron auf und wiederholt die Berechnung fuer alle Muster p der Trainingsmenge. Im Folgenden wird jedoch immer nur von einem Muster ausgegangen, daher gilt: E = 0.5 * (SUM j aus O (y[j] - o[j])^2) Gradientenabstieg: Ein Algorithmus zur Minimierung einer Funktion. Dazu wird ein Anfangs-Eingabewert x willkuerlich gewaehlt. Nun berechnet man den Gradienten an dieser Stelle, multipliziert ihn mit einer reellen "Schrittweite" oder "Lernrate" eta und zieht ihn von x ab. Dadurch rueckt x in Richtung eines kleineren Funktionswertes. Das wiederholt man so lange, bis eine befriedigende Loesung gefunden ist. Nachteile des Gradientanabstiegs: * Es werden nur "lokale Minima" gefunden, d.h. Stellen, an denen die Ausgabe der Funktion zwar klein ist, aber nicht notwendigerweise optimal klein. In der Praxis sind allerdings lokale Minima oft aehnlich gut wie globale * Es koennen lokale, "instabile Maxima" gefunden werden, d.h. Stellen, an denen der Funktionswert groesser ist als in der Umgebung, die Steigung aber 0. * In "Plateaus", d.h. flachen Umgebungen, in denen die Steigung in alle Richtungen fast 0 ist, bewegt sich der Algorithmus kaum * In "Schluchten", d.h. Umgebungen mit hoher Steigung um ein Minimum herum, kann der Algorithmus moeglicherweise stetig um das Minimum herumspringen ("Oszillation"). * Es koennen "Randoptima" gefunden werden, d.h. Stellen am Rande der Menge fuer die die Funktion definiert ist. * Minima koennen uebersprungen werden. * In "Hohlwegen", d.h. Schlucht in einer Dimension aber fallende Steigung in einer anderen Dimension, kann die Schlucht eine grosse Schrittweite verursachen, die in die Dimension der fallenden Steigung aber unsinnig ist. * In "Spitzkehren", d.h. Biegungen von Hohlwegen, kann man die Kurve verpassen und weiter in eine Dimension laufen, die nicht dem optimalen Weg ins Minimum entspricht. Fehlersignal: Eine Zahl, die fuer jedes Neuron eines Netzes angibt, wie stark dieses Neuron fuer den Gesamtfehler des Netzes verantwortlich ist. Es gilt d[i] = dE/dnet[i], das Fehlersignal fuer Neuron i ist also die Ableitung des Gesamtfehlers nach der Aktivierung des Neurons i. Im Folgenden wird immer vom quadratischen Fehler ausgegangen. Fuer Ausgabeneuronen berechnet sich d[i] wie folgt: d[i] = dE/dnet[i] = d(0.5 * ( (y[i]-o[i])^2 + (y[j]-o[j])^2 ... + (y[z]-o[z])^2 )) / dnet[i] fuer die Ausgabeneuronen i,j,...z = d( 0.5 * (y[i]-o[i])^2 ) / dnet[i] // da die anderen unabh. von net[i] = d( 0.5 * (y[i]-o[i])^2 ) / do[i] * do[i]/dnet[i] // nach Kettenregel = 0.5 * 2 * (y[i]-o[i]) * -1 * do[i]/dnet[i] // nach Kettenregel = (o[i]-y[i]) * d(sgd(net[i]))/dnet[i] // da o[i]=sgd(net[i]) = (o[i]-y[i]) * sgd(net[i]) * (1-sgd(net[i])) // wg der Ableitung von sgd = (o[i]-y[i]) * o[i] * (1-o[i]) // da o[i]=sgd(net[i]) // allgemein: = E'(o[i]) * aktfkt'(o[i]) Fuer Nicht-Ausgabeneuronen berechnet sich d[j] so: d[j] = dE/dnet[j] = dE(net[k1](net[j]),...net[kn](net[j]))/dnet[j] fuer alle Nachfolgerneuronen k1,k2,...kn von Neuron j // Der Fehler wird hier also in Abhaengigkeit von den Aktivierungen // der Nachfolger von j betrachet. In der Tat bestimmen die // Aktivierungen einer einzelnen Schicht (hier die Schicht aus // k1,...kn) den Fehler E bereits komplett. // Die Aktivierung eines Neurons k kann als Funktion von der // Aktivierung eines Vorgaengers (hier: j) gesehen werden, // also net[k](net[j]) = SUM (j,k) aus "->" dE/dnet[k] * dnet[k]/dnet[j] // nach der mehrdimensionalen Kettenregel = SUM (j,k) aus "->" d[k] * dnet[k]/dnet[j] // da d[k] = dE/dnet[k] = SUM (j,k) aus "->" d[k] * d(SUM i aus V w[i,k] * o[i])/dnet[j] fuer alle Vorgaenger V von k // Die Aktivierung eines Neurons bestimmt sich als Skalarprodukt // aus seinem Eingabevektor (hier: Vektor o der Ausgaben der // Vorgaenger) mit seinem Gewichtsvektor (hier: die zugehoerigen // Gewichte w[],k) = SUM (j,k) aus "->" d[k] * d(w[j,k] * o[j])/dnet[j] // alle anderen Summanden w[i,k]*o[i] fuer i!=j sind nach net[j] // abgeleitet 0: Die Ausgaben eines Neurons i in derselben Schicht // mit j sind nicht von net[j] beeinflusst = SUM (j,k) aus "->" d[k] * w[j,k] * do[j]/dnet[j] // da das Gewicht w[j,k] nicht von net[j] abhaengt = SUM (j,k) aus "->" d[k] * w[j,k] * dsgd(net[j])/dnet[j] // da o[j] = sgd(net[j]) = SUM (j,k) aus "->" d[k] * w[j,k] * sgd(net[j])*(1-sgd(net[j])) // wegen der Ableitung von sgd = SUM (j,k) aus "->" d[k] * w[j,k] * o[j] * (1-o[j]) // da o[j] = sgd(net[j]) = o[j] * (1-o[j]) * SUM (j,k) aus "->" d[k] * w[j,k] // allgemein: = aktfkt'(o[j]) * SUM (j,k) aus "->" d[k] * w[j,k] Das Fehlersignal laesst sich also fuer die Ausgabeneuronen direkt berechnen. Fuer aller Schichten davor berechnet es sich fuer ein Neuron j als Summe aller Terme d[k] * w[j,k] * o[j] * (1-o[j]), wobei k die Nachfolger von j durchlaeuft. So kann man das Fehlersignal also fuer alle Neuronen rueckwaerts durch das Netz berechnen. Gradient eines Gewichtes: Die Zahl dE/dw[i,j], die angibt, wie stark das Gewicht w[i,j] an dem Gesamtfehler E beteiligt ist. Es gilt: dE/dw[i,j] = dE/dnet[j] * dnet[j]/dw[i,j] // Nach Kettenregel = d[j] * d(SUM (h,j) aus "->" o[h]*w[h,j])/dw[i,j] // Nach Def. = d[j] * d(o[i]*w[i,j])/dw[i,j] // alle anderen unabhaengig = d[j] * o[i] = o[i] * d[j] Fuer den Schwellwert eines Neurons ergibt sich durch Simulation mit on-Neuron: dE/dtheta[j] = dE/dw[onneuron,j] = o[onneuron] * d[j] = -d[j] Backpropagation, Offline Backpropagation, Batch Backpropagation, Epochen- Backpropagation: Der folgende Algorithmus zum Trainieren sigmoider Netze. 1. Waehle eine Lernrate eta (etwa 0.2) 2. Initialisiere die theta[i] und w[i,j] mit kleinen Zufallszahlen // Sind die Zahlen gross, so ist die Aktivierung eines Neurons vom // Betrag her zu weit vom "Umschlagpunkt" 0 der Aktivierungsfunktion // weg, die Neuronen fahren sich fest 3. Nimm ein neues Tupel deltatheta mit Komponenten fuer jedes Neuron, setze alle Komponenten auf 0. Nimm ein neues Tupel deltaw mit Komponenten fuer alle w[i,j] und setze alle auf 0. 4. Nimm ein Muster der Trainingsmenge 5. Berechne die Ausgabe des Netzes fuer dieses Muster 6. Berechne rueckwaerts die Fehlersignale d[i] fuer jedes Neuron 7. Addiere auf jedes deltaw[i,j] den Gradienten dE/dw[i,j]=o[i]*d[j] 8. Addiere auf jedes deltatheta[i] den Gradienten dE/dthetha[i]=-d[i] 9. Falls noch nicht alle Muster dran waren, weiter bei 4 10. Subtrahiere von allen w[i,j] das eta-fache von deltaw[i,j]. 11. Subtrahiere von allen theta[i] das eta-fache von deltatheta[i]. Der Aufwand pro Muster ist O(|w|), also linear mit der Anzahl der Gewichte. Damit ist das Training zwar nicht mehr biologisch plausibel, dafuer aber relativ funktionstuechtig. Das Verfahren funktioniert genauso auch fuer Shortcuts. Dieses laesst sich ueber theoretisch eingefuegte id-Neuronen nachrechnen. Backpropagation haften die Nachteile des Gradientenabstiegs an. Zusaetzlich kommt es noch zu "sigmoider Daempfung", d.h. zur Sigmoide- bedingten Abschwaechung des Fehlersignals bei mehreren Schichten. Da die Steigung einer sigmoiden Funktion bei x=0 am groessten ist, kommt es hier zur groessten Parameteraenderung bei Backpropagation. Dieses "Flip-Flop-Verhalten" sorgt dafuer, dass ein Neuron dazu tendiert definitiv zu feuern oder nicht zu feuern, was der Stabilitaet des Verfahrens zugute kommt. FNNs koennen allerdings in Schwierigkeiten kommen, wenn zu trennende Punkte sehr nah aneinander liegen, da dann zu leicht lokale Optima gefunden werden. Epoche: Ein Durchlauf durch alle Muster beim Trainieren. Online Backpropagation, Backpropagation by pattern: Eine Modifikation des Backpropagation-Algorithmus, bei der die Aenderung der Gewichte und Biaswerte direkt nach jedem Muster erfolgt und nicht am Ende fuer alle zusammen. D.h. der folgene Algorithmus: 1. Waehle eine Lernrate eta (etwa 0.2) 2. Initialisiere die theta[i] und w[i,j] mit kleinen Zufallszahlen 3. Nimm ein Muster der Trainingsmenge 4 Berechne die Ausgabe des Netzes fuer dieses Muster 5. Berechne rueckwaerts die Fehlersignale d[i] fuer jedes Neuron 7. Subtrahiere von jedem theta[i] die Zahl eta*(-d[i]) 8. Subtrahiere von jedem w[i,j] die Zahl eta*(d[i]*o[j]) 9. Falls noch nicht alle Muster dran waren, weiter bei 3 Online Backpropagation umgeht das Problem der lokalen instabilen Maxima, da durch die zufaellige Musterauswahl eine Art Rauschen entsteht. Online Backpropagation ist allerdings kein wirklicher Gradientenabstieg mehr, sondern ein sogenannter stochastischer Gradientenabstieg. Online Backpropagation zeigt sich besonders fuer grosse Mustermengen mit vielen redundanten (d.h. gleichen) Daten nuetzlich. Aufwand von Backpropagation: Ein Zyklus geht fuer jedes Pattern jedes Gewicht durch, der Aufwand pro Zyklus betraegt also |W|*|P|. Ist die Lernrate klein genug und befindet sich der aktuelle Gewichtsvektor w[t] nahe genug am Minimum w[opt], und ist die Steigung der Ableitung in w[opt] positiv, so konvergiert RProp exponentiell schnell. Beweis: Im naechsten Minimum der Fehlerfunktion ist der Gradient Null und der Gradient der Ableitung positiv. Nun kann die Fehlerfunktion lokal durch eine quadratische Funktion approximiert werden, da gilt: E(w) ~= E(w[opt]) + 1 * E(w[opt])' * (w-w[opt]) + 0.5*E(w[opt])''* (w-w[opt])^2 //Nach Taylor = E(w[opt]) + 0.5*E(w[opt])''* (w-w[opt])^2 //Da E(w[opt])'=0 Fuer diese quadratische Funktion laesst sich nun nachrechnen, dass w exponentiell schnell gegen w[opt] wandert. Backpropagation mit Momentum: Eine Modifikation des Backpropagation- Algorithmus, bei der pro Aenderung noch ein Anteil der vorherigen Aenderung hinzugenommen wird ("Traegheit"). Dadurch werden die Probleme der Oszillation und der Hochplateaus umgangen. In linearen Hochplateaus bleibt die Schrittweite bedingt durch den Algorithmus allerdings auf ein Vielfaches des Produktes von Steigung und Lernrate begrenzt. Fuer Schrittweite s, Momentumfaktor a, Steigung m und Lernrate eta gilt: s < eta*m/(1-a) Beweis: Schrittweite in Schritt 1: eta*m Schrittweite in Schritt 2: eta*m*a + eta*m Schrittweite in Schritt 3: (eta*m*a + eta*m)*a + eta*m Schrittweite in Schritt 4: ((eta*m*a+eta*m)*a+eta*m)*a + eta*m Schrittweite in Schritt k: SUM i=0..k eta*m*a^i = eta*m* SUM i=0..k a^i = eta*m* (1-a^k)/(1-a) // Nach Summenformel Fuer k gegen unendlich und |a|<1: = eta*m/(1-a) Manhatten-Training: Eine Modifikation des Backpropagation-Algorithmus, bei der von den Gewichte nicht dE/dw[i,j] subtrahiert wird, sondern eine Konstante, versehen mit dem Vorzeichen von dE/dw[i,j]. Dadurch gibt das Fehlersignal nur die Richtung an, nicht aber die Schrittweite. Dieses entspricht einem Gradientenabstieg auf E=SUM i aus O |o[i]-y[i]|. adaptiv: variabel und anpassbar. DeltaBARDelta, SuperSAB: Eine Modifikation des Backpropagation- Algorithmus, bei der jedes Gewicht w[i,j] ueber eine eigene adaptive Lernrate eta[i,j] verfuegt. Gehen zwei Schritte in dieselbe Richtung, so wird die Lernrate erhoeht. Dadurch wird das Problem des Hinundherschwingens in Hohlwegen vermieden, bei denen in eine Dimension eine hohe Lernrate benoetigt wird, um voran zu kommen, in die andere Dimension jedoch diese Lernrate zu Oszillation fuehren wuerde. RProp, Resilient Propagation: Eine von Martin Riedmiller entwickelte Modifikation des Offline Backpropagation-Algorithmus, die folgende Veraenderungen einfliessen laesst: * Jedes Gewicht hat seine eigene Lernrate (von SuperSAB) * Die Lernraten sind adaptiv (von SuperSAB) * Die Lernraten werden vervielfacht, wenn die aktuelle Aenderung und die letzte Aenderung in dieselbe Richtung zeigten * Die Lernraten werden gebruchteilt, wenn die aktuelle Aenderung und die letzte Aenderung in verschiedene Richtungen zeigten * Zeigten zwei Aenderungen in verschiedene Richtungen, so wird die letzte Aenderung zurueckgenommen * Den Lernraten sind Minimal- und Maximal-Werte als Schranken gegeben * Die Aenderung bestimmt sich aus der Lernrate und dem Vorzeichen des Fehlersignals (vom Manhatten-Training) Damit vereinigt RProp die Vorteile der anderen Algorithmen und liefert sehr schnell sehr gute Approximationen. Regularisierung, Weight-Decay: Eine Modifikation des Backpropagation- Algorithmus, bei der jedes Gewicht w[i,j] in jedem Schritt mit (1-eta) multipliziert wird, wobei eta sehr klein ist (10E-4 o.ae.). Dadurch wird vermieden, dass die Betraege der Gewichte zu gross werden und Overfitting beguenstigt wird. Die Verkleinerung der Gewichte fuehrt zu einer eher quadratischen und damit weniger lokale Minima besitzenden Funktion. Richtung: Ein Vektor von der Dimension des Eingabevektors. Man kann in diese Richtung laufen, indem man auf den Eingabevektor immer einen Bruchteil der Richtung addiert. Geradensuche: Ein Algorithmus zum Minimieren einer Funktion, bei dem man sich zunaechst fuer eine Richtung entscheidet und in dieser Richtung laeuft, bis ein Minimum gefunden ist. Dann entscheidet man sich erneut fuer eine Richtung und sucht erneut ein Minimum usw. Steepest Descent: Eine Geradensuche, die die Richtung nach dem Gradienten bestimmt. Dieser Algorithmus ist einfach, aber nicht effizient, da er leicht in Oszillation geraet. Conjugate Gradient Algorithm: Eine Geradensuche, bei der die vorherige Richtung die neue Richtung in jedem Schritt mit beeinflusst. Der Grad der Beinflussung wird mit mathematischen Methoden optimiert, sodass die neue Suchrichtung senkrecht zur alten ist. Das Verfahren konvergiert bei quadratischen Funktionen garantiert nach soviel Schritten wie Parameter da sind , ist allerdings unvorhersagbar fuer wenig quadratische Funktionen. Newton-Verfahren: Ein Algorithmus zur Minimierung einer Funktion, bei der die Information der zweifachen Ableitung (Kruemmung) der zu minimierenden Funktion benutzt wird, um eine Schrittweite zu berechnen und ein Minimum zu finden. Die zweifache Ableitung ist allerdings im Mehrdimensionalen sehr aufwaendig zu berechnen. Quickprop: Eine Vereinfachung des Newton-Verfahrens. Sie ist mathematisch kompliziert, liefert aber keine besseren Ergebnisse als Rprop und ist zudem sehr parameterabhaengig und instabil. Zufallssuche: Ein eher ineffizienter Algorithmus zur Minimierung einer Funktion, bei dem wiederholt der Funktionswert an zufaellig gewaehlten Stellen berechnet wird, bis ein zufriedenstellend kleiner Wert herauskommt. Genetischer Algorithmus: Ein Algorithmus zur Minimierung einer Funktion, der mehrere Eingabewerte zufaellig generiert, dann einige davon, die einen guten Funktionswert haben, permutiert und mit anderen vermischt. Auf diese Weise entstehen neue Eingabevektoren, mit denen der Vorgang wiederholt wird, bis eine befriedigende Loesung gefunden ist. // Genetische Algorithmen koennen auch andere Optimierungsprobleme loesen, // aber jedes Optimierungsproblem laesst sich als Minimierung einer // Funktion auffassen gewichteter Mittelwert: Der gewichtete Mittelwert eines Zahlentupels x=(x[1], x[2], ..., x[n]) ist das Skalarprodukt aus x und einem Gewichtungsvektor a=(a[1],a[2],...,a[n]), wobei die a[i] positiv sind und SUM a=1..n a[i]=1 gilt. Jedes a[i] gewichtet also das zugehoerige x[i] und bestimmt, wie stark es in das Ergebnis einfliessen soll. Ist a[1]=a[2]=...=a[n]=1/n, so ist das Ergebnis der normale Mittelwert. Netzmittelung: Ein Algorithmus zur Approximation einer Funktion mithilfe neuronaler Netze, bei dem mehrere Netze normal auf der Trainingsmenge trainiert werden. Die endgueltige Approximation fuer eine Eingabe berechnet sich dann als gewichteter Mittelwert der Ergebnisse der einzelnen Netze auf dieser Eingabe. Diese Idee entspricht der eines Ensembles. Da die Menge der Netze nicht beschraenkt ist, ist Netzmittelung unendlich maechtig. Der Fehler des gemittelten Ergebnisses ist geringer als der gemittelte Fehler der einzelnen Netze! Beweis: Sei f die zu lernende Funktion, f[i] die Funktion des i-ten Netzes und fw = SUM i=1..n a[i]*f[i] die gemittelte Funktion. Dabei sei SUM i=1..n a[i] = 1 und a[i]>0. Dann ist der Fehler von fw gegenueber f: (f - fw)^2 = f^2 - 2*f*fw + fw^2 // Binomische Formel = 2*fw^2 - 2*f*fw + f^2 - fw^2 // + und - fw^2 = 2*(fw-f)*fw + f^2 - fw^2 // zusammenfassen = SUM i=1..n 2*a[i]*f[i]*(fw-f) + f^2 -fw^2 // fw eingesetzt = SUM i=1..n (-2*a[i]*f[i]*f + 2*a[i]*f[i]*fw ) // auseinandergezogen + SUM i=1..n a[i]*f^2 // da SUM a[i] = 1 + SUM i=1..n a[i]*fw^2 // dito = SUM i=1..n a[i]*(f[i]^2-2*f*f[i]+f^2-f[i]^2+2*f[i]*fw-fw^2) = SUM i=1..n a[i]*(f[i]-f)^2 - SUM i=1..n a[i]*(f[i]-fw)^2 Der erste Summand ist der gemittelte Fehler der einzelnen f[i]. Der zweite Summand gibt die Abweichung der einzelnen f[i] von der gemittelten Funktion an (entspricht der Varianz der einzelnen Netze). Da der zweite Summand durch die Quadrierung und positiv gewichtete Summierung positiv ist, ist also der gemittelte Fehler der einzelnen f[i] groesser als der Fehler von fw. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Aufbauen eines FNN ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Training eines Netzes: Der Aufbau eines Neuronalen Netzes inklusive Vorarbeit, Trainieren und Auswertung, um fuer ein Anwendungsproblem aus gegebenen Daten Vorhersagen fuer unbekannte Daten machen zu koennen. Das Training gliedert sich in 5 nicht immer klar getrennte Schritte: 0. Daten sammeln Die Daten kommen aus den Anwendungsgebieten wie z.B. Biologie, Robotik, Medizin, Cognitive Science, Wetterforschung. 1. Daten vorverarbeiten Die Daten muessen praepariert werden, um es dem Netz so einfach wie moeglich zu machen, das bedeutet: * Bei Zeitreihenprognosen Zeitfenster bilden, ueberlagernde Trends (z.B. die Inflation) herausrechnen * Vorwissen integrieren Bei Spielen wird nicht eine Folge von Spielstaenden genommen, sondern feature-codierte Spielstaende, damit das Netz die Spielregeln nicht lernen muss. * die Eingaben auf reelle Werte abbilden, insbesondere symbolische Daten codieren als (0,0,0,1), (0,0,1,0) etc.. Durch diese "unaere Codierung" wird ungerechtfertigte Aehnlichkeit symbolischer Werte vermieden * nicht vorhandene Werte durch Default-Werte ersetzen * Wichtiges explizit darstellen * Evtl. Fouriertransformation vornehmen, die Daten normieren (Mittelwert abziehen, Korrelation herausrechnen, mit Kovarianz normieren, s. statistik.txt) * Eingaben stetig machen (z.B. Winkel nicht 0 Grad bis 360 Grad, weil an 360 Grad --> 0 Grad unstetig, sondern als zwei Eingaben mit cos(x) und sin(x)=cos(x+pi/2)) * Eingaben auf denselben Bereich abbilden, z.B. alle Eingabekomponenten auf den Bereich [0;1] mappen, um ungerechtfertigte Ungleichheiten zwischen den Dimensionen zu vermeiden. Evtl. wichtige Dimensionen hoeher skalieren. * Sollausgaben skalieren. Werte an den Grenzen der Bildmenge der Aktivierungsfunktion (z.B. 1.0 oder 0.0 fuer sgd) sind unguenstig, da sie das Training verlaengern und festfahren. * Glaetten der Daten * Kanten in den Daten finden Die Vorverarbeitung ist problemspezifisch und aufwaendig, aber essentiell fuer den Erfolg. 2. Architektur auswaehlen Geschieht mithilfe der Kreuzvalidierung. Meist hat das Netz 1 oder 2 verborgene Schichten mit etwa 5 bis 10 Neuronen pro Schicht. Die Daumenregel sagt, dass die Anzahl der Parameter (d.h. Gewichte und Schwellwerte) kleiner als ein Zehntel der Anzahl der Muster sein soll. 3. Netz trainieren Meist wird dazu Backpropagation mit einigen Tricks verwendet. 4. Ergebnisse interpretieren Hier muessen eventuell die Ausgaben des Netzes auf den Sachverhalt zurueckgerechnet werden (Intervalle zurueckskalieren, Ausgabe als Klassifikation interpretieren etc.). Ausserdem sollte die Generalisierungsfaehigkeit mithilfe einer Validierung geprueft werden. "Matrixlaufen": Ein Algorithmus zur Anpassung von Daten aus R^2. Dazu werden die Daten in einer rechteckigen Matrix D angeordnet und sodann eine vorgegebene quadratische Matrix M mit der Kantenlaenge n an jedem Punkt (x,y) von D angelegt. Dann wird jeweils die gewichtete Summe s = SUM i=1..n SUM j=1..n D[x+i-1][y+j-1] * M[i][j] gebildet und durch die Summe aller Komponenten von M dividiert: s' = s / SUM i=1..n SUM j=1..n M[i][j] Dann wird der Punkt, der unter die Mitte der Matrix M zu liegen kam (naemlich D[x+n/2][y+n/2]) durch dieses s' ersetzt. Auch fuer hoeherdimensionale Daten laesst sich das Verfahren analog verwenden. Datenglaettung: Ein Algorithmus zur Verminderung des Rauschens (unter Verlust von Genauigkeit). Dazu wird mit einer Matrix ueber die Daten gelaufen, die in der Mitte hohe Zahlen hat und am Rand niedrige. Dadurch gleicht sich jeder Punkt seiner Umgebung an. Kantenfindung: Ein Algorithmus zum Kontrastschaerfen von Daten. Dazu wird mit einer Matrix ueber die Daten gelaufen, die in der Mitte einen negativen Wert hat und am Rand positive Werte. Die Werte in der Mitte der Raender werden hoeher gewaehlt als die an der anderen (die Matrix heisst dann "Kantenextraktor"). Dadurch werden genau die Punkte an der Grenze zwischen hohen Werten und niedrigen Werten intensiviert. Validierungsmenge: Eine Menge von Beispielen, die nicht in der Trainingsmenge sind und die zur Bestimmung der guenstigsten Architektur benutzt wird. Testmenge: Eine Menge von Beispielen, die nicht in der Trainingsmenge sind und die zum Testen der Generalisierungsfaehigkeit des Netzes auf unbekannten Daten verwendet wird. Validierung: Das Testen eines Netzes auf Daten, die nicht in der Trainingsmenge waren. Meist teilt man die Daten auf in eine Trainingsmenge und eine Testmenge. Mit der Trainingsmenge trainiert man und prueft das Netz zwischendurch immer mal auf Daten der Testmenge. Der Fehler auf der Trainingsmenge wird kontinuierlich kleiner, der Fehler auf der Testmenge steigt jedoch ab einem bestimmten Punkt wieder (Overfitting). Kreuzvalidierung: Ein Verfahren zum gruendlichen Trainieren eines Netzes. Dazu wird die Datenmenge M in eine bestimmte Anzahl von nicht ueberlappenden Mengen M[1],M[2],..M[n] geteilt. Dann trainiert man auf M ohne ein M[i] und testet auf M[i]. Dieses wiederholt man fuer alle i=1..n und mittelt den entstehenden Fehler. Durch dieses Verfahren wird der strukturelle Fehler des Netzes (s.u.) gering gehalten. Early stopping: Ein Verfahren zum Trainieren eines Netzes, welches beim Trainieren auf der Trainingsmenge permanent auf einer Testmenge validiert. Sobald der Fehler auf der Testmenge wieder steigt, bricht man ab. Dieses Verfahren bringt nur erkennbare Vorteile bei einer Anzahl Daten, die kleiner ist als etwa das 30-fache der Anzahl der freien Parameter des Netzes. Pruning: Ein Verfahren zum Trainieren eines zu Anfang grossen Netzes, bei dem nach mehreren Trainingszyklen das unwichtigste Teil des Netzes geloescht wird. Da sich so die Anzahl der Parameter des Netzes verringert, verringert sich auch sein Testfehler. Da allerdings das unwichtigste Teil geloescht wird, bleibt der Trainingsfehler gleich. Somit wird der strukturelle Fehler heruntergeschraubt. Es gibt mehrere Strategien zur Beurteilung der Wichtigkeit von Netzteilen: * Mag-Pruning: Das vom Betrag her kleinste Gewicht wird eliminiert * Skelettierung: Dasjenige Neuron, welches die geringste Auswirkung auf den Gesamtfehler hat, wird herausgenommen. * Optimal Brain Damage: Dasjenige Gewicht, bei dem die Fehlerfunktion die kleinste Kruemmung hat, d.h. bei dem die Ableitung der Ableitung minimal ist. * Evolutive Verfahren (z.B. "ENZO"): Diese benutzen genetische Algorithmen Zeitfenster: Eine Folge konstanter Laenge von zeitlich aufeinanderfolgenden Werten. feature-codiert: Durch ein Tupel von festgelegten Merkmalen charakterisiert. Testfehler: Der Fehler, den ein trainiertes Netz auf unbekannten Daten macht. Es gibt verschiedene Kriterien zur Beurteilung der Guete des Testfehlers: * er ist besser als bisherige Ergebnisse * er stellt den Chef zufrieden * er ist besser als Defaultergebnisse * er ist nahe an der theoretischen Unterschranke Generalisierungsfehler, struktureller Fehler: Die Differenz zwischen Testfehler und Trainingsfehler. Der Generalisierungsfehler wird auch "Varianz" genannt. Bias-Varianz-Dilemma: Die Schwierigkeit, eine geeignete Architektur zu finden. Sie darf nicht zu klein sein (nicht maechtig genug fuer die Trainingsmenge) und nicht zu gross (nicht generalisierungsfaehig genug, Overfitting). Mathematischer Hintergrund: Der Erwartungswert der Abweichung eines berechneten Wertes fw vom wirklichen Funktionswert f ist E( (fw-f)^2 ) = Var( fw-f ) + E( fw-f )^2 // da Var(X) = E(X^2) - E(X)^2 = E( (fw-f-E(fw-f))^2 ) + E(fw-f)^2 // da Var(X) = E( (X-E(X))^2 ) = E( (fw-f-E(fw)+E(f))^2 ) + E(fw-f)^2 // da E(A+B) = E(A) + E(B) = E( (fw-f-E(fw)+f)^2 ) + E(fw-f)^2 // da E(f)=f = E( (fw-E(fw))^2 ) + E(fw-f)^2 = Var(fw) + E(fw-f)^2 Der Erwartungswert der Abweichung (d.h. des Fehlers) ist also die Summe aus der Streuung (Varianz) der berechneten Funktion und dem Erwartungswert der Differenz von berechnetem und tatsaechlichem Wert (Bias). Hier ist der Zusammenhang: * kleines Netz -- weniger Parameter -- niedrige VC-Dimension (s.u.) -- einfache Funktion -- Generalisierungsfaehigkeit -- kleinerer Fehler auf Testdaten -- kleinerer struktureller Fehler -- kleinere Varianz -- groesserer Fehler auf Trainingsdaten -- groesserer empirischer Fehler -- groesserer Bias -- raue Fehlerfunktion -- kann effizienter trainiert werden * grosses Netz -- mehr Parameter -- hoehere VC-Dimension (s.u.) -- komplizierte Funktion -- weniger Generalisierungsfaehigkeit, Overfitting -- groesserer Fehler auf Testdaten -- groesserer struktureller Fehler -- groessere Varianz -- kleinerer Fehler auf Trainingsdaten -- kleinerer empirischer Fehler -- kleinerer Bias -- glatte Fehlerfunktion Die Vorteile eines kleinen Netzes koennen auch z.B. durch Pruning erreicht werden. Generell haben schwache Lerner (Perzeptron) einen hohen empirischen Fehler und einen geringen strukturellen Fehler, gute Lerner (Tower, Upstart) umgekehrt. Obere Schranke fuer die Architektur: Ist die Trainingsmenge nicht widerspruechlich, so genuegen soviele Neuronen, wie die Trainingsmenge Beispiele hat, um alle Beispiele exakt abzubilden. Defaultergebnis: Ein Ergebnis, welches durch einen Trivial-Algorithmus erlangt wurde. Beispiel: Abbilden aller Eingaben auf sich selbst, pauschales Klassifizieren aller Eingaben als "positiv". Unterschranke des Testfehlers: Ein Wert, den der Testfehler niemals unterschreiten kann, da er durch das Rauschen in den Daten zustandekommt. Er ergibt sich aus dem Erwartungswert der quadratischen Abweichung eines verrauschten Funktionswertes f+eta vom berechneten Wert fw: E( (f+eta - fw)^2 ) = E( f+eta - fw )^2 + Var(f+eta - fw) // da Var(X) = E(X^2) - E(X)^2 = E( f+eta - fw )^2 + E(( f+eta-fw - E(f+eta-fw) )^2) // da Var(X) = E( (X-E(X))^2 ) = ( E(f+eta) - fw )^2 + E(( f+eta-fw - E(f+eta-fw) )^2) // da fw(x) konstant = ( E(f+eta) - fw )^2 + E(( f+eta - E(f+eta) )^2) // da fw(x) konstant = ( E(f+eta) - fw )^2 + Var(f+eta) // da Var(X) = E( (X-E(X))^2 ) Der erste Summand (der "systematische Fehler") ist der zu minimierende Anteil der Gesamtabweichung. Der zweite Summand (der "unsystematische Fehler") ist die Streuung der Daten und kann gar nicht beeinflusst werden. Damit ist dieser Summand eine Unterschranke fuer den Testfehler. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Alternativen zu einem FNN ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sequenz: Eine Folge von Vektoren derselben Dimension. Partiell rekurrentes Netz, partially recurrent neural net, pRNN: Ein Netz mit Zyklen. Partiell rekurrente Netze haben eine zeitliche Struktur. Daher benutzt man folgende Bezeichnungen: * x[i](t) ist die i-te Komponente des Eingabevektors x zum Zeitpunkt t. * net[i](t) ist die Aktivierung des Neurons i zum Zeitpunkt t. Man setzt net[i](t)=x[i](t) fuer Eingabeneuronen i. * o[i](t) ist die Ausgabe des Neurons i zum Zeitpunkt t. Man setzt o[i](t)=x[i](t) fuer Eingabeneuronen i. Zum Berechnen einer Ausgabesequenz aus einer Eingabesequenz initialisiert man zunaechst alle o[i](0) und net[i](0) fuer Nicht- Eingabeneuronen i zufaellig. Die Aktivierung und Ausgabe eines Nicht-Eingabeneurons i berechnet sich dann wie ueblich net[i](t+1) = SUM (j,i) aus "->" w[j,i]*o[j](t)-theta[i] o[i](t+1) = aktfkt[i](net[i](t+1)) Aktivierungen werden also fuer alle Neuronen pseudo-gleichzeitig berechnet ("Synchrone Dynamik"). Anwendungen partiell rekurrenter Netze: * Zeitreihenvorhersagen fuer Wetter, dynamische Systeme, Finanzdaten * Filtern von Rauschen, Tracking * Planung, Robotik, Sehen * Spracherkennung, -produktion und -verarbeitung * Verbindung zu symbolischen Formalismen Automat: Ein Formalismus, welcher eine Funktion berechnen kann. Automaten bilden die theoretische Grundlage der gesamten symbolischen Informatik. // Fuer einen detaillierten Ueberblick s. infod.txt Partiell rekurrente Netze und symbolische Formalismen: pRNNs koennen Automaten simulieren. Umgekehrt lassen sich aus einem pRNN in bestimmten Faellen Automaten rekonstruieren. Damit koennen pRNNs als Verbindung zwischen symbolischen und subsymbolischen Formalismen gesehen werden. pRNNs sind allerings maechtiger als Automaten, sie gehoeren der Menge der "nicht-uniformen boolschen Schaltkreise" an und sind damit "super-Turing universell". Approximationsvollstaendigkeit von pRNNs: Da pRNNs FNNs einschliessen, sind sie fuer stetige Funktionen auf kompakten Mengen approximationsvollstaendig. Backpropagation through time: Ein Algorithmus zum Trainieren partiell rekurrenter Netze. Ein pRNN kann hinsichtlich seiner zeitlichen Struktur entfaltet werden, sodass ein FNN entsteht, welches fuer jeden Zeitschritt t eine Folge von Schichten hat. Dabei muessen als Nebenbedingung solche Gewichte des FNNs, die dasselbe Gewicht des pRNNs repraesentieren, gleich sein (sog. "shared weights"). Das FNN kann aber dann mit Backpropagation mit leichten Abwandlungen trainiert werden. Ist W die Anzahl der Gewichte und T die Anzahl der Zeitschritte, so liegt Backpropagation through time in O(W*T). Real time recurrent learing: Ein Algorithmus zum Trainieren partiell rekurrenter Netze. Wie bei Backpropagation through time wird hier das pRNN entfaltet. Die Gradienten werden jedoch von vorne nach hinten berechnet. Das erhoeht zwar den Zeitaufwand auf O(W^2*T) und macht die Benutzung von Rprop unmoeglich, erlaubt aber das Lernen nach jedem Muster. Elman-Netz: Ein pRNN, in dem die Neuronen mit einer Speicherzelle ("Kontextzelle") verbunden sind. Diese speichert jeweils die letzte Ausgabe des Neurons und spielt sie im naechsten Zeittakt wieder ein. Problem der verschwindenden Gradienten: Die Schwierigkeit, ein pRNN so zu konfigurieren, dass es sowohl stabil gegen Rauschen ist als auch in der Lage, Langzeit-Beziehungen zwischen den Eingaben zu erkennen. Diese Ziele sind gegensaetzlich. Voll rekurrentes Netz, fully recurrent neural net, fRNN: Ein Netz, bei dem alle Neuronen mit allen Neuronen verbunden sind. Man benutzt dieselben Bezeichnungen, allerdings wird der Eingabevektor nur einmalig angelegt. stabiler Zustand: Ein Tupel von Aktivierungen fuer alle Neuronen eines fRNNs, sodass gilt: o[i](t) = o[i](t+1) = aktfkt[i](net[i](t+1)) fuer alle Neuronen i. Hopfieldnetz: Ein fRNN, bei dem die Gewichte symmetrisch sind und alle Neuronen zugleich Eingabeneuronen und Ausgabeneuronen sind. Die Aktivierungsfunktion ist die Perzeptronaktivierungsfunktion H. Ein Neuron ist mit sich selbst ueber das Gewicht w[i,i]=0 verbunden. Zur Berechnung eines Ausgabevektors zu einem Eingabevektor wird zunaechst o[i](0)=net[i](0)=x[i] gesetzt. Dann waehlt man zufaellig ein Neuron i0 aus und berechnet net[i0](t+1) = SUM (j,i0) aus "->" w[j,i0]*o[j](t)-theta[i0] o[i0](t+1) = H(net[i0](t+1)) So faehrt man fort, bis ein stabiler Zustand erreicht ist ("Asynchrone Dynamik"). Eine synchrone Dynamik kann zu Zweier-Zyklen ohne stabilen Zustand fuehren. Energiefunktion: Eine Funktion E:R^n->R, die zu den Ausgabewerten o[i] aller Neuronen i eines Hopfieldnetzes eine reelle Zahl liefert. Sie heisst "Energie" des Netzes. Es gilt: E(o[1],o[2],...,o[n]) = -0.5 * (SUM i=1..n SUM j=1..n w[i,j]*o[i]*o[j]) + SUM i=1..n theta[i]*o[i] Das Hopfieldnetz sucht Minima seiner Energiefunktion und nimmt dort einen stabilen Zustand ein. Konvergenz von Hopfieldnetzen: Jedes Hopfieldnetz erreicht auf jede Eingabe nach endlich vielen Schritten einen stabilen Zustand. Beweis: Die Energiefunktion ist nach unten beschraenkt (alle o[i]=0). Ausserdem ist die Energie des Netzes in einem nachfolgenden Schritt niemals groesser als in einem vorhergehenden. Damit pendelt sich das Netz in einem lokalen Minimum der Einergiefunktion ein. Plateaus der Energiefunktion koennen naemlich nur endlich sein. Dieser Zusammenhang gilt nicht fuer normale fRNNs oder synchrone Dynamiken. Orthogonale Daten: Vektoren, bei denen alle paarweisen Skalarprodukte 0 ergeben. Duenn gesaete Datenmenge, sparse data set: (?) Hebb-Training: Ein one-shot Algorithmus zum Trainieren eines Hopfieldnetzes. Dazu werden zunaechst die Schwellwerte eliminiert. Besteht die Datenmenge P aus x[p] aus {-1,1}^n, so setzt man w[i,j] = (SUM p=1..|P| x[p][i]*x[p][j])/n Damit wird bei einem Pattern w[i,j]=1 fuer gleiche x[i],x[j] und -1 fuer ungleiche Musterpunkte, was der Idee des Hebb-Lernens entspricht. Hebb-Training fuehrt zu richtigen Minima der Energiefunktion, falls die Daten orthogonal sind. Das Verfahren kann allerdings auch zu falschen Minima der Energiefunktion fuehren. Falsche Minima, spurious states: Minima der Energiefunktion eines Hopfieldnetzes (und damit stabile Zustaende), die nicht einem gelernten Vektor entsprechen. Falsche Minima koennen entweder gar nichts mit den gelernten Vektoren zu tun haben, sie koennen Mischungen aus gelernten Vektoren sein (Ueberlagerung) oder Invertierungen gelernter Vektoren. Grund fuer das letztere Phaenomen ist die Symmetrie der Energiefunktion bezueglich einer Invertierung der Eingabe. Fuer zufaellige Datenmengen ist die Anzahl der Minima in O(n/log(n)), fuer duenn gesaete Datenmengen in O(n*sqrt(n)/log(n)). Hopfield-Perzeptron-Training: Ein Algorithmus zum Trainieren eines Hopfieldnetzes, der ein Hopfieldnetz auf ein Perzeptron zurueckfuehrt. Diese Reduktion zeigt die prinzipielle Beschraenktheit der Maechtigkeit eines Hopfieldnetzes. Anwendungen von Hopfieldnetzen: Hopfieldnetze dienen als Assoziativspeicher. Sie sind fehlertolerant und fuellt sich "weich" ("smoothly"), d.h. es gibt keine feste Daten-Obergrenze. Da die vorgegebenen Vektoren und die angelegten Vektoren direkt in Aktivierungen des Netzes bestehen, kann man die Vektoren durch "Aufleuchten" der aktivierten Neuronen im Netz als graphische Muster direkt visualisieren. Da Hopfieldnetze Minima der Energiefunktion finden, koennen sie fuer beliebige quadratische Optimierungsprobleme Teilloesungen finden. Dazu addiert man zu der zu minimierenden Funktion "Strafsummanden", die die Verletzung einer Nebenbedingung bestrafen. Dann stellt man diese Funktion zu einer Energiefunktion um und konstruiert das entsprechende Hopfieldnetz. Auch das TSP laesst sich zu einer solchen quadratischen Funktion umschreiben. Polynome beliebigen Grades waeren mit verborgenen Neuronen moeglich, dann ist die VC-Dimension unendlich (s.u.). Support Vector Machine, SVM: Ein optimal generalisierendes Perzeptron mit nichtlinearer hochdimensionaler Vorverarbeitung. Das Training einer SVM ist sehr effizient und umfasst folgende Ideen: * Die Daten werden durch eine nicht-lineare Funktion phi vorverarbeitet, die den Datenraum in einen hoeherdimensionalen Datenraum abbildet. In hoeheren Dimensionen koennen die Daten dann leichter linear getrennt werden (Covers Theorem). Deshalb geht in folgende Rechnungen immer phi(x) anstelle von x ein. * Die so vorverarbeiteten Daten werden als Eingabe fuer ein Perzeptron mit Gewichtsvektor w verwendet. * Die Soll-Ergebnisse der Muster werden als -1 (negativ) und +1 (positiv) angegeben. Unter der Vorraussetzung, dass die Grebene wie in "Terminieren des Perzeptronalgorithmus" beschrieben verschoben ist, und unter Vernachlaessigung der Schwelle muss dann fuer alle Muster (x[i];y[i]) aus R^n x {-1,1} gelten: y[i]*w*phi(x[i])-1 >= 0 Denn fuer negative Muster gilt: w*phi(x[i]) =< -1 // * (-1) <=> (-1) * w*phi(x[i]) >= 1 <=> (-1) * w*phi(x[i]) - 1 >= 0 <=> y[i] * w*phi(x[i]) - 1 >= 0 // da y[i]=-1 Und fuer positive Muster gilt: w*phi(x[i]) >= 1 <=> w*phi(x[i]) - 1 >= 0 <=> y[i]*w*phi(x[i]) - 1 >= 0 // da y[i]=1 * Es wird derjenigen Gewichtsvektor w gesucht, bei dem der Abstand aller Punkte zu der durch w definierten Grebene maximal ist. Dazu wird w als Linearkombination der gegebenen Punkte x[i] ausgedrueckt: w = SUM i=1..n a[i]*y[i]*phi(x[i]) w setzt sich also aus den mit y[i]*a[i] gewichteten Musterpunkten zusammen. Die a[i] sind dabei positiv und geben die Wichtigkeit der x[i] an, naemlich ihre Naehe zu der Grebene. Mittels mathematischer Optimierungsmethoden sucht man nun die a[i], sodass |w| minimal wird. Dann naemlich hat die Grebene einen maximalen Abstand von allen Punkten und |w| ist der Abstand der Grebene zum naechsten Punkt. Fuer Support-Vektoren x[i] gilt y[i]*w*phi(x[i])=1. Diejenigen x[i] mit a[i]!=0 sind die Punkte, die am naechsten an der Trennungsgrebene liegen. Sie heissen "Support Vectors" (Stuetzvektoren). Alle uebrigen Punkte sind fuer das Problem irrelevant. Da die so gefundene (eindeutige) Grebene maximalen Abstand zu allen Punkten hat, ist sie optimal generalisierungsfaehig. Die Ausgabe der SVM zu einer Eingabe z berechnet sich wie folgt: svm(z) = H(w*phi(z)) = H( SUM i=1..n a[i]*y[i]*phi(x[i]) * phi(z) ) Da sowohl hier als auch bei der Optimierung oft das Skalarprodukt phi(x[i])*phi(z) berechnet werden muss, benutzt man Kernels. Kernel, Kern: Eine Hilfs-Funktion, die das Skalarprodukt zweier phi-vorverarbeiteter Daten approximiert. Sie wird haeufig in SVMs verwendet, da das wirkliche Skalarprodukt im Hoeherdimensionalen sehr aufwendig zu berechnen ist, waehrend des Trainings der SVM allerdings haeufig benoetigt wird. Schliesslich spielt die dahintersteckende Funktion phi ueberhaupt keine Rolle mehr. Auch ist die Zuordnung phi->kernel nicht umkehrbar. k(x,y) ~= phi(x)*phi(y) Werden polynomielle Kernels k(x,y)=(x*y+1)^p benutzt, so kann die SVM als FNN mit polynomieller Aktivierungsfunktion auffassen: Dazu werden die Gewichte zwischen Eingabeneuronen und Neuronen der verborgenen Schicht auf die x[i] gesetzt, sodass beim ersten verborgenen Neuron x[1]*eingabe ankommt, beim zweiten x[2]*eingabe etc. Die Schwelle der verborgenen Neuronen setzt man auf -1. Mit polynomieller Aktivierungsfunktion berechnen die verborgenen Neuronen dann (x[i]*eingabe+1)^p, was dann von einem Perzeptron aufsummiert werden kann. Allgemein lassen sich 3-schichtige FNNs als SVMs interpretieren. Soft-Margin: Eine obere Schranke fuer die a[i] einer SVM. Dadurch wird die SVM fehlertolerant, da ab einer bestimmten Iteration die falschen x[i] keine hoeheren a[i] mehr bekommen und der Algorithmus damit terminieren kann. WTA-Strategie: "Winner takes it all"-Strategie, eine Vorgehensweise, bei der aus einer Menge von Elementen allein dasjenige betrachtet wird, welches die Anforderungen am besten erfuellt. LVQ: Lernende Vektorquantisierung, ein Algorithmus zum Lernen einer klassifizierenden Funktion. Gelernt wird eine Funktion f:R^n -> {c[1], c[2], ... c[m] }, die Punkte des R^n zu m verschiedenen Klassen zuordnet. Die Vorraussetzung dazu ist, dass Punkte derselben Klasse "Wolken" bilden, d.h. voneinander einen geringen Abstand haben. Der Algorithmus sucht nun m Punkte, die die Wolken am besten repraesentieren: 1. Initialisiere m Punkte w[1],... w[m] zufaellig im R^n Die Menge dieser Punkte heisst "Codebook" 2. Nimm ein Muster (x;c[y]), wobei y aus {1, 2, ... m } ist 3. Suche den x naechstgelegenen Repraesentanten w[next] 4. Falls der naechstgelegene richtig war (next==y), ruecke w[next] noch naeher an x heran: w[next] := w[next] + eta*(x-w[next]) 5. Falls der naechstgelegene falsch war (next!=y), ruecke w[next] von x weg: w[next] := w[next] - eta*(x-w[next]) 6. Wenn noch Muster vorhanden sind, weiter bei 2 7. Laufe erneut durch alle Muster (--> 2) oder Abbruch Eta ist dabei eine Lernrate zwischen 0 und 1. Auf diese Weise ruecken die Repraesentanten w[1],...w[m] schrittweise in die Mitten ihrer zugehoerigen Wolken. Auch hier findet wieder Hebbsches Lernen statt. Der obige Algorithmus benutzt die WTA-Strategie. Soll nun ein unbekannter Punkt x klassifiziert werden, so sucht man den naechstliegenden Repraesentanten w[next] und klassifiziert x als c[next]. LVQ mit einer Klasse: Soll jeder Punkt auf dieselbe Klasse abgebildet werden und konvergiert der LVQ-Algorithmus, so ist der resultierende Repraesentant w[1] der Mittelpunkt der Datenwolke. Beweis: Sei q die Anzahl der Muster Sei w[1][k] der Repraesentant nach dem k-ten Training aller Muster w[1][k+1] = w[1][k] + eta * (SUM i=1..q x[i]-w[k]) // da immer obiger Schritt 4 eintritt w[1][k+1] - w[1][k] = eta * (SUM i=1..q x[i]-w[k]) 0 = eta * (SUM i=1..q x[i]-w[k]) // unter der Annahme, dass LVQ terminiert, // also irgendwann w[1][k+1]=w[1][k] gilt 0 = SUM i=1..q x[i]-w[k] 0 = (SUM i=1..q x[i]) - (SUM i=1..q w[k]) 0 = (SUM i=1..q x[i]) - q*w[k] q*w[k] = (SUM i=1..q x[i]) w[k] = (SUM i=1..q x[i]) / q LVQ mit zwei Klassen: LVQ kann in einen Zyklus geraten, wenn zwei Klassen wie folgt liegen: ++++++++++++++ ++++++++++++++ ------------- ------------- Dann naemlich ist die Gerade zwischen den Schwerpunkten nicht die optimale Loesung, sie wird von den falsch klassifizierten Punkten gedreht werden. Sobald aber alle Punkte korrekt abgebildet sind, ziehen die Schwerpunkte die Gerade wieder zurueck etc. LVQ mit Lernratenreduktion: Eine Modifikation des LVQ-Algorithmus, bei der die Lernrate eta nach und nach verringert wird, um Konvergenz zu erzwingen. LVQ mit Datentransformation: Eine Modifikation des LVQ-Algorithmus, bei der die Daten vor dem eigentlichen Algorithmus umgerechnet werden, sodass LVQ besser konvergiert. Moegliche Umrechnungsweisen sind * z-Transformation: x[i] := (x[i] - E(x)) / Var(x) Dadurch werden Abstand der Daten voneinander und Position "normiert" * log-Transformation: x[i] := log(x[i]) // bei n > 1 komponentenweise Dadurch koennen zunaechst undurchsichtige Konstellationen entzerrt werden Multimodalitaet: Die Tatsache, dass Punkte derselben Klasse 2 oder mehrere verschiedene Wolken bilden. DLVQ: Dynamisch Lernende Vektorquantisierung, eine Modifikation des LVQ-Algorithmus, die mehrere Repraesentanten pro Klasse erlaubt und damit Multimodalitaet abbilden kann. Zunaechst laeuft der LVQ-Algorithmus wie oben beschrieben. Dabei wird allerdings nicht nur der richtige Repraesentant angezogen, sondern gleichzeitig immer auch der naechstfalsche weggeschoben. Sobald der Algorithmus konvergiert, prueft man, ob die resultierenden w[i] alle x[i] gut genug approximieren. Ist das nicht der Fall, fuehrt man fuer die fehlerhafte Klasse einen neuen Repraesententen w[m+1] ein und trainiert erneut. RLVQ: Relevance Learning Vector Quantization, eine Modifikation des LVQ-Algorithmus, die die Wichtigkeit einzelner Dimensionen des Punkteraums einschaetzen kann. Dazu wird als Abstandsmessung eines Punktes x von einem Repraesentanten w die Formel d(x,w) = SUM i=1..n lambda[i]*(x[i]-w[i])^2 verwendet, also der gewichtete quadrierte Abstand. Jede Dimension i wird dabei einzeln mit ihrem eigenen lambda[i] gewichtet. Die lambda[i]'s werden je nach ihrer Nuetzlichkeit gleich gelassen oder verringert: Gehoert der einem ausgewaehlten x naechstgelegene Repraesentant der richtigen Klasse an, so wird lambda erniedrigt, sonst erhoeht (?). Erreicht ein lambda[i] 0, so ist die i-te Dimension fuer die Klassifizierung der Daten irrelevant. RLVQ kann als Gradientenabstieg interpretiert werden. Gaussfunktion: Die Funktion gauss:R->R mit gauss(x)=e^-(|x|^2/sigma^2). Diese Funktion hat ihr Maximum 1 bei x=0 und geht fuer groessere und kleinere x gegen 0. Je groesser die Konstante sigma ist, desto flacher ist die Kurve. Je kleiner sigma ist, desto mehr weist die Kurve einen Zacken bei x=0 auf und ist sonst fast 0. Radiale-Basis-Funktionen-Netz, RBF-Netz: Ein Netz bestehend aus * einer Eingabeschicht von n Neuronen Dabei ist eine Trainingsmenge P={(x[1],y[1]), (x[2],y[2]), ...} mit Eingabevektoren x[i] aus R^n und Sollergebnissen y[i] aus R vorrausgesetzt. * einer verborgenen Schicht aus m<|P| Neuronen Diese Schicht ist mit der Eingabeschicht mit den Gewichten 1 voll vernetzt. Die Neuronen i=1..m haben die Aktivierungsfunktionen phi[i](z) = gauss( |z-m[i]| ) = e^-(|z-m[i]|^2/sigma[i]^2). m[i] ist dabei gleich einem x[j] der Trainingsmenge und heisst "Zentrum" von Neuron i, sigma[i] ist die "Ausdehnung" des Neurons i. * einer Ausgabeschicht aus 1 Neuron, welches mit der verborgenen Schicht durch die Gewichte w[i]~=y[i] verbunden ist und die Aktivierungsfunktion der Identitaet Wird eine Eingabe x angelegt, so wird durch die Gaussfunktion vorrangig dasjenige "Gewinnerneuron" der verborgenen Schicht aktiviert, dessen Zentrum m[i] der Eingabe x am naechsten ist. Alle anderen verborgenen Neuronen haben je nach der Differenz ihres Zentrums von x eine Aktivierung nahe 0. Das Ausgabeneuron bildet nun den mit den Aktivierungen gewichteten Mittelwert aller y[i], der sich am ehesten nach dem "Gewinnerneuron" richtet. Mit einem RBF-Netz lassen sich beliebige stetige Funktionen beliebig genau approximieren. Die berechnete Funktion sei rbf(x). Ein RBF-Netz laesst sich als SVM mit Gaussfunktion als Vorverarbeitung interpretieren. RBF-Algorithmus: Der folgende Algorithmus zum Trainieren eines RBF-Netzes: 1. Waehle die Anzahl der verborgenen Neuronen und ihre Zentren und Ausdehnungen Dazu gibt es 3 Alternativen: * Zufaellige Wahl: Die m[i] sind irgendeine Untermenge der Mustervektoren x[i] * Destruktives Verfahren: Beginne mit |P| verborgenen Neuronen, entferne Neuronen, bis Fehler zu gross * Cluster-Verfahren: Bestimme Zentren und Ausdehnung von Anhaeufungen von Datenpunkten x[i], bestimme daraus m[i] und sigma[i]. Dieses kann z.B. mit einer SOM (s.u.) geschehen oder ueber den "k-means"-Algorithmus. 2. Passe die Parameter w[i] an Dieses kann durch Loesen von linearen Gleichungssystemen so geschehen, dass rbf(x[i])=y[i] fuer alle x[i], die Zentren sind. Anmerkung: Die partiellen Ableitungen lassen sich berechnen, man koennte also auch mit einem Gradientenabstiegsverfahren lernen. Dagegen sprechen jedoch die Probleme dieses Verfahrens und die Tatsache, dass Lokalitaetseigenschaften verloren gingen. SOM, Self-Organizing Map, Kohonenkarte: Ein Neuronenverbund zum Clustern von Datenmengen, bestehend aus: * einer Eingabeschicht aus n Neuronen * einer Ausgabeschicht aus m Neuronen Jedes dieser Neuronen i ist mit jedem Eingabeneuron j ueber ein Gewicht w[i][j] verbunden. Die Gewichte und Neuronen haben jedoch nicht die bei Netzen uebliche Funktion! Die Ausgabeneuronen sind auf einem Gitter angeordnet, sodass jedes Ausgabeneuron Nachbarneuronen hat. Wird ein Eingabevektor angelegt, so feuert als einziges dasjenige Ausgabeneuron i, dessen Gewichtsvektor w[i] die kleinste Differenz zur Eingabe aufweist (WTA-Strategie). Eine Kohonenkarte kann also n-dimensionale Eingabevektoren zu m Gruppen clustern, wobei der Aehnlichkeit von Gruppen durch die Nachbarschaftsbeziehung Rechnung getragen wird. Eine Kohonenkarte kann also als Datenkompression gesehen werden, bei der Daten zu Prototypen w[i] komprimiert werden. Die biologische Motivation fuer dieses Verfahren ergibt sich nach Kohonen aus der Tatsache, dass aehnliche Reize benachbarte Hirnregionen aktivieren. Die SOM implementiert charakteristische biologische Verhaltensmuster wie Wettbewerb, Kooperation und Selbst- Amplifizierung. Kontext-Karte: Eine SOM, die auf Entitaeten und Attributen trainiert wurde. Hat man n Entitaeten und m Attribute, die fuer alle Entitaeten definiert sind, so spannt man den Eingaberaum auf als {0,1}^(n*m), in dem jeder Punkt (e[1], e[2], ... e[n], a[1], a[2], ... a[m]) fuer eine Konstellation von Entitaeten e[i] und Attributen a[i] steht. In den Trainingsmustern ist je ein e[i]=1 und die anderen 0. Die a[j] sind dann 1 fuer "Dieses Attribut j trifft auf die Entitaet i zu" und sonst 0. Trainiert man die SOM auf diesen Vektoren und fragt nachher (e[1],...e[n], 0, 0,...0) ab, wobei je ein e[i] der Reihe nach auf 1 gesetzt wird, so geben die Gewinnerneuronen die Position der Entitaet im Ausgabegitter an. In diesem Gitter sind die Entitaeten nach ihrer Aehnlichkeit angeordnet. Distanzfunktion: Eine Funktion d:N x N -> R, die den Abstand zweier Ausgabeneuronen i und j voneinander bestimmt. Zur Berechnung kann die Position von i und j im Ausgabegitter zueinander benutzt werden. Nachbarschaftsfunktion: Eine Funktion h:N x N -> [0;1], die den Grad der Nachbarschaft zweier Ausgabeneuronen angibt. h(i,j) ist 1 fuer i=j und geht gegen 0 fuer weit voneinander entfernte i und j. Meist setzt man: h(i,j)=gauss(d(i,j)). Kohonenkarten-Algorithmus: Der folgende Algorithmus zum Trainieren einer Kohonenkarte: 1. Waehle eine Lernrate eta 2. Initialisiere alle w[i][j] zufaellig 3. Nimm einen Eingabevektor x aus der Datenmenge 4. Bestimme das "Gewinnerneuron" i mit minimaler Differenz |w[i] - x| 5. Addiere fuer alle Ausgabeneuronen j zu ihrem w[j] das Produkt eta*h(i,j)*(x-w[j]) 6. Falls noch nicht alle Eingabevektoren dran waren, weiter bei 3 Dieses Vorgehen wiederholt man, bis jedes Ausgabeneuron eine Gruppe von Daten gefunden hat, die es repraesentiert. In Schritt 5 wird jeder Gewichtsvektor w[j] in Richtung des Eingabevektors veschoben, und zwar gewichtet mit der Lernrate eta und dem Grad der Nachbarschaft von Neuron j zum Gewinnerneuron i. Dieser Algorithmus unterteilt die Daten also unueberwacht in Cluster. Als Verfeinerung kann die Lernrate mit der Anzahl der Epochen verringert werden. Auch die Nachbarschaftsfunktion kann mit der Zeit strenger werden (Erhoehung von sigma). Die Ergebnisse der Kohonenkarte koennen mit LVQ nachbearbeitet werden. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Lernbarkeit ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Lernalgorithmus: Ein Algorithmus, der zu einer Trainingsmenge eine Funktion liefert. Damit kann ein Lernalgorithmus als eine Funktion aufgefasst werden: h( { (x[1];y[1]), ... (x[n];y[n]) } ) = fw h(x,f) = fw Lernende Funktionenklasse: Eine Funktionenklasse, in der man schrittweise eine Funktion finden kann, die eine Trainingsmenge richtig abbildet. Bedingungen an die lernende Funktionenklasse sind: * Parametrisierbarkeit (d.h. durch Veraendern bestimmter Werte erhaelt man eine neue Funktion der Klasse) * Approximationsvollstaendigkeit * Effiziente Trainierbarkeit (z.B. mit Gradientenabstieg) * Generalisierungsfaehigkeit * Aufteilbarkeit in Modelle mit wachsender Komplexitaet (d.h. man kann zunaechst mit einfachen Funktionen beginnen und bei zu grossem Trainingsfehler die Komplexitaet erhoehen) PAC: probably approximately correct, die Eigenschaft eines Lernalgorithmus h, fuer grosse Mustermengen die zu approximierende Funktion mit beliebig grosser Wahrscheinlichkeit beliebig gut zu approximieren. In Formeln: Gegeben eine zu lernende Funktion f, eine Fehler-Wahrscheinlichkeit p und einen Fehler von epsilon, so gibt es eine Mindest-Musteranzahl m, ab der gilt: P({z : E(|f(z)-h(x,f)(z)|) > epsilon}) < p Das bedeutet: Die Wahrscheinlichkeit, dass der Erwartungswert des Fehlers epsilon ueberschreitet, ist kleiner als p. Ist h PAC, so generalisiert h jede beliebige Funktion ab einer Mindest-Musteranzahl m, die man im Vorhinein berechnen kann. Fuer eine Funktionenklasse F, einen Fehler epsilon und eine Vertrauensschranke delta muss gelten: |F|^2*(1-eps)^m =< delta Ist eine Funktionenklasse PAC-lernbar, so gibt es mindestens einen guten Algorithmus, der sie lernen kann. PAC und korrekte Beispiele: PAC hat nichts damit zu tun, ob die gelernte Funktion fw die Trainingsdaten richtig macht. Beispiel:Sei f(x)=((x E {1,2,3})?1:0). Diese Funktion liefert also nur fuer 1,2 und 3 als Ergebnis 1, sonst 0. Nun lernt ein Algorithmus daraus die konstante Funktion fw(x)=0. Dann macht fw Beispieldaten falsch (naemlich f(1), f(2), f(3)). Der Algorithmus ist aber trotzdem PAC, weil die Fehlerwahrscheinlichkeit beliebig klein werden kann: Die Wahrscheinlichkeit, bei den unendlich vielen reellen Zahlen, die fw richtig macht, die falschen zu treffen, ist naemlich sowieso 0. Beispiel:Gegeben sei eine Funktion f ungleich 0. Nun lernt ein Algorithmus aus Beispieldaten {(x[1],f(x[1])),... ,(x[n],f(x[n]))} eine Funktion fw, die genau fuer die Beispieldaten die richtigen Ergebnisse liefert und sonst 0 ist: fw(x)=(x==x[i]?y[i]:0). fw macht also alle Beispieldaten richtig. Nichtsdestotrotz ist der Algorithmus nicht PAC: Die Fehlerwahrscheinlichkeit von fw gegenueber f laesst sich nicht beliebig klein kriegen, da die Wahrscheinlichkeit, dass fw(x)==0 gleich 1 ist. Arcustangens: Eine Funktion arctan:R->[-pi/2,pi/2], die einer Kathetenlaenge im rechtwinkligen Dreieck die Groesse des gegenueberliegenden Winkels zuordnet, wenn die Ankathete die Laenge 1 hat. cos-Netz: Ein FNN aus 1 Eingabe, 2 verborgenen Neuronen und 1 Ausgabe. Dabei hat das Ausgabeneuron die Perzeptronaktivierungsfunktion H, die beiden verborgenen Neuronen haben jedoch a(x)=arctan(x)/pi+cos(x)/10/(1+x^2)+1/2 als Aktivierungsfunktion. Die Eingabe ist mit dem Gewicht t mit dem einen verborgenen Neuron verbunden und mit dem Gewicht -t mit dem anderen verborgenen Neuron. Das Ausgabeneuron hat die Schwelle 1. Dann berechnet das Netz H(a(t*x)+a(-t*x)-1) ...wenige Umformungen spaeter... = H(cos(t*x)) Ueberdeckungszahl: Die Maechtigkeit derjenigen minimalen Teilmenge einer Funktionenklasse, die genuegt, um alle Funktionen dieser Klasse bis auf einen vorgegebenen Fehler zu approximieren. Ist also eine Menge von Funktionen F gegeben und ein maximaler Fehler eps, so sucht man ein paar Funktionen f[i] aus F, sodass man fuer jede andere Funktion f aus F ein f[i] hat, mit dem die Fehlerwahrscheinlichkeit E(|f(x)-f[i](x)|){0,1} eine Funktion f aus F gibt, die alle x[i] genau wie d abbildet. Es gibt 2^m solcher Funktionen d, fuer die es je eine Funktion in F geben muss: d[1]: x[1]->0,x[2]->0, ...x[m]->0 d[2]: x[1]->1,x[2]->0, ...x[m]->0 ... d[2^m]: x[1]->1,x[2]->1, ...x[m]->1 VC, VC-Dimension: Eine Funktion, die einer Funktionenklasse die maximale Anzahl zersplitterbarer Punkte zuordnet. Um die VC-Dimension einer Funktionenklasse zu bestimmen, sucht man Punkte x[1],...x[m] so, dass alle moeglichen Abbildungen dieser Punkte auf Nullen und Einsen ein Pendant in F haben. Die maximale Anzahl m von Punkten, fuer die dieses gelingt, ist die VC-Dimension der Funktionenklasse. Die VC-Dimension bestimmt die "Maechtigkeit" der Funktionenklasse. Die VC-Dimension ist proportional zum Logarithmus der Ueberdeckungszahl N(epsilon,F). Beispiele: * F = alle Funktionen => VC(F) = INF Besteht die Funktionenklasse aus allen denkbaren Funktionen, so koennen beliebig viele Punkte zersplittert werden -- denn die binaeren Funktionen d[i] stehen ja selbst allesamt zur Verfuegung. * F endlich => VC(F) =< log2(|F|) Sucht man m zu zersplitternde Punkte, so gibt es 2^m viele verschiedene binaere Funktionen d[i] auf ihnen. Also muss F mindestens ebensoviele Funktionen enthalten, um alle d[i] nachahmen zu koennen: 2^m =< |F| <=> m =< log2(|F|) <=> VC(F) =< log2(|F|) * F = { f | f(x)=H(p(x)) mit Polynomen p(x) vom Grad n } => VC(F)=n+1 Ist F die Klasse aller Polynome vom Grad n, in die Perzeptronaktivierungsfunktion gesteckt, so spiegelt f(x) das Vorzeichen der zugrundeliegenden Polynomfunktion p(x) wieder: Ist p(x)>=0, so ist f(x)=H(p(x))=1. Ist p(x)<0, so ist f(x)=0. Sollen Punkte x[i] auf 1 bzw. 0 abgebildet werden, so muss die Polynomfunktion also an diesen Stellen positiv bzw. negativ sein. Insbesondere muss zwischen 2 benachbarten x[i] mit verschiedenem Ergebnis eine Nullstelle p(x)=0 liegen. Ein Polynom vom Grad n hat hoechstens n Nullstellen, daher lassen sich (wegen des "worst-case" der abwechselnd auf 1 und 0 abgebildeten Punkte) maximal n+1 Punkte zersplittern. * F = Menge aller Perzeptronen mit Eingabedimension n => VC(F)=n+1 Ein Perzeptron der Eingabedimension 1 kann maximal 2 Punkte zersplittern. Sollen naemlich 3 Punkte zersplittert werden, so kann die Abbildung x[1]->1,x[2]->0,x[3]->1 nicht nachgeahmt werden, da das Perzeptron im Eindimensionalen lediglich die Eingabe mit der Schwelle vergleicht und so die drei Punkte nicht auseinanderhalten koennte. Ein Perzeptron der Eingabedimension 2 kann maximal 3 Punkte zersplittern, da ab 4 Punkten XOR nicht mehr abgebildet werden kann. Aehnliche Faelle treten stets auch im n-Dimensionalen auf. * F = Funktionsklasse aller Perzeptronnetze mit w Gewichten => VC(F) in O(w*log(w)) Aus der Tatsache, dass ein einzelnes Perzeptron die VC-Dimension n+1 hat, laesst sich die VC-Dimension fuer Perzeptronnetze herleiten. * F = Funktionsklasse aller sigmoiden Netze mit w Gewichten und N Neuronen => VC(F) in O(w^2*N^2) * F = Funktionenklasse aller SVMs => VC(F) =< R^2/y^2 Die VC-Dimension einer SVM ermittelt sich aus dem Perzeptron, welches die phi-vorverarbeiteten Daten linear trennt. Die VC-Dimension muesste also gleich der Eingabedimension des Perzeptrons zuzueglich 1 sein, allerdings ist die Dimension der vorverarbeiteten Daten sehr hoch, was zu einem sehr hohen (dh. unguenstigen, s.u.) VC(F) fuehren wuerde. Sind allerdings die Daten vom Betrag her alle kleiner als eine reellen Schranke R und ist y der Abstand der Trenngrebene zu den Daten, so laesst sich VC(F) auf R^2/y^2 beschraenken. (Dies gilt auch fuer die oben behandelten einfachen Perzeptrons.) Indem die SVM den Abstand der Trenngrebene zu den Daten maxmiert, minimiert sie ihre VC-Dimension und wird generalisierungsfaehiger. * F = { f:[0,1]->{0,1} | f ist beliebig } Diese Funktionenklasse ist unendlich maechtig, ihre VC-Dimension ist INF. * F = { f:[0,1]->{0,1} | f(x)=H(cos(t*x)), t=pi*2^n fuer n aus N } Dieses sind die periodisch zwischen 1 und 0 oszillierenden Funktionen. Erhoeht man n, so oszilliert f doppelt so schnell. Da fuer gegebene Punkte stets eine Funktion gefunden werden kann, die sie alle wie gewuenscht abbildet, ist die VC-Dimension unendlich. * F = { f | f wird von irgendeinem cos-Netz berechnet } Damit ist F genau die obige Funktionenklasse und hat somit unendliche VC-Dimension. * F = { f | f ist stueckweise konstant } Diese Funktionen sind unendlich maechtig, ihre VC-Dimension ist INF. * F = { f | f kann von einem 5-Perzeptronennetz berechnet werden } Die VC-Dimension eines Perzeptronennetzes ist durch O(|w|*log(|w|)) beschraenkt. * F = { f:[0,1]->{0,1} | f ist stetig } Es gibt nur 2 stetige Funktionen, die in die Menge {0,1} abbilden, naemlich f1:x->1 und f2:x->0. Somit ist |F|=2 und die VC-Dimension 1. * F = Funktionenklasse aller pRNNs RNNs sind aber im Allgemeinen nicht verteilungsunabhaengig PAC oder verteilungsunabhaengig UCED. Sie sind zwar PAC und UCED, allerdings mit schlechten Grenzen. Die VC-Dimension haengt von der Anzahl der Gewichte und der Eingabelaenge ab. VC und PAC: Eine Funktionenklasse F ist verteilungsunabhaengig PAC-lernbar und damit verteilungsunabhaengig UCED, genau dann, wenn VC(F) nicht unendlich ist. Da log(N(epsilon,F)) proportional zu VC(F) ist, ist die Anzahl der Beispiele, die Generalisierungsfaehigkeit garantieren, ebenso proportional zu VC(F). Je einfacher die Funktionenklasse ist, desto geringer ist VC(F) und desto weniger Beispiele werden benoetigt.