Teoria informacji/TI Wykład 3

From Studia Informatyczne

Minimalna długość kodu

Jak widzieliśmy w analizie przykładu gry w zgadywanie, jeśli wszystkie prawdopodobieństwa są potęgami \frac{1}{2}, to entropia jest równa średniej długości optymalnego kodu. Udowodnimy, że zawsze stanowi ona dolne ograniczenie:


Definicja [długość kodu]

Dla danego kodu \varphi, średnią długość kodu definiujemy jako
L(\varphi ) = \sum_{s \in S} p(s) \cdot |\varphi (s)|

Dla danego S i parametru r>1 niech L_r(S) będzie minimum ze wszystkich L(\varphi) dla dowolnego kodu \varphi:S \to \Sigma^*, gdzie |\Sigma|=r. Zauważmy, że na mocy Twierdzenia McMillana wystarczy, że znajdziemy minimum dla wszystkich kodów bezprefiksowych.


Twierdzenie

Dla dowolnej skończonej przestrzeni probabilistycznej S
H_r(S) \le L_r(S)
i równość zachodzi wtedy i tylko wtedy, gdy wszystkie prawdopodobieństwa p(s) są potęgami \frac{1}{r}

Dowód

Rozważmy dowolny kod \varphi:S \to \Sigma^* gdzie |\Sigma|=r. Pokażmy, że

H_r(S) \le L(\varphi)

Wystarczy w tym celu użyć Złotego Lematu dla x_i=p(s_i) i y_i=\frac{1}{r^{|\varphi(s_i)|}}.

Pozostało jedynie pokazać drugą część twierdzenia. Jeśli H_r(S)=L_r(S), to znaczy, że H_r(S)=L(\varphi) dla pewnego kodu \varphi. Znów na podstawie Złotego Lematu dostajemy p(s) = \frac{1}{r^{|\varphi (s)|}} dla wszystkich s \in S.

Z drugiej strony, jeśli wszystkie prawdopodobieństwa są postaci \frac{1}{r^{\ell(s)}}, to na mocy nierówności Krafta istnieje kod \varphi z |\varphi(s)|=\ell(s), i dla tego kodu L(\varphi)=H_r(S). A zatem L_r(S) \le H_r(S), czyli musi zachodzić równość. image:End_of_proof.gif


Znalezienie optymalnego kodu bezprefiksowego dla danego rozkładu prawdopodobieństwa nie jest wcale trudnym zadaniem. Algorytm rozwiązujący ten problem podał amerykański inżynier David A. Huffman (1925-1999).

Algorytm Huffmana
(dla zbioru kodowanego S i alfabetu \Sigma)
Jeśli |S| \le |\Sigma|, przypisz po prostu jakieś symbole obiektom z S. W przeciwnym wypadku:
1. Jeśli |\Sigma| > 2, w razie konieczności uzupełnij S symbolami o prawdopodobieństwie 0, 
   tak aby |S| \mod (|\Sigma| -1) = 1.
2. Wybierz k=|\Sigma| symboli t_1, \ldots, t_k \in S o minimalnych prawdopodobieństwach.
3. Uruchom rekurencyjnie ten algorytm dla zbioru S'=S-\{t_1, \ldots, t_k\}+\{\#\} z prawdopodobieństwami 
   q_s=p_s dla s \in S i q_\# = p_{t_1} + \ldots + p_{t_k}.
