Teoria informacji/TI Wykład 3

Jak widzieliśmy na przykładzie z grą, 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$, 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ęść twierdzenie. 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. Prosty algorytm rozwiązujący ten problem podał Huffman. Wygląda on następująco:

Algorytm Huffmana
(dla zbioru kodowanego S i alfabetu $\mathrm{\Sigma }$)
Jeśli $|S|\le |\mathrm{\Sigma }|$ to przypisz po prostu jakieś symbole obiektom z S. W przeciwnym wypadku
1. 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 je 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:

$s_1{s}_1\mapsto 0$

$s_1{s}_2\mapsto 10$

$s_2{s}_1\mapsto 110$

$s_2{s}_2\mapsto 111$

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. Można to zrobić przez żmudne elementarne wyliczenia, ale spróbujemy uzyskać wynik na podstawie ogólnych własności zmiennych losowych.

Przypomnijmy że wartość oczekiwana 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{(}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 $\psi (X)$, czyli sumę p(s) po wszystkich s dla których $\psi (X(S))$ jest spełnione.

Przypominamy z Rachunku Prawdopodobieństwa:

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 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{(}R)$ i $Y:Q\to \mathbb{(}R)$, definiujemy zmienne $\widehat{(}X)$, $\widehat{(}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)}$. Rozkład sumy tych zmiennych będzie miał postać

$(\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)}$

Ale zgodnie z definicją, to jest dokładnie zmienna losowa 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:

$H_r{S}^n=n\cdot H_{r}S$