Aufgabe: Kapazität des Skalarproduktes

Das mit dem (Un-)Supervised Learning schauen wir uns nun in einem sehr einfachen Beispiel an und fragen uns
Wieviele Bits kann ein einziges Neuron eigentlich speichern?

Warum ist das Wichtig?

---

Tiefe Neuronale Netze (a.k.a. Deep Learning) bilden das Forschungsgebiet unserer Zeit. Bevor wir in später in der Vorlesung in die Thematik einsteigen werden, möchten wir etwas zu dem wichtigsten Baustein, dem Skalarproduktes (a.k.a. dem Neuron), aus informationstheoretischer Sicht lernen. Konkret leiten wir in dieser Aufgabe her, wieviele Daten sich ein Neuron überhaupt merken kann. Wir starten mit dem Konzept, dass wir Daten über einen Kanal übertragen wollen, danach müssen wir "lediglich" zählen, wieviele Möglichkeiten es gibt diese Daten mit dem gegebenen Modell abzubilden. Warum "lediglich" und nicht lediglich? Diese Aufgabe ist durchaus mit etwas Knobeln verbunden. Beachten Sie, dass die Kerneinsicht (letzte Aufgabenteile) aber auch ohne Lösung für die vorhergehenden Knobelaufgaben erarbeitet werden kann.

Hintergrund zur Problemstellung

Wir definieren ein Neuron \(f_\omega\), als die Funktion \(f_\omega:\mathbb{R}^K \rightarrow \mathbb{R}\), die die Eingabe \(x\) auf einen Vektor \(\omega \neq 0\) projeziert.
\[ f_\omega(x) := x \cdot \omega := x^T\omega \]
(Typischerweise werden Neuronen mit einem Bias-Term formuliert, also \(w^Tx + b\). Dieser kann o.B.d.A durch ein weiteres Gewicht \(w_{K+1}\) ersetzt werden, und einer festgelegten Dimension mit Wert \(1\) im Datensatz, also \(x^{(K+1)} = 1\). Da hier die Datenmenge konstant ist können wir den Biasterm alternativ auch vom Datenterm abziehen und erhalten so auch eine Bias-freie Darstellung.)
Wir möchten nun Wissen, wieviele Bits ein solches Neuron speichern kann. Dies klingt zuerst einmal merkwürdig, da die reellen Zahlen unendlich groß sind; wie soll hier eine Anzahl an Bits erscheinen? Die Antwort ist „mit Informationstheorie“. Um Informationstheorie überhaupt anwenden zu können wird ein Kanal benötigt über den Daten übertragen werden.
Wir schließen die Eigenschaft der unendlichen Information in einer reellen Zahl unter Angabe des folgenden Protokolls aus:
Protokoll zur übertragung von Gewichten über einen Kanal:
Wir gehen davon aus, dass unser Datensatz aus einer Menge aus Tupeln besteht, \({(x_i, y_i)}\). Die \(x_i \in \mathbb{R}^K\) sind dabei die Eingabedaten (z.B. Bilder) mit zugehörigem Ground-Truth \(y_i \in \{0,1\}\) (z.B. die Klasse des jeweiligen Bildes).
Die Frage, die wir uns jetzt stellen ist die Folgende:

1. Angenommen wir haben einen Algorithmus (nennen wir ihn „Lern Algorithmus“), der den ganzen Datensatz erhält.
2. Dieser Algorithmus soll nun sein gelerntes wissen über den Datensatz über einen Kanal übertragen. (Im Falle des Neurons ist dies gerade \(\omega\).)
3. Der Empfänger auf der anderen Seite des Kanals erhält dieses Wissen und soll nun mit den öffentlich bekannten Daten \(x_i\) das „geheime Wissen“ \(y_i\) wiederherstellen.

Die Annahmen dabei sind:

1. Die Gewichte \(\omega\) selbst befinden sich in einer Blackbox und dürfen nicht direkt untersucht werden.
2. Gewichte können nur einmalig verwendet werden (Probing ist nicht erlaubt).

Frage Was groß ist die Kapazität dieses Kanals? Anders Ausgedrückt: Wie viel Information der Eingabedaten kann durch das „Training“ (a.k.a. schlaues Auswählen von \(\omega\)) eines Neurons bestenfalls gespeichert werden?
Äquivalent dazu sind die Fragen:

• Wieviele verschiedene semantisch verschiedene Abbildungen können durch \(\boldsymbol w\) ausgedrückt werden?
• Wie unterscheidet sich dieses Ergebnis zur Anzahl alle möglichen binären Zuweisungen des \(n\)-Stichproben großen Datensatzes, nämlich \(2^N\)?

Denn, falls beide Zahlen nah beieinander sind, ist der Kanal in der Lage alle \(N\) bits mit nur geringem Fehler zu übertragen.

Aufgabe (Theorie)

