News

Tschüss, Zellen: Game of Life als kontinuierliche Version

Ich interessiere mich ja für Themen im Umkreis des Artificial Life – nicht, um in dem Bereich zu forschen, sondern einfach als Hobby. Das Gebiet des Artificial Life ist eine gigantische Spielwiese. Man versucht, künstliche Systeme aus einfachsten Bestandteilen herzustellen – aber so, dass sie vielleicht ein paar der Eigenschaften von lebenden, biologischen Systemen innehaben. Es gibt viele Ansätze, solch ein künstliches System zu basteln, die meisten Systeme werden einfach mehr oder weniger aufwändig simuliert – kostet wenig, ist schön zum Ansehen, und ist einfacher auszuwerten. Ein gutes Beispiel ist meine Diplomarbeit, in der Schwarmverhalten einfach entsteht. Bringt nun einer dieser Ansätze spontan ein Systemverhalten hervor, das man aus den Regeln des Systems nicht ohne weiteres erkennen konnte, spricht man häufig von „emergentem Verhalten“ oder schlicht „Emergenz“. Dazu unten gleich noch kurz mehr.

Ein sehr bekanntes Beispiel für ein Artificial-Life-System sind sogenannte Zelluläre Automaten. Das sind im Grunde Kästchenwelten, also diskrete Welten meist einer oder zwei Dimensionen. Jedes Kästchen kann verschiedene Zustände innehaben. Auch die Zeit ist diskret, sie läuft in Zeitschritten und in jedem Zeitschritt ergibt sich der Zustand eines Kästchens (auch Zelle genannt) aus den Zuständen seiner Nachbarkästchen im vorherigen Zeitschritt. Mit anderen Worten, ein Kästchen bestimmt seinen Zustand anhand einer Übergangstabelle („Regel“ genannt) rein lokal – also ohne Kenntnis der Gesamtwelt. Bilden sich nun riesige, Kästchenübergreifende Systeme und Strukturen heraus, sprechen viele Leute wieder von Emergenz. Das interessante an Zellulären Automaten ist, dass man wirklich alle Zeitschritte durchrechnen muss und meist nicht einfach eine Formel finden kann, die den Zustand eines Kästchens für einen beliebigen Zeitschritt vorhersagt.

Nach der allgemeinen Einführung nun endlich mal was konkretes: Der bekannteste der Zellulären Automaten ist Conway's Game of Life. Es wurde von John Conway entwickelt, einem britischen Mathematiker, der Spaß an solchen mathematischen Spielchen hatte. Das Game of Life ist eine 2D-Kästchenwelt, wie Rechenpapier. Jede Zelle kann zwei Zustände einnehmen: Tot oder lebendig. Es ist klar, dass jede Zelle auf Rechenpapier von 8 anderen Zellen eingekreist wird. Ich habe gesagt, dass jede Zelle ihren Zustand für den nächsten Zeitschrift anhand ihrer lokalen Nachbarschaft „ausrechnet“, und so ist es auch hier. Es heißt Game of Life, also passiert das ganze biologisch motiviert:

  • Lebendige Zellen sterben an Einsamkeit, wenn sie weniger als zwei lebendige Nachbarn haben. Sie sterben an Überbevölkerung, wenn sie mehr als drei lebendige Nachbarn haben. Bei zwei und drei lebenden Nachbarn bleiben sie unverändert lebendig.
  • Tote Zellen leben im nächsten Zeitschritt, wenn sie exakt drei lebendige Nachbarn haben.

Diese Regeln reichen aus, um eine Vielzahl von Figuren aus lebenden Zellen zu basteln. Manche dieser Figuren sind „Stilleben“, bleiben also wie sie sind, weil jede ihrer Zellen eben entweder genau zwei oder genau drei lebendige Nachbarn hat. Manche sind periodisch: Sie verändern sich, Zellen sterben also und erwachen zum Leben, sie nehmen aber irgendwann wieder ihren Anfangszustand ein. Interessant sind periodische Figuren, bei denen der Anfangszustand, wenn er wieder erreicht ist, im Vergleich zu vorher verschoben ist. Diese nennt man „Spaceships“, da sie sich sozusagen durch den Raum bewegen. Eines der bekanntesten und einfachsten Spaceships ist der sogenannte „Glider“. Er ist rechts abgebildet, klickt mal drauf, dann seht ihr ihn in Bewegungm, lebende Zellen sind schwarz (© 2008, Wikipedia, Autor: Dhatfield).

