Teoria informacji/TI Ćwiczenia 5

From Studia Informatyczne

Spis treści

Ćwiczenia

Ćwiczenie 1 [Warunkowa entropia łączna]

Udowodnij, że H(A,B|C) \leq H(A|C) + H(B|C)

i że równość zachodzi wtedy i tylko wtedy, gdy A i B są niezależne w odniesieniu do C, czyli

p (a \wedge b|c) = p(a|c) \cdot p(b|c).

Rozwiązanie

Przeprowadzimy dowód identyczny jak w twierdzeniu o entropii łącznej.

\aligned H(A|C) + H(B|C) & = \sum_{a,c} p(a \wedge c) \log \frac{1}{p(a|c)} + \sum_{b,c} p(b \wedge c) \log \frac{1}{p(b|c)}\\ & = \sum_{a,b,c} p(a \wedge b|c) \log \frac{1}{p(a|c)}+ \sum_{a,b,c} p(a \wedge b|c) \log \frac{1}{p(b|c)}\\ & = \sum_{a,b,c} p(a \wedge b \wedge c) \log \frac{1}{p(a|c) \cdot p(b|c)} \endaligned

Z drugiej strony mamy z definicji

H(A,B|C) & = \sum_{a,b,c} p(a \wedge b \wedge c)\log \frac{1}{p(a \wedge b|c)}

Dowodzona równość sprowadza się zatem do prostego faktu, że dla dowolnych wartości a, b i c:p (a \wedge b|c) \ge p(a|c) \cdot p(b|c). Dodatkowo równość zachodzi wtedy i tylko wtedy, gdy dla każdej trójki a, b, c wartości te są równe, czyli A i B są niezależne w odniesieniu do C.


Ćwiczenie 2 [Zawieranie informacji wzajemnych]

Udowodnij R(X;Y;Z) \le I(X;Y) \le H(X).


Ćwiczenie 3 [Informacja wzajemna trzech zmiennych]

Wskaż przykład zmiennych losowych X, Y, Z takich że

R(X;Y;Z)<0.

Rozwiązanie

Przykładowym rozwiązaniem może być następująca trójka: X i Y określające wyniki rzutów niezależnych monet

