relative-entropie.md
-
Konrad Völkel authoredKonrad Völkel authored
Relative Entropie
Logarithmen
:::{admonition} Lemma Sei l \colon \{1,\dots\} = \mathbb{N}_{>0} \to \mathbb{R} eine Funktion mit
- l(ab) = l(a) + l(b) -- "vollständig additiv"
- l(n+1) \geq l(n) -- "monoton wachsend" Dann existiert eine Konstante c \in \mathbb{R} sodass l(n) = c \ln(n). :::
:::{admonition} Bemerkung Aufgrund der Formel
\ln(x) = \dfrac{\log_a(x)}{\log_a(e)}
können wir die Konstante c interpretieren als c = \log_a(e), d.h. die Funktion l ist ein Logarithmus zur Basis a. :::
Es ist auch gleich klar, dass das gleiche Lemma für \log_2 anstelle von \ln gilt (lediglich die Konstante ist eine andere).
Wenn wir also etwas abzählen wollen, sodass der Zählwert eines Produkts die Summe der einzelnen Zählwerte ist, dann müssen wir das mit einem Logarithmus tun.
:::{admonition} Beweis Wir wollen zeigen, dass für Funktionen f,g \colon \mathbb{N}_{>0} \to \mathbb{R}, die die Bedingungen aus dem Lemma erfüllen, stets
f(n) g(2) = f(2) g(n)
gilt, denn mit g = \ln ist dann das Lemma bewiesen (c=f(2)).
Seien n,k,l \in \mathbb{N} sodass 2^{l-1} \leq n^k \leq 2^l. Aus der Monotonie folgt dann
f(2^{l-1}) \leq f(n^k) \leq f(2^l)
und aus der Additivität
(l-1)f(2) \leq kf(n) \leq lf(2)
ebenso die gleiche Ungleichungskette für g anstelle f, aber das multiplizieren wir noch mit -1:
-lg(2) \leq -kg(n) \leq -(l-1)g(2).
Die Summe dieser beiden Ungleichungsketten können wir nun vereinfachen zu
-f(2)g(2) \leq k\left(f(n)g(2) - f(2)g(n)\right) \leq f(2)g(2)
teilen wir durch k, und lassen dann k \to \infty gehen, so sehen wir, dass f(n)g(2) - f(2)g(n) \to 0 geht (für k \to \infty, wovon es gar nicht abhängt). :::
:::{admonition} Lemma Wenn eine stetige Funktion F \colon \mathbb{R} \to \mathbb{R} die Funktionalgleichung F(xy) = xF(y) + F(x)y erfüllt und schneller wächst als x, so existiert eine Konstante c \in \mathbb{R} sodass F(x) = -x\log(x)c. :::
:::{admonition} Beweis Die Funktion g(x) := F(x)/x erfüllt g(xy) = g(x) + g(y) und wächst monoton, also gibt es c' mit g(x) = c'\log(x), und c:=-c' funktioniert. :::
:::{admonition} Bemerkung Wir sehen also, dass die Information I(x) = -x\log(x) eine sehr natürliche Größe ist. :::
:::{admonition} Lemma Der Logarithmus ist eine konkave Funktion, d.h. für eine Konvexkombination \lambda x + \mu y (d.h. \lambda + \mu = 1 und 0 \leq \lambda, \mu \leq 1) gilt
\lambda \log(x) + \mu \log(y) \leq \log(\lambda x + \mu y) :::
:::{admonition} Beweis Idee: Die Ableitung von \log(x) ist \frac{1}{x} und das ist auf (0,\infty) streng monoton fallend. Mit dem Mittelwertsatz kann man nun zeigen, dass \log(x) streng konkav sein muss (also sogar < statt \leq in der Ungleichung oben). :::
Wir haben vorher schon ein heuristisches Argument verwendet, aber nun können wir rigoros zeigen:
:::{admonition} Proposition Wenn p = (p_1,\dots,p_n) eine diskrete Verteilung auf \Omega = \{1,\dots,n\} beschreibt, so gilt für die Entropie H(p) \leq \log(n) (die Entropie der Gleichverteilung). :::
:::{admonition} Beweis Wir nutzen aus, dass die Summe in der Definition der Entropie eine Konvexkombination ist, und dass der Logarithmus konkav ist:
$H(p) = \sum_{i=1, p_i\neq 0}^n p_i \log \frac{1}{p_i} $
\leq \log \left( \sum_{i=1, p_i\neq 0}^n p_i \frac{1}{p_i} \right)
\leq \log\left( \sum_{i=1}^n 1 \right) = \log(n) :::
Relative Entropie
:::{admonition} Definition Seien p,r \in \Delta_n (der Menge der Wahrscheinlichkeitsvektoren in \mathbb{R}^n, also Vektoren, deren Einträge zwischen 0 und 1 liegen und deren Summe über alle Einträge genau 1 ist). Die Entropie (auch: Kullback-Leibler-Divergenz D_{KL}) von p relativ zu r ist
H(p \Vert r) := \sum_{i,\ p_i > 0}^n p_i \log \left( \frac{p_i}{r_i} \right) \in \mathbb{R} \cup \{\infty\}. :::
:::{admonition} Proposition Schreibe u_n = (\frac{1}{n}, \dots, \frac{1}{n}) \in \Delta_n für die Gleichverteilung auf \{1,\dots,n\}. Dann ist
H(p \Vert u_n) = H(u_n) - H(p) = \log(n) - H(p) :::
:::{admonition} Proposition H(p \Vert r) = 0 \text{ genau dann wenn } p=r (ohne Beweis) :::
:::{admonition} Proposition H(p \Vert r) \geq 0 :::
:::{admonition} Beweis H(p \Vert r) = -\sum p_i \log \left( \dfrac{r_i}{p_i} \right) \geq - \log \left( \sum p_i \dfrac{r_i}{p_i} \right) \geq - \log \left( \sum r_i \right) = -\log 1 = 0
dabei haben wir wieder die Konkavität des Logarithmus ausgenutzt. :::
:::{admonition} Beispiel Die relative Entropie ist nicht symmetrisch und kann durchaus unendlich groß werden:
H\left(u_2 \big\Vert \begin{pmatrix} t \\ 1-t \end{pmatrix} \right) = \frac{1}{2} \log \left( \frac{1}{2t} \right) + \frac{1}{2}\log \left(\frac{1}{2(1-t)}\right) \xrightarrow{t \to 0} \log(\infty) = \infty.
Wie zuvor besprochen ist H\left( \begin{pmatrix} t \\ 1-t \end{pmatrix} \big\Vert u_2 \right) = \log(n) - H\left( \begin{pmatrix} t \\ 1-t \end{pmatrix} \right) und
H(u_2) = t\log(t) - (1-t)\log(1-t) \xrightarrow{t \to 0} 0 - 1\log(1) = 0 :::
Verbundentropie
:::{admonition} Definition Die Verbundentropie von zwei diskreten Zufallsvariablen X,Y ist
H(X,Y) := \mathbb{E} I_{X,Y} = -\sum_{i=1}^n \sum_{j=1}^n P(X = z_i, Y=z_j) \log P(X=z_i, Y=z_j) :::
:::{admonition} Proposition H(X) + H(Y) \geq H(X,Y) \geq \max\left( H(X), H(Y) \right) :::