11. Einführung in künstliche neuronale Netzwerke¶

In dieser Einheit kommen wir zu einem sehr populären Kapitel bzw. Werkzeug aus dem Bereich des Machine Learnings, nämlich künstlichen neuronalen Netzwerken.

Diese tauchen meist unter dem Begriff des supervised Learning auf, sie können allerdings auch beim unsupervised Learning eingesetzt werden. Wir verhalten uns hier trotzdem traditionell und organisieren uns für unsere Einheit einen gelabelten Trainingsdatensatz. Genauer gesagt werden wir sogar den gleichen Datensatz verwenden, den wir in der vorangegangenen Einheit bereits kennen gelernt haben.

Wir werden hier auch wieder ein Klassifikationsproblem) angehen, einfach weil das zugänglicher ist. In dem Setup, das wir hier aufbauen werden, ist es allerdings überhaupt kein Problem, auf ein Regressionsproblem umzusteigen, denn dafür muss man dann unten nur die Loss-Funktion austauschen – aber dazu kommen wir noch.

Der Plan für diese Einheit ist, zunächst die benötigten Packages zu installieren, dann über die grundsätzliche Struktur von künstlichen neuronalen Netzten zu reden, und danach ein einfaches Netzwerk zu trainieren und auszuwerten.

Zunächst aber noch die Imports für heute.

11.1 Installation von PyTorch und PyTorch Lightning in Jupyter Notebook¶

Die folgenden Kommandos installieren die Packages PyTorch und PyTorch Lightning direkt über das Jupyter Notebook in jenem Anaconda-Environment, in dem Jupyter läuft. Wenn Sie das nicht möchten, dann erzeugen Sie ein eigenes conda Environment für diese Aktion, aktivieren Sie es und starten Sie dort Jupyter Notebook neu. Führen Sie erst dann die Installationsbefehle aus.

Nach diesen beiden Aktionen sollte alles Nötige installiert sein, um das Notebook weiter auszuführen. Hier sagen die Outputs, dass bereits alle Packages installiert sind, weil ich das bereits vorher erledigt habe. Bei einer neuinstallation werden die entsprecheneden Informationen über den Installationsprozess ausgegeben, die man normalerweise bei der Einrichtung direkt in der Shell zu sehen bekommt.

11.2 Erzeugen des Datensatzes für das Training des künstlichen neuronalen Netzwerks¶

Als nächstes werden wir im Prinzip den gleichen Datensatz erzeugen wie beim letzen mal beim Supervised Learning, nur mit ordentlich mehr Punkten. Wie Sie vielleicht bereits wissen, braucht es für entsprechend große Netzwerke auch dementsprechend viel Trainingsdaten. Legen wir also los:

Das sieht nach einem sehr interessanten Datensatz aus. Jetzt kommen wir also zum nächsten Schritt, dem Aufsetzen des Lernens und Vorhersagens mit PyTorch. Dazu muss ich zunächst zumindest ein Bisschen ausholen:

11.3 Grundlegende Struktur eines einfachen künstlichen neuronalen Netzwerks¶

Ein einfaches künstliches neuronales Netzwerk (ab jetzt einfach kurz “KNN” genannt), besteht aus folgenden grundlegenden Elementen:

• Einem Input-Layer, in das die Inputs passen
• Einem Output-Layer, das die Outputs ausgibt
• Mehreren sogenannten “hidden” Layers dazwischen, oder einer ganz frei wählbaren Netzwerk-Topologie
• Besteht ein KNN aus mehreren hidden Layers, dann wird es bereits als “deep” bezeichnet, man nennt die entsprechende Variante von Machine Learning dann auch “Deep Learning”.
• Zwischen aufeinanderfolgenden Layers können verschiedene zusätzliche “Effekte” eingebaut werden, die zur Stabilität des Trainings und der Vorhersagen beitragen können. Damit wollen wir uns hier nicht befassen (das kommt im Laufe der Zeit von selber). Eine Sache ist aber wichtig:
• Zwischen aufeinanderfolgenden Layers kommt immer eine sogenannte “Nichtlinearität” oder “Aktivierungsfunktion”. Diese sorgt dafür, dass die Kombination von aufeinanderfolgenden Layers nicht trivial wird, denn:

Die einfachste Layer-Variante (und nur damit beschäftigen wir uns hier) nennt man “fully-connected” oder “dense” Layer. Es besteht aus einer fixen Anzahl von Einheiten, sogenannten “Neuronen”. Jedes Neuron beinhaltet einen Zahlenwert, der dadurch bestimmt wird, dass die Inputs (Zahlenwerte) aus den Neuronen des vorigen Layers linearkombiniert werden.

Sie können sich das so wie eine Matrix-Vektor-Multiplikation vorstellen. Jedes fully-connected Layer ist ein Vektor von Zahlen. Und jedes Nachfolgende Layer wird daraus durch Multiplikation des vorangegangenen Vektors mit einer Matrix von Koeffizienten berechnet. Da das eine lineare Abbildung ist, wäre die Hintereinanderausführung mehrerer solcher Layers wieder linear.

Und genau daher verwendet man eine nichtlineare Aktivierung. Klassische Aktivierungsfunktionen sind z.B. der Arkustangens oder die sogenannte Sigmoid-Funktion: $$\mathrm{sig}(x)=\frac{1}{1+e^{-x}}$$ Das sieht geplottet so aus:

Die Nichtlinearität sorgt im Wesentlichen dafür, dass es z.B. einen bestimmten Wertebereich für die Outputs gibt. Statt beliebiger Zahlen kommen bei der Sigmoid-Funktion Werte zwischen $0$ und $1$ heraus. Beim Arkustangens ist es ein Wertebereich von $-1$ und $1$. Sie sorgt aber auch dafür, dass das Netz die Möglichkeiten durch mehrere Layers gut nutzen kann.

Soviel ganz kurz und Grundlegend zur Struktur eines einfachen KNN. Was von all dieser Struktur wird nun aber beim Training gelernt? Was ist vorgegeben?

11.4 Freie Parameter und Hyperparameter in einem einfachen künstlichen neuronalen Netzwerk¶

Ist die Struktur eines KNN einmal festgelegt, dann folgt daraus, welche und wie viele freie, also trainierbare bzw. lernbare, Parameter in diesem Netz stecken. Dass die Anzahl der freien Parameter in einem Modell eine wichtige Größe ist, das wissen wir bereits. Im Zusammenhang mit KNNs verdient der Vergleich der Anzahlen der Parameter im Modell mit der Anzahl der Datenpunkte allerdings zusätzliche Aufmerksamkeit.

Schnell ist man versucht, das Netz tiefer und die Layers breiter zu machen, um dem Netzwerk zu ermöglichen, aller Art Strukturen in den Daten zu finden oder zu erlernen, aber dabei schießt man oft über das Ziel hinaus. Das Problem, das hier auftritt, heißt “Overfitting”, d.h., das Netz lernt einfach die Trainingsdaten auswendig. Das soll aber nicht passieren, denn sonst kann es über die Trainingsdaten hinaus (z.B. für die Testdaten) keine besonders guten Vorhersagen mehr machen. Also wenden wir uns kurz dem Thema Parameter zu.

Zunächst einmal zu den Begriffen:

• Ein freier Parameter in einem Machine-Learning-Modell wird beim Training angepasst
• Ein Hyperparameter eines Machine-Learning-Modells wird durch die Struktur oder andere Aspekte vorgegeben und ändert sich während eines Trainings normalerweise nicht

Nehmen wir z.B. ein einfaches Netzwerk her, das aus einem Input-Layer, einem Output-Layer und zwei hidden Layers besteht, alle fully-connected. Das ist also ein Layer mehr als im Bild oben, aber die Prinzipien sind die gleichen. Dann haben wir dabei allein durch die HyperparameterNetzwerk-Topologie folgende Hyperparameter:

• Die Anzahl der Neuronen im Input-Layer
• Die Anzahl der Neuronen im Output-Layer
• Die Anzahl der hidden Layers
• Die Anzahl der Neuronen im ersten hidden Layer
• Die Anzahl der Neuronen im zweiten hidden Layer

