Zusammenhang zwischen Informationtheorie & Aufgabe 1 & 2

ist das Wissen, das man beim Beobachten einer diskreten Zufallsvariable \(X\) sammelt.
\[ X \sim p ⇒ I(x) := -log_2\ p(x) \]

ist die erwartete Information einer Zufallsvariable.
\[ X \sim p ⇒ H(x) := E_X[I(X)] \]
Die Definition ist so gewählt, dass eine optimale Binär-Kodierung, sich im Mittel um höchstens ein Bit von der Entropie unterscheidet, \[ H(x) ≤ E_X[\text{length}(C(X))] < H(X) + 1. \] Die Maximale Entropie beträgt \(H(X) ≤ log2(n),\) wobei \(n\) die Anzahl der möglichen Werte für \(X\) ist.

• für Information:

\[ I(x,y) = I(x|y) + I(y) = I(y|x) + I(x). \]

• für Entropie (Joint Entropy):

\[ H(X,Y) = H(X|Y) + H(Y) = H(Y|X) + H(X), \] wobei \(H(X|Y)\) die in \(X\) enthaltene Information, die sich nicht durch \(Y\) ergibt, ist.

ist die gelernte Information einer Zufallsvariable durch das Beobachten einer anderen Variable.
\[ I(X;Y) = \text{KL}( p(x,y) || p(x)p(y)) = H(X) - H(X|Y) = H(Y) - H(Y|X), \] wobei \(p(\cdot)\) drei WSK-Verteilungen repräsentiert.
Eigenschaften:

• \(I(X;Y) = 0 ⇔ X,Y\) sind unabhängig
• \(I(X;Y) = max ⇔ X=Y\) (in dem Fall ist \(I(X;Y) = H(X) = H(Y)\))
• \(I(X;Y) = I(Y;X)\)
• \(I(X;Y) = I(φ(Y);ψ(X))\) (fallls \(φ,ψ\) invertierbar sind)
• Beziehung zur Korrelation \(ρ_XY = Cov[X,Y] / √ Var[X]·Var[Y] ∈ [-1,1]\):
  
  • \(ρ_··\) beschreibt nur lineare Abhängigkeit \(Y = aX + b\) (für \(Var[X]=Var[Y]=1\) ist \(a=ρ_XY\)).
    
  • Beispielsweise sind \(Y = X²\) linear Unabhängig, aber dennoch Abhängig.

Mengenanschaung \[ \begin{aligned} |A| &:= H(A) \text{ (die in A enthaltene Information)}\\\\ |A \cup B | &= H(A,B)\\\\ |A \setminus B | &= H(A|B)\\\\ |A \cap B | &= I(A;B) \end{aligned} \]

Sei die Markov-Kette \(X \rightarrow Y \rightarrow Z\) gegeben, dann gilt \[ I(X;Y) \ge I(X;Z).\]
Lemma: Sei die Markov-Kette \(Y \rightarrow X \rightarrow T_1 \rightarrow ... \rightarrow T_k \rightarrow \hat Y\) gegeben, dann gilt \[ I(X;Y) \ge I(T_1;Y) \ge ... \ge I(T_k;Y) \ge I(Y;\hat Y) \] \[ H(X) \ge I(X;T_1) \ge ... \ge I(X;T_k) \ge I(X;\hat Y) \] Die Ungleichung sind Gleichungen, falls die \(T_i(\cdot)\) ausreichende Abbildungen sind.

(engl. sufficient Statistic)
Eine ausreichende Variable \(S(X)\) einer Zufallsvariablen \(X\) ist eine Variable, die die gesamte Information einer Zufallsvariablen \(X\) bezüglich einer anderen Zufallsvariablen \(Y\) enthält, d.h. \[ I(S(X); Y) = I(X;Y) \]
Minimale Ausreichende Variable
Man nennt eine ausreichende Abbildung minimal, falls sie die einfachste ausreichende Abbildung ist, d.h. \[ T(X) := \arg \min_{S(X):I(S(X);Y)=I(X;Y)} I(S(X); X) \]

Im Allgemeinen existiert keine minimale ausreichende Variable. Suche daher \[ \min_{p(t|x),p(y|t),p(t)} I(X;T)-\beta I(T;Y) \]

• Der Lagrange-Multiplier \(\beta\) ist dabei die Steuerung des Trade-offs zwischen
  • geringer Auflösung / hoher Kompression und hoher Auflösung / geringer Kompression
• Implizite Lösung existieren: die Bottleneck Gleichungen