SnAIp Part B – Unsupervised Learning in Snap!
Unsupervised Learning in Snap!
SnAIp ist ein Framework und Curriculum zur konstruktionistischen Vermittlung von maschinellem Lernen für den Unterricht. Part B beschäftigt sich mit einem der drei Paradigmen maschinellen Lernens, Unsupervised Learning:
Lernziele:
Die Schülerinnen und Schüler…
- erläutern, wie Cluster durch Unsupervised Learning Verfahren gefunden werden können.
- grenzen Unsupervised Learning von anderen Paradigmen maschinellen Lernens ab
- verwenden UL Algorithmen, um Daten in Snap! zu analysieren und zu bearbeiten.
- optimieren UL Algorithmen, um bessere Ergebnisse zu erhalten.
1. Was ist Unsupervised Learning
Um die Idee von Unsupervised Learning (zum Clustern von Daten) einzuführen, nutzen wir die Unplugged-Aktivität Goldrush. Dazu erhalten die Schülerinnen und Schüler die entsprechenden Materialien (Karte, Datenpunkte, Prototypen, Regeln). Unser Ziel ist es, mitten im amerikanischen Gold Rush basierend auf Meldungen von Goldfunden erfolgversprechende Punkte zum graben zu identifizieren.
Aufgabe:
Ihr habt drei Grabungsteams zur Verfügung, diese sind durch die Münzen visualisiert. Eure Aufgabe ist es, für jedes der Teams einen bestmöglichen Grabungsort festzulegen. Ein guter Grabungsort liegt möglichst zentral in einem Goldfeld.
Zur Verfügung habt ihr außerdem eine Reihe von Berichten über Goldfunde in Form von Kärtchen mit x- und y-Koordinate des Fundortes. Mischt diese Kärtchen und legt sie verdeckt als Stapel neben die Karte. Zieht nun immer ein Kärtchen, überlegt euch, wie ihr dieses verarbeitet, und legt es danach verdeckt auf den Ablagestapel.
Nachdem ihr alle Kärtchen verarbeitet habt, gebt für jedes der drei Grabungsteams x und y Koordinate des bestmöglichen Grabungsortes an!
Euch stehen keine weiteren Hilfsmittel zur Verfügung, insbesondere keine Stifte ;).
Die Schülerinnen und Schüler sollen sich nun selbst einen Algorithmus überlegen, mit dem die Ausgrabungsteams möglichst gute, d.h. zentral in Goldfeldern gelegene Grabungsorte wählen.
Als Abschluss erhalten die Schülerinnen und Schüler die Folie mit den eingezeichneten Datenpunkten, um die Prototypen mit den tatsächlichen Datenpunkten vergleichen zu können.
Die besten zwei Gruppen stellen ihren Algorithmus vor. Vermutlich wird dieser ähnlich zu folgendem Algorithmus sein:
- Legt 3 Münzen, die sogenannten Prototypen, zufällig auf die Karte.
-
Zieht jetzt nacheinander die Datenpunkte vom Stapel. Für jeden neuen Datenpunkt:
- Bestimmt den Prototypen, der dem Datenpunkt am nächsten liegt
- Bewegt diesen Prototypen nun die Hälfte der Entfernung zum Datenpunkt in die Richtung des Datenpunkts
Der beschriebene Algorithmus ist eine Variante des Unsupervised Learning-Verfahrens Learning-Vector-Quantification. Die Prototypen repräsentieren die gefundenen Cluster in den Daten, in unserem Beispiel also die Regionen, über die besonders viele Berichte mit Goldfunden kursieren. Gegebenenfalls können die Schülerinnen und Schüler nun noch das gegebene LVQ-Verfahren umsetzen, und mit ihrem Algorithmus vergleichen.
Anmerkung: Abhängig von der Reihenfolge, in der die Datenpunkte abgearbeitet werden, und der initialen Positionierung der Prototypen kann durchaus der Fall eintreten, dass die Prototypen auch für das LVQ-Verfahren nicht mit den Clustern in den Daten übereinstimmen. Lassen sie die Schülerinnen und Schüler in diesem Fall mit Hilfe der Lösungsfolie analysieren, warum dies der Fall ist. Dies stellt eine Grundlage für die spätere Optimierung des Algorithmus dar!
Nach Durchführung der Aktivität sollte auf Basis der Erfahrungen der Schülerinnen und Schüler die zugrunde liegende Idee von Unsupervised Learning thematisiert und ggf. von den anderen Paradigmen Supervised und Reinforcement Learning abgegrenzt werden (vgl. auch diese Darstellung aller Lernverfahren).
Unsupervised Learning zeichnet sich dadurch aus, dass im Unterschied zu Reinforcement oder Supervised Learning nur Rohdaten als Eingabe verwendet werden. Es werden weder Belohnungen (RL) noch Label (SL) durch den Benutzenden vorgegeben. Die jeweiligen Verfahren finden dann selbstständig Muster und Ähnlichkeiten in den Daten. Hierdurch können Cluster oder Ausreißer in Datensätzen gefunden werden. Typische Anwendungsfälle sind beispielsweise die “Kunden kauften auch”-Empfehlungen in Onlineshops oder die Erkennung von verdächtigem Netzwerktraffic.
Im Falle des in der Unplugged-Aktivität genutzten LVQ-Verfahrens, werden Cluster im Datensatz gefunden, indem Prototypen für die einzelnen Cluster für jeden Datenpunkt angepasst werden. Der wohl bekannteste UL-Algorithmus, “k-means”, funktioniert auf eine konzeptionell ähnliche Art und Weise.
Die Unplugged-Aktivität dient auch im weiteren Unterrichtsverlauf immer wieder als Hilfestellung, ob bei der Implementierung in Snap! oder der Analyse von Grenzfällen wie Ausreißern oder der initialen Positionierung der Prototypen und darauf aufbauend der Optimierung des Algorithmus.
Materialien
2. Unsupervised Learning in Snap!
Als nächstes wird das Goldrush-Projekt nun in Snap! umgesetzt. In der Vorlage werden bereits zufällige Cluster von Goldfunden erzeugt. Die Schülerinnen und Schüler ergänzen nun das Sprite “Prototyp” um die Umsetzung des LVQ-Algorithmus entsprechend der Regeln aus der Unplugged Aktivität:
Für jeden Datenpunkt…
- identifizieren sie dazu den nähesten Prototypen
- und bewegen ihn die Hälfte der Distanz in Richtung des Datenpunkts
In der Vorlage werden zufällig Datenpunkte erzeugt, und die Bestimmung des nähesten Prototypen ist bereits durch einen Block vorgegeben. Die Schülerinnen und Schüler müssen also lediglich die Abfrage des nähesten Datenpunkts und das Aktualisieren der Position des jeweiligen Prototypen ergänzen.
Aufgabe
Lösung
Durch die Simulation können nun deutlich größere Datenmengen verarbeitet werden, die sich in jedem Durchlauf unterscheiden. Hierzu kann nun eine Vielzahl weiterer Experimente mit dem Verfahren durchgeführt werden:
Die Anzahl der Prototypen stimmt in unserer Unplugged-Aktivität zufälligerweise mit der Anzahl der Cluster überein. Das ist hier nicht mehr der Fall! Lassen sie die Schülerinnen und Schüler mit der Anzahl der Prototypen experimentieren! Ohne mehr Wissen über die Datengrundlage und Ziele der Datenanalyse lässt sich keine fundierte Schätzung über eine optimale Wahl der Anzahl der Prototypen abgeben.
Auch hier sollte erneut die zugrunde liegende Idee von Unsupervised Learning aufgegriffen und dessen Merkmale thematisiert werden.
Einschub: InIK und eigene Daten
Alternativ können Sie die Implementierung des Algorithmus in Snap! auch auf eigenen Daten, die zuvor mit oder durch die Schülerinnen und Schülern erhoben wurden, durchführen.
Ein einfaches Beispiel dazu wäre, Breiten- und Längengrade der Wohnorte der Schülerinnen und Schüler zu sammeln, und als csv-Datei in Snap! zu importieren. Diese können nun mit Hilfe der Snap!-Bibliothek “world map” dargestellt werden. Der LVQ-Algorithmus kann nun genutzt werden, um geeignete Bushaltestellen für den Schulbus zu identifizieren, an der Implementierung des Algorithmus ändert sich dabei nichts.
Ein solches, an “Informatik im Kontext” angelehntes Vorgehen, kontextualisiert die Inhalte in der Lebenswelt der Schüler. Konzepte des Datenmanagements, wie die Erfassung, Bereinigung oder Archivierung von Daten (Data Lifecycle) sowie Methoden der Statistik und Datenanalyse, in unserem Fall Maschinelles Lernen, können hierbei aufgegriffen werden.
Materialien
- Vorlage GoldRush
- Lösung GoldRush
- Bushaltestellenprojekt
3. Wettbewerb: Algorithmus verbessern
Im nächsten Schritt kann wollen wir nun unser maschinelles Lernverfahren verbessern. Dazu bietet sich ein Wettbewerb an: Den Schülerinnen und Schülern werden Beispieldaten via csv zur Verfügung gestellt, die als Datenpunkte eingelesen und visualisisert werden.
Die Schülerinnen haben vermutlich im Rahmen der Unplugged-Aktivität und/oder der Implementierung erste Erfahrungen mit Schwächen des simplen LVQ-Algorithmus gemacht. Diese stellen nun geeignete Ausgangspunkte da. Das Material der Unplugged-Aktivität bietet sich auch für eine zunächst theoretische Analyse verschiedener Ideen zur Verbesserung an.
Mögliche Ideen zur Verbesserung des Algorithmus:
- Mehrere Iterationen des Algorithmus
- Zunehmende Abschwächung der Anpassung der Prototypen
- Prototypen erhalten jedes mal zunehmende Priorität, wenn sie nicht bewegt werden
- …
Materialien:
- Beispielhafte Optimierung
4. Mehr Dimensionen
Natürlich ist das LVQ bzw. Unsupervised Learning Verfahren nicht auf zwei Dimensionen beschränkt. Im Gegenteil, die Suche nach Clustern oder Ausreißern wird vorwiegend für Probleme mit mehr Variablen eingesetzt. Wir wollen uns nun auch von der 2D-Welt und unseren kartenbasierten Beispielen verabschieden, und damit auch von unserer Visualisierung. Folgende Projekte bieten sich dafür an:
Bildkomprimierung: Bei der Kompression von Grafikdateien werden häufig verschiedene ähnliche Farbtöne zu einer Farbe zusammengefasst, um Speicherplatz zu sparen. Wir wollen diese “ähnlichen Farben” nun mit Hilfe von LVQ bestimmen. Die drei Farbkanäle — R, G, und B — stellen unsere Dimensionen dar. In der Vorlage werden verschiedene Pixelbilder erzeugt und die Pixel in einer Liste zur Verfügung gestellt. Analog zu den Goldfunden, wird nun für jedes Pixel der näheste Prototyp bestimmt und dessen Position angepasst. Zum Abschluss wird das Bild nun komprimiert, in dem für jedes Cluster alle zugehörigen Pixel in der Farbe des Prototypen eingefärbt werden.
Die skizzierten Projekte eignen sich darüberhinaus etwa zur Thematisierung von Abstandmaßen und der Kodierung kategorialer bzw. nicht quantitativer Daten:
- Welchen “Abstand” haben Punkte im mehrdimensionalen Raum?
- Wie kodiere ich kategoriale Daten wie beispielsweise Geschlecht (m,w, d) oder Wohnsituation (Mehrfamilienhaus, Einfamilienhaus, …) zur statistischen Auswertung?
Materialien:
5. Ausblick
Gegen Ende bietet es sich an, Unsupervised Learning Verfahren abschließend mit den beiden anderen Paradigmen maschinellen Lernens, Reinforcement und Supervised Learning gegenüberzustellen. Bei Reinforcement Learning konnten wir die Güte unseres Modells darüber bestimmen, wie erfolgreich ein Agent in einem bestimmten Spiel ist. Bei Supervised Learning funktioniert das analog, wie viele Testdaten richtig bzw. falsch gelabelt werden. Während wir dort also Modelle objektiv bewerten können, ist dies bei Unsupervised Learning Verfahren schwierig. Wie sollen wir bei der Clusterung von Daten wissen, ob wir die richtigen Cluster gefunden haben? Vielleicht gibt es keine wirklichen Cluster in den Daten oder sie entsprechen nicht denen, die wir gefunden haben. Ohne das Modell in der Realität auszuprobieren, werden wir uns schwer tun, die Güte unseres Modells bewerten zu können.
Gerade daher kommt aber auch der Reiz von Unsupervised Learning: Die Algorithmen arbeiten nicht anhand von außen vorgegebener Kriterien (Labels, Belohnungsfunktion), sondern finden selbstständig Muster und Zusammenhänge in Daten, die wir Menschen so möglicherweise nie gefunden hätten!
Hinweise für Lehrkräfte
Warum LVQ?
Der Vorteil von LVQ ist die einfache Umsetzung, gerade für zweidimensionale Räume. Dabei ist LVQ konzeptionell sehr ähnlich zu den “typischen” UL-Algorithmen wie k-means, der mit Hilfe der Mittelwerte der bisherigen Cluster arbeitet (vgl. z.B. Wie Maschinen lernen).
ML und Statistik
Gerade UL-Algorithmen eignen sich um die Ähnlichkeiten von maschinellem Lernen und Statistik zu diskutieren.
Unterstützendes Material
- Goldrush Unplugged: Karte & Datenpunkte & Lösungsfolie
- Goldrush Vorlage & Lösung
- Bushaltestellenprojekt
- Beispielhafte Optimierung
- Visualisierung Bildkompression