Podstawy Teorii Informacji

Poza Bity: Mierzenie Samej Informacji

W naszej podróży przez świat kompresji danych ustaliliśmy fundamentalną różnicę między technikami bezstratnymi i stratnymi. Metody bezstratne idealnie zachowują każdy fragment oryginalnych danych poprzez sprytne usuwanie nadmiarowości, podczas gdy metody stratne osiągają większą redukcję rozmiaru kosztem odrzucenia danych uznanych za nieistotne. Rodzi to głębsze pytanie: czy istnieje sposób na zmierzenie rzeczywistej ilości informacji zawartej w danych? Czy możemy określić teoretyczną granicę, punkt, poza którym żaden algorytm kompresji bezstratnej nie jest w stanie bardziej zmniejszyć pliku?

Odpowiedź brzmi: tak, a pochodzi ona z dziedziny matematyki i informatyki znanej jako Teoria Informacji. Zapoczątkowana przez Claude'a E. Shannona w latach 40. XX wieku, teoria ta dostarcza niezbędnych narzędzi matematycznych do analizy i ilościowego określania informacji. Pozwala nam to przejść od intuicyjnego rozumienia kompresji do precyzyjnego, naukowego podejścia. Aby zrozumieć granice kompresji, musimy najpierw nauczyć się, jak mierzyć informację. Teoria Informacji uczy nas, że informacja jest fundamentalnie miarą nieprzewidywalności lub, prościej mówiąc, zaskoczenia.

Autoinformacja: Mierzenie Zaskoczenia Pojedynczego Zdarzenia

Zanim będziemy mogli zmierzyć informację w całym pliku lub wiadomości, musimy zacząć od najmniejszego składnika: pojedynczego zdarzenia lub symbolu. Miarą tego jest .

Intuicja Stojąca za Zaskoczeniem

Wyobraźmy sobie dwie wiadomości na temat jutrzejszej pogody:

Słońce wzejdzie na wschodzie.
Niespodziewanie uformuje się rzadka burza tropikalna i przyniesie rekordowe opady śniegu.

Pierwsza wiadomość jest całkowicie przewidywalna. Jest to zdarzenie pewne. Usłyszenie jej dostarcza nam zasadniczo zero nowych informacji. Druga wiadomość jest niezwykle mało prawdopodobna i szokująca. Usłyszenie jej przekazuje ogromną ilość nowych informacji. Ta intuicyjna zależność jest sednem autoinformacji: ilość informacji, jaką niesie zdarzenie, jest odwrotnie proporcjonalna do prawdopodobieństwa jego wystąpienia. Rzadkie zdarzenia są zaskakujące, a zatem informatywne. Częste zdarzenia są przewidywalne, a zatem mało informatywne.

Sformułowanie Matematyczne

Shannon uchwycił tę zależność w prostym, eleganckim wzorze. Autoinformacja $I(x)$ zdarzenia $x$ o prawdopodobieństwie $P(x)$ jest zdefiniowana jako:

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

Rozłóżmy ten wzór na czynniki pierwsze, aby zrozumieć, dlaczego działa tak idealnie:

$P(x)$ : Jest to prawdopodobieństwo zajścia zdarzenia $x$ . Jest to liczba z przedziału od 0 (niemożliwe) do 1 (pewne).
$\frac{1}{P(x)}$ : Ten człon bezpośrednio oddaje ideę zaskoczenia. Jeśli zdarzenie jest bardzo prawdopodobne (np. $P(x) = 0.99$ ), ta wartość jest mała (około 1.01). Jeśli zdarzenie jest bardzo mało prawdopodobne (np. $P(x) = 0.0001$ ), ta wartość jest bardzo duża (10,000).
$\log_2$ : Logarytm o podstawie 2 jest używany do mierzenia informacji w najbardziej podstawowej jednostce: bicie. Logarytm odpowiada na pytanie: "Do jakiej potęgi musimy podnieść podstawę (2), aby otrzymać naszą liczbę?" W tym kontekście skaluje on wartość "zaskoczenia" do bardziej zarządzalnej miary. Ma również piękną właściwość, która sprawia, że informacja jest addytywna: informacja o dwóch połączonych, niezależnych zdarzeniach jest sumą ich indywidualnych informacji.
Znak minus ( $-$ ): Prawdopodobieństwa są zawsze liczbami z przedziału od 0 do 1, a logarytm liczby z tego zakresu jest zawsze ujemny lub zerowy. Znak minus we wzorze po prostu zamienia wynik na liczbę dodatnią, co jest bardziej intuicyjne przy mierzeniu wielkości takiej jak informacja.