X=\bigg\{ \begin{matrix} 0 & \mbox{z prawd.} & \frac{1}{2}\\ 1 & \mbox{z prawd.} & \frac{1}{2} \end{matrix}
Y=\bigg\{ \begin{matrix} 0 & \mbox{z prawd.} & \frac{1}{2}\\ 1 & \mbox{z prawd.} & \frac{1}{2} \end{matrix}

Oraz Z = X \oplus Y.

Wtedy oczywiście H(X)=H(Y)=H(Z)=1. Każda para zmiennych jest niezależna, w szczególności I(Z;X)=0 i H(X|Z)=1.

Z wartości dwóch zmiennych można odtworzyć wartość trzeciej z nich: H(X|Y,Z)=0.

Podstawiając do wzoru otrzymujemy

R(X;Y;Z) = I(X;Y)-I(X;Y|Z) = I(X;Y)-H(X|Z)+H(X|Y,Z) = 0 - 1 + 0 = -1


Ćwiczenie 4 [Warunkowa entropia dla bliskich rozkładów]

Niech X' i X będą dwiema zmiennymi losowymi takimi że Pr(X' \neq X) \le \varepsilon (dla pewnego małego \varepsilon).

Pokaż że H(X'|X) może być dowolnie duże.

Rozwiązanie

Dla dowolnego n i zmiennej losowej X możemy skonstruować rozkład X', taki że Pr(X' \neq X) \le \varepsilon iH(X'|X) \ge n. W tym celu definiujemy zbiór Z rozłączny ze zbiorem wartości X i taki że |Z|= \lceil 2^\frac{n}{\varepsilon}\rceil. Rozkład X' niech będzie następujący:

X'=\bigg\{ \begin{matrix} X & \mbox{z prawd.} & 1-\varepsilon & &\\ z \in Z & \mbox{z prawd.} & \frac{\varepsilon}{\lceil 2^\frac{n}{\varepsilon}\rceil} & \mbox{ dla każdego } & z \in Z \end{matrix}

Pierwszy warunek jest oczywiście spełniony. Aby sprawdzić drugi obliczamy:

\aligned H(X'|X) & = \sum_{x',x} p(x,x')\log \frac{1}{p(x'|x)}\\ & = (1-\varepsilon) \cdot \log 1 + \sum_{z\in Z} p(z) \log \frac{1}{p(z)}\\ & = 0 + \varepsilon \cdot \log \frac{\lceil 2^\frac{n}{\varepsilon}\rceil}{\varepsilon}\\ & \ge n + \varepsilon \log \frac{1}{\varepsilon} \ge n. \endaligned


Ćwiczenie [Wąskie gardło]

Rozważmy zmienne losowe X, Y, Z tworzące łańcuch Markowa X \to Y \to Z (czyli Pr(Z=z|X,Y)=Pr(Z=z|Y)).

Udowodnij, że I(X;Z|Y)=0 (czyli cała wspólna informacja między X i Z musi zawierać się w Y).

Udowodnij własność wąskiego gardła, mówiącą że I(X;Z)\le H(Y).

Rozwiązanie

Wprost z definicji

\aligned I(X;Z|Y) & = H(Z|Y)-H(Z|X,Y)\\ & = \sum_{x,y,z} p(x \wedge y \wedge z) \bigg(\log \frac{1}{p(z|y)} - \log \frac{1}{p(z|x,y)}\bigg)\\ \endaligned

Skoro powyższe zmienne tworzą łańcuch Markowa, to wszystkie różnice mają tu zerowe wartości, a więc I(X;Z|Y)=0.

Aby udowodnić drugą część ćwiczenia wystarczy zauważyć, że

I(X;Z)=\underbrace{I(X;Z|Y)}_{=0}+\underbrace{R(X;Y;Z)}_{\le H(Y)}


Laboratorium

Zadanie 1

Treść

Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:

  1. Kodowanie Huffmana zastosowane do bloków 2 symboli.
  2. Kodowanie kolejnego symbolu pliku, a_{n+1}, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, a_n.
    W algorytmie tym, dla każdego symbolu a występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu, b, pod warunkiem a: p(b|a). Dla takiego rozkładu symboli b (przy ustalonym a) obliczany jest kod Huffmana \varphi_a. Kody są generowane dla wszystkich symboli a.
    Symbole pliku są kodowane kolejno, od pierwszego do ostatniego, przy czym symbol a_{n+1} kodowany jest za pomocą kodu \varphi_{a_n}. Tak zakodowana wiadomość jest możliwa do odkodowania, ponieważ w chwili dekodowania a_{n+1} symbol a_n jest już znany.
  3. Kodowanie analogiczne do (2), jednakże przebiegające od końca pliku do początku, zatem korzystające z kodu \varphi_{a_{n+1}} do zakodowania a_n. W tym przypadku \varphi_b jest kodem wygenerowanym dla rozkładu p(a|b) symboli a poprzedzających ustalony symbol b.

Uwaga: zwróć uwagę, że warianty (2) i (3) wykorzystują kody w nietypowy sposób - do zakodowania jednej wiadomości używanych jest wiele różnych kodów, stosowanych na przemian do kodowania kolejnych symboli.

Polecenie

  1. Porównaj warianty (1) i (2) oraz (2) i (3) pod względem osiąganego stopnia kompresji:
    • Który z wariantów pozwoli uzyskać większy stopień kompresji? Czy zależy to od charakterystyki danych wejściowych? Jeśli to możliwe, podaj ścisły dowód.
    • Czy fakt, że znaki w pliku tekstowym są zapisane w "naturalnej" kolejności, czyli w takiej, w jakiej są odczytywane przez człowieka, pozwala na uzyskanie większego stopnia kompresji za pomocą metody (2) niż (3)?
    • Oprócz wariantów (1)-(3) rozważ też sytuację, gdy zamiast kodu Huffmana stosowany jest kod, którego średnia długość jest dokładnie równa entropii odpowiedniego rozkładu (dla zainteresowanych: kodowanie arytmetyczne jest metodą, która w pewnym sensie pozwala osiągnąć średnią długość kodu równą entropii; zob. arithmetic coding).
  2. Jaka jest złożoność pamięciowa i czasowa metod (1)-(3)?
  3. Napisz programy kompresuj1, kompresuj2 i kompresuj3, implementujące algorytmy (1)-(3). Wykonaj eksperymenty, które potwierdzą poprawność Twoich odpowiedzi na powyższe pytania.

Wskazówki

Wskazówka I:

Aby odpowiedzieć na pytania z pkt. 1 skorzystaj z własności entropii łącznej i warunkowej.

Wskazówka II:

W eksperymentach możesz wykorzystać dwa pliki tekstowe:

  • naturalny.txt - zawierający fragment tekstu w języku polskim lub angielskim,
  • cyfry.txt - zawierający ciąg cyfr z przedziału '1' - '3', generowanych niezależnie z rozkładu równomiernego.

Pamiętaj, aby pliki były dostatecznie długie - tylko wtedy uzyskane wyniki będą wiarygodne.

Rozwiązanie

Rozwiązanie zadania powinno zawierać:

  • wykonywalne programy,
  • kody źródłowe programów,
  • dane wejściowe wykorzystane do eksperymentów,
  • raport zawierający:
    • odpowiedzi na pytania, być może z dowodami,
    • opis wykonanych eksperymentów i wykorzystanych danych wejściowych,
    • interpretację wyników eksperymentów.

Pliki źródłowe i raport należy podpisać imieniem i nazwiskiem autora.

Ocenie podlegać będzie: poprawność i ścisłość rozumowania, poprawność implementacji, umiejętność zaplanowania eksperymentów i interpretacji ich wyników. Nie będzie brana pod uwagę efektywność czasowa i pamięciowa programów.


Zadanie 2

Treść

Dane wejściowe mają postać ciągu \{a_i\}_1^{10000} symboli nad alfabetem A = A_0 \cup A_1 \cup A_2, gdzie A_0=\{spacja\}, A_1=\{'a',...,'z'\}, A_2=\{'0',...,'9'\}. Kolejne znaki tego ciągu są generowane losowo z następującego rozkładu prawdopodobieństwa:

  • symbol a_1 jest generowany z rozkładu (\mu_1+\mu_2)/2,
  • jeśli a_n \in A_0 , to a_{n+1} jest generowany z rozkładu (\mu_1+\mu_2)/2,
  • jeśli a_n \in A_1 , to a_{n+1} jest generowany z rozkładu (\mu_0+\mu_1)/2,
  • jeśli a_n \in A_2 , to a_{n+1} jest generowany z rozkładu (\mu_0+\mu_2)/2,

gdzie \mu_0, \mu_1 i \mu_2 to rozkłady prawdopodobieństwa na zbiorze A takie, że:

  • \mu_0(A_0)=1 (czyli rozkład \mu_0 jest skupiony na zbiorze A_0 ),
  • \mu_1(A_1)=1,
  • \mu_2(A_2)=1.

Polecenie

  1. Opracuj możliwie najskuteczniejszą metodę kompresji danych o powyższej charakterystyce, opartą na kodowaniu Huffmana. Zaimplementuj ją.
  2. Oszacuj teoretycznie ile średnio bitów L pliku skompresowanego będzie przypadało na jeden symbol pliku wejściowego. Przyjmij, że znana jest entropia rozkładów \mu_1 i \mu_2 .
  3. Wykonaj eksperymenty, aby sprawdzić swoje przewidywania. Wygeneruj kilka ciągów o podanej wyżej charakterystyce dla różnych wyborów rozkładów \mu_1 i \mu_2 , skompresuj je Twoją metodą i porównaj rozmiary plików wejściowych i wynikowych.
  4. Oszacuj teoretycznie wartość L dla zwykłej kompresji Huffmana zastosowanej do danych o podanej charakterystyce. Czy Twój algorytm osiąga lepszą kompresję?
  5. Jaka dodatkowa informacja musiałaby być zapisana w skompresowanym pliku, aby umożliwić jego dekompresję? Oszacuj jej rozmiar.

Wskazówka I:

Ciąg \{a_i\}_1^{10000} to ciąg złożony z 10000 znaków (liter, cyfr lub spacji), w którym występują słowa złożone z samych liter lub z samych cyfr, rozdzielane pojedynczymi spacjami. Prawdopodobieństwo wystąpienia słowa złożonego z liter jest takie samo jak słowa złożonego z cyfr. Prawdopodobieństwa wystąpienia poszczególnych symboli mogą być różne - zależnie od rozkładów \mu_1 i \mu_2 .

Wskazówka II:

W algorytmie kompresji wykorzystaj jednocześnie kilka różnych kodów Huffmana, stosowanych na przemian, podobnie jak w algorytmach (2) i (3) z Zadania 1.


Zadanie 3 (konkurs)

Wstęp

Prowadzący powinien przygotować dwa pliki, dane1 i dane2, zawierające dane o pewnej szczególnej charakterystyce (takiej samej w obu plikach). Plik dane1 zostanie udostępniony studentom, którzy na jego podstawie będą musieli określić typ redundacji występującej w danych i opracować możliwie najskuteczniejszy algorytm kompresji oparty na kodowaniu Huffmana.

Każdy student zaimplementuje swój algorytm w postaci dwóch programów, kompresuj i dekompresuj. Programy zostaną przesłane do prowadzącego, który wykona za ich pomocą następujące czynności:

  1. skompresuje plik dane2, otrzymując plik skompresowany,
  2. zdekompresuje plik skompresowany, otrzymując plik zdekompresowany,
  3. jeśli pliki dane2 i zdekompresowany będą identyczne, przyzna autorowi danego algorytmu liczbę punktów równą: <rozmiar_pliku_dane2> / <rozmiar_pliku_skompresowany>,
  4. w przeciwnym przypadku (gdy pliki się różnią), przyzna 0 punktów.

Wygra student, który otrzyma najwięcej punktów, czyli ten, którego program poprawnie skompresuje i zdekompresuje plik dane2, uzyskując przy tym największy stopień kompresji. Prowadzący może też osobno przyznawać punkty za pomysłowość w opracowaniu algorytmu, wówczas punkty może otrzymać też student, którego implementacja okazała się niepoprawna.

W celu opracowania skutecznego algorytmu kompresji studenci będą musieli wykonać dokładną analizę (np. statystyczną) pliku dane1. Prowadzący może też podać dodatkowe informacje, np. źródło pochodzenia danych i ich znaczenie - ułatwi to opracowanie skutecznego algorytmu.

Prowadzący może wykorzystać do testów kilka plików o różnej długości zamiast jednego pliku dane2. Pozwoli to na bardziej obiektywne porównanie różnych algorytmów, których jakość może w istotny sposób zależeć od rozmiaru kompresowanych danych.

Przykład

Fragment pliku dane1 lub dane2 może wyglądać następująco:

3             6             1998         40.6
3             7             1998         44.2
3             8             1998         42.5
3             9             1998         47.6
3             10            1998         47.1
3             11            1998         29.0
3             12            1998         25.2
3             13            1998         29.5
3             14            1998         37.9
3             15            1998         38.1
3             16            1998         35.1
3             17            1998         37.8
3             18            1998         38.2
3             19            1998         38.8
3             20            1998         40.6
3             21            1998         38.0
3             22            1998         33.7
3             23            1998         38.2
3             24            1998         42.6
3             25            1998         41.1
3             26            1998         46.6
3             27            1998         63.6
3             28            1998         69.9
3             29            1998         67.7
3             30            1998         68.1
3             31            1998         72.0

Powyższe dane są zapisem dziennych temperatur w Nowym Jorku, wyrażonych w stopniach Fahrenheita. Pochodzą ze strony Uniwersytetu w Dayton. Pierwsze trzy kolumny to miesiąc, dzień i rok, kiedy wykonano pomiar. Ostatnia kolumna to wartość temperatury.

Można opracować algorytm, który kompresuje dane powyższego typu znacznie skuteczniej niż zwykła kompresja Huffmana. W tym celu warto skorzystać z następujących obserwacji:

  • Pola są rozdzielane spacjami, lecz mają stałą szerokość, dlatego liczbę spacji uzupełniających dane pole można obliczyć bez konieczności zapisywania jakiejkolwiek informacji w pliku skompresowanym.
  • Kolejne linie odpowiadają kolejnym dniom, dlatego numer dnia, miesiąca i roku można obliczyć na podstawie wartości z poprzedniej linii.
    Uwaga: prowadzący może wykonać losową permutację linii, wtedy zadanie będzie ciekawsze, choć trudniejsze. W takiej sytuacji nie będzie można już obliczyć daty w kolejnej linii, tylko trzeba będzie ją zapisywać w postaci skompresowanej. Najkorzystniej jest zastosować oddzielny kod Huffmana dla każdej kolumny, ponieważ w każdej kolumnie wartości mają inny rozkład. Ponadto nie należy kodować pojedynczych znaków ASCII, ale traktować całą liczbę jako jeden symbol.
  • Wartość temperatury należy również kodować oddzielnym kodem Huffmana, traktując całą wartość jako jeden symbol. Ewentualnie można zauważyć, że cyfra po przecinku ma rozkład bardzo bliski równomiernemu, który nie zależy od wartości przed przecinkiem, więc część całkowitą i ułamkową temperatury można kodować oddzielnymi kodami Huffmana bez wyraźnego pogorszenia stopnia kompresji. Łączny rozmiar obydwu kodów będzie znacznie mniejszy niż rozmiar jednego kodu dla całej liczby, co pozwoli uzyskać mniejszy rozmiar wynikowego pliku (należy pamiętać, że w nagłówku pliku skompresowanego muszą być zapisane wszystkie wykorzystywane kody, inaczej dekompresja nie będzie możliwa).
  • Temperatura w dwóch kolejnych dniach jest zwykle podobna. Można więc kodować nie wartość temperatury, ale zmianę wartości temperatury między dwoma kolejnymi dniami. W ten sposób będzie kodowana liczba, której stopień rozproszenia (a więc entropia) jest znacznie mniejszy.
  • Temperatura o tej samej porze roku w dwóch różnych latach jest zwykle podobna, co też można wykorzystać do poprawy stopnia kompresji, szczególnie w sytuacji, gdy linie pliku są spermutowane (sąsiednie linie nie muszą opisywać kolejnych dni) - wówczas trudno jest wykorzystać fakt, że temperatura w kolejnych dniach jest podobna. Na przykład można policzyć na podstawie pliku dane1 jakie były średnie temperatury w poszczególnych porach roku i następnie - zamiast wartości temperatury - kodować różnicę temperatury w danym dniu i średniej temperatury w danej porze roku.
  • Niekoniecznie wszystkie używane kody Huffmana muszą być zapisywane w pliku skompresowanym. Na przykład numer dnia będzie miał rozkład bardzo bliski równomiernemu, przynajmniej na zbiorze wartości {1,2...,28}. Można więc przyjąć a priori rozkład równomierny, wtedy program dekompresuj będzie umiał samodzielnie wygenerować odpowiedni kod Huffmana, bez konieczności wczytywania go z pliku skompresowanego.
  • Wszędzie tam, gdzie jest stosowany kod Huffmana, można też zastosować kodowanie bloków, co powinno poprawić nieco stopień kompresji.