4. Mając dane drzewo T_{S'} z poprzedniego punktu skonstruuj drzewo T_S w następujący sposób: 
   Dodaj k synów do słowa T_{S'}(\#) i oznacz ich jako t_1, \ldots, t_k.


Dla przedstawionej powyżej definicji kodu problem mamy zatem rozwiązany. Niestety, w większości wypadków długość takiego optymalnego kodu będzie się różniła od dolnej granicy H_r(S). Na szczęście możemy ten problem obejść. Okazuje się, że dla dowolnego zadanego S i p można uzyskiwać mniejszą średnią długość kodu, dowolnie zbliżając się do H_r(S). Uzyskuje się to przez lekkie poszerzenie samego pojęcia kodu.


Przykład [Kodowanie par]

Niech S=\{s_1,s_2\} z p(s_1)=\frac{3}{4}, p(s_2)=\frac{1}{4}. Oczywiście L_2(S)=1. (Jednocześnie łatwo oszacować, że H_2(S)<1). Oznacza to, że nie możemy zakodować wiadomości \alpha \in \Sigma^* w postaci krótszej niż sama \alpha. Wyobraźmy sobie jednak następujące kodowanie par:

\aligned  s_1 s_1 & \mapsto 0 \\  s_1 s_2 & \mapsto 10\\  s_2 s_1 & \mapsto 110\\  s_2 s_2 & \mapsto 111 \endaligned

Nie jest to w dosłownym sensie kod dla S, ale wygląda na to, że możemy go użyć do zakodowania dowolnych wiadomości o parzystej długości. Faktycznie, zgodnie z definicją to jest kod dla S^2. Rozważmy S^2 = S \times  S jako produkt (probabilistyczny) przestrzeni, w którym

p \left(  s_i, s_j \right) = p(s_i) \cdot p(s_j)

Średnia długość naszego kodowania dwuznakowych bloków będzie wynosić

\left( \frac{3}{4} \right)^2 \cdot 1 + \frac{3}{4} \cdot \frac{1}{4}\cdot (2 + 3) + \left( \frac{1}{4} \right)^2 \cdot 3 = \frac{9}{16} + \frac{15}{16} + \frac{3}{16} = \frac{27}{16} < 2

Jak można się spodziewać, podążając tym tropem dla kodów złożonych z trzech, czterech i więcej znaków, będziemy mogli otrzymać coraz efektywniejsze kodowania. Czy jednak możemy zejść poniżej granicy entropii, czyli uzyskać

\frac{L_r (S^n )}{n} < H_r (S)

dla pewnego n?

Udowodnimy później, że to jest niemożliwe, ale Pierwsze Twierdzenie Shannona pokaże, że możemy zbliżyć się do niej dowolnie blisko dla n \to \infty.

Najpierw jednak policzmy entropię H(S^n) przestrzeni S^n interpretowanej jako przestrzeń produktowa.

Entropia przestrzeni produktowej

Entropię H(S^n) możemy znaleźć przez nieco żmudne elementarne wyliczenia, ale wygodniej będzie skorzystać z ogólnych własności zmiennych losowych opisanych w wykładzie 7 z Rachunku prawdopodobieństwa i statystyki.

Przypomnijmy, że wartość oczekiwaną (zwaną też nadzieją matematyczną) zmiennej losowej X:S \to \mathbb{R} można przedstawić na dwa równoważne sposoby:

E X = \sum_{s \in S} p(s) \cdot X(s) = \sum_{t \in X(S) \subseteq \mathbb{R} }  t \cdot p (X = t)

Drugi sposób często zapisuje się prościej jako

\sum_{t \in \mathbb{R} }  t \cdot p (X = t)

przyjmując, że suma dowolnie wielu zer daje 0.

Używana tutaj notacja p(X=t) jest szczególnym przypadkiem notacji p (\psi (X)), określającej prawdopodobieństwo że zachodzi zdarzenie \psi(X), czyli sumę p(s) po wszystkich s \in S, dla których zdanie \psi(X(S)) jest spełnione.

Przypominamy z Rachunku Prawdopodobieństwa (por. wspomniany wykład 7):

Fakt [Liniowość wartości oczekiwanej]

Jeśli X i Y są dowolnymi zmiennymi losowymi (określonymi na tej samej przestrzeni probabilistycznej), to dla dowolnych \alpha , \beta \in \mathbb{R}:
E (\alpha X + \beta Y) = \alpha E X + \beta E Y


Rozważmy teraz przypadek, gdy mamy dwie przestrzenie probabilistyczne S i Q. (Zwyczajowo, jeśli nie powoduje to niejasności, będziemy używać tej samej litery p na określenie prawdopodobieństwa we wszystkich przestrzeniach).

Niech S \times Q będzie przestrzenią produktową z prawdopodobieństwem określonym następująco

p(s,q)=p(s) \cdot p(q).

Dla zmiennych losowych X : S \to \mathbb{R} i Y : Q \to \mathbb{R}, definiujemy zmienne \hat{X}, \hat{Y} na S \times Q jako

\hat{X} (s,q) = X(s)
\hat{Y} (s,q) = Y(q)

Oczywiście mamy:

p (\hat{X} = t) = \sum_{\hat{X}(s,q) = t} p (s,q) = \sum_{ {X}(s) = t} \;  \sum_{q \in Q}  p(s) \cdot p(q)
= \sum_{ {X}(s) = t} p(s) = P(X = t)

i analogicznie p (\hat{Y} = t) = p (Y = t). Zatem E \hat{X} = E X i E \hat{Y} = E Y. Z liniowości wartości oczekiwanej

E (\hat{X} + \hat{Y}) = E \hat{X} + E \hat{Y} = EX + EY

Niech teraz X: s \mapsto \log_r \frac{1}{p(s)} i Y: q \mapsto \log_r \frac{1}{p(q)}. Zgodnie z definicją entropii, mamy więc H_r(S) = E X =E \hat{X}, H_r(Q) = E Y = E \hat{Y}. Z przyjętych definicji i własności funkcji \log otrzymujemy

(\hat{X} + \hat{Y}) (s,q) =  \log_r \frac{1}{p(s)} + \log_r  \frac{1}{p(q)} = \log_r \frac{1}{p(s)} \cdot \frac{1}{p(q)}= \log_r \frac{1}{p(s,q)}

A zatem (\hat{X} + \hat{Y}) jest dokładnie tą zmienną losową na S \times Q, której wartość oczekiwana jest entropią S \times Q. Czyli

H_r (S \times Q) = E (\hat{X} + \hat{Y}) = H_r(S)+H_r(Q).

W konsekwencji:

Fakt

Niech S^n będzie n-tą potęgą przestrzeni S z prawdopodobieństwem p(s_1,\ldots ,s_n) = p(s_1) \cdot \ldots \cdot p(s_n). Wtedy
H_rS^n=n \cdot H_rS.