---

Augabe 1: Korrelation und Mutual Information

Die Kovarianz zweier Zufallsvariablen \(X\) und \(Y\) ist als \[ Cov[X,Y] = \mathbb{E}\left[\left(X- \mathbb{E}[X]\right)\left(Y- \mathbb{E}[Y]\right)\right] \] definiert und die Korrelation zweier Zufallsvariablen \(X\) und \(Y\) ist durch \[ \rho_{XY} = \frac{Cov[X,Y]}{\sqrt{Var[X]Var[Y]}} \] gegeben. (Der Nenner normalisiert den Wert lediglich auf das Intervall \([-1,1]\).

1. Zeigen Sie, dass zwei unabhängige Zufallsvariablen eine Korrelation von Null haben, \(Cov[X,Y] = 0\).
2. Zeigen Sie mithilfe eines Gegenbeispiels, dass eine Korrelation von 0 keine Unabhängigkeit impliziert (Im Gegensatz zur Mutual Information).
3. Tatsächlich ist die Korrelation lediglich in der Lage lineare Zusammenhänge zu messen. Wir zeigen dies nun auf folgende Art und Weise: Für die zwei Zufallsvariablen \(X\) und \(Y\) suchen wir eine lineare Funktion \(f(x) = ax + b\), die die Relation dieser zwei Variablen so gut wie möglich beschreibt. Um die Parameter dieser zu finden formulieren wir (was sonst) ein Least Squares Problem: \[ L(a,b) = \frac{1}{2} \mathbb{E}_{X,Y}\left[ (f(X) - Y)^2 \right]. \] Bestimmen Sie \(a\) und \(b\) so, dass \(L(a,b)\) minimal wird.
   
   Schließen Sie, dass die Korrelation zweier Zufallsvariablen lediglich lineare Zusammenhänge abbildet.

Aufgabe 2: Kapazität des Skalarproduktes

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.

Problemstellung

Wir definieren ein Neuron \(f_\omega\), als die Funktion \(f_\omega:\mathbb{R}^K \rightarrow \mathbb{R}\), die die Eingabe 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\).)

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.

Aufgabe

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(\sum_{k=1}^K w_kx_i^{(k)}\right)\right),\qquad a(x) = \left\{\begin{matrix} 1 & x>0\\ 0 & x ≤ 0\end{matrix}\right. \] (\(x_i^{(k)}\) ist dabei die \(k\)-te Komponente des \(i\)-ten Datenpunktes \(x_i\) aus dem Datensatz.)

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)

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

1. Beginnen Sie mit \(K=1\) und beliebigem großen 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. 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. \]