Das Wahrscheinlichkeits-simplex
Eine Wahrscheinlichkeitsverteilung über q Symbole ist ein Punkt im (q−1)-dimensionalen Simplex: der Menge aller Vektoren (p₁, ..., p_q) mit pᵢ ≥ 0 und Σ pᵢ = 1.
Für q = 2: Das Simplex ist eine Strecke [0,1], die durch eine einzelne Wahrscheinlichkeit p parameterisiert wird. Für q = 3: Das Simplex ist ein gleichseitiges Dreieck in ℝ². Jeder Ecke ist eine deterministische Verteilung (ganzes Gewicht auf einem Symbol); der Mittelpunkt ist die gleichmäßige Verteilung.
Entropie H(p) weist jedem Punkt des Simplex eine reelle Zahl zu. Die Geometrie der Funktion bestimmt viele grundlegende Ergebnisse.
Konkavität
H ist konkav im Simplex: für jede zwei Verteilungen p und q und jedes λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Eine Mischung aus zwei Verteilungen hat eine Entropie von mindestens so groß wie das gewichtete Mittel ihrer individuellen Entropien. Intuition: Mischen von zwei Quellen erhöht die Unsicherheit.
Konkavität überprüfen
Für binäre Entropie H(p) ist die Konkavität im Graphen sichtbar: Die Kurve biegt sich nach oben, fällt nie unter einem Strich, der zwei Punkte verbindet.
Formale Prüfung für Konkavität: Die zweite Ableitung H''(p) ≤ 0 überall.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 für alle p ∈ (0,1)
Die zweite Ableitung ist überall im Innern streng negativ: H ist streng konkav.
Die Kapazitätsreichende Verteilung
Die Kanalkapazität ist definiert als das Maximum der wechselseitigen Information über alle Eingabeverteilungen p(x):
C = max_{p(x)} I(X; Y)
wobei I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Für den binären symmetrischen Kanal mit Fehlerwahrscheinlichkeit Q: Die kapazitätsreichende Eingabeverteilung ist die gleichmäßige Verteilung p(0) = p(1) = 0,5.
Warum: H(Y) wird durch die gleichmäßige Ausgabeverteilung maximiert. Bei einem BSC wird durch eine gleichmäßige Eingabe eine gleichmäßige Ausgabe erzeugt. Jede andere Eingabeverteilung macht H(Y) kleiner, was die wechselseitige Information I(X;Y) reduziert.
Geometrisch: Die wechselseitige Information I(X;Y) ist eine konvexe Funktion der Eingabeverteilung p(x) im Simplex. Das Maximum einer konvexen Funktion auf einem konvexen Satz wird an einem eindeutigen Punkt (dem Zentrum, für einen symmetrischen Kanal) erreicht.
KL-Divergenz
Die Kullback-Leibler-Divergenz (relative Entropie) von der Verteilung q zur Verteilung p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 immer (Gibbs' Ungleichheit). D(p || q) = 0, wenn und nur wenn p = q.
D ist nicht eine wahre Distanz: sie ist asymmetrisch (D(p||q) ≠ D(q||p) im Allgemeinen) und erfüllt nicht die Dreiecksungleichheit. Aber sie fungiert als Maß dafür, wie weit p von q in Wahrscheinlichkeitsraum entfernt ist.
KL-Divergenz tritt in der gesamten Informationstheorie auf:
- Wechselinformation: I(X;Y) = D(p(x,y) || p(x)p(y)). Die wechselseitige Information ist die KL-Divergenz zwischen der gemeinsamen Verteilung und dem Produkt der Ränder - wie weit die gemeinsame Verteilung von der Unabhängigkeit abweicht.
- Gibbs' Ungleichheit: Das Noiseless-Coding-Theorem folgt direkt aus D(p || q) ≥ 0.
- Kanalkapazität: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Berechnung von KL-Divergenz
Beispiel: p = (0.5, 0.5) gleichmäßige binäre, q = (0.8, 0.2) verzerrte binäre.
D(p || q) = 0.5 log₂(0.5/0.8) + 0.5 log₂(0.5/0.2)
= 0.5 log₂(0.625) + 0.5 log₂(2.5)
≈ 0.5 × (−0.678) + 0.5 × 1.322 ≈ −0.339 + 0.661 ≈ 0.322 Bits
Kapazität als geometrische Entfernung
Die Kapazität hat eine geometrische Interpretation im Raum der Wahrscheinlichkeitsverteilungen.
Für ein Kanal p(y|x) definieren wir die kapazitätsreichende Eingabeverteilung p*(x). Die Kapazität erfüllt:
C = D(p*(y) || r(y))
wobei p(y) = Σ p(x) p(y|x) die Ausgabeverteilung unter der optimalen Eingabe ist und r(y) = argmin_r max_x D(p(y|x) || r(y)) die minimumsinformative Ausgabeverteilung ist — der Punkt im Ausgabeprobabilitätsraum, der den konditionalen Ausgabeverteilungen p(y|x=0) und p(y|x=1) gleichzeitig am nächsten (im KL-Divergenz-Sinn) liegt.
Das ist die informationsgeometrische Sicht: Die Kapazität ist der Radius des kleinsten KL-Divergenz-Kreises im Ausgabeverteilungsraum, der alle konditionalen Verteilungen p(y|x=0) und p(y|x=1) enthält.
Für den BSC: p(y|x=0) = (1-Q, Q) und p(y|x=1) = (Q, 1-Q). Durch Symmetrie ist die minimumsinformative Ausgabe r(y) = (0,5; 0,5). Kapazität = D((1-Q, Q) || (0,5; 0,5)) = 1 − H(Q). Die Formel liefert das standardmäßige Ergebnis aus der Geometrie.
Kapazität aus KL-Divergenz
Bestätigen Sie die geometrische Formel: C = D(p(y|x=0) || r(y)) für einen BSC mit Q = 0,1, r(y) = (0,5; 0,5).
p(y|x=0) = (0,9; 0,1) (senden Sie 0, erhalten Sie 0 mit einer Wahrscheinlichkeit von 0,9, erhalten Sie 1 mit einer Wahrscheinlichkeit von 0,1).
D((0,9; 0,1) || (0,5; 0,5)) = 0,9 log₂(0,9/0,5) + 0,1 log₂(0,1/0,5)
= 0,9 log₂(1,8) + 0,1 log₂(0,2)
log₂(1,8) ≈ 0,848, log₂(0,2) ≈ −2,322
= 0,9×0,848 + 0,1×(−2,322) ≈ 0,763 − 0,232 ≈ 0,531 Bit
Überprüfen Sie: C = 1 − H(0,1) ≈ 1 − 0,469 = 0,531 Bit ✓
Leistungsabfall und Grenzen der Kompression
Rate-Distortion-Theorie erweitert die Informationstheorie auf verlustbehaftete Kompression. Statt die Frage zu stellen: 'Welche minimale Anzahl von Bits ist erforderlich, um eine Quelle genau zu repräsentieren?', fragt sie: 'Welche minimale Rate R(D) Bits pro Symbol ist erforderlich, wenn eine durchschnittliche Toleranz für einige Distortion D gegeben ist?'
Die Rate-Distortion-Funktion R(D) ist konvex und degressiv in D: eine größere Toleranz für Distortion ermöglicht niedrigere Raten. Bei D = 0 (verlustfrei): R(0) = H(source). Mit zunehmender D fällt R(D) ab.
Geometrisch: R(D) zeichnet eine Kurve auf dem (Rate, Distortion)-Bereich. Jede erreichbare (R, D)-Koordinate liegt auf oder über dieser Kurve. Punkte unter der Kurve sind unmöglich - man kann nicht unter dem grundlegenden Limit bei jeder Distortionstufe komprimieren.
Das Rate-Distortion-Theorem (Shannon, 1959): Für jedes R > R(D) existieren Codes, die eine erwartete Distortion von maximal D erreichen. Für R < R(D): Es gibt keinen Code, der die erwartete Distortion D erreicht. Die Kurve ist eine geometrische Grenze im (Rate, Distortion)-Bereich.