Podstawy Teorii Informacji

Poza bitami: miara informacji

W analizie kompresji rozróżniamy techniki bezstratne i stratne. Metody bezstratne zachowują wszystkie dane, wykorzystując redundancję, natomiast metody stratne zmniejszają rozmiar przez trwałe odrzucenie wybranych informacji. Powstaje pytanie, jak zmierzyć ilość informacji w danych i określić granicę kompresji bezstratnej.

Narzędzia te dostarcza teoria informacji, rozwijana między innymi przez Claude'a E. Shannona. W pracy z 1948 roku Shannon opisał matematyczny model komunikacji i miary informacji. Informację można w tym ujęciu wiązać z nieprzewidywalnością zdarzeń, czyli z ich zaskoczeniem.

Autoinformacja: miara zaskoczenia pojedynczego zdarzenia

Zanim będziemy mogli zmierzyć informację w całym pliku lub wiadomości, musimy zacząć od najmniejszego składnika. Jest nim pojedyncze zdarzenie lub symbol. Miarą tego jest .

Zależność między prawdopodobieństwem a zaskoczeniem

Rozważmy dwa przykładowe zdania o jutrzejszej pogodzie:

Słońce wzejdzie na wschodzie.
Wystąpi rzadka burza tropikalna i rekordowy opad śniegu.

Pierwsze zdanie opisuje zdarzenie o prawdopodobieństwie bliskim 1, więc wnosi niewiele nowej informacji. Drugie opisuje zdarzenie rzadkie, więc jego wystąpienie byłoby bardziej informacyjne. Autoinformacja rośnie wraz ze spadkiem prawdopodobieństwa, a zależność jest logarytmiczna: rzadkie zdarzenia mają większą autoinformację, częste zdarzenia mniejszą.

Sformułowanie matematyczne

Autoinformacja $I(x)$ zdarzenia $x$ o prawdopodobieństwie $P(x)$ jest definiowana wzorem:

I(x) = \log_2\left(\frac{1}{P(x)}\right) = -\log_2(P(x))

Wzór można odczytać w kilku krokach:

$P(x)$ : To prawdopodobieństwo zdarzenia $x$ . Dla tego wzoru przyjmujemy $0 < P(x) \le 1$ . Wartość 1 oznacza zdarzenie pewne, a wartość 0 oznacza zdarzenie niemożliwe, dla którego autoinformacja nie ma skończonej wartości.
$\frac{1}{P(x)}$ : Odwrotność prawdopodobieństwa rośnie dla rzadkich zdarzeń. Dla $P(x) = 0.99$ wynosi około 1.01, a dla $P(x) = 0.0001$ wynosi 10,000.
$\log_2$ : Logarytm o podstawie 2 mierzy informację w bitach. Dla niezależnych zdarzeń informacja wspólnego wyniku jest sumą autoinformacji obu zdarzeń.
Znak minus ( $-$ ): Dla $0 < P(x) \le 1$ logarytm ma wartość ujemną lub równą zero. Znak minus sprawia, że autoinformacja jest nieujemna.

Przykład 1: rzut symetryczną monetą

Zastosujmy wzór do pojedynczego rzutu symetryczną monetą.

Są dwa możliwe wyniki: Orzeł (O) i Reszka (R).
Prawdopodobieństwo wyrzucenia orła wynosi $P(O) = 0.5$ .
Prawdopodobieństwo wyrzucenia reszki wynosi $P(R) = 0.5$ .

Teraz obliczmy autoinformację dla zaobserwowania orła:

I(O) = -\log_2(P(O)) = -\log_2(0.5) = -\log_2\left(\frac{1}{2}\right) = -(-1) = 1 \text{ bit}

Autoinformacja dla reszki również wynosi 1 bit. Rozstrzygnięcie niepewności zdarzenia o dwóch jednakowo prawdopodobnych wynikach dostarcza dokładnie jednego bita informacji.

Przykład 2: rzut niesymetryczną monetą

Rozważmy monetę niesymetryczną, w której jeden wynik jest bardziej prawdopodobny niż drugi.

Załóżmy, że moneta jest obciążona, aby najczęściej wypadała Reszka.
Prawdopodobieństwo Orła: $P(O) = 0.125$ (czyli 1/8).
Prawdopodobieństwo Reszki: $P(R) = 0.875$ (czyli 7/8).

Obliczmy autoinformację dla każdego wyniku:

I(O) = -\log_2(0.125) = -\log_2\left(\frac{1}{8}\right) = -(-3) = 3 \text{ bity}

I(R) = -\log_2(0.875) \approx -(-0.1926) \approx 0.1926 \text{ bita}

Przykład pokazuje informację jako miarę zaskoczenia. Rzadki wynik, Orzeł, dostarcza 3 bity, natomiast przewidywalny wynik, Reszka, około 0.19 bita. Potwierdzenie wyniku o wysokim prawdopodobieństwie wnosi mniej informacji.

: średnia informacja ze źródła danych

Autoinformacja opisuje pojedyncze zdarzenie. Plik danych, taki jak dokument tekstowy lub obraz, jest sekwencją wielu symboli, na przykład znaków lub wartości pikseli. Do oceny możliwości kompresji całego pliku potrzebujemy średniej ilości informacji na symbol. Tą miarą jest entropia.

Entropia jest wartością oczekiwaną autoinformacji źródła. Odpowiada na pytanie o to, ile informacji średnio niesie symbol generowany przez to źródło.

Matematyczne sformułowanie entropii

Entropia źródła danych $X$ , które produkuje zbiór symboli $\{x_1, x_2, \ldots, x_n\}$ z odpowiednimi prawdopodobieństwami $P(x_i)$ , jest oznaczana przez $H(X)$ i obliczana przez zsumowanie autoinformacji każdego symbolu, ważonej jego prawdopodobieństwem wystąpienia:

H(X) = \sum_{i=1}^{n} P(x_i) \cdot I(x_i) = -\sum_{i=1}^{n} P(x_i) \cdot \log_2(P(x_i))

Entropia dotyczy rozkładu źródła, nie pojedynczego pliku. Jeśli symbole są zależne od kontekstu, można opisać źródło modelem warunkowym i analizować entropię warunkową. Stały rozkład niezależny od sąsiedztwa jest prostszym przybliżeniem.

Podstawa logarytmu wybiera jednostkę. Podstawa 2 daje bity, a inne podstawy dają inne jednostki.

Jednostką entropii jest bit na symbol. Wartość ta opisuje średnią nieprzewidywalność źródła przy przyjętym rozkładzie prawdopodobieństwa.

Dla alfabetu o $n$ symbolach entropia spełnia ograniczenie $0 \le H(X) \le \log_2 n$ . Wartość zero występuje, gdy źródło zawsze emituje ten sam symbol. Górna granica jest osiągana przy jednakowych prawdopodobieństwach wszystkich symboli.

Przykład 1: entropia symetrycznej monety

Korzystając z naszego przykładu symetrycznej monety, gdzie $P(O)=0.5$ , $I(O)=1$ bit, oraz $P(R)=0.5$ , $I(R)=1$ bit:

H(X) = (P(O) \cdot I(O)) + (P(R) \cdot I(R)) = (0.5 \cdot 1) + (0.5 \cdot 1) = 1 \text{ bit/symbol}

Entropia wynosi 1 bit na symbol. Jest to maksymalna wartość dla źródła o dwóch wynikach. Przy takim modelu wyniki są jednakowo prawdopodobne, więc rozkład nie zawiera nadmiarowości wynikającej z różnic częstości.

Przykład 2: entropia niesymetrycznej monety

Dla naszej niesymetrycznej monety, z $P(O)=0.125$ , $I(O)=3$ bity, oraz $P(R)=0.875$ , $I(R) \\approx 0.1926$ bita:

H(X) = (P(O) \cdot I(O)) + (P(R) \cdot I(R)) = (0.125 \cdot 3) + (0.875 \cdot 0.1926) \approx 0.375 + 0.1685 \approx 0.544 \text{ bita/symbol}

Entropia wynosi około pół bita na symbol. Ta wartość opisuje przewidywalność źródła. Rzadkie zdarzenie niesie dużo informacji, lecz występuje rzadko, więc średnia informacja źródła pozostaje niska. Taki rozkład wskazuje na redundancję możliwą do wykorzystania w kompresji bezstratnej.

Entropia jako granica kompresji bezstratnej

Twierdzenie Shannona o kodowaniu źródłowym określa asymptotyczny limit dla długich ciągów symboli ze źródła opisanego ustalonym modelem. Entropia $H(X)$ jest dolną granicą średniej liczby bitów na symbol w bezstratnym kodowaniu.

Dla długich bloków symboli ze źródła

X

nie można uzyskać bezstratnego kodowania o średniej liczbie bitów na symbol poniżej

H(X)

. Średnie długości kodu powyżej

H(X)

są osiągalne asymptotycznie przy odpowiednim kodowaniu.

Entropia opisuje średnią informację według przyjętego modelu, natomiast nadmiarowość zależy także od reprezentacji. W uproszczeniu znak może zajmować 8 bitów w zapisie bajtowym, lecz ASCII definiuje 7 bitów, a UTF-8 używa od 1 do 4 bajtów na punkt kodowy. Zakresy 1.5 do 2.5 bitów na znak dla polskiego tekstu oraz 1 do 1.5 dla angielskiego mogą być wyłącznie wynikami konkretnego korpusu i modelu, nie uniwersalną granicą. Algorytmy takie jak ZIP z Deflate usuwają część redundancji reprezentacji, lecz granica wynika z entropii przyjętego modelu.

W praktyce kodowanie pracuje na skończonych blokach, więc wynik może być większy od entropii przez zaokrąglenia, nagłówki i opis modelu. Modele uwzględniające kontekst symboli mogą osiągnąć niższą średnią niż model, w którym każdy symbol ma stały rozkład niezależny od sąsiedztwa.

Granica opisuje średnią dla długich ciągów. Konkretne wiadomości mogą być krótsze lub dłuższe od średniej, a zapis metadanych zwiększa rozmiar wyniku.