Simpleks probabilistyczny
Rozkład probabilistyczny nad q symbolami to punkt w (q−1)-wymiarowym simpleksie probabilistycznym: zbiór wszystkich wektorów (p₁, ..., p_q) z pᵢ ≥ 0 i Σ pᵢ = 1.
Dla q = 2: simpleks to odcinek linii [0,1], sparametryzowany pojedynczym prawdopodobieństwem p. Dla q = 3: simpleks to trójkąt równoboczny w ℝ². Każdy wierzchołek to rozkład deterministyczny (całe prawdopodobieństwo na jeden symbol); środek to rozkład jednostajny.
Entropia H(p) przypisuje każdemu punktowi simpleksu liczbę rzeczywistą. Geometria funkcji określa wiele fundamentalnych wyników.
Wklęsłość
H jest wklęsła na simpleksie: dla dowolnych dwóch rozkładów p i q oraz dowolnego λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Mieszanina dwóch rozkładów ma entropię co najmniej równą średniej ważonej ich poszczególnych entropii. Intuicja: mieszanie dwóch źródeł zwiększa niepewność.
Weryfikacja wklęsłości
Dla binarnej entropii H(p), wklęsłość jest widoczna na wykresie: krzywa się wyznacza, nigdy nie opada poniżej żadnego akord łączący dwa punkty.
Formalny test wklęsłości: druga pochodna H''(p) ≤ 0 wszędzie.
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 dla wszystkich p ∈ (0,1)
Druga pochodna jest ściśle ujemna wszędzie we wnętrzu: H jest ściśle wklęsła.
Rozkład osiągający pojemność
Pojemność kanału jest definiowana jako maksimum informacji wzajemnej względem wszystkich rozkładów wejścia p(x):
C = max_{p(x)} I(X; Y)
gdzie I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Dla binarnego kanału symetrycznego z prawdopodobieństwem błędu Q: rozkład wejścia osiągający pojemność to rozkład jednostajny p(0) = p(1) = 0.5.
Dlaczego: H(Y) jest maksymalizowana przez jednostajny rozkład wyjścia. Przy binarnym kanale symetrycznym, jednostajne wejście daje jednostajne wyjście. Każdy inny rozkład wejścia zmniejsza H(Y), zmniejszając I(X;Y).
Geometrycznie: informacja wzajemna I(X;Y) jest funkcją wklęsłą rozkładu wejścia p(x) na simpleksie. Maksimum funkcji wklęsłej na zbiorze wypukłym jest osiągane w unikalnym punkcie (środek, dla kanału symetrycznego).
Dywergencja Kullbacka-Leiblera
Dywergencja Kullbacka-Leiblera (entropia względna) od rozkładu q do rozkładu p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 zawsze (nierówność Gibbsa). D(p || q) = 0 wtedy i tylko wtedy gdy p = q.
D nie jest prawdziwą odległością: jest asymetryczna (D(p||q) ≠ D(q||p) generalnie) i nie spełnia nierówności trójkąta. Ale działa jak miara tego, jak 'daleko' p jest od q w przestrzeni probabilistycznej.
Dywergencja KL pojawia się wszędzie w teorii informacji:
- Informacja wzajemna: I(X;Y) = D(p(x,y) || p(x)p(y)). Informacja wzajemna to dywergencja KL między rozkładem łącznym i iloczynem rozkładów brzegowych — jak daleko łączny rozkład jest od niezależności.
- Nierówność Gibbsa: noiseless coding theorem wynika bezpośrednio z D(p || q) ≥ 0.
- Pojemność kanału: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Obliczanie dywergencji KL
Przykład: p = (0.5, 0.5) jednostajny binarny, q = (0.8, 0.2) skośny binarny.
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 bity
Pojemność kanału jako odległość geometryczna
Pojemność kanału ma interpretację geometryczną w przestrzeni rozkładów probabilistycznych.
Dla kanału p(y|x), definiuj rozkład wejścia osiągający pojemność p*(x). Pojemność spełnia:
C = D(p*(y) || r(y))
gdzie p(y) = Σ p(x) p(y|x) to rozkład wyjścia pod optymalnym wejściem, a r(y) = argmin_r max_x D(p(y|x) || r(y)) to rozkład wyjścia minimalnej informacji — punkt w przestrzeni rozkładów wyjścia najbliższy (w dywergencji KL) do wszystkich warunkowych rozkładów wyjścia jednocześnie.
To jest informacyjno-geometryczny pogląd: pojemność kanału to promień najmniejszej kuli dywergencji KL w przestrzeni rozkładów wyjścia, która zawiera wszystkie rozkłady warunkowe p(y|x=0) i p(y|x=1).
Dla BSC: p(y|x=0) = (1−Q, Q) i p(y|x=1) = (Q, 1−Q). Przez symetrię, minimalny rozkład informacji r(y) = (0.5, 0.5). Pojemność = D((1−Q, Q) || (0.5, 0.5)) = 1 − H(Q). Wzór odzyskuje standardowy wynik z geometrii.
Pojemność z dywergencji KL
Zweryfikuj geometryczny wzór: C = D(p(y|x=0) || r(y)) dla BSC z Q = 0.1, r(y) = (0.5, 0.5).
p(y|x=0) = (0.9, 0.1) (wyślij 0, odbierz 0 z prawdopodobieństwem 0.9, odbierz 1 z prawdopodobieństwem 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ów
Sprawdzenie: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 bitów ✓
Szybkość-zniekształcenie & Granice kompresji
Teoria szybkości-zniekształcenia rozszerza teorię informacji na kompresję stratną. Zamiast pytać 'jaka jest minimalna liczba bitów aby reprezentować źródło dokładnie?' pyta: 'mając tolerancję dla jakiegoś średniego zniekształcenia D, jaka jest minimalna szybkość R(D) bitów na symbol?'
Funkcja szybkości-zniekształcenia R(D) jest wypukła i malejąca w D: większa tolerancja zniekształcenia pozwala na niższe szybkości. Dla D = 0 (bezstratna): R(0) = H(źródło). Gdy D wzrasta, R(D) → 0.
Geometrycznie: R(D) śledzi krzywą na płaszczyźnie (szybkość, zniekształcenie). Każda osiągalna para (R, D) leży na lub powyżej tej krzywej. Punkty poniżej krzywej są niemożliwe — nie możesz kompresować poniżej fundamentalnego limitu na żadnym poziomie zniekształcenia.
Twierdzenie o szybkości-zniekształceniu (Shannon, 1959): dla dowolnego R > R(D), istnieją kody osiągające oczekiwane zniekształcenie co najwyżej D. Dla R < R(D): żaden kod nie osiąga oczekiwanego zniekształcenia D. Krzywa jest geometryczną granicą w przestrzeni (szybkość, zniekształcenie).