Weiter interessante Figurenarten sind sogenannte „Metusehlas“, das sind Figuren, die aus möglichst einfachen Anfangszuständen möglichst lange unvorhersehbares Gewimmel erzeugen. Zigtausende Schritte aus einer einstelligen Anzahl gesetzten Anfangszellen sind keine Seltenheit. Es gibt eine riesige Fangemeinde, das Game of Life ist internetweit extrem populär. Eine vielzahl von Personen hat riesige Figuren aus abertausenden Zellen zusammengesetzt. Also können wir direkt mal ein paar Videos ansehen, die das ganze noch mehr illustrieren.

Kölner Mathefiasko: Studenten kannten Aufgabentypen der Klausur vorher. Neu: Jetzt mit Nachklausur!

Vor ein paar Tagen habe ich von einer Mathematik-Einführungsklausur im Grundschullehramts-Studiengang in Köln berichtet, bei der im ersten Durchgang satte 94% durchgefallen sind. Zunächst war ich eher auf Studi-Seite. Nach weiteren Infos über Klausur und Service musste ich von dieser Betrachtung Abstand nehmen. Ich habe daher im letzten Artikel anhand der Klausur, des Stoffes und der Stellungnahme der Universität begründet, warum bei dem gegeben Stoffumfang und Service gar nicht mit der „Stimmung in der Vorlesung“ argumentiert werden konnte.

Für diese These gibt es neue, starke Argumente. Der Jahrgang bekam eine Probeklausur (veröffentlicht mit freundlicher Genehmigung der Dozentin, danke!). Bei einer Probeklausur kann der Student nur gewinnen. Sie enthält realistische Klausuraufgaben – es macht aber nichts, wenn man sie nicht kann. Man kann sich als Student die Stoppuhr anstellen, sie lösen und Feedback erhalten. Dann sieht man, ob man gut im Stoff ist oder bis zur richtigen Klausur lieber noch einen Zahn zulegen sollte. So eine Probeklausur erfordert stundenlange, freiwillige Arbeit von Dozentenseite – wie auch schon ein Skript und Musterlösungen zu Übungszetteln. Darum gibt es auch nur in wenigen Vorlesungen eine. Ich werde wieder versuchen, sie fernab von Stimmungen auseinander zu nehmen und für Leser, die nicht im Uni-Alltag drin sind, nachvollziehbar zu machen.

Wollt ihr wissen, wer eure Kinder prägt?

Vor ein paar Tagen las ich, wie eine Matheklausur im Grundschullehramt in Köln zum Fiasko wurde. Im ersten Durchlauf fielen von 374 Teilnehmern satte 94% durch, mit der Nachklausur sind dann aber um die 100 durchgekommen. Da dachte ich erst „Hui, wie bei uns im ersten Semester, die nehmen die fast-Lehrer ja ganz schön ran“. Bis hier war ich neutraler Meinung, vielleicht mit leichter Tendenz zur der Studiseite. Mir begann aber an folgenden Stellen, Übles zu schwanen (Zitate sind kursiv):

  • „Die Klausur war hammerschwer, das war richtig ungerecht“, sagt Lisa, die ihren richtigen Namen nicht nennen will, „dabei wollen wir Lehrer werden, nicht Mathematiker.“
  • Der Ärger war so groß, dass sich sogar Eltern einschalteten: Luise Morschel, […] Mutter einer betroffenen Studentin, formulierte zusammen mit ihrem Mann, einem Mathematiklehrer, einen offenen Brief ans nordrhein-westfälische Wissenschaftsministerium.

Ich muss hier niemandem erklären, was man über einen volljährigen Studenten denkt, dessen Eltern vorsprechen und klarmachen, dass sie die Uni im Grunde für eine erweiterte Schulform halten. Familie Morschel ist in dieser Hinsicht aber ein derart besonderes Meisterstück gelungen, dass sie mir am Schluss dieses Beitrags noch einen eigenen Absatz für die Realsatire-Fans unter euch wert sein wird. Insgesamt aber dachte ich, man könne das als Einzelfall sehen. Ich kannte die Klausur selbst nicht, hatte also beim Lesen kein Fachwissen und daher auch keine Meinung. Aus meiner Fachschaftszeit weiß ich: Ganz, ganz selten wird wirklich mal ein Jahrgang „abgewürgt“, auch die Dozenten sind dann nicht glücklich. Zudem schien die Uni Köln um eine Lösung bemüht. Toll!

