Teoria informacji/TI Wykład 3

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 $\phi$, średnią długość kodu definiujemy jako $L(\phi )=\sum _{s\in S}p(s)\cdot |\phi (s)|$

Dla danego S i parametru $r>1$ niech $L_r(S)$ będzie minimum ze wszystkich $L(\phi )$ dla dowolnego kodu $\phi :S\to {\mathrm{\Sigma }}^{*}$, gdzie $|\mathrm{\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 $\phi :S\to {\mathrm{\Sigma }}^{*}$ gdzie $|\mathrm{\Sigma }|=r$. Pokażmy, że

$H_r(S)\le L(\phi )$

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

Pozostało jedynie pokazać drugą część twierdzenia. Jeśli $H_r(S)=L_r(S)$, to znaczy, że $H_r(S)=L(\phi )$ dla pewnego kodu $\phi$. Znów na podstawie Złotego Lematu dostajemy $p(s)=\frac{1}{r^{|\phi (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 $\phi$ z $|\phi (s)|=\ell (s)$, i dla tego kodu $L(\phi )=H_r(S)$. A zatem $L_r(S)\le H_r(S)$, czyli musi zachodzić równość.

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 $\mathrm{\Sigma }$)
Jeśli $|S|\le |\mathrm{\Sigma }|$, przypisz po prostu jakieś symbole obiektom z S. W przeciwnym wypadku:
1. Jeśli $|\mathrm{\Sigma }|>2$, w razie konieczności uzupełnij S symbolami o prawdopodobieństwie 0, 
   tak aby $|S|mod(|\mathrm{\Sigma }|-1)=1$.
2. Wybierz $k=|\mathrm{\Sigma }|$ symboli $t_1,\dots ,t_k\in S$ o minimalnych prawdopodobieństwach.
3. Uruchom rekurencyjnie ten algorytm dla zbioru $S^{\prime }=S-\{t_1,\dots ,t_k\}+\{\mathrm{\#}\}$ z prawdopodobieństwami 
   $q_s=p_s$ dla $s\in S$ i $q_{\mathrm{\#}}=p_{t_1}+\dots +p_{t_k}$.
4. Mając dane drzewo $T_{S^{\prime }}$ z poprzedniego punktu skonstruuj drzewo $T_S$ w następujący sposób: 
   Dodaj k synów do słowa $T_{S^{\prime }}(\mathrm{\#})$ i oznacz ich jako $t_1,\dots ,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 {\mathrm{\Sigma }}^{*}$ w postaci krótszej niż sama $\alpha$. Wyobraźmy sobie jednak następujące kodowanie par:

$\begin{array}{rl}{s}_1{s}_1& \mapsto 0\\ s_1{s}_2& \mapsto 10\\ s_2{s}_1& \mapsto 110\\ s_2{s}_2& \mapsto 111\end{array}$

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(s_i,s_j)=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 \mathrm{\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{ℝ}$ można przedstawić na dwa równoważne sposoby:

$EX=\sum _{s\in S}p(s)\cdot X(s)=\sum _{t\in X(S)\subseteq \mathbb{ℝ}}t\cdot p(X=t)$

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

$\sum _{t\in \mathbb{ℝ}}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{ℝ}$: $E(\alpha X+\beta Y)=\alpha EX+\beta EY$

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{ℝ}$ i $Y:Q\to \mathbb{ℝ}$, 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}=EX$ i $E\hat{Y}=EY$. 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)=EX=E\hat{X}$, $H_r(Q)=EY=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,\dots ,s_n)=p(s_1)\cdot \dots \cdot p(s_n)$. Wtedy $H_r{S}^n=n\cdot H_{r}S$.