Die Anzahlen der Neuronen im Input- und Output-Layer werden grundsätzlich durch die Dimension von Input-Daten und dem gewünschten Output vorgegeben. Für unseren Beispiel-Datensatz sind das 2 Inputs ($x$ und $y$ der Punkte) und 2 Outputs (die Wahrscheinlichkeiten für die Klassen). Die Anzahlen der Neuronen in den hidden Layers können wir frei wählen. Nennen wir sie für den Moment einmal $m_1$ und $m_2$. Da die Neuronen von einem Layer zum nächsten alle miteinander verbunden sind, erhalten wir so die folgende Gesamtanzahl von freien Parametern in unserem KNN: $$2\times m_1 + m_1 \times m_2 + m_2 \times 2$$ Wenn wir z.B. $64$ Neuronen in beide hidden Layers setzen, dann werden das bereits $64\times 68= 4352$ freie Parameter. Es kann hier also, insbesondere mit fully-connected Layers, sehr schnell gehen, und man hat einen ganzen Haufen freie Parameter im Modell. Behalten wir das einmal im Hinterkopf.

11.5 Training eines künstlichen neuronalen Netzwerks im Allgemeinen¶

Was bedeutet das nun für das Training? Wir haben beim vergangenen Mal bereits supervised Machine Learning praktiziert und verschiedene Modelle per “Fit” auf unsere Daten losgelassen. Aber was ist dabei eigentlich passiert? Wenn ein KNN (oder ein anderes ML-Modell) trainiert wird, dann wird dabei versucht, ein Optimierungsproblem zu lösen. Optimierung kennen wir ja bereits aus früheren Einheiten. Wie beim supervised ML besprochen, optimieren wir hier den Unterschied der Modell-Vorhersagen zu den tatsächlichen Labels der Trainingsdaten.

Das passiert auch hier. Die Methode, die dabei angewendet wird, ist meist eine Variante von Gradient Descent, den wir auch bereits kennen. Die Schrittweite beim Gradient Descent ist ein weiterer Hyperparameter und wird als “Learning Rate” bezeichnet Die zu minimierende Funktion ist die “Kostenfunktion”, die entsteht, wenn man den sogenannten “Loss” über alle Trainingsbeispiele mittelt. Die Loss-Funktion kann man verschieden wählen, meist je nach Problemstellung, und auch diese Wahl ist eigentlich ein Hyperparameter. Wir werden sie hier weiter unten einfach aus dem PyTorch-Fundus für Loss-Funktionen auswählen.

Ein weiterer Hyperparameter ist die sogenannte “Batchsize”. Was ist das nun schon wieder? Beim Deep Learning sind die Datenmengen teils riesig. Das bedeutet unter anderem, dass sie meist in Teilen dem Modell zum Lernen “gefüttert” werden. Z.B., wenn $100$ Datenpunkte auf einmal, gemeinsam mit dem Modell, gut in den Speicher der Grafikkarte passen, dann wählt man Batchsize $100$. Damit kann man auch gut experimentieren, um den Lern-Prozess effizient zu gestalten.

Wenn alle Daten einmal durch das Modell gelaufen sind, dann spricht man von einer “Epoche”. Das passiert mehrmals, und man lässt also das Modell einige (viele, teils sehr viele) Epochen lang trainieren.

So, jetzt habe ich aber langsam genug geredet. Gehen wir’s an.

11.6 Training eines künstlichen neuronalen Netzwerks mit PyTorch und PyTorch Lightning¶

Am direktesten ist es, wenn ich hier einfach die Teile unseres kleinen Netzwerks mit PyTorch und PyTorch Lightning der Reihe nach zusammensetze, und dann starten wir das Training. Hier kommen erstmal noch eine Runde von Imports.

Dieses Erste Setup wollte ich Ihnen zeigen, bevor wir die entsprechende Python-Klasse für das Netzwerk (und noch eine, ganz kurze für die leichtere Verwendung des Datensatzes) erstellen. Ich weiß schon, wir haben uns bisher nicht um Klassen in Python gekümmert, aber das ist trotzdem keine Hexerei. Denken Sie so ähnlich wie für eine Funktion in Python, nur mächtiger. Dann werden Sie schnell die Einträge hier verstehen.

PyTorch Lightning macht es sehr einfach, die Funktionalität von PyTorch zu nutzen, die selbst bereits sehr umfangreich und komfortabel ist. Fangen wir einfach mal an. Die Sache kommt trotzdem etwas umfangreich daher, aber das liegt daran, dass diese Methoden einfach sehr mächtig sind und daher auch entsprechende vorbereitung erfordern.

Das ist nun einmal recht gut gelaufen. Auch die Accuracy auf den Testdaten wissen wir bereits. Was ist aber beim Training genau passiert, und wie verhalten sich die Losses bei Training und Validation? Dafür machen wir jetzt noch einen Plot in alter Tradition.

Hier sieht man, dass die Loss-Funktion beim Training etwas weiter nach unten geht als für die Validierung. Das bedeutet, die Labels im Validierungs-Set werden nicht so gut wiedergegeben wie jene im Trainingsset, was zu erwarten ist.

11.7 Übungsaufgabe: Experimentieren mit dem Beispiel-KNN in PyTorch Lightning¶

Nachdem Sie nun bis hierher durchgehalten haben, ist es an der Zeit, dass Sie selbst mit diesem Werkzeug experimentieren. Auch wenn es am Anfang unübersichtlich ist, werden Sie mit der Zeit dahinter kommen, wie die einzelnen Teile funktionieren und noch viel spannendere Netzwerke bauen können, als wir es hier getan haben. Hilfreich sind dabe auf jeden Fall grundsätzlich die Dokumentationen von PyTorch und PyTorch Lightning, aber das ist eher für spätere Versuche.

Für den Anfang bieten sich folgende Versuche an:

• Ändern Sie die Dimension der hidden Layers (also die Anzahl der Neuronen dort) und beobachten Sie, was passiert.
• Schalten Sie das dritte hidden Layer dazu und beobachten Sie, was passiert.
• Nehmen Sie das zweite hidden Layer heraus und beobachten Sie, was passiert.
• Versuchen Sie, die Test-Accuracy möglichst hoch hinaufzubringen.
• Sie können auh den Trainingsdatensatz vergrößern (normalerweise bringen mehr Daten beim Deep Learning Vorteile).

Jedenfalls wünsche ich Ihnen dabei viel Vergnügen!

10 Supervised Machine Learning: Grundlagen¶

In dieser Einheit beschäftigen wir uns mit den Grundlagen des Supervised Machine Learnings. Der Begriff “supervised” bedeutet in diesem Zusammenhang, dass es zu jedem Datenpunkt einen Wert gibt, der die für das Machine Learning interessante Eigenschaft des Datenpunkts bezeichnet.

Das kann z.B. die Zuordnung zu einer Klasse (bei einem Klassifikationsproblem) sein, oder ein numerischer Wert (bei einem Regressionsproblem). Was auch immer es ist, der allgemeine Begriff dafür ist “Label”. Man spricht daher beim supervised Machine Learning auch grundsätzlich von “labeled data”, also annotierten Daten.

Im Gegensatz zum unsupervised Learning, das wir in der vorangegangenen Einheit behandelt und ausprobiert haben, gibt es hier also recht direkte Möglichkeiten, zu versuchen, dem eigenen Computerprogramm eine Vorhersagekraft für die Eigenschaften eines Datensatztes “beizubringen”. Dieser Prozess wird daher recht treffend auch als “Training” bezeichnet. Wie das genau vor sich geht, das werden wir uns noch etwas detaillierter ansehen.

Zunächst möchte ich Ihnen aber einfach einmal ein Beispiel für gelabelte Datensätze zeigen. Fangen wir gleich mit Daten für ein Klassifikationsproblem an. Zunächst aber noch die Imports für heute.

10.1 Vorbereitung der Daten und der Labels für Supervised Learning mit Hilfe von Scikit-Learn¶

Zunächst müssen wir die Daten vorbereiten. Für viele Datensätze, die man z.B. auf kaggle.com finden kann, ist das zwar schon passiert, aber manchmal muss man da selbst noch etwas nachbessern. Das gilt vor allem dann, wenn man sich die Input-Daten (auch features genannt) und die Labels selbst aussuchen möchte. Damit wir allerdings nicht allzuviel Zeit damit zubringen, gibt es dafür eine kleine Abkürzung.

Wir werden hier einen Datensatz selbst erzeugen, und zwar bereits mit der Machine-Learning Package Scikit-Learn selbst. Dort gibt es eigene Funktionalität für die Erzeugung von Test-Datensätzen, die wir hier ausprobieren werden. Obwohl das sehr einfach geht und eigentlich “blind” verwendet werden kann, sehen wir uns genau an, wie die Daten zusammengesetzt und aufgebaut sind.