Ein kleiner Überblick über Neuronale Netze

Download des Manuskriptes - Zeta2-Version

Die Dateinamen können sich jederzeit ändern – bitte verlinkt nur auf diese Unterseite hier, nicht auf die Dateien an sich.

Originalversion eBookReader-optimiert
Deutsch PDF, 6.2MB, 256 Seiten PDF, 6.2MB, 296 Seiten
Englisch PDF, 6.2MB, 244 Seiten PDF, 6.1MB, 286 Seiten

Originalversion? EBookReader-Version?

Die Originalversion ist zweispaltig im gewohnten Layout und Design. Die eBookReader-optimierte Version ist einspaltig. Zusätzlich wurden Kopfzeilen, Fußzeilen und Randbemerkungen entfernt.

Für den Druck und das Lesen am Rechner ist die eBookReader-Version aufgrund der deutlich erhöhten Seitenanzahl, des weniger schönen Layouts und des Fehlens der Komfortmerkmale eher unattraktiv. Auf eBookReadern wird die Lesbarkeit so allerdings ganz nachhaltig verbessert und das Blättern reduziert.

Die eBookReader-Version wird ab jetzt bei jedem Release aus den Originalinhalten mitgeneriert. Anders als für die Originalversion sieht mein Release-Workflow aber keine zusätzliche typographische und Designoptimierung für sie vor. Das ist nämlich der einzige Schritt, den ich nicht automatisieren kann und der, wenn man es ordentlich machen will, auch etwas Zeit kostet. Was die Ästhetik und Typographie angeht, erwartet bei der eBookReader-Version also keinen Support :-)

Für Leser

Gebt Feedback!

Dieses Manuskript hat durch seine Leser schon sehr viel an Nutzen gewonnen, wie auch an den vielen Helfernamen im Vorwort ersichtlich ist. Wenn ihr mir Feedback zum Script gebt, seid sicher, dass ich mich freue, und es auf die eine oder andere Weise in die jeweils nächste Edition mit einfließt. Also: Wenn ihr irgendwelche Beschwerden, Fehlerberichtigungen, Vorschläge oder einfach Lob ;-) habt, nehmt sofort hier Kontakt auf.

Nutzungsbestimmungen

Von der Epsilon-Edition an ist das Manuskript unter Creative Commons Attribution-No Derivative Works 3.0 Unported License lizensiert, bis auf einige wenige Kleinteile, die liberaleren Lizenzen unterstehen (siehe Vorwort und Verweise im Text selbst). Natürlich berührt die Lizenz nicht den Source Code des Manuskripts, der (zunächst) nicht veröffentlicht wird.

Zielsetzung des Manuskripts

Ziel der Arbeit ist, dass jemand, der sich erst einmal in dem Fachgebiet umsehen oder eine Seminararbeit über ein bestimmtes Paradigma Neuronaler Netze schreiben will, sich nicht sofort ein Buch für 50 Euro kaufen muss. Trotzdem ist es wichtig festzustellen, dass das Script im Entstehen begriffen ist und auch noch einige Gliederungsprinzipien umgestellt werden.

Zitieren dieser Arbeit

Dass es keinen offiziellen Verleger gibt, muss bei einer Referenzierung im wissenschaftlichen Sinne natürlich beachtet werden. Damit International die gleiche Referenz kursiert, schlage ich vor, zunächst folgende Referenz zu verwenden:

David Kriesel, 2007, Ein kleiner Überblick über Neuronale Netze, erhältlich auf http://www.dkriesel.com

Diese betrifft die Deutsche Version. Auf der Englischen Version dieser Seite steht die entsprechende englische Referenz. Bitte referenziert immer unter angabe der URL, da sie bis jetzt das einzige wirkliche Identifikationsmittel des Manuskripts ist. Den Editionsnamen habe ich aus beiden Referenzen absichtlich weggelassen, da er sich hin und wieder ändert und Google Scholar und Citeseer damit Probleme haben. Hier noch ein BibTeX Entry:

