Aufgabe 1: Generalisierung

Seien \((X_t,Y_t)\) und \((X_v,Y_v)\) zwei Datensätze. Wir wollen aus den \(X\)-Werten auf die \(Y\)-Werte schließen. Hierbei gilt \(Y_t\in \{0,1\}^n\) und \(Y_v\in \{0,1\}^m\), wir versuchen also binäre Werte vorherzusagen.

Sei nun \(A\) ein beliebiger Algorithmus der die Trainingswerte \((X_t,Y_t)\) nimmt und versucht \(Y_v\) aus \(X_v\) vorherzusagen. Er erreicht dabei eine Accuracy von \(z\%\).

Aufgaben:

• Zeigen Sie, dass ein paar an Datensätzen existiert, sodass \(A\) eine Accuracy von \((1-z)\%\) erreicht.
  Wie sehen diese Datensätze aus?
• Folgern Sie, dass \(A\) für zufällig gezogene Daten eine erwartete Accuracy von \(50\%\) hat
• Diskutieren Sie, was dies für die Auswahl eines Algorithmus für ein spezifisches Problem bedeutet.

Praxisaugabe 2: Unsupervised Learning

Sie haben in LE3 bereits mit MNIST gearbeitet. Ein etwas komplexerer Datensatz ist CIFAR-10 (einige von Ihnen hatten damals diesen stattdessen verwendet). Der Datensatz besteht aus 10 Klassen (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck) zu je \(12.000\) Farb-Bildern, wiederum jeweils bestehend aus \(28\cdot28\) Pixeln.

1. Bestimmen Sie die Entropie die in der Zufallsvariable des Labels stecken.
2. Als nächstes wollen wir die Entropie in den Pixeln der Bilder bestimmen.
   
   Wir haben bereits in der Vorlesung gesehen, dass Shannon-Entropie lediglich für diskrete Zufallsvariablen definiert ist. Glücklicherweise ist das auch hier gegeben, denn alle Klassen werden bitwertig codiert. Ziel ist es also die Bilder einzulesen und dann die bitweise Entropie zu bestimmen.
   Mit anderen Worten fassen wir die Zufallsvariable \(F\) (F, wie Fotoaparat), die ein Bild sampelt als \(28\cdot28\cdot3\cdot32\)-dimensionale Variabble auf (28 Pixel für Höhe und Breite, 3 Farben, 32 Bit).
   
   Schätzen Sie nun experimentell für jede Komponente der Zufallsvariable die Wahrscheinlichkeit für eine \(1\).
3. Wie genau ist die Schätzung bei 50.000 Bildern?
   Hinweis: Varianz der Bernoullivariable.
4. Wie hoch ist die Gesamtentropie des Pixelrauschens?
   Stellen Sie in einem Graphen dar, wie das Verhältnis der Entropien der signifikantesten Bit-Stelle gegenüber der zweit-signifikantesten Bit-Stelle, usw. aussieht.
5. Neben Pixelrauschen gibt es auch Rauschanteile im Bild, die größere Flächen abbilden. Modellieren Sie eine weitere Rauschquelle, die benachbarte Pixel auf Gleichheit untersucht.
   Bilden Sie das Mittel von jeweils vier benachbarten Pixeln und speichern Sie das Ergebnis als neuer Pixel im Zentrum wieder ab. Die resultierende Zufallsvariable hat nun die Größe \(27\cdot27\cdot3\cdot32\). Auch hier können Sie die Analyse aus Aufgabenteil 3. und 4. anwenden.
   
   Wie hoch ist die Entropie dieser Zufallsvariable?
6. Dies kann beliebig häufig wiederholt werden, bis man beim Bildmittelwert, also der Zufallsvariable der Größe \(1\cdot1\cdot3\cdot32\), angelangt. Visualisieren Sie nun das Verhältnis an Gesamtentropie, abhängig von der Anzahl an Reduktionsschritten, die in Aufgabenteil 5 besprochen wurden.
7. Jede der bestimmten Entropien auf verschiedenen Größenskalen ist eine untere Schranke für die Information im Datensatz. Ist auch die Summe eine untere Schranke? Können Sie die obere Schranke angeben?
8. Schließen Sie was ein unsupervised Learning-Algorithmus, also ein solcher, der keine Information über die Label bekommt informationstheoretisch eigentlich leisten muss.