Wir betrachten also die Rekonstruktionen \(\hat y_i\) des Neuron gegeben durch \(f_\omega(x) := w^T\cdot x\) mit Parameter \(\omega\) und Aktivierungsfunktion \(a\): \[ \hat y_i := a\left(f_\omega\left(x_i\right)\right),\qquad a(x) = \left\{\begin{matrix} 1 & x>0\\ 0 & x ≤ 0\end{matrix}\right. \]

Es sei nun \(T(N,K)\) die Anzahl verschiedener Funktionen \(f_\omega\), um eine beliebige aber feste Menge von \(N\) Punkte in \(K\) Dimensionen auf je eine Ausgabe \(\{0,1\}\) abzubilden. (Alle Punkte seien dabei in allgemeiner Lage. Im Prinzip gehen wir so davon aus, dass keine zwei Punkte gleichzeitig auf der so definierten Null-Ebene von \(f_\omega\) liegen).)

1. Unser Ziel ist es, eine Formel für \(T(N,K)\) zu finden: Die folgenden Aufgaben sollen dabei den richtigen Lösungsansatz liefern. (Überspringen Sie diese Teilaufgabe gerne, falls Sie hier stecken bleiben. Eine Rekursive Formel finden Sie im Eingeklappten Bereich "Lösungsansatz".)
   
   
   Lösungsansatz

   1. Beginnen Sie mit \(K=1\) und Datensatz der größe \(N\). Wieviele verschiedene Funktionen von \(N\) Punkten können mit der Familie \(f_\omega\) abgebildet werden?
   2. Nun zum umgekehrten Fall: \(N = 1\), beliebige Dimension \(K\). Wieviele verschiedene Funktionen sind es jetzt?
   3. Es sei nun \(K = 2\) und \(N\) beliebig. Wie groß ist \(T(N,K)\)?
      
      Hinweis: Für \(N≥3\) können nicht mehr alle möglichen Zuweisungen repräsentiert werden. (Beispiel: XOR). Hinweisbild:

      

   4. Zeigen Sie, dass für beliebige \(K\) and \(N\) die Gleichung \( \begin{align} T(N,K) &= T(N-1,K) + T(N-1,K-1)\\ \end{align} \) gilt.
   5. Leiten Sie entweder eine geschlossene Formel für \(T(N,K)\) her, oder einfacher: bestimmen Sie programmatisch die Anzahl für \(1 \le K \le 100\) und \(1 \le N \le 300\).
   
   
   
2. Bestimmen Sie nun den Quotienten \(\frac{T(N,K)}{2^N}\) und bestimmen Sie Approximativ den Wert in den angegebenen Bereichen \[ \frac{T(N,K)}{2^N} \approx \left\{\begin{matrix} ?, & N≤\phantom{[}K\phantom{2KK} \\ ?, & N\in[K,2K)\\ ?, & N = \phantom{[}2K\phantom{2K)}\\ ?, & N > \phantom{[}2K\phantom{2K)}\\ \end{matrix}\right. \]
   1. Plotten Sie dazu am besten den Graph von \(\frac{T(N,K)}{2^N}\). Etwas besser sichtbar ist das Ganze, wenn Sie in der visualisierung die Achse für \(N\) durch \(N/K\) substituieren bzw. die \(N\)-Achse mit \(1/K\) strecken.
   2. Was können Sie dem Plott entnehmen, etwa im Hinblick die angegebenen Bereiche, insbesondere \(N \approx 2K\).

Aufgabe (Praxis)

Wir drehen die Aufgabe nun um: Wir starten mit dem Skalarprodukt auf einem gegebenen Datensatz, dass diesen möglichst "optimal" löst. Das Ziel ist nun zu bestimmen, wieviele Bits dieses Skalarprodukt in der Praxis tatsächlich speichert bzw. rekonstruieren kann.

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)))

1. Vorbereitung: Im Falle einer Klasse gleicht das Modell im Grunde dem einer Support-Vector-Maschine (SVM). (Im Falle dass sie den Mechanismus nicht kennen, ist dies nicht so schlimm, gehen Sie einfach davon aus, dass der Algorithmus für uns ein "gutes" Gewicht für das obige Skalarprodukt wählt.
   
   Wir ermitteln also eine SVM, am einfachsten per sklearn.
   
   

   svm = LinearSVC(dual=False, max_iter=25)
   svm.fit(traindata.reshape((num_examples,-1)), trainlabels)
   trainlabels_reconstruct = svm.predict(traindata.reshape((num_examples,-1)))
   
   # übrigens: das Gewicht w können Sie per svm.coeff_ einsehen.
   

   
   
   Als Datensatz wählen wir wieder CIFAR-10.

   trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True, transform=torchvision.transforms.ToTensor())
   traindata   = trainset.train_data.numpy()
   trainlabels = trainset.test_labels.numpy()
   

   
   
   Filtern Sie den Datensatz zuerst, sodass nur zwei Klassen enthalten sind, etwa 4 und 7.
2. Nutzen Sie nun predict wie oben angegeben, und Zählen Sie wieviele Punkte (des Trainingssets!) korrekt auswendig gelernt wurden.
3. Wievielen gelernten Bits entspricht das in etwa? Insbesondere: Wie passt das Ergebnis zu unserer theoretisch ermittelten Kapazität von oben zusammen?.