Augabe 1: Bayes'sche Inferenz

Angenommen, wir werfen eine Münze 50 mal. Sie zeigt 20 mal "Kopf" und 30 mal "Zahl".
Die Frage die wir uns jetzt stellen ist, ob wir es mit einer fairen Münze zu tun haben.
Hierzu probieren wir drei Möglichkeiten vorzugehen, um herauszufinden, ob wir es mit einer fairen Münze zu tun gehabt haben.

1. Frequentistische Ansicht (alternative Hypothesen):
   Es gibt gute Münzen und betrügerische Münzen. Gute Münzen haben eine 50/50 Chance für Kopf und Zahl. Eine betrügerische zeige als Beispiels ein mittleres Verhältnis von 75 Kopf zu 25 Zahl (statt 50/50).
   Berechnen Sie die Wahrscheinlichkeit für die beiden Alternativen (Betrug & gut).
2. Frequentistische Ansicht (Signifikanztest):
   Es gibt gute Münzen und betrügerische Münzen. Gute Münzen haben eine 50/50 Chance für Kopf und Zahl.
   Wie hoch ist die Wahrscheinlichkeit, dass die Münze nicht verfälscht wurde und trotzdem mehr als 10% (5 Würfe) vom Mittelwert (25/25) abweicht?
3. Bayes'sche Sichtweise:
   Die Wahrscheinlichkeit, dass unsere Münze "Kopf" zeigt, beträgt \(\theta \in [0,1]\) . Berechnen Sie eine Wahrscheinlichkeitsverteilung für den Wert von \(\theta\) angesichts der Daten, die Sie gesehen haben (nehmen Sie einen gleichmäßigen Prior auf \(\theta\) an, d.h., bevor Sie die Daten gesehen haben, werden alle Werte von \(\theta\) als gleich wahrscheinlich angesehen).
   Zeichnen Sie die Verteilung in ein Diagramm.

Aufgabe 2: Bayes'scher Weltuntergang

Aufgabe: Leiten Sie eine Wahrscheinlichkeitsverteilung für die Wahrscheinlichkeit ab, dass die Welt im Jahr \(2021,2022,\dots\) noch existiert, ohne dass die Menschheit ausstirbt oder ein dramatisches Ereignis eintritt, das die Bevölkerungszahl unter die Vorhersagen drückt.

Bemerkung: Das vollständige Weltuntergangsargument, wie es im ersten Link diskutiert wird, ist noch etwas weiter ausgearbeitet worden. Wir rechnen nur das Basisargument nach.

Lösungshinweise:

1. Starten Sie damit \(\lambda\) und \(t_0\) aus dem Modell und den angegebenen Datenpunkten zu schätzen.
2. Bestimmen Sie den Zeitpunkt \(t_\text{10M}\), an dem dem Modell nach \(10\) Milliarden Menschen erreicht werden.
3. Bestimmen Sie als nächstes eine Formel \(\operatorname{Total}(t)\) für die Gesamtanzahl aller Menschen, die bis zum Zeitpunkt \(t\) auf der Erde sind oder waren.
4. Nun zum eigentlichen Argument: Wir möchten die Wahrscheinlichkeit \(P(t = t')\) bestimmen, die angibt wie wahrscheinlich es ist, dass die Menschheit zum Zeitpunkt \(t'\) noch existiert oder ein dramatisches Ereignis eintritt, das die Bevölkerung unter die Vorhersagen drückt.
   
   Den Übergang des Modells zu einer Wahrscheinlichkeit schafft dazu Annahme 2. Angenommen also, Menschen "erscheinen" gleichverteilt. Dann ist die Wahrscheinlichkeit, dass wir selbst bis zum Zeitpunkt \(t'\) bereits geboren wurden, durch \[P(\text{zufälliger Mensch wurde geboren} | t \le t') = \frac{\operatorname{Total}(t')}{\operatorname{Total}(t_\text{max})}\] gegeben.
   Den Zeitpunkt \(t_\text{max}\) kennen wir nicht, möchten ihn aber schätzen!
5. Dies ist eine gleichverteilte Zufallsvariable!
   
   • Doomsday Argument: Wir können demnach annehmen, dass eine 95%ige Chance besteht, dass eine Person zu den letzten 95% aller Menschen gehört, die jemals geboren werden. Warum?
   • Ausgehend von der Gesamtzahl der Menschen, die bis zu einem bestimmten Jahr geboren wurden, können wir die obere Konfidenzgrenze von 95% für die Gesamtzahl der Menschen bestimmen, die jemals geboren werden.
   • Bezeichnen wir das aktuelle Jahr als \(t_c\), die Zahl der bis \(t_c\) geborenen Menschen als \(\operatorname{Total}(t_c)\) und die Gesamtzahl der Menschen, die jemals geboren werden, als \(\operatorname{Total}(t_\text{max})\). Das Argument besagt demnach implizit, \[P\left(\frac{\operatorname{Total}(t_c)}{\text{Total}(t_\text{max})}\ge 0.05\right) \ge 0.95\]
   
   
   Berechnen Sie \(\operatorname{Total}(t_c)\) für jedes Jahr \(t_c = 2021, 2022, \dots\) unter Verwendung der in Schritt 3 abgeleiteten Formel \(\operatorname{Total}(t)\).

Aufgabe 3: Informationstheorie Hintergrundwissen

1. Lesen Sie Massimiliano Tomassoli's Zusammenschrift mit dem Namen "Information Theory for Machine Learning".
   (  Hier geht es direkt zur PDF-Version.)
   Die ganze Zusammenschrift ist sehr lesenswert. Ich empfehle aber zumindest die folgenden Abschnitte zu lesen:
   • Teil I, Abschnitt 1 (Introduction) bis Abschnitt 7 (Maximum Entropy)
   • Teil I, Abschnitt 12 (Mutual Information)
   • Teil I, Abschnitt 13 (A Set Theoretic view of Information Theory)
2. Bearbeiten Sie dazu eine der folgenden Aufgaben:
   Wahlaufgabe A: Verbesserung des Huffman-Codes

   In der Vorlesung wurden Huffman-Codes vorgestellt. Diese sind so konstruiert, dass sie die Ereignisse \(x_1, \dots, x_n\) einer Zufallsvariable \(X\) so kodieren, dass die Länge des Codes \(C(x_i)\) gerade der Information des Ereignisses \(x_i\) entspricht, \[ C(x_i) = I(p_{x_i}) = -\log(p_{x_i}) \]
   
   Wir haben in der Vorlesung gesehen, dass Huffman-Codes im Mittel maximal ein Bit verschwenden. \[ H(X) ≤ E_X[C(X)] < H(X) + 1 \tag{1}\]
   
   

   Die Herleitung dazu ist recht einfach:

   ---

   Wenn die Länge des Codes gerade der Information des Ereignisses entspricht, dann können wir die tatsächliche Länge \(C(x)\) durch die nächste ganze Zahl abschätzen (die Länge ist stets eine ganze Zahl). \[ I(x) ≤ C(x) = \left\lceil I(x)\right\rceil < I(x) + 1 \] Im Mittel ergibt sich damit: \[ E_X[I(X)]) ≤ E_X[C(X)] < E_X[I(X)] + 1\\ H(X) ≤ E_X[C(X)] < H(X) + 1 \]

   
   
   Ist es möglich Codes zu erstellen, die sich um weniger als 1 Bit im Mittel verschätzen?
   
   Wir nehmen an, dass wir eine Zufallsvariable \(Z\) beobachten, die lediglich ein \(n\)-dimensionaler Vektor ist, der aus unabhängigen gleichverteilten Zufallsvariablen \(X_i\) besteht, \[ Z = (X_1, \dots, X_n) \]
   
   

   1. Leiten Sie zuerst her, dass \(H(Z) = n\cdot H(X)\) gilt.
   2. Setzen Sie nun \(H(Z)\) anstelle von \(H(X)\) in die obige Ungleichung \((1)\) ein und folgern Sie, dass für \(n\rightarrow \infty\) der Huffman-Code von \(n\) Beobachtungen beliebig genau die Information der Eingabe codiert.
   
   
   
   Wahlaufgabe B: maximale Entropie

   Minimale Entropie zu erreichen ist recht einfach; wir wählen für ein Ereignis die Wahrscheinlichkeit 1, für alle anderen Ereignisse die Wsk. 0. Die Information einer solchen Zufallsvariable ist gerade 0. (Dies verdeutlicht, warum die Information häufig auch Überraschung genannt wird).
   
   Gegeben sei eine beliebige Zufallsvariable \(X\), die die Werte \(x_1,\dots,x_n\) mit unbekannten Wahrscheinlichkeiten \(p_1,\dots,p_n\) annehmen kann. Wir möchten nun herleiten, wann die Entropie maximal wird.
   
   

   1. Beweisen Sie die Jensen-Ungleichung:
      Gegeben sei eine konvexe Funktion \(f\) und eine Zufallsvariable \(X\).
      Dann gilt \[E[f(X)] ≥ f(E[X]).\] (Die Gleichheit gilt genau dann, wenn \(f\) linear ist, oder \(H(X) = 0\).)
      
      Hinweis: Eine Funtkion \(f:\mathbb{R} \rightarrow \mathbb{R}\) ist genau dann konvex, wenn sich alle Funktionswerte über allen linearen Funktionen befinden, die die Funktion schneiden, also \[f(x) ≥ a\cdot x + b \qquad\forall x\].
   2. Nutzen Sie nun die Jensen-Ungleichung, um die maximale Entropie der Zufallsvariable \(X\) zu bestimmen.
      Hinweis: Beginnen Sie mit der Definition der Entropie und nutzen Sie, dass \(f = -\log\) eine konvexe Funktion ist.
   
   
   
   Wahlaufgabe C: Korrelation und Mutual Information

   Wir haben in der Vorlesung etwas über Mutual Information zweier Zufallsvariablen gelernt. Diese Aufgabe soll ein besseres Gefühlt dafür geben, warum dies ein strikt stärkeres Maß als die Korrelation zweier Zufallsvariablen ist.

   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).
      Hinweis: Wählen Sie eine (einfache) nicht-lineare Abbildung \(f(X)\).
   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.