Theorieaufabe: 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: Unsupervised Learning

Dazu schaun wir uns den Datensatz CIFAR-10 an:
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 \(32\cdot 32\) Pixeln.

import matplotlib.pyplot as plt
import numpy as np

def imshow(img):
    img = img / 2 + 0.5     # unnormalize
    npimg = img.numpy()
    plt.imshow(np.transpose(npimg, (1, 2, 0)))
    plt.show()

batch_size = 64 # number of images to get for every iteration of trainloader
trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True, transform=transform)
trainloader = torch.utils.data.DataLoader(trainset, batch_size=batch_size, shuffle=True, num_workers=2)
classes = ('class-%i' % i for i in range(10))

# get some random training images
dataiter = iter(trainloader)
images, labels = dataiter.next()

# show images
imshow(torchvision.utils.make_grid(images))
# print labels
print(' '.join('%5s' % classes[labels[j]] for j in range(batch_size)))

Aufgaben

1. Bestimmen Sie die Entropie die in der Zufallsvariable des Labels stecken.
2. Zum Vergleich möchten wir dem die Entropie der Daten gegenüberstellen.
   1. Warum ist dies bei Fotos deutlich schwieriger (a.k.a. naiv nicht machbar) ?
   2. Wir versuchen uns also an einer Approximation, indem wir die Bit-Codierung der Eingabedaten untersuchen.
      
      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 abtastet als \(\text{höhe}\cdot \text{breite}\cdot \text{farben}\cdot \text{anzahl bits}\)-dimensionale Variabble auf (28 Pixel für Höhe und Breite, 3 Farben, 32 Bit).
      
      
      1. Bestimmen Sie also erstes die Bit-weise Entropie der Pixeldaten. Also: Schätzen Sie experimentell für jede Komponente der Zufallsvariable die Wahrscheinlichkeit für eine \(1\) und bestimmen sie damit die Entropie dieser Zufallsvariable. (Wir ignorieren hierzu die Position der Zufallsvariable im Bild, und Mitteln so implizit über alle Positionen).
      2. 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. Was kann man hier beobachten?
   3. Warum ist die Summe der pixelweisen Entropie der einzelnen Bits ist dabei nur eine untere Schranke für die tatsächliche Entropie der Eingabedaten?
      Hinweis: Neben Pixelrauschen gibt es auch Rauschanteile im Bild, die größere Flächen abbilden. Nennen Sie ein paar.
      
   4. Was ist die größte obere Schranke für die tatsächliche Entropie der Eingabedaten?
      Also wieviel Entropie kann überhaupt theoretisch in der Zufallsvariable maximal stecken?
   5. Wir wollen die Entropie nun etwas besser von oben abschätzen.
      Entropie hat ja was mit Bits zu tun, die Übertragen werden. Wie können wir dazu den tatsächlich benutzten Speicher verwenden, die die Daten brauchen um die Entropie abzuschätzen? In welcher Form sollten wir dieses am Besten benutzen? (Zip-Archiv, Entpackt, als JPEG?)
   6. Optional: Bestimmen Sie als zuletzte eine bessere untere Schranke für die Entropie.
      Sie können sich gerne etwas selbst überlegen, oder aber untersuchen ob das folgende Verfahren gute Ergebnisse liefert.
      
      Algorithmus
      • Wir bestimmen als erstes wieder die Entropie des niederwertigsten Bits des Pixelrauschens.
      • Als nächstes modellieren wir eine "großflächgere" Rauschquelle indem wir stets vier benachbarte Pixel aufsummieren und dann die Entropie des resultierenden niederwertigste Bits bestimmen.
      • Wir wiederholen dies mehrfach bis unsere Bilder nur noch aus einem einzelnen Pixel bestehen. Hier bestimmen wir wie im Aufgabenteil (b.) die Bit-Weise Entropie.
      • Wir schätzen die Entropie der Daten nun durch die Summe der Einzelentropien ab.
3. Schließen Sie nun daraus was ein unsupervised Learning-Algorithmus, also ein solcher, der keine Information über die Label bekommt informationstheoretisch eigentlich leisten muss.