Zusammenfassung Neuroinformatik (c) 2001-01-01 Fabian M. Suchanek http://suchanek.name/texts/summaries/neuroinf.txt Dieses ist eine Zusammenfassung des Kurses "Einfuehrung in die Neuroinformatik", der im WS 2000 von Dr. Martin Riedmiller an der Universitaet Osnabrueck gehalten wurde. 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. Anwendungen der Neuroinformatik: Prognose, Musik, Robotik (Regelungstechnik) Gehirn: 1E11 Neuronen, Parallelverarbeitung Schaltzeit 1ms, Mustererkennung 1ms Kuenstliches neuronales Netz: Eingabeneuronen -> verborgene Schichten aus Neuronen -> Ausgabeneuronen Verbindungen zwischen den einzelnen Neuronen sind gewichtet Eingabe ist ein Vektor _x, Ausgabe ist ein Vektor _y Ueberwachtes Lernen: Dem Netz werden Trainingspaare/Mustermengen aus Eingabevektoren und erwuenschten Ausgabevektoren vorgesetzt. Eine unbekannte Eingabe _x soll auch ein vernuenftiges Ergebnis erzielen. Klassifikation: Eingabedaten sollen in 2 (oder mehr) Klassen unterschieden werden (FMS: Ausgabetyp ist boolean). Regression: Approximation einer Funktion. Eingabedaten sollen Funktionswert liefern. Das MacCulloch-Pitts-Neuron (MCP-Neuron): * hemmende (inhibitorische) Eingaenge * erregend (exzilatorische) Eingaenge * Schwellwert theta Eingangsaktivierungen sind 0 oder 1 Ausgangsaktivierungen sind 0 oder 1 Das MCP-Neuron ist aktiv, wenn * kein hemmender Eingang aktiv ist * die Summe der erregenden Eingaenge > theta ist Mit dem MCP-Neuron lassen sich &,| und ~ realisieren: &(x1,x2) x1,x2 --theta=2--> |(x1,x2) x1,x2 --theta=1--> ~x1 x1 *-------------> (hemmender Eingang) Da alle f:{0,1}^n->{0,1} aus &,| und ~ zusammensetzt sind, kann jede beliebige Boolsche Funktion mit einem Netz aus MCP-Neuronen umgesetzt werden. Allgemeines Neuronenmodell (Perzeptron): Eingaenge x(i), Gewichte w(i), Ausgang o 3 Verarbeitungsschritte: 1. Sammeln der Eingangsaktivierungen net=f(_x,_w), z.B. net=SUM(x(i)*w(i)) 2. Berechnung der Aktivierung a Schwellwertfunktion Gtheta liefert Aktivierung 1 oder 0 in Abhaengigkeit von net und Schwellwert theta. Alternativ: Standardfunkion G0, Gtheta(net)=G0(net-theta) 3. Ausgabe o=h(a), oft wird einfach o=a gesetzt Elimination der Schwelle: Setzt man ein zusaetzliches Gewicht w(0)=-theta mit x(0)=1 ein, so wird die Schwelle automatisch beachtet, G0 reicht. Lineare Trennbarkeit: Eine Mustermenge M={(_x(1),y(1)),...(_x(p),y(p))}, y(i) E {1,2}, _x(i) E R^n heisst linear trennbar genau dann, wenn es w(0)..w(p) gibt fuer alle _x(1..p), sodass w(0)+w(1)*x(1,i)+...w(n)*x(n,k)>=0 <=> y(k)=1. FMS: Eine Mustermenge aus k Trainingsdaten der Form (Eingangsvektor, Ergebnis) heisst linear trennbar, wenn ein einzelnes Neuron jedem Eingangsvektor das gewuenschte Ergebnis (1 oder 2) zuordnen kann, d.h. wenn es Gewichte gibt, bei denen fuer jeden Eingangsvektor die Summe der w(i)*x(i) nur dann positiv ist, wenn das gewuenschte Ergebnis 1 ist. Das Perzeptron kann genau die linear trennbaren Mengen berechnen. Lineare Trennbarkeit im 2-Dimensionalen: Eine 2D-Eingangsvektormenge kann man sich als Punkte im 2D- Koordinatensystem veranschaulichen. Diese Punkte sollen in 2 Klassen geteilt werden (Ergebnistyp 1 oder 2), veranschaulicht z.B. durch 2 Farben rot und gruen. Ist die Menge linear trennbar, so laesst sich eine Gerade zwischen die roten und gruenen Punkte legen. Formal: w(0)+w(1)*x(1)+w(2)*x(2)>=0 <=> y=1 Grenzfall: w(0)+w(1)*x(1)+w(2)*x(2)=0 <=> x(2)=-w(0)/w(2)-w(1)/w(2)*x(1) Das entspricht einer Geradengleichung y=m*x+b, festgelegt durch die Gewichte w(0), w(1) und w(2). Die XOR-Funktion ist nicht linear trennbar. Lineare Trennbarkeit im n-Dimensionalen: Im n-Dimensionalen definieren w(0)..w(n) eine Hyperebene, die den Eingaberaum in 2 Haelften trennt. Der Lernalgorithmus des Perzeptrons: (Rosenblatt 1959) 1. _w=_0; error=false; 2. FOR(k=1;k<=p;k++) { a) //Berechne Ausgabe von Muster k o=G(SUM(w(i)*x(i,k)) b) //Korrigiere Gewichtsvektor IF(o==1 && y(k)==0) { error=true; _w=_w-_x; } IF(o==0 && y(k)==1) error=true; _w=_w+_x; } // IF(o==y(k)) OK; 3. IF(error) GOTO 2; Sind die Trainingsmuster linear trennbar, konvergiert der Perzeptron- Algorithmus. Buchstabenerkennung nach Rosenblatt: Am Eingaberaster werden zufaellig ausgewaehlte Punkte an "Praedikate" (umgekehrte Verteiler) angeschlossen (symbolisiert die nach Rosenblatt zufaellige Vernetzung von Augenzaepfchen und Neuronen). Diese Verteiler bilden die Eingaenge zu einem Perzeptron, das dann das Ergebnis liefert. Einfaches lineares Element (Adaline, Adaptive Linear Combiner, ADC): Fuehrt lineare Regression durch, findet also zu Eingabedaten eine Ausgleichsgerade. Gesucht sind die Gewichte w(0)..w(n), sodass o(k)=SUM(w(i)*x(i,k))=y(k). Lernalgorithmus, mathematischer Ansatz: Der Fehler ist SUM(o(k)-y(k)) Mathematischer Ansatz: Minimiere SUM( (o(k)-y(k))^2 ) (Kleinster-Quadrate-Ansatz, Least-Squares-Ansatz) Delta-Regel (Widrow-Hoff-Regel): Sei o(k)=SUM(w(i)*x(i,k)) Dann ist der Fehler e(k)=o(k)-y(k) Regel: w(i)=w(i)+my*(y(k)-o(k))*x(i) NeuesGewicht=AltesGewicht+Lernrate*Fehler*Eingabe Gradientenabstiegsverfahren: Im Eindimensionalen: Hat man nur einen Eingabewert, so sei e=f(w). Gesucht ist dasjenige w*, fuer das e=f(w) minimal ist. Ansatz: Waehle wt beliebig, Betrachte f'(wt)=df(wt)/dw Falls f'(wt)<0, erhoehe wt Falls f'(wt)>0, erniedrige wt Problem: Man wird in lokalen Minima gefangen Ansatz: wt=wt-my*f'(wt) mit Lernrate my>0 Im n-Dimensionalen: Man hat einen Eingabevektor, e=f(_w) Man bildet die partiellen Ableitungen von f nach jeder Komponente w(1)..w(n): df(_w)/dw(1). Der Vektor Df(_w)=(df(_w)/dw(1),...) der partiellen Ableitungen heisst Gradient. Ansatz: _wt=_wt-my*Df(_wt) Die Lernrate my muss kleiner werden. Kettenregel: g:x->g(x)=u, f:x->f(x)=y f o g:x->(f o g)(x)=f(g(x))=y (f o g)'(x)=f'(g(x))*g'(x) dy/dx = dy/du *du/dx Die Delta-Regel als Gradientenabstiegsverfahren: Minimiere e(w)=0.5*(o-y)^2 _w=_w-my*De(_w) w(i)=w(i)-my* de(w)/dw(i) w(i)=w(i)-my* de(w) /do * do/dw(i) w(i)=w(i)-my* d0.5*(o-y)^2/do * SUM(w(j)*x(j))/dw(i) w(i)=w(i)-my* (o-y) * x(i) w(i)=w(i)+my*(y-o)*x(i) //Delta-Regel Mehrschichtige neuronale Netze (Multilayer-Perzeptron, MLP): Grundidee: Hintereinanderschaltung von Neuronen in Schichten Aufbau: Eingabeschicht: Hier liegt der Eingabevektor _x an Verborgene Schichten (Hidden layers): Hintereinanderliegend Ausgabeschicht: Hier liegt der Ergebnisvektor _o an Die Eingaben werden Von Schicht zu Schicht vorwaertspropagiert Anzahl der verborgenen Schichten und Neuronen beliebig Alle Verbindungen sind von EIngabe zu Ausgabe gerichtet, keine Zyklen Ausgeduennte Netze oder Shortcuts sind moeglich Ueberwachtes Lernen Repraesentationsfaehigkeit des MLP: Mit einem MLP mit einer verborgenen Schicht lassen sich stetige Funktionen beliebig genau approximieren, sogar endlich viele Unstetigkeitsstellen sind erlaubt. Aufbau eines MLPs: o(i) ist Ausgabeneuron i (Aktivierung) net(i) ist Netzeingang von Neuron i w(i,j) ist Gewicht von Neuron j zu Neuron i V(i) ist Vorgaengerneuron von i N(i) ist Nachfolgeneuron von i o(i)=f(SUM(w(i,j)*o(j)) fuer alle Vorgaengerneuronen j Aktivierungsfunktion: Funktion, die aus net(i) o(i) berechnet. Muss differenzierbar sein, daher Approximation der Stufenfunktion durch "logistische" Aktivierungsfunktion: fl(x)=(1+e^(-ax))^-1 Eigenschaften: lim x->-oo fl(x)=0, lim x->oo fl(x)=1 Einfluss von a: a gross => steiler, eher Stufenfunktion Ableitung: fl'(x)=fl(x)*(1-fl(x)) Einfluss eines Gewichtes w(i,j) auf o(i): Bestimmung der partiellen Ableitung do(i)/dw(i,j) do(i)/dw(i,j)=do(i)/dnet(i) * dnet(i)/dw(i,j) =fl'(net(i)) * d(SUM w(i,j)*o(j))/dw(i,j) =fl'(net(i)) * o(j) =fl(net(i))*(1-fl(net(i)))*o(j) =o(i)*(1-o(i))*o(j) Backpropagation: Lernverfahren fuer MLPs. Gegeben: Mustermenge M, MLP mit n Eingaengen und m Ausgaengen, beliebige Struktur Gesucht: _w, sodass 0.5*SUM( SUM( (o(l,k)-y(l,k))^2 ) ) minimal fuer alle Muster k-^ ^- fuer alle Ausgaenge l Betrachtung eindimensionaler Zielwerte, also E(w)=0.5*SUM( (o(k)-y(k))^2 ) ueber alle Mustermengen k Zentrale Idee: Gradientenabstiegsverfahren w(i,j)=w(i,j)-my*dE(_w)/dw(i,j) Wie beeinflusst w(i,j) e? de/dw(i,j)=de/do(i)*do(i)/dw(i,j) 1. Fall: i ist Ausgabeneuron de/do(i)=d0.5*(o-y)^2/do(i)=o-y 2. Fall: i ist kein Ausgabeneuron de/do(i)=SUM(de/do(k)*do(k)/do(i)) fuer alle k E N(i) do(k)/do(i)=do(k)/dnet(k)*dnet(k)/do(i) =fl'(net(k))*dSUM(w(k,j)*o(j))/do(i) =o(k)*(1-o(k))*w(k,i) de/do(i)=SUM(de/do(k)*o(k)*(1-o(k)*w(k,i)) ueber alle Nachfolger k von i Idee des Backpropagationalgorithmus: Fuer Ausgabeschicht ist de/do(i) direkt berechenbar Sodann immer davor liegende verborgene Schicht berechnen Lernen mit Backpropagation: Fuer alle Muster k=1..p ( Propagiere _x(k) vorwaerts Berechne de(l)/dw(i,j) durch Backpropagation Erhoehe den Fehler(i,j) um de(l)/dw(i,j) ) Fuer alle Gewichte: w(i,j)=w(i,j)-my*Fehler(i,j) Epochenlernen: Einen Durchgang durch alle Muster bezeichnet man als Epoche. Obigen Algorithmus nennt man daher auch Epochenlernen, Batchlernen oder Offline-Lernen. Musterlernen: Genausogut kann man die Gewichte _w nach jeder Berechnung von de(l)/dw(i,j) anpassen. Diese Vorgehensweise wird als Musterlernen, Learning by pattern, Online-Lernen oder stochastischer Gradienten- abstieg bezeichnet. Bei groesseren Mustermengen wird schneller gelernt. Problem der lokalen Minima: Gradientenabstiegsverfahren liefern lokale Minima. Abhilfe: *In der Praxis sind lokale Minima aehnlich gut *Initialisierung mit mehreren Zufallsbelegungen _w Problem der flachen Plateaus: Hat die Fehlerfunktion die Form eines flachen Plateaus, so kommt das GAV kaum voran, da die Ableitung nahe 0 ist. Abhilfe: Hoehere Lernrate Problem der steilen Schluchten: enthaelt die Fehlerfunktion steile Schluchten, so wird man aus ihr herauskatapultiert (Ableitung zu gross) oder oszilliert in der Schlucht. Es existiert keine Regel zur richtigen Einstellung der Lernrate. Modifikation der Lernregel mit Momentumterm: Idee: Beruecksichtigung vorangegangener Lernschritte w(i,j)=-my*dE(_w)/dw(i,j)+a*Dw(i,j) mit a E[0..1]. So wird eine gleiche Richtung verstaerkt, ein Vorzeichenwechsel abgemildert. Conjugate Gradient Verfahren: 1. Schritt: Minimierung von E(_w) in Suchrichtung _d (line search) 2. Schritt: Bestimmung einer neuen Suchrichtung aus alter Suchrichtung _d und Gradient DE(_w) Sehr schnelle Konvergenz in der Praxis Theorie: Minimierung einer quadratischen Funktion, Verfahren konvergiert nach n=#Parameter Schritten. RPROP: Nur ein Gewicht wird betrachtet (lokales Verfahren) deltaw(i,j)=-SUM(dE(_w)/dw(i,j)) Fuer jedes Gewicht eine eigene Schrittweite. Nachkoemmlinge: SuperSAB, Quickprop Verbesserungen von RPROP: 1. Aenderung des Gewichtes unabhaengig von der Groesse der Ableitung, lediglich das Vorzeichen wird betrachtet. Einfuehrung von Aenderungswerten delta(i,j) (Schrittweiten) fuer jedes Gewicht. 2. Anpassung der Aenderungswerte: Vergroesserung der Schrittweite, wenn vorherige dasselbe Vorzeichen hat, Verkleinerung, wenn ungleiche Richtungen Parameter: delta(i,j,0)=0.1 (Stdwert) deltamax=50 (Stdwert) Performance: Robust gegen Parameterwahl, schnell 10-5-10-Problem: 10 Eingabeneuronen, 5 in der verborgenen Schicht, 10 Ausgabeneuronen Eingabe (0001000) soll gleich Ausgabe sein, die information soll also zwischenzeitlich auf 5 Neuronen komprimiert sein. Generalisierung: Bei Approximierungen soll das System den allgemeinen Charakter der Daten erkennen. Ist die Praezision zu niedrig, werden noch nicht einmal die Trainingsdaten richtig approximiert, ist die Praezision zu gross, kommt es zum Overfitting: Zwar werden alle Trainingsdaten exakt abgebildet, jedoch wird die wahre Natur der Daten nicht erkannt, es wird nicht die einfachste Erklaerung gefunden, das System ist nur auf die Trainingsdaten spezialisiert, Messfehler werden nicht geoutet, auf andere Daten wird unsinnig geantwortet, es wird nicht generalisiert. Datenmengen: 1. Trainingsdaten: Erstellung der Parameter _w 2. Validierungsdaten: Erstellung von Hyperparametern (Anzahl der verborgenen Schichten, Verbindungsstruktur) 3. Testdaten: Abschaetzung der Leistung des fertigen Modells, der Generalisierungsfaehigkeit Early Stopping: Will man Overfitting vermeiden, so hoert man mit dem Training einfach auf, sobald der Fehler auf der Validierungsmenge wieder steigt (wobei der Fehler auf der Trainingsmenge beim Trainieren stetig sinkt). Regularisierung: Idee: Halte _w im moeglichst kleinen Bereich, abs(w) klein Realisierung: E(w)=0.5*SUM(SUM((o(i,k)-y(i,k))^2)) (Trainingsfehler) + lambda*SUM(w(j)^2) (Regularisierungsfehler) Ist lambda sehr gross, werden im Wesentlichen nur die Gewichte minimiert. Prunning: Entfernen von Verbindungen * Groessenbasiert (magnitude-based) die kleinen Gewichte raus (:=0) * Fehlerbasiert, z.B. Optimal Brain Damage/Surgeon Verfahren * Evolutive Verfahren ("ENZO") 2-Spiralen-Problem: Das System soll entscheiden, ob ein Punkt in einem Koordinatensystem auf der weissen oder schwarzen Spirale liegt. Die Spiralen liegen dabei ineinander gedreht. 2 Eingaenge: x und y Koordinaten 1 Ausgang: Ja oder Nein, i.e. gehoert zu schwarzer Spirale oder gehoert zu weisser Spirale Ergebnis: Das Netz kann nicht in Bereiche ausserhalb der Trainingsmenge abstrahieren, funktioniert nur innerhalb der vorgegebenen Spirale. Radiale-Basis-Funktionen-Netze (RBF-Netze): Ziel: Exakte Interpolation Gegeben: p Datenpaare { (x1,y1),... } Gesucht: f(_x(i))=y(i) Loesung: 1. Transformation des Eingabewertes _x --> phi(_x) 2. Lineare Kombination der transformierten Werte f(x)=SUM(w(i)*phi(i,_x)) ueber i=1..p w(1)..w(p) sind Parameter der Funktion Naiver Ansatz: phi(i,_x)=-(_x==_x(i)) '1 oder 0 Waehle w(i)=y(i) => f(_x)=y(i), wenn _x=_x(i) und 0 sonst Radiale-Basis-Funktionen-Ansatz: phi(i,_x) ist Funktion vom Abstand von _x(i), phi(i,_x)=||_x-_x(i)|| Typische Wahl von phi: Gaussfunktion phi(i,_x)=e^-(||_x-_x(i)||^2/sigma^2) phi(i,_x) liefert 1, wenn _x=_x(i) und sonst einen Wert zw. 0 und 1 Ist sigma gross, ist phi "tolerant", ist sigma klein, liefert phi(i,_x) fast null fuer alle werte ausser _x(i) Ziel ist es nun, die w(i)'s so zu bestimmen, dass f(_x(i))=y(i) (LGS) RBF-Netze bestehen dann schliesslich aus einer Eingabeschicht (_x), n phi(i)-Neuronen und einem Output-Neuron, welches die Outputs der phi(i)-Neuronen mit ihren jew. w(i) multipliziert und aufaddiert. Im Allgemeinen ist die Anzahl der verborgenen Neuronen kleiner als p. Die Zentren _my(i) der Basisfunktion sind Parameter des Netzes, die gelernt werden muessen. Repraesentationsfaehigkeit eines RBF-Netzes: Mit einem RBF-Netz lassen sich beliebige stetige Funktionen beliebig genau approximieren. Lernen eines RBF-Netzes: Verborgene Neuronen haben Parameter _my(i) (Zentren) und sigma(i) (Werte). Gelernt wird in 2 Schritten: 1. Wahl der Anzahl der verborgenen Neuronen und Wahl von _my(i) und sigma(i) Wahl der Zentren _my(i): 1. Zufaellige Wahl: Untermenge der Trainingsmuster _x(i) oder 2. Destruktives Verfahren: Beginne meit p verborgenen Neuronen, entferne Neuronen, bis Fehler zu gross oder 3. Cluster-Verfahren (z.B. k-means-Verfahren): Bestimme Zentren und Ausdehnung von Anhaeufungen von Datenpunkten _x(i), bestimme daraus _my(i) und sigma(i) 2. Anpassung der Parameter w(i) (einfach, da lineares Problem, analytisch berechenbar) 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. Vergleich von MLP und RBF-Netzen: Schichten: RBFN hat nur 3, MLP beliebig viele Trainingsphasen: RBF hat 2, MLP verwendet Gradientenabstiegsverfahren Aktivitaet: Beim RBFN nur wenige Neuronen aktiv (Lokalitaet), beim MLP tragen viele Neuronen zum Ergebnis bei Eingaberaum: Beim RBFN fuehren hochdimesionale Eingaben zu vielen verborgenen Neuronen, beim MLP besteht keine Beziehung Unueberwachtes Lernen: Ziel: Beschreibung der Verteilung von Daten _x in einem Eingaberaum, automatische Gruppenbildung (Clustering). Aehnliche Daten sollen derselben Gruppe zugeordnet werden, z.B. fuer die Vorverarbeitung von Daten oder Data-Mining. Kohonenkarten: Clustering mit Nachbarschaftsbeziehung zwischen den Clustern. Biologische Motivation: Aehnliche Reize aktivieren benachbarte Hirnregionen. In einer Kohonenkarte ist jedes Neuron ueber einen Gewichtsvektor mit allen Eingaben verbunden, _w(i)=(w(i,1)..w(i,n)). Jedes Neuron hat bis zu 4 Nachbarn. Es gilt das "Winner takes all"-Prinzip: Das Neuron i* , dessen _w(i) am naechsten an der EIngabe liegt, "gewinnt". Fuer i* gilt: ||_x-_w(i*)||=min {_x-_w(j)} Einfache Lernregel fuer Kohonenkarten: Am Anfang zufaellige Initialisierung der w(i). Dann werden die Daten angelegt und der _w(i)-Vektor des "Gewinners" wird in Richtung der Eingabe _x verschoben: _w(i*):=_w(i*)-(_x-_w(i*))*eta. eta ist die Lernrate zwischen 1 und 0. Kohonenlernregel: Beruecksichtigung der Nachbarschaftsbeziehung. Sei d(i,j) die Distanz zwischen Neuron i und Neuron j (z.B. einfach Anzahl der Kanten). Dann definiet man sich eine Nachbarschaftsfunktion h(i,j), die maximal (=1) ist, wenn i=j und gegen null geht, je groesser der Abstand von i und j ist. Meist bedient man sich der Gaussfunktion, also h(i,j)=e^-(d(i,j)^2/sigma^2). So beruecksichtigt man das lokale Umfeld des Gewinnerneurons i*: _w(j):=_w(j)+eta*h(i*,j)*(_x-_w(j)) Als Verfeinerung koennte man die Lernrate als Funktion der Anzahl der Lernschritte definieren: eta(t)=eta0*e^-(t/T), wobei t die Nummer des momentanen Durchlaufs ist und eta0 und T als Parameter vorgegeben sein muessen. Auch die Nachbarschaftsfunktion kann man dahingehend anpassen: sigma(t)^2=sigma0*e^-(t/T). So wird die Nachbarschaftsfunktion mit der Zeit immer intolernater, immer genauer.