Ein Datensatz besteht aus einer Liste von $2$ Teilen:

• Den Inputs/Features, als NumPy-Array, d.h. eine Matrix, in deren Zeilen die Input-Daten-Vektoren stehen
• Den Labels als Array, allerdings nur als eindimensionales, weil dort für jeden Input-Vektor nur eine Zahl (die Klassen-ID) steht.

Mit Scikit-Learn kann man verschieden “geformte” 2D-Punktwolken erzeugen und diese als Datensätze ausgeben lassen. Dazu verwenden wir Funktionen aus dem Modul _sklearn.datasets_:

Das sieht wirklich sehr schön mondförmig aus (mit dem anfänglichen Wert von noise von $0.1$. Das “Rauschen” könnten wir allerdings auch etwas aufdrehen, z.B. auf $0.9$, dann sieht das so aus:

Von Monden ist hier nicht mehr so viel zu sehen, aber man kann sie noch erahnen (wenn man es weiß). Lassen wir mal für die folgenden Experimente mit den verschiedenen Classifiern den noise-Wert auf $0.9$, damit es etwas interessanter wird.

10.2 Ausgewogenheit der Daten beim Supervised Learning¶

Eine Sache ist jedoch noch wichtig zu erwähnen, bevor wir zum Training kommen. Und zwar handelt es sich dabei um die Ausgewogenheit des Datensatzes, was die Labels betrifft. Es ist grundsätzlich wichtig auf einen ausgewogenen (balanced) Datensatz zu achten, damit es nicht zu (teilweise brutalen) Artefakten bei Vorhersagen kommt.

Als extremes Beispiel stellen Sie sich kurz einen anderen Datensatz vor, bei dem es $99$ Daten der einen Klasse und nur einen einzigen Datenpunkt aus der anderen Klasse gibt. Auf diesen Daten ein gutes Modell zu trainieren, ist sehr schwierig. Aber es ist außerdem noch genauso schwierig, ein gutes Modell von einem komplett einseitigen Modell zu unterscheiden, und das kommt so:

Ein Modell, das immer nur die vorherrschende Klasse vorhersagt, liegt damit nämlich bereits zu $99$ Prozent richtig. Das ist eigentlich für jedes Machine-Learning-Problem eine beeindruckende Performance. Trotzdem ist das Modell eigentlich unbrauchbar, gerade dann, wenn es auf die seltenen Fälle (aus der wenig repräsentierten Klasse) ankommt, weil man z.B. die Ausnahmen gut vorhersagen will.

Das Fazit dieses kurzen Ausflugs: Ein ausgewogener Datensatz ist sehr wichtig für erfolgreiches Training. Schauen wir kurz nach, wie ausgewogen unser Datensatz mit den Monden ist:

Diese Verteilung ist hier also schön ausgeglichen, so wie es sein soll, wir haben hier also unsere “balanced data”. Damit haben wir jetzt was die Vorbereitung der Daten betrifft unsere Schuldigkeit getan und können damit den nächsten Schritte tun.

10.2 Die wichtigsten Schritte beim Supervised Learning im Allgemeinen¶

Das Prozedere beim Supervised Learning ist üblicherweise folgendermaßen:

• Die Daten werden zunächst vorbereitet und überprüft (das haben wir gerade getan).
• Dann werden die Daten in zwei (oder drei) Teile geteilt, nämlich in einen Trainings-Teil und einen Test-Teil (und einen Validierungsteil, damit man Hyper-Parameter tunen kann, dazu kommen wir in der nächsten Einheit).
• Der Trainingsteil sollte üblicherweise größer sein als der Rest, z.B. $80$ – $10$ – $10$ Prozent oder $60$ – $20$ – $20$. Wir werden es uns hier einfach machen und $80$ zu $20$ Prozent aufteilen und auf ein separates Validierungsset verzichten.
• Beim Aufteilen werden die Daten üblicherweise auch durchgemischt. Das führt dazu, dass nicht lauter gleiche Labels hintereinander kommen, sondern auch die Reihenfolge ausbalanciert ist (wichtig fürs Training).
• Dann bekommt der Machine-Learning-Algorithmus die Trainingsdaten, um sie zu fitten. Das geschieht je nach Algorithmus auf verschiedene, geeignete Arten.
• Anschließend wird das erhaltene Machine-Learning-Modell auf den Testdaten ausprobiert. Das bedeutet, man schickt die Testdaten durch das Modell und vergleicht die vorhergesagten Ergebnisse mit den tatsächlichen Labels der Daten.
• Beim Testen erhält man einen Score, z.B. das Verhältnis von richtig vorhergesagten Datenpunkten zu falsch vorhergesagten.
• Je besser dieser Score, desto besser. Allerdings sollte man jedenfalls besser sein als zufälliges Raten, was z.B. bei $2$ Klassen $50$ Prozent wäre.

Für alle diese Dinge verwenden wir durchgängig die Package Scikit-Learn, aus der wir ja in der vergangenen Einheit auch bereits die Algorithmen für das Unsupervised Learning importiert hatten.

10.3 Aufteilen der Daten in Trainingsdaten und Testdaten¶

So, nun konkret zu den Schritten. Teilen wir zunächst die Daten auf. Das geht ganz einfach mit einer Funktion aus Scikit-Learn, nämlich:

Das Modell soll also anhand der Punkte (mit Labels) auf der linken Seite lernen und die Punkte auf der rechten Seite möglichst richtig klassifizieren können, ohne diese beim Training gesehen zu haben.

10.4 Supervised Learning: Das Training am Beispiel Decision Tree¶

Jetzt können wir unsere Daten bereits in ein Machine-Learning-Modell füttern. Als Beispiel eignen sich hier einige aus dem Supervised-Learning-Fundus von Scikit-Learn. Wir beginnen mit einem Decision Tree (Entscheidungsbaum). Dabei geht es darum, aus den Werten einzelner Inputs bzw. features Entscheidungen abzuleiten, die dann zum richtigen Ergebnis führen (im Mittel auf den Trainingsdaten). Beispiele dafür in unserem Fall wären Statements wie

• Wenn $x<-0.5$, dann ist das Klasse 0
• Wenn $x>0.5$, dann ist das Klasse 1
• Wenn $-0.5<x<0.5$ und $y>1$, dann ist das Klasse 0
• usw.

Jetzt aber zum konkreten Aufruf für das Training. In Scikit-Learn sind alle Algorithmen fix und fertig implementiert, sodass man sie im Prinzip nur starten muss. Dazu muss man meist eine Instanz einer Klasse erzeugen, die wir im Allgemeinen dann direkt als “Modell” bzw. model bezeichnen, und dann dafür einen “Fit” aufrufen, womit das Training gemeint ist.

10.5 Supervised Learning: Überprüfen der Genauigkeit der Vorhersagen des Machine-Learning-Modells¶

Als nächstes wollen wir nun wissen, wie gut unsere Vorhersagen quantitativ sind. Dazu vergleichen wir die Output-Labels des Modells mit den tatsächlichen Labels des Test-Sets. Dafür gibt es in Scikit-Learn mehrere sogenannte _metrics_, die wir ebenfalls einfach aufrufen können, z.B. _accuracy_, das ist im Wesentlichen der Anteil der korrekten Vorhersagen an allen Vorhersagen.

Ist das jetzt gut oder nicht? Erinnern wir uns, dass die Hälfte der Daten Klasse $0$ ist, die andere Hälfte Klasse $1$. Das bedeutet, dass ein rein zufälliges Raten zu $50$ Prozent Genauigkeit führen müsste. Checken wir das einmal kurz ganz einfach, indem wir zufällig gewählte Klassen-Indizes mit den Test-Labels vergleichen:

Das ist tatsächlich in der Nähe von $50$ Prozent. Die Abweichung kommt daher, dass wir hier mit $100$ Testdaten arbeiten, und das vergleichsweise wenige sind, sodass eine solche Abweichung vorkommen kann. Dagegen kann man allerdings die Qualität des Decision Trees nicht von vornherein einschätzen. Vielleicht können wir den ja noch etwas besser machen.

10.6 Verbessern eines Machine-Learning-Modells beim Supervised Learning durch Verändern der Parameter am Beispiel Decision Tree¶

In der folgenden Zelle kommt ein Aufruf, der zu einem weiteren Modell, model1, führt. Dabei werden wir die Struktur eines Decision Trees intuitiv etwas besser kennen lernen. Ein solcher Baum hat eine oder mehrere Verzweigungen, die zu weiteren Verzweigungen (in einer bestimmten Anzahl von Ebenen) oder “Blättern” führen können. Alle diese Teile heißen auf englisch nodes.

Man kann nun den Baum auf ein paar Arten einschränken, sodass z.B.:

• Eine maximale Anzahl von Blättern erlaubt ist
• Eine maximale Anzahl von Verzweigungs-Ebenen erlaubt ist

Diese beiden Parameter werden wir nun bei der Erzeugung der Instanz mit übergeben und so unseren Baum einschränken. Keine Sorge, sie werden gleich sehen, was das bedeutet und wie sich der Baum verändert, denn wir können ihn mit Hilfe einer plot_tree Funktion auch gleich visualisieren.

Grundsätzlich gilt, dass ein Baum nicht mehr Blätter haben kann, als seine Verzweigungen zulassen, die jeweils immer nur von einem node in der höheren Ebene zu zwei nodes in der darunter liegenden Ebene führen können. Bei Einer Ebene kann es also maximal zwei Blätter geben, bei zwei Ebenen vier Blätter, etc. Daher können wir die max_leaf_nodes auf eine größere Zahl setzen, z.B. auf $10$, und dann wird die maximale Anzahl der Ebenen im Wesentlichen bestimmen, wie viele Nodes und Ebenen wie verwendet werden.

Fangen wir mit einer Ebene an und gehen wir dann einfach mit dem Parameter max_depth immer höher. Diese Zellen setze ich hier einfach mehrfach untereinander

Die Relation in der ersten Zeile des Verzweigungsnodes ist die Bedingung, nach der die Datenpunkte aufgeteilt werden. Die Anzahl der aufgeteilten Punkte steht dann jeweils in den Nodes in der darunterliegenden Ebene. “gini” ist das Entscheidungskriterion, um eine optimale Bedingung zu finden. Konkret ist es ein Maß für die “Unterschiedlichkeit” in der Gruppe von Datenpunkten, sollte also idealerweise möglichst klein sein. Und im Array “value” finden sich die Anzahlen für die Klassenanteile der Daten in dieser Gruppe/diesem Node.

Weiter geht es mit einer Subebene mehr:

Hier kann man sich sehr schön die Entwicklung der Bäume mit immer mehr Unter-Ebenen ansehen. Ebenso schön sieht man, wie der Baum versucht, die Datenpunkte möglichst gut und clever aufzuteilen, und wie manche der Blätter-Nodes sogar schon eine 0 auf einer Seite der “values” stehen haben. Was ist aber jetzt eigentlich mit der Genauigkeit insgesamt passiert? Sehen wir nach:

Bereits bei der Einschränkung auf eine Ebene hatte sich der Wert der accuracy etwas verschlechtert, und dann bei zwei Ebenen nochmal. Bei drei Ebenen und dann auch bei vier Ebenen ist der Wert der accuracy allerdings wieder besser geworden, d.h., wie der Baum aussieht, spielt hier eine Rolle. Aber Achtung: Wie gut der Baum performt, kann von verschiedenen Dingen abhängen:

• Von dem Datensatz, der untersucht wird
• Von der Ausgeglichenheit des Datensatzes
• Von der (zufälligen) Aufteilung in Training und Test

Wenn sich davon etwas ändert, z.B. die Train-Test-Aufteilung, dann kann die Performance-Kurve für unsere Daten und für die gewählten Parameter durchaus anders aussehen und auch umgekehrte Trends aufweisen.

Kommen wir aber nochmal zum Anfang zurück: Da wir dort (ohne Optionen im Aufruf) ja im Prinzip den besten Performance-Wert erhalten hatten, stellt sich die Frage:

Was haben wir denn da dann ursprünglich eigentlich für einen Baum verwendet? Hier ist er:

Insgesamt sieht man hier, dass Supervised Learning viel mit Verständnis der Situation, der Daten, des Modells, dessen Möglichkeiten und der Hintergründe zu tun hat. Insgesamt ist hier auf jeden Fall die eigene Erfahrung wesentlich, denn nur über solche Dinge nachzulesen hilft für viele Probleme nicht weiter.

Damit Sie selbst gleich ein Bisschen Erfahrung sammeln können, kommen wir daher jetzt zur Übungsaufgabe dieser Einheit:

10.7 Übungsaufgabe: Experimentieren mit Supervised-Learning Algorithmen aus der Scikit-Learn Package¶

Nach dieser Einführung wissen Sie folgendes:

• Wie ein Datensatz beim Supervised Learning strukturiert ist
• Wie man einfache Datensätze zum Trainieren in Python mit Scikit-Learn erzeugen kann
• Wie Supervised Learning grundsätzlich abläuft
• Wie Sie einfache Modelle mit Scikit-Learn trainieren
• Wie Sie mit einem trainierten Modell Vorhersagen machen
• Wie Sie die Qualität einer Vorhersage auf einem Test-Set überprüfen
• Wie Sie Ergebnisse und andere hilfreiche Informationen visualisieren können

Diese Vorgehensweise ist immer die gleiche. In Scikit-Learn ist auch die grundsätzliche Code-Struktur immer gleich. Wenn Sie also eine Instanz eines Machine-Learning-Modells erzeugt haben, dann funktioniert das Training und die Vorhersagen immer gleich. Alles, was Sie austauschen müssen, sind die Modell-Aufrufe (und die eventuell damit verbundenen Parameter).

Gehen Sie nun in der Scikit-Learn-Übersicht für Supervised Learning auf die Suche nach weiteren interessanten Algorithmen, die Sie gerne auf unseren Datensatz loslassen würden. Oder erzeugen Sie einen eigenen Datensatz nach Ihren Wünschen und experimentieren Sie damit. Ich wünsche viel Vergnügen!

Hier schon mal ein paar Zeilen als Inspiration/Start, denn die Möglichkeiten sind sehr vielfältig und umfangreich (damit könnten wir mehrere zusätzliche Lehrveranstaltungen füllen).

9 Unsupervised Machine Learning: Clustering von Daten¶

In dieser Einheit Beschäftigen wir uns mit einer interessanten Methode, um Daten zu “ordnen”, dem Clustering. Damit tauchen wir ein Stück in das Gebiet des Machine Learnings ein, genauer gesagt, gehört dieser Ansatz zum sogenannten “unsupervised learning”. Das bedeutet, dass man über den Datensatz nicht allzuviel wissen muss, um ihn in Kategorien (bzw. Cluster) einteilen zu können oder ihn besser verstehen zu lernen.

Allerdings ist auch nicht von vornherein klar, dass es eine Struktur in den Daten gibt, die eine signifikante Bedeutung hat. Damit Sie das besser verstehen, sehen wir uns am besten gleich ein Beispiel an. Ich habe diemal wieder ein Stück aus einem Dataset von kaggle.com vorbereitet. Genauer gesagt, von der folgenden Quelle: https://www.kaggle.com/datasets/grisme/hourly-snapshots-of-lightning-network Nehmen Sie eine beliebige CSV Datei aus dem Unterordner “nodes” des Datensatzes (wir verwenden hier _2019_12_11_16_0537.csv) und benennen Sie diese entsprechend auf ‘lightning_strokes.csv’ um. Im Moodle finden Sie dieses Beispiel fertig zum Download, sodass Sie sich nicht das gesamte Dataset herunterladen müssen.

Hier aber zunächst noch die Imports für heute:

9.1 Was ist bzw. macht ein Clustering-Algorithmus eigentlich?¶

Bevor wir uns jetzt ans Clustering machen, möchte ich noch eine Runde erklären, was das eigentlich kann und tun soll. Dadurch wird sich auch die Frage beantworten, die ich gerade vorher im Kommentar gestellt habe, nämlich: Werden diese Daten sich fürs Clustern eignen?

Ein Clustering-Algorithmus teilt einen Datensatz in Gruppen ein. Das passiert auf der Basis der Eigenschaften der Daten untereinander, z.B. wie “benachbart” sie sind (was auch immer das dann im Detail heißen mag). Wenn wir Daten haben, die 2-dimensionalen Koordinaten entsprechen (so wie in unserem Beispiel), dann ist die Sache recht anschaulich. Das werden wir hier also auch so verwenden und uns ansehen. Das muss aber nicht so sein. Sie können Daten verwenden, für die eine Ähnlichkeit recht umständlich definiert ist, oder sogar erst definiert werden muss.

Für das Clustering selbst (also die Gruppeneinteilung von Daten) gibt es verschiedene Algorithmen, die verschiedene Parameter für das Gruppieren nutzen. Lassen Sie uns also zunächst einmal diese Parameter kurz durchsehen:

• Die Anzahl der gewünschten/vermuteten Cluster: Manche Algorithmen, wie z.B. K-Means (siehe weiter unten) verlangen die Festlegung auf eine bestimmte Anzahl von Clustern von vornherein. Das bedeutet, man legt z.B. 3 Cluster fest, clustert dann die Daten so und sieht (bzw. kann berechnen), wie gut diese Wahl gepasst hat.
• Ein bestimmter Abstand, den die Elemente maximal haben dürfen, um zum gleichen Cluster zu gehören, oder etwas Derartiges. Das kann ein einzelner Abstand oder ein gemittelter sein, je nachdem. So etwas setzt auch voraus, dass man zumindest irgendeine Ahnung von der ungefähren Dimension so eines Clusters hat.
• Die Art der Daten und zwar entweder absolute Koordinaten oder Distanzen: Manche Algorithmen brauchen gar keine absoluten Distanzen, um ein Clustering berechnen zu können, sondern nur die Distanzen zwischen allen Elementen der Daten. Das Agglomerative Clustering, das wir uns gleich ansehen werden, ist so ein Algorithmus. Diese Variante (nur Distanzen) kann ziemlich praktisch sein, vor allem dann, wenn man die Abstandsmessung, die man zur Verfügung hat, nicht so einfach in koordinaten umsetzen kann. Denken Sie z.B. an eine Sequenzähnlichkeit von Buchstabenketten oder DNA.
• Die Art, wie die Distanzen berechnet werden: Z.B. kann man immer die kleinste Distanz eines Elements zu einem bereits bestehenden Cluster nehmen, oder die gemittelten Distanzen des Elements zu allen Elementen eines bestehenden Clusters, oder dergleichen mehr.

Insgesamt läuft es darauf hinaus, dass man, je nach Algorithmus, die eine oder andere Vorgabe machen muss, damit der Algorithmus arbeiten kann. Andere Parameter kommen jeweils dann als Resultat heraus oder kommen nicht vor.

Wir sehen uns jetzt drei verschiedene Algorithmen nacheinander an, die etwas verschieden funktionieren. Mit jedem davon könnten wir viel mehr Zeit verbringen, die wir allerdings nicht haben. Daher erkläre ich jeweils nur kurz das Grundprinzip, zeige Ihnen den grundlegenden Aufruf aus der Package Scikit-Learn, und wir vergleichen den Output für jeweils einen zentralen Parameter.

Aber keine Sorge: In der Übungsaufgabe sind Sie dann wieder zum Experimentieren mit dem Clustering dieser Daten aufgerufen.

9.2 Der Algorithmus Agglomerative Clustering, kurz und einfach erklärt, mit Beispiel¶

Agglomeratives Clustering wird auch als “hierarchisches” Clustering bezeichnet. Warum, das ergibt sich aus der Funktionsweise. Die Schritte bei dieser Art des Clusterings ist wie folgt:

• Die Distanzen zwischen allen Datenpunkten werden berechnet (oder sie sind anstelle von absoluten Koordinaten bereits gegeben, siehe oben)
• Die beiden Datenpunkte mit der kürzesten Distanz werden zu einem Cluster kombiniert.
• Dieser Cluster wird entweder durch alle seine Mitglieder repräsentiert und deren Koordinaten bleiben für Vergleiche verfügbar, oder er bekommt eine zentrale Koordinate zugewiesen
• Für den neuen Cluster werden alle Distanzen zu den anderen Punkte im Datensatz berechnet
• Die beiden Datenpunkte (inklusive des neuen Clusters) mit der kürzesten Distanz werden wieder zu einem neuen Cluster kombiniert.
• Das kann so vor sich gehen, dass entweder der erste Cluster wächst oder ein separater neuer Cluster aus zwei einzelnen Datenpunkten entsteht und der erste Cluster unverändert bleibt.
• Dieser Vorgang wiederholt sich so oft, bis alle Punkte Clustern zugeordnet sind.
• Das führt letztendlich dazu, dass am Ende alle Daten in einem riesigen Cluster landen, dass allerdings gleichzeitig die Hierarchie innerhalb des Clusters über einen Baumgraphen klar ist
• Wenn man tatsächlich mehrere Cluster erhalten möchte, dann muss man mit dem Kombinieren aufhören, bevor alles in einem Cluster landet. Das geht entweder über eine Maximale Distanz, bei der aufgehört wird, oder über eine bestimmte Anzahl von Clustern, die man haben möchte, und bei der dann aufgehört wird.

Insgesamt ist diese Methode sehr mächtig. Wir sehen uns jetzt einmal konkret an, was Agglomeratives Clustering aus unseren Beispieldaten macht. Der Grundaufruf der Klassen aus Scikit-Learn ist immer der gleiche: Wir generieren eine Instanz der Klasse soundso und davon holen wir uns dann die sogenannten “Labels”, d.h. die Zahlen, die für jedes Element im Datensatz die Clusterzugehörigkeit anzeigen. So sieht das aus:

So stellt sich der Algorithmus also die Daten in 4 Clustern vor. Das kann man jetzt gut finden oder auch nicht, aber damit geben wir uns natürlich nicht zufrieden. Daher lassen wir einen Loop über verschiedene Anzahlen von Clustern laufen und sehen uns die Ergebnisse nebeneinander an. Dabei zeigt ein Colorbar an der Seite jeweils an, wie die Farben zu den Nummern der Cluster gehören.

9.3 Der Algorithmus DBSCAN, kurz und einfach erklärt, mit Beispiel¶

Als nächste Möglichkeit sehen wir uns einen Algorithmus an, der als DBSCAN bekannt ist. Diese Abkürzung steht für Density-Based Spatial Clustering of Applications with Noise, und das funktioniert wie folgt:

• Der Algorithmus durchsucht die Datenpunkte der Reihe nach, und klärt für jeden Datenpunkt, ob er ein core-sample ist
• Ein core-sample ist dadurch gekennzeichnet, dass es von einer bestimmten Anzahl anderer Samples höchstens einen bestimmten Abstand hat.
• Durch dieses Konzept der mindestens soundsoviele Punkte mit höchstens diesem Abstand voneinander wird eine Dichte beschrieben (daher density-based)
• Ein Cluster besteht dann in diesem Fall aus einer zusammenhängenden Menge von core-samples und allen Punkten, die von einem dieser core-samples höchstens den vorbestimmten Abstand haben (die selber aber keine core-samples sind, weil sie am Rand eines Clusters liegen, bzw. dort, wo er “weniger dicht” wird).
• Alle Punkte, die nicht innerhalb des vorgegebenen Abstands zu einem core-sample liegen, werden als Ausreißer bzw. Noise (Rauschen) gewertet und bekommen einen extra Label zugewiesen
• Kritische Parameter hier sind also:
  • Der Abstand, der die Dichte bestimmt, und
  • Die minimale Anzahl von Punkten, die es braucht, um core-samples zu finden

Schauen wir uns zunächst einmal von einem solchen Clustering den Output an:

Jetzt können wir natürlich auch hier einen Loop laufen lassen, der uns mehrere Darstellungen unseres Datensatzes mit verschiedenen Parametern zeigt. Am wichtigsten ist hier der voreingestellte Abstand, weshalb wir diesen über Werte in einer Liste variieren werden.

In den Figuren, die im Folgenden erzeugt werden, sehen Sie an der Seite wieder das Colorbar. Dort können Sie auch anhand der Skala sehen, wie viele Cluster jeweils erzeugt wurden.

Hier sieht man deutlich den Effekt der verschieden eingestellten Abstände. Bei kleinen Werten ergeben sich teils seltsame Muster. Erst bei mittelgroßen Werten erscheint das Clustering auch auf den ersten Blick sinnvoll. Bei zu großen Werten landen wieder alle Punkte in einem einzigen Cluster.

Was man ebenfalls anhand des Colorbars schön sehen kann, sind die jeweils als “Ausreißer” bzw. “Noise” eingestuften, ganz dunkelblauen Punkte.

9.4 Der Algorithmus K-Means, kurz und einfach erklärt, mit Beispiel¶

Als letzten Cluster-Algorithmus sehen wir uns noch einen sehr gebräuchlichen an, nämlich k-means. Dieser Algorithmus setzt ein Prinzip um, das uns vielleicht im Vergleich mit den beiden bisher erklärten noch etwas intuitiver erscheint, was nämlich die Bildung und Definition der Cluster betrifft. Hier sind die Eckpunkte von k-means:

• Die Anzahl $N$ der Cluster muss bei diesem Algorithmus vorgegeben werden und ändert sich auch während der Laufzeit des Algorithmus nicht.
• Der Datensatz wird in $N$ Cluster eingeteilt.
• k-means geht grundsätzlich von Daten auf der Basis von Koordinaten aus. Vorberechnete Differenzen nimmt er nur mit einigen Modifikationen an.
• Für jeden Cluster wird ein sogenanntes “Centroid” berechnet, also das Clusterzentrum. Zu beachten ist, dass das Clusterzentrum im Allgemeinen nicht einem der Datenpunkte im Datensatz entsprechen wird (also quasi ein extra-Punkt ist, der sich im Laufe der Zeit ändert).
• Diese Clusterzentren werden nun so optimiert, dass jeder Datenpunkt zu jenem Cluster gehört, dessen Centroid er am nächsten liegt.
• Das führt zu einer Optimierung der Varianz der Abstände der Datenpunkten zum Centroid in jedem Cluster
• Bei der Optimierung werden im wesentlichen zwei Schritte ausgeführt:
  • Zuordnung jedes Datenpunkts zum nächsten Centroid
  • Neuberechnung der Centroiden auf der Basis dieser Zuordnung
• Die wiederholte Ausführung dieser beiden Schritte wird bei Konvergenz der Centroiden-Positionen abgebrochen

Sehen wir uns das jetzt einmal in der Praxis an. Der Parameter, den wir hier variieren werden, ist wieder die Anzahl der Cluster.

9.5 Übungsaufgabe: Experimentieren mit Clustering-Algorithmen¶

Die heutige Übungsaufgabe lautet: Experimentieren mit Cluster-Algorithmen, und zwar sowohl mit denen, die wir bereits verwendet haben, als auch mit weiteren, wenn Sie möchten. Spielen Sie mit den Parametern und stellen Sie diese so ein, dass Sie die Resultate gut interpretierbar finden würden.

Als weiterer Schritt (optional) bietet sich an, noch weitere Clustering-Algorithmen zu testen. Gehen Sie dazu auf die Überblicksseite für Clustering bei Scikit-Learn und suchen Sie sich etwas aus, von dem Sie glauben, dass es besonders gut zu unserem Datenbeispiel passt.

8. Monte-Carlo-Methoden, Teil 2 – Monte-Carlo-Integration, Teil 2 und Random Walk¶

Im vorangegangenen Notebook haben wir uns mit Monte-Carlo-Methoden im Allgemeinen beschäftigt. Am Ende der Einheit haben wir außerdem das Konzept der Monte-Carlo-Integration gestreift, und zwar mit der Berechnung einer Näherung der Zahl $\pi$ über zufällig verteilte Punkte auf dem Einheitsquadrat. Das ist jedoch nicht die typische Art und Weise, Monte-Carlo-Integration zu betreiben.

Obwohl man mit einer Integration die Fläche unter der Kurve einer Funktion berechnet, ist das komplett analoge Beispiel mit der Berechnung von $\pi$ unter der Kurve des Viertelkreises, der im Einheitsquadrat eingeschrieben ist, tatsächlich mehr ein anschauliches Beispiel für eine MC-Simulation. Die MC-Integration verwendet allerdings meist ein anderes Prinzip.

8.1 Das Integral als Erwartungswert über eine Zufallsvariable¶

Konkret haben wir in der vergangenen Einheit den Wert des folgenden Integrals simuliert: $$4\int_0^1 dx \sqrt{1-x^2}$$ Das Resultat war eine Näherung der Zahl $\pi$, eine Fehlerabschätzung inklusive (weil wir mehrere Samples verwendet haben. Muss man das Integral allerdings tatsächlich so umständlich berechnen (also viele Punkte auf die ganze Fläche werfen, dann bestimmen welche unter dem Funktionswert liegen und welche darüber, alles abzählen und das Verhältnis bilden) oder geht das einfacher?

Es geht tatsächlich einfacher. Der Trick ist, das Integral, das wir gerade aufgeschrieben hatten, als Erwartungswert einer Funktion zu interpretieren. Um das noch etwas besser zu sehen, schreiben wir das Integral nochmals auf, und zwar zunächst einmal so: $$\int_{x_{min}}^{x_{max}} dx h(x)$$ Wir haben hier noch nicht viel gemacht, außer die Integrationsgrenzen mit zwei Variablen zu benennen, die Funktion allgemein als $h$ zu bezeichnen und den (irrelevanten) Vorfaktor wegzulassen. Der nächste Schritt ist allerdings der wesentliche. Wir schreiben das gleiche Integral jetzt als: $$\int_{x_{min}}^{x_{max}} dx f(x) g(x)$$ Auch das ist keine Hexerei, denn wir haben einfach nur die Funktion $h$ als ein Produkt von zwei anderen Funktionen $f$ und $g$ geschrieben. Warum ist das jetzt so viel besser als vorher?

Die Antwort auf diese Frage ist, dass uns nun die Interpretation als Erwartungswert leichter fällt. Sagen wir, $f$ sei eine Funktion, von der wir den Erwartungswert berechnen. Und $g$ ist eine Wahrscheinlichkeitsverteilung, und zwar der Zufallsvariablen $x$, deren Werte zwischen ${x_{min}}$ und ${x_{max}}$ liegen. Dann definiert dieses Integral tatsächlich den Erwartungswert der Funktion $f$ über die $g$-verteilte Zufallsvariable $x$.

Alles schön und gut, aber wie veranstalten wir damit nun eine MC-Integration?

8.2. Näherung des Erwartungswerts durch Sampling¶

Wir nähern das Integral, also den Erwartungswert durch Sampling der Zufallsvariablen $x$. Konkret müssen wir dazu folgendes tun:

• Den eigentlichen Integranden in ein Produkt von zwei Funktionen $f$ und $g$ zerlegen
• Eine der beiden (in unserem Beispiel $g$) als Wahrscheinlichkeitsverteilung interpretieren (und verwenden können)
• Wir sampeln $N$ Werte $x_i$ für $x$, und zwar aus der Verteilung $g$
• Wir bestimmen die Summe $$\frac{1}{N} \sum_{i=1}^N f(x_i)$$
• Wir betreiben wieder Statistik mit mehreren Samples und bestimmen Mittelwerte und Standardabweichung

Soweit, so gut. Sehen wir uns jetzt nochmals das Integral an, das zum Wert von $\pi$ führt: $$4\int_0^1 dx \sqrt{1-x^2}$$ Hier kann man z.B. einfach $f(x)=\sqrt{1-x^2}$ und $g(x)=1$ (also gleichverteilte Zufallszahlen) nehmen. Somit ergibt sich für die Näherung des Integrals die Summe $$\frac{1}{N} \sum_{i=1}^N \sqrt{1-x_i^2}$$ mit gleichverteilten $x_i$.

Probieren wir das mal aus.

8.3 Näherungswert für $\pi$, revisited¶

Zunächst lohnt es sich, der Übersichtlichkeit halber ein paar Schritte des Prozesses als Funktionen zu definieren. Die Schritte, die wir hier machen, sind:

• Die Funktion, um die es geht
• Die Summe (eigentlich der Mittelwert) als Näherung des Erwartungswertes
• Das Wiederholen des Aufrufs für mehrere Samples und die damit verbundene Statistik

Was wir hier nicht als Argument einer Funktion einbauen, ist die spezifische Wahrscheinlichkeitsverteilung, die wir verwenden wollen. Die Gleichverteilung wird stattdessen erstmal fix eingebaut.

Als nächstes können wir nun diese Funktionen zusammensetzen und damit eine Simulation bzw. Integration starten. Die Ergebnisse sehen wir uns in Abhängigkeit von der Anzahl der verwendeten Punkte pro Summe bzw. Erwartungswert an. Nachdem der Loop durchgelaufen ist, werden auch noch die Ergebnisse entsprechend ausgegeben.

8.4 Verwendung der Wahrscheinlichkeitsverteilung¶

Bisher haben wir noch nicht wirklich Gebrauch von der Möglichkeit gemacht, die Wahrscheinlichkeitsverteilung eigentlich ziemlich beliebig aus dem Integral zu separieren. Aber auch dafür wollen wir uns jetzt ein Beispiel ansehen. Dabei geht es um das Integral $$\int_0^\infty dx\; x^3 e^{-x^2}$$

Um es zu mit MC-Integration zu berechnen, nehmen wir es wie folgt auseinander: $f(x)=x^3$ und $g(x)=e^{-x^2}$. Dabei stellen wir fest, dass $g$ noch nicht ganz einer Wahrscheinlichkeitsverteilung entspricht. Genauer gesagt, hat eine Normalverteilung mit Mittelwert $0$ die folgende Form $$\frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{x^2}{2\sigma^2}}$$ Ein anderes Problem ist, dass wir nur eine Seite der Normalverteilung brauchen, weil das Integral von $0$ bis $\infty$ reicht. Wir nehmen also stattdessen die sogenannte Halbnormalverteilung der Form $$\frac{\sqrt{2}}{\sigma\sqrt{\pi}} e^{-\frac{x^2}{2\sigma^2}}$$

Damit das zusammenpasst, müssen wir also $\sigma=1/\sqrt{2}$ setzen, und es ergibt sich die Verteilung $$\frac{2}{\sqrt{\pi}} e^{-x^2}$$ Damit haben wir also als korrekte Zerlegung $f(x)=\frac{\sqrt{\pi}}{2} x^3$ und $g(x)=\frac{2}{\sqrt{\pi}} e^{-x^2}$ gefunden. Und damit ergibt sich für die Näherung des Integrals die Summe $$\frac{1}{N} \sum_{i=1}^N \sqrt{\pi}x_i^3 / 2$$ mit halbnormalverteilten $x_i$.

Zur Kontrolle sehen wir uns einmal das Integral an, wie SymPy es berechnet:

Als nächstes machen wir nun die numerische Abschätzung via MC-Integration. Dafür habe ich von oben nochmal die entsprechenden Zellen kopiert und die Funktion angepasst, sowie die Wahrscheinlichkeitsverteilung ausgetauscht.

Mit dieser Technik lassen sich im Prinzip beliebige Integrale numerisch nähern. Was wir hier nicht gemacht haben, was aber diesbezüglich wichtig ist: Die Methode funktioniert nicht nur genauso gut in mehr als einer Dimension, sie ist sogar besonders effizient, je höher die Anzahl der Dimensionen wird. Dazu noch ein Detail, das Sie sich gut merken können (auch, weil wir es in der vergangenen Einheit explizit gezeigt haben):

Der Fehler bei der Monte-Carlo-Integration skaliert wie der Kehrwert der Wurzel aus $N$, der Anzahl der verwendeten Punkte bzw. der Sample-Größe. Dieser Wert hängt nicht von der Dimension des Integrals ab, während das für andere numerische Integrationsmethoden sehr wohl der Fall ist (z.B. für Gauss-Quadratur-Verfahren muss man eine Anzahl Integrationspunkte in jeder Dimension festlegen). Wenn Sie sich also nur eine Eigenschaft bei Monte-Carlo-Methoden merken, dann merken Sie sich das:

Der Fehler skaliert wie $\frac{1}{\sqrt{N}}$.

8.5 Komplexeres Beispiel für Monte-Carlo-Simulation: Random Walk¶

Nachdem Sie nun mit der spezifischen Technik der MC-Integration vertraut sind, wenden wir uns wieder der allgemeinen Simulation zu. Insbesondere sehen wir uns ein Problem an, dem Sie vielleicht auch einmal im echten Leben begegnen werden: Dem Random Walk.

Damit ist folgendes gemeint: Wir stellen uns folgende Situation bzw. folgendes System vor:

• Ein Mensch/Hund/Roboter, nennen wir ihn “agent”, kann Schritte ausführen
• Die Schritte können in der Größe fixiert sein, oder durch eine Wahrscheinlichkeitsverteilung bestimmt werden
• Die Richtung eines Schrittes kann ebenfalls eingeschränkt sein (z.B. entlang der Koordinatenachsen auf einem Gitter) oder in beliebiger Richtung ausgeführt werden können
• Die Richtung wird für jeden Schritt zufällig über eine Wahrscheinlichkeitsverteilung gewählt
• Jeder Schritt wird von der Position ausgeführt, an der der vorige Schritt geendet hat
• Die Bewegung, die so entsteht, ist ein zusammenhängender Weg
• Simuliert man viele solcher Wege, dann erhält man verschiedene Informationen, wie immer über die statistische Auswertung der Ergebnisse

Somit haben wir das Grundgerüst, das eigentlich sehr übersichtlich und ziemlich geradlinig ist. Deshalb wollen wir uns das gleich einmal konkret ansehen.

Nachdem die Funktion für einen Schritt in mehreren Walks definiert ist, werden wir nun eine Runde von Walks laufen lassen. Dafür brauchen wir jeweils eine Anzahl von Schritten und Walks, und dann einen Loop, bei dem die Schritte ausgeführt und die Positionen mitgeschrieben werden.

Nachdem wir jetzt die Daten erzeugt und auch bereits visualisiert haben, wollen wir sie noch etwas auswerten. Dafür können wir einfach das NumPy-Array mit den Positionen verwenden und bestimmte Dinge berechnen (und dann ebenfalls grafisch darstellen). Interessant sind z.B.

• Mittlere Entfernung vom Ursprung in Abhängigkeit von der Anzahl der Schritte
• Maximale Entfernung vom Ursprung in Abhängigkeit von der Anzahl der Schritte
• Richtung am letzten Punkt im Walk

Sehen wir uns das alles einfach der Reihe nach an:

8.6 Übungsaufgabe: Experimentieren mit dem Random Walk¶

Für die Untersuchungen von Random Walks gibt es viele Möglichkeiten. Experimentieren Sie nun mit diesem Problem. Kopieren Sie den Code von oben und testen Sie je nach Zeit und Möglichkeit (und unter anderem, je nachdem, was Sie sonst noch alles verändern möchten) folgende Änderungen/Szenarien:

• Ändern Sie die Schrittweite auf eine andere Konstante. Was passiert?
• Wählen Sie die Schrittweite zufällig aus einer Wahrscheinlichkeitsverteilung Ihrer Wahl. Was passiert?
• Verpassen Sie dem Random Walk eine “Schlagseite” (“Biased Random Walk”), d.h. machen Sie z.B. die Schrittweite von der Richtung abhängig. Was passiert?
• Schränken Sie die Richtung auf ein Gitter ein (also die Richtung auf z.B. die 4 Winkel 0, 90, 180, 270 Grad). Was passiert?
• Erhöhen Sie die Anzahl der Schritte und beobachten Sie die Werte für mittlere und maximale Distanz vom Ursprung. Können Sie eine bestimmte Abhängigkeit dieser Größen von der Anzahl der Schritte feststellen?

7 Monte-Carlo Methoden – Simulation und Integration¶

In diesem Notebook beschäftigen wir uns mit den sogenannten Monte-Carlo Methoden. Im wesentlichen handelt es sich dabei um einen Satz von Methoden, die verschiedene Situationen mit Hilfe von (Pseudo-)Zufallszahlen simulieren oder verschiedene Größen auf diese Art berechnen helfen.

Recht bekannt ist die Monte-Carlo Integration, mit der wir uns im zweiten Teil dieser Einheit beschäftigen werden. Zunächst sollen Sie allerdings eine allgemeinere Einführung in die Anwendung von Monte-Carlo Methoden bekommen, denn die Monte-Carlo Integration ist eher als Spezialfall anzusehen.

7.1 Allgemeine Strategie einer Monte-Carlo Simulation¶

Die allgemeine Strategie einer MC-Simulation ist eigentlich recht simpel und geradlinig: Man nehme eine interessante Situation/Fragestellung, deren Regeln man kennt, setze diese in einem Computerprogramm um, lasse dieses Programm einige (viele viele) Male laufen, und werte die Ergebnisse statistisch aus.

Was das Wort “statistisch” hier soll, dazu kommen wir gleich noch. Aber grundsätzlich würde es für eine super-brutale erste Näherung auch genügen, das Programm nur einmal laufen zu lassen. Dann hätte man ein Ergebnis, mit dem man de facto auch bereits einen Teil der Antwort auf die Fragestellung bekommt, aber eben nur einen Teil.

Und zwar deshalb, weil in einer MC-Simulation der Zufall (bzw. Pseudozufallszahlen) eine große Rolle spielt. Somit ist das eine Ergebnis, das man bekommen hat, eben auch nur ein möglicher Ausgang der Situation, mit der man sich befasst. Was sonst noch alles passieren kann, das kommt erst ans Licht, wenn man das Programm eben sehr oft laufen lässt. Zum besseren Verständnis einer ordentlichen Auswertung einer MC-Simulation kommen wir kurz zu ein paar Begriffen zurück, die uns bereits begegnet sind:

7.2 Samples, Sample-Means¶

Wir haben bereits in der vergangenen Einheit (bei der Stochastischen Optimierung) über Sampling gesprochen. Damals ging es in erster Linie darum, dass ein Sample ein Satz von Zufallszahlen ist, mit dem man irgendeine Berechnung anstellt. Im Kontext der MC-Simulation ist ein Sample jedoch noch etwas mehr, nämlich ein Teil der Simulation. Die gesamte Simulation besteht aus mehreren Samples, die kombiniert werden, um die statistische Auswertung klar zu machen. Wieso, dazu gleich mehr im folgenden Abschnitt.

Zunächst aber noch zum Mittelwert einer Größe in einem Sample. Wenn wir z.B. einen Würfel werfen (siehe auch weiter unten), dann beträgt der Mittelwert der Augen, gemessen über ein Sample, die Anzahl der im Sample geworfenen Augen durch die Anzahl der Würfe. Das ist dann das Sample-Mean. Analog kann man für ein Sample auch verschiedene andere Eigenschaften von Variablen bestimmen, wie z.B. die Standardabweichung, etc.

Das ist schon ein guter Anfang, doch es geht noch besser.

7.3 Der Zentrale Grenzwertsatz und Mean of Sample-Means¶

Der zentrale Grenzwertsatz (auf Englisch “Central-Limit Theorem”) soll uns hier nicht sehr grundlegend beschäftigen, sondern eher als Erklärung und Motivation dafür dienen, einen Satz von Samples für die Auswertung einer MC-Simulation zu verwenden.

Genauer gesagt nehmen wir die Mittelwerte einer Größe aus mehreren Samples und mitteln diese nochmals zu einem Sample-Mean. Wieso? Der Zentrale Grenzwertsatz besagt, dass für mehrere Zufallsvariablen, die der gleichen Verteilung folgen, die Verteilung der Sample-Means normalverteilt ist. Das bedeutet:

• Nimmt man ein Sample und berechnet damit einen Mittelwert, dann hat man zwar einen Anhaltspunkt für den Mittelwert der tatsächlichen zugrundeliegenden Verteilung, aber nicht mehr.
• Nimmt man die Sample-Means und berechnet deren Mean und Standardabweichung (das darf man, denn die Verteilung ist ja eine Normalverteilung), dann hat man sowohl eine bessere Näherung für den tatsächlichen Mittelwert, als auch gleichzeitig eine Abschätzung für den statistischen Fehler in der Bestimmung dieses Mittelwerts.
• Wenn man nun die Anzahl der Elemente eines Samples erhöht (also die Samplegröße), dann bekommt man grundsätzlich genauere Werte für den Mittelwert.
• Wenn man allerdings mehrere Samples verwendet, dann bekommt man eine bessere Einschätzung des Fehlers im Mittelwert.

Wir werden damit gleich experimentieren, damit Sie sehen, was gemeint ist.

7.4 Beispiel: Böse Eins¶

Als einfaches Beispiel wollen wir uns ein einfaches Würfelspiel ansehen, das mit nur einem normalen Würfel (D6) gespielt wird: Böse Eins. Die Regeln dafür, hier von SpielWiki übernommen, lauten:

Die Spieler würfeln der Reihe nach mit einem Würfel. Jeder Spieler darf fünfmal würfeln. Die Augen aus den einzelnen Würfen werden notiert. Wirft man jedoch eine Eins, werden die Augen der jeweiligen Runde ungültig. Sieger ist, wer als erster 100 Punkte hat.

Um dieses Spiel zu simulieren, lassen wir mehrere Samples von Durchläufen für das Spiel von einem Programm durchrechnen. Für die Analyse wählen wir Größen aus, die uns geeignet erscheinen, das zu erfahren, was wir wissen wollen oder was interessant scheint, z.B.:

• Was ist die durchschnittliche Punktzahl pro Spieler pro Runde?
• Nach wie vielen Runden ist ein Spiel durchschnittlich zu Ende?

Diese Größen zeichnen wir dann während der Simulation zu geeigneten Zeitpunkten auf, um am Ende dann die entsprechenden Statistiken anzufertigen. Die statistische Auswertung wird wieder zunächst über die Runs, dann innerhalb der Samples, und schließlich über die Samples gemacht, sodass wir fundierte Informationen bekommen.

Legen wir also los.

7.5 Monte-Carlo-Integration¶

An dieser Stelle möchte ich kurz auf die Monte-Carlo-Integration zu sprechen kommen. Diese ist im wesentlichen auch nichts anderes als eine MC-Simulation, nämlich eine “Simulation eines Integrals”. Das Prinzip kann man recht einfach mit der Berechnung der Zahl Pi demonstrieren, die “durchgeführt” wird, in dem man virtuelle Pfeile auf ein Dartboard wirft, genauer gesagt, auf einen Kreis, der einem Quadrat eingeschrieben ist. Sehen wir uns das gleich mal an.

Wir simulieren hier also folgenden Prozess:

• Jemand hat $N$ Pfeile (Punkte)
• Er verteilt diese zufällig auf einem Quadrat mit Seitenlänge $1$
• Diesem Quadrat ist ein Viertelkreis (macht die Sache einfacher) eingeschrieben
• Nachdem die Punkte verteilt sind, wird unterschieden und abgezählt:
  • Wie viele Punkte liegen im Viertelkreis und
  • wie viele Punkte liegen außerhalb des Viertelkreises?
• Das Verhältnis von Punkte im Viertelkreis zu Gesamtpunkte ist eine Näherung des Verhältnisses der Flächeninhalte des Viertelkreises ($1^2 \pi / 4$) zu jenem des Quadrats ($1^2=1$), also für die Zahl $\pi / 4$.
• Wenn man das statistische Verhältnis aus der Simulation also mit 4 multipliziert, erhält man eine Näherung für die Zahl $\pi$.

Und los geht’s:

7.6 Übungsaufgabe: Experimentieren mit der MC-Simulation des Wertes von $\pi$¶

Nehmen Sie nun die oben definierte Funktion für die MC-Simulation des Wertes von $\pi$ zur Hand und verändern Sie die Parameter für Anzahl der Runs und Punkte. Können Sie zeigen, dass der numerische Fehler des Means of Sample-Means wie eins durch die Wurzel aus dem Produkt dieser beiden Anzahlen skaliert?

6 Stochastische Optimierung und Genetische Algorithmen¶

In diesem Notebook wollen wir uns letztlich mit stochastischer Optimierung und genetischen Algorithmen befassen. Wir tun das zwar hauptsächlich auf einem pragmatischen Niveau, aber auch sodass wir in der kurzen Zeit bereits etwas damit anfangen können.

Zu diesem Zweck brauchen wir kurz ein paar Vorüberlegungen zu den Begriffen Zufallszahlen und Sampling (Stichproben), und zwar hauptsächlich, wie wir diese in Python bekommen und woher.

6.1 Zufallszahlen¶

Echte Zufallszahlen sind schwer zu erzeugen. Daher bedienen sich Computer-Nutzer sogenannter Pseudo-Zufallszahlen. Damit ist gemeint, dass man einen (Pseudo-Zufallszahlen-)Generator hat, der eine bestimmte Methode verfolgt, um die gewünschte Anzahl von Zahlen so zu erzeugen, dass sie möglichst gut der gewünschten Wahrscheinlichkeitsverteilung entsprechen. Sehen wir uns das gleich einmal anhand einiger Beispiele an.

Zunächst die Imports von heute:

NumPy hat ein Modul namens random, in dem man die wichtigsten Dinge finden kann, z.B.:

Zur Erinnerung: Wir können jederzeit die Eigenschaften einer so erzeugten Verteilung überprüfen, z.B. den Mittelwert und die Standardabweichung, aber auch höhere Momente wie Skewness oder NumPyKurtosis: