Institut für Informatik
Modellierung 2
Michael Wand
Ann-Christin Wörl & David Hartmann
Sommersemester 2023
Aufgabe 1: Welford-Algorithmus
Welford-Algorithmus
Gegeben Sei \(X\) eine 1-d Zufallsvariable und seien weiter \(x_1, \dots, x_n\) beobachtete Werte dieser Zufallsvariable.
Dann ist \(
\overline x_k := \frac{1}{k} \sum_i x_i
\) der Mittelwert und \(
\sigma_k := \frac{1}{k} \sum_i \left(x_i - \overline x_k\right)^2
\) die Varianz des (Teil-)Datensatzes \((x_1,\dots,x_k)\).
Erwartungswert:
Die folgende Umformung führt zu der Online-Variante dieser Berechnung: \[
\overline x_n := \overline x_{n-1} + \frac{x_n - \overline x_{n-1}}{n}.
\]
Varianz:
Ganz ähnlich lässt sich auch die online-Berechnung der Varianz herleiten: \[
\sigma_n^2 = \frac{(n-1)\sigma_{n-1}^2+(x_n - \overline x_{n-1})(x_n-\overline x_n)}{n} = \sigma^2_{n-1} + \frac{(x_n - \overline x_{n-1})(x_n - \overline x_n) - \sigma^2_{n-1}}{n}.
\] Diese Art die Varianz zu bestimmen kann jedoch zu numerischen Problemen führen — wir subtrahieren hier eine potentiell sehr kleine Zahl von einer beliebig großen Zahl. Eine numerisch stabilere Variante nutzt den linken Teil der Gleichung bzw. die Tatsache, dass die Formel der Standardabweichung die Summe aller Differenzen vom Mittelwert enthält: \[
\begin{align}
M_{2,n} &= M_{2,n-1} + (x_n - \overline x_{n-1})(x_n - \overline x_n)\\
\sigma^2_n &= \frac{M_{2,n}}{n}.
\end{align}
\]
Aufgabe
Gegeben Sei ein zufälliger 1-d Datensatz. Der Einfachheit halber nehmen wir hier eine normalverteilte Zufallsvariable \(X \sim \mathcal{N}_{0,1}\) an.
- Implementieren den obigen Welford Algorithmus zur Bestimmung der Varianz in PyTorch.
Testen Sie an einem einfachen Beispiel, dass die Berechnung korrekt ist. - Generieren Sie einen normalverteilten Datensatz & messen Sie zuerst nach, dass Mittelwert und Standardabweichung mit den Parametern der gegebenen CDF übereinstimmen.
Testen Sie auch verschiedene Parameter für Varianz und Erwartungswert und prüfen Sie ob und wann diese Methode stabilere Ergebnisse liefert als die naive Methode. - Zuletzt noch etwas anderes praktisch relevantes:
Es ist stets möglich sich die letzten \(m\) Beispiele zu merken und so eine lokale Statistik zu berechnen. Durch eine kleine Änderung in der obigen Formel des Mittelwertes ist es möglich dieses ebenfalls online zu formulieren. \[ \operatorname{EMA}_\alpha(\overline x_n) := (1-\alpha)\cdot \operatorname{EMA}_\alpha(\overline x_{n-1}) + \alpha \cdot x_n. \] Bis auf den Faktor \((1-\alpha)\) ist diese Formel identisch mit der oberen Version. Diese Änderung lässt jedoch vergangene Werte langsam verfallen.
Wie muss \(\alpha\) gewählt werden, dass der so definierte lokale Mittelwert zu 99.9% aus den letzten \(100\) Beispielen besteht?
Aufgabe 2: Ein elementarer Klassifizierer — Äpfel und Birnen Bananen vergleichen
Stellen wir uns vor, wir wurden mit der Aufgabe betraut für eine Waage im Supermarkt eine automatische Früchteerkennung zu implementieren. Zum Testen haben wir eine Hand voll Bilder erhalten, wie sie typischerweise von der Waage aufgenommen werden. In dem Archiv befinden sich 36 Bilder von Äpfeln und 35 Bilder von Bananen.
(Wir kümmern uns hier nur um den Prototypen: erkannt werden sollen nur Äpfel und Bananen. ;) )
Qualitätsmaß:
Bevor wir einen Klassifizierer testen, müssen wir vorher die Qualität eines Klassifizierers definieren. Um etwa Auswendig lernen zu verbieten teilen wir den Datensatz in zwei Teile auf (5 zufällige Bilder bilden) Test- und (die restlichen Bilder den) Trainingsdatensatz. Dabei bilden die Bilder mit ungeradem Index den Trainingsdatensatz und die mit geradem Index den Testdatensatz.
Ein Datenpunkt \((x,y)\) ist dabei stets ein Tupel, bei dem \(x\) ein Bild der Dimension \(d\) (etwa \(d = \text{Bildhöhe} \cdot \text{Bildbreite} \cdot \text{anzahl Farbkanäle}\)) ist und \(y\) die Klasse des Bildes anzeigt. In unserem Fall entspricht die Klasse Apfel dem Wert \(y=0\) und die Klasse Banane dem Wert \(y=1\).
Die Indikatorfunktion \(1_y\) bezeichne dabei die Funktion, die genau dann 1 ist, wenn sie im Wert des Subskript \(y\) ausgewertet wird. Ansonsten nimmt die Funktion den Wert 0 an. \[
1_y (x) := \left\{ \begin{matrix}
1, & \text{falls } x = y,\\
0, & \text{sonst } \phantom{x = y,}
\end{matrix} \right.
\] Den ersten Teil verwenden wir um den Klassifizierer zu „trainieren“, den zweiten Teil nutzen wir, um unser Qualitätsmaß zu testen.
Ein Klassifizierer \(f\) ist dabei besser, je höher dessen Genauigkeit (engl. accuracy) auf dem test set \(T := \left\{(x,y) | x\in \mathbb{R}^d, y \in \{0,1\}\right\}\) ist, \[
\text{accuracy}(T,f) := \frac{1}{|T|} \sum_{(x,y)\in T} 1_y(f(x)).
\] (Mit anderen Worten messen wir hier den Anteil an richtigen Klassfizierungen im Datensatz).
Implementieren Sie nun die folgenden drei Klassifizierer und testen Sie die jeweilige Qualität auf dem test-set.
- Multivariate Gaußverteilung: Als erstes Visualisieren wir den Datensatz. Bestimmen Sie dazu zu jedem Bild zuerst die mittlere Farbe \((\mu_r,\mu_g,\mu_b)\) und visualisieren Sie so alle Bilder als Punktwolke in 3d (z.B. mit Matplotlib
Axes3d.scatter).
Als nächstes bestimmen wir zu jeder Klasse die Gaußverteilung der Farbe die die wahrscheinlichste Erklärung der Klasse darstellt.
Um nun zu bestimmen zu welcher Klasse ein Bild gehört, werten wir die Wahrscheinlichkeiten der beiden Gaußverteilungen für die jeweilige Klasse aus und wählen diejenige Klasse, die eine größere Wahrscheinlichkeit für das Bild angibt. - k-Means: Als nächstes testen wir, ob die Klassenmittelwerte \(\mu_y\) einen guten Klassifizierer bilden.
Bestimmen Sie die pixelweisen Mittelwerte der beide Klassen Apfel & Banane (wenn Sie möchten kann hier durchaus Ihre implementierung des Welford-Algorithmus genutzt werden, dies ist aber nicht unbedingt nötig).
Im Gegensatz zu den Mittelwerten aus Aufgabenteil 1 erhalten Sie hier nicht 3 Werte pro Mittelwert, sondern Bilder der selben Dimension wie der Eingabebilder.
Geben Sie diese aus. Was können Sie beobachten?
Wir definieren den Klassifizierer nun so, dass für ein beliebiges Bild \(x\) die Klassie vorhergesagt wird, deren mittleres Bild \(\mu_y\) am nächsten liegt, also \[ f_1(x) := \arg\min_y ||x - \mu_y||_2. \]
- PCA (Wdh. Modellierung 1): Reduzieren Sie die Dimensionalität der Bilder mit PCA (d. h., projezieren Sie die Bilder auf die 3 Eigenvektoren mit den größten Eigenwerten). Visualisieren Sie die Verteilung der Beispiele im 3D-Eigenraum (dies ist auch eine Punktwolke, aber anders als in Aufgabenteil 1!), und versuchen Sie auch, die Eigenbilder selbst zu visualisieren. Als Klassifizierung kann hier genauso vorgegangen werden wie in Aufgabenteil 1; Gaußverteilung bestimmen und dann die wahrscheinlichste Lösung wählen.