Przykład 1: Rzut Symetryczną Monetą

Zastosujmy to do najprostszego możliwego scenariusza z niepewnością: 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 wynosi oczywiście również 1 bit. Ten wynik jest głęboki: mówi nam, że rozstrzygnięcie niepewności idealnie zrównoważonego zdarzenia o dwóch wynikach dostarcza dokładnie jednego bita informacji. To idealnie łączy matematyczną definicję informacji z podstawową jednostką danych cyfrowych.

Przykład 2: Rzut Niesymetryczną Monetą

Rozważmy teraz monetę niesymetryczną, w której jeden wynik jest znacznie 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}

Ten przykład pięknie ilustruje koncepcję informacji jako zaskoczenia. Zaobserwowanie rzadkiego zdarzenia (Orła) dostarcza znaczną ilość informacji (3 bity). Z drugiej strony, zaobserwowanie wysoce przewidywalnego zdarzenia (Reszki) dostarcza bardzo mało nowych informacji (około 0.19 bita). Już spodziewaliśmy się, że wypadnie reszka, więc potwierdzenie tego faktu nie jest bardzo informatywne.

: Średnia Informacja ze Źródła Danych

Autoinformacja jest potężna, ale opisuje tylko pojedyncze zdarzenie. Plik danych, taki jak dokument tekstowy czy obraz, to długa sekwencja wielu symboli (znaków, wartości pikseli). Aby zrozumieć potencjał kompresji całego pliku, musimy znać średnią ilość informacji na symbol. Tą miarą jest entropia.

Entropia jest w istocie wartością oczekiwaną autoinformacji źródła. Odpowiada na pytanie: "Średnio, ile zaskoczenia lub informacji niesie każdy symbol produkowany 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))

Jednostką entropii jest bit na symbol. Daje nam to pojedynczą, potężną liczbę, która charakteryzuje średnią nieprzewidywalność i zawartość informacyjną całego źródła.

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 możliwa entropia dla źródła o dwóch wynikach. Oznacza to, że źródło jest całkowicie losowe i nieprzewidywalne. Nie ma tu nadmiarowości do wykorzystania.

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 jest tutaj znacznie niższa, około pół bita na symbol. Ta niska wartość ilościowo określa przewidywalność źródła. Mimo że rzadkie zdarzenie niesie dużo informacji, zdarza się tak rzadko, że średnia zawartość informacyjna źródła jest niska. Wskazuje to na znaczną nadmiarowość, co oznacza duży potencjał do kompresji bezstratnej.

Entropia jako Ostateczna Granica Kompresji Bezstratnej

To prowadzi nas do najważniejszego wniosku teorii informacji dla kompresji danych. Twierdzenie Shannona o kodowaniu źródłowym dowodzi, że entropia $H(X)$ źródła ustanawia fundamentalną, nieprzekraczalną dolną granicę dla kompresji bezstratnej.

Niemożliwe jest bezstratne skompresowanie danych ze źródła

X

w taki sposób, aby średnia liczba bitów na symbol w skompresowanym wyjściu była mniejsza niż entropia

H(X)

tego źródła.

Entropia reprezentuje zatem prawdziwą, nieredukowalną zawartość informacyjną źródła danych. Każda część reprezentacji danych wykraczająca poza jej entropię jest nadmiarowością. Na przykład, tekst w języku polskim jest zwykle przechowywany przy użyciu 8 bitów na znak (ASCII/Unicode). Jednak jego entropia jest znacznie niższa, szacowana na około 1.5 do 2.5 bitów na znak ze względu na wzorce statystyczne. Różnica między 8 bitami, których używamy, a ~2 bitami prawdziwej informacji to nadmiarowość, którą mogą usunąć algorytmy kompresji, takie jak ZIP. Entropia wyznacza teoretyczny cel: wiemy, że nigdy nie będziemy w stanie bezstratnie skompresować polskiego tekstu tak, aby średnio zajmował mniej niż ~2 bity na znak.