@Book{ Kriesel2007NeuralNetworks, 
       author = { David Kriesel }, 
       title =  { Ein kleiner \"{U}berblick \"{u}ber Neuronale Netze },
       year =   { 2007 }, 
       url =   { erh\"{a}ltlich auf http://www.dkriesel.com } 
     }

Auch hier gibt es wieder die englische Version auf der englischen Übersetzung dieser Seite.

Roadmap

Damit das Manuskript eine „runde Sache“ wird, ist noch etwas zu tun. Prinzipiell wünsche ich mir, dem Manuskript noch folgendes hinzuzufügen (diese Roadmap wird nicht bei jedem Release aktualisiert, also können einige Punkte schon erledigt sein):

  1. Implementierungsfragen und SNIPE: Seit der Entstehung des Scriptes ist in Form von SNIPE ein hochleistungsfähiges Framework Neuronaler Netze entstanden. Dies soll auf eine Linie mit dem Script gebracht werden: Überall im Script sollen sich Anmerkungen finden wie „Dieses Feature ist so-und-so in SNIPE implementiert“. Hierzu soll sich auch noch ein ausführliches Kapitel gesellen, wie man Neuronale Netze effizient implementiert. So kann das Script die Referenzdokumentation von SNIPE werden, und SNIPE die Referenzimplementierung zum Script.
  2. Evolution Neuronaler Netze: Es soll (auch im Hinblick auf SNIPE) noch ein großes Kapitel geschrieben werden, wie man Neuronale Netze evolviert, also mit inklusive Topologie und Gewichtswerten einfach evolutionär wachsen lässt, was natürlich auch mit rekurrenten Netzen funktioniert. Dieses Kapitel ist fast fertig.
  3. Praxistipps: In Kapitel 4 und 5 fehlt mir noch eine ganze Reihe Praxistipps (z.B. wie man zu lernende Daten am besten aufbereitet, sowie weitere Praxistipps speziell zu MLPs mit zugehörigen Referenzen.
  4. Kleinere Sachen: Ein Kurzabschnitt über Resilient Propagation und einige Algorithmen mehr würden sich in Kapitel 5 gut machen. Das Kapitel über rekurrente Multilayerperceptronartige Netze soll sinnvoll vertieft und vergrößert werden. Prinzipiell nenne ich im Manuskript einige Sachverhalte, die noch referenziert werden müssen. Ein kleines Kapitel über Echo-State-Networks wäre nett.

Das wars im groben … :-) es ist also noch ein bisschen zu tun, bis ich das Manuskript „fertig“ nenne. Allerdings nicht soviel, wie schon getan wurde. Definitiv aber wird das nicht in einem einzigen Release passieren.

Letzte Releases

Klicken Sie auf einen Nachrichtentitel, um mehr zu erfahren. Versionsinformationen von Delta-Version und früher finden sich direkt unter den Überschriften. Die Newsmeldungen zu alten Versionen habe ich mittlerweile entfernt.

Was sind Neuronale Netze und was steht im Script?

Neuronale Netze sind ein von der Natur inspirierter Mechanismus, der es Computern ermöglicht, ähnlich wie ein Gehirn zu lernen - der Computer kann so, wenn er die Lösung für ein Problem kennt, korrekte Lösungen für ähnliche Probleme finden und vieles mehr.

Das Script gliedert sich in verschiedene Teile, welche sich wiederum in Kapitel gliedern. Hier eine kurze Inhaltsangabe dieser Abschnitte:

Teil I: Von der Biologie zur Formalisierung - Motivation, Philosophie, Geschichte und Realisierung Neuronaler Modelle

Einleitung, Motivation und Geschichte

Wie kann man dem Computer etwas beibringen? Entweder, in dem man ein starres Progamm schreibt - oder, indem man ihm das Lernen ermöglicht. Lebende Wesen haben keinen Programmierer, der ihnen ein Programm für ihre Fähigkeiten schreibt, welches nur ausgeführt werden muss. Sie lernen - ohne Vorkenntnisse durch Eindrücke von außen - selber und kommen damit zu besseren Problemlösungen als jeder Computer. Kann man solches Verhalten auch bei Maschinen wie Computern erreichen? Können wir solche Kognition von der Biologie adaptieren? Geschichte, Entwicklung, Niedergang und Wiederauferstehung eines großen Ansatzes, Probleme zu lösen.

Biologische Neuronale Netze

Wie lösen Biologische Systeme Probleme? Wie funktioniert ein System von Neuronen? Wie kann man dessen Funktionalität erfassen? Wozu sind verschieden große Mengen von Neuronen imstande? Ein kleiner Überblick über die große Komplexität einfacher Bausteine Neuronaler Informationsverarbeitung - und deren Vereinfacherung, um sie technisch adaptieren zu können. Achtung: Dieses Kapitel ist in der Betaversion des Scriptes nicht enthalten.

Bausteine technischer Neuronaler Netze

Formale Definitionen und umgangssprachliche Erklärungen der Bestandteile, die die technischen Adaptionen der biologischen Neuronalen Netze ausmachen. Erste Beschreibungen, wie man diese Bestandteile zu einem Neuronalen Netz zusammensetzen kann.

Gedanken zum Training Neuronaler Netze

Ansätze und Gedanken, auf welche Arten Maschinen etwas beizubringen ist. Korrigiert man Neuronale Netze? Bestärkt man sie nur? Lässt man sie gar ganz alleine ohne Hilfe lernen? Gedanken darüber, was wir während des Lernvorganges überhaupt verändern möchten, wie wir es verändern, über Fehlermessung und wann wir mit den Lernen fertig sind.

Teil II: Überwacht lernende Netzparadigmen

Das Perceptron

Der Klassiker unter den Neuronalen Netzen. Wenn von einem Neuronalen Netz gesprochen wird, ist meistens ein Perceptron oder eine Variation davon gemeint. Perceptrons sind mehrschichtige Netze ohne Rückkopplung, mit festen Eingabe- und Ausgabeschichten. Beschreibung des Perceptrons, seiner Grenzen und seiner Erweiterungen, welche die Grenzen umgehen sollen. Herleitung von Verfahren, es lernen zu lassen, und Diskussion über deren Probleme.

Radiale Basisfunktionen

RBF-Netze nähern Funktionen an, indem sie Gaußglocken strecken, stauchen und anschließend räumlich versetzt aufsummieren. Beschreibung ihrer Funktion und ihres Lernvorganges, Gegenüberstellung mit Multilayerperceptrons.

Rückgekoppelte Multilayerperceptrons

Gedanken über Netze, welche eigene interne Zustände besitzen. Ansätze des Lernens mit derartigen Netzen, Skizzierung ihrer Dynamik.

Hopfieldnetze

In einen magnetischen Feld übt jedes Teilchen Kraft auf jedes andere Teilchen aus, so dass sich die Teilchen insgesamt so ausrichten, wie es am energetisch günstigsten für sie ist. Wir kopieren diesen Mechanismus der Natur, um verrauschte Eingaben zu ihren richtigen Vorbildern zu korrigieren.

Learning Vector Quantisation

Learning Vector Quantisation ist ein Lernverfahren mit dem Ziel, in vordefinierte Klassen unterteilte Trainingsmengen von Vektoren durch wenige Repräsentanten-Vektoren möglichst gut wiederzugeben. Ist dies geschafft, so ist eine einfache Zuordnung bis dato unbekannter Vektoren in eine dieser Klassen möglich.

Teil III: Unüberwacht lernende Netzparadigmen

Self Organizing Feature Maps

Ein Paradigma unüberwacht lernender Neuronaler Netze, welches einen Eingaberaum durch seine feste Topologie kartographiert und so selbstständig nach Ähnlichkeiten sucht. Funktion, Lernverfahren, Variationen und Neuronales Gas.

Adaptive Resonance Theory

Kurze Beschreibung eines Ansatzes Neuronaler Netze, der ermöglichen soll, zur Laufzeit Information hinzuzulernen.

TEIL IV: Exkurse, Anhänge und Register

Clusteranalyse und Regional and Online Learnable Fields

Das Grimmsche Wörterbuch beschreibt das heute ausgestorbene deutsche Wort „`Kluster“' mit „`was dicht und dick zusammensitzet“'. In der statistischen Clusteranalyse wird die Gruppenbildung innerhalb von Punktwolken untersucht. Vorstellung einiger Verfahren, Vergleich ihrer Vor- und Nachteile. Betrachtung eines lernenden Clusteringverfahrens auf Basis Neuronaler Netze. Ein Regional and Online Learnable Field modelliert aus einer Punktwolke mit womöglich sehr vielen Punkten eine vergleichsweise kleine Menge von für die Punktwolke repräsentativen Neuronen.

Neuronale Netze zur Vorhersage

Betrachtung einer Anwendung Neuronaler Netze: Ein Blick in die Zukunft von Zeitreihen.

Reinforcement Learning

Was, wenn keine Trainingsbeispiele existieren, man aber trotzdem beurteilen kann, wie gut man gelernt hat, ein Problem zu lösen? Betrachten wir ein Lernparadigma, welches zwischen überwachtem und unüberwachtem Lernen anzusiedeln ist.