---

Aufgabe: Kapazität des Skalarproduktes

Oder: Wieviele Bits kann ein einziges Neuron speichern?

Warum ist das Wichtig?

---

Tiefe Neuronale Netze (a.k.a. Deep Learning) bilden das Forschungsgebiet unserer Zeit. Bevor wir in diese 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.

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 ersetzt werden, und einer festgelegten Dimension 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 Funktionen 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.

Theorieaufgabe

Wir betrachten also die Rekonstruktionen \(\hat y_i\) des Neuron \(f_\omega\) 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 \(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 auf der so definierten Null-Ebene von \(f_\omega\) liegen).)

Ziel ist es, eine Formel für \(T(N,K)\) zu finden:

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\).
6. 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\).

Praxisaufgabe — stimmt die Rechnung oben?

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.

1. 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 MNIST oder CIFAR.

   trainset = torchvision.datasets.MNIST(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?.