Entropia wyjaśniona

W 1948 roku inżynier z Bell Labs, Claude Shannon, zadał pytanie, którego nikt wcześniej nie sformułował precyzyjnie: ile informacji zawiera wiadomość? Jego odpowiedzią była liczba, mierzona w bitach, która zależy nie od tego, co wiadomość znaczy, lecz od tego, jak bardzo jest zaskakująca. Ta liczba, entropia, wyznacza granice każdego programu do kompresji, każdego łącza sieciowego i każdego nośnika danych, a także wyjaśnia, dlaczego niektóre teksty kurczą się do ułamka swojej objętości, a innych nie da się ścisnąć wcale.

Słupki prawdopodobieństw liter blednące od częstych do rzadkich i krzywa entropii opadająca w miarę poznawania kontekstu
Słupki prawdopodobieństw liter blednące od częstych do rzadkich i krzywa entropii opadająca w miarę poznawania kontekstu

Informacja to zaskoczenie

Przełomowa myśl Shannona polegała na tym, by mierzyć informację tym, jak nieoczekiwana jest wiadomość, a nie tym, co znaczy. Jeśli znasz już odpowiedź, jej usłyszenie niczego ci nie mówi; jeśli mogła być jedną z tysiąca rzeczy, mówi wiele. Wiadomość wskazująca jedną z dwóch jednakowo prawdopodobnych możliwości niesie jeden bit. Jedna z czterech wymaga dwóch bitów, jedna z ośmiu – trzech, a ogólnie jedna z N jednakowo prawdopodobnych możliwości wymaga log₂ N bitów. Symbol występujący z prawdopodobieństwem p niesie więc −log₂ p bitów: im jest rzadszy, tym więcej mówi.

Wzór Shannona

Entropia to średnia informacja na symbol: H = −Σ p log₂ p, z sumą po wszystkich symbolach i ich prawdopodobieństwach p. Dla uczciwej monety H wynosi 1 bit. Dla monety, która w 90% przypadków spada orłem, to tylko 0,47 bitu, bo wynik zwykle nie jest zaskoczeniem. Entropia jest największa, gdy wszystkie symbole są jednakowo prawdopodobne – log₂ n bitów dla n symboli – i równa zeru, gdy jeden symbol jest pewny. Shannon wybrał tę nazwę za radą Johna von Neumanna, bo ten sam wzór pojawia się w fizyce, gdzie entropia mierzy nieuporządkowanie.

Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.
Claude Shannon, który w 1948 w Bell Labs precyzyjnie określił, ile informacji zawiera komunikat, i mierzył ją w bitach.

Granica kompresji

Twierdzenie Shannona o kodowaniu źródła mówi, że żaden kod bezstratny nie może średnio używać mniej bitów na symbol, niż wynosi entropia źródła, i że kody mogą się do niej zbliżyć dowolnie blisko. Kodowanie Huffmana, wymyślone w 1952 roku przez studenta Davida Huffmana, nadaje częstym symbolom krótkie kody, a rzadkim długie, i odbiega od entropii o mniej niż jeden bit na symbol; kodowanie arytmetyczne zbliża się jeszcze bardziej. Entropia nie jest więc tylko opisem, lecz twardą granicą: pliku losowych bajtów, z 8 bitami entropii na bajt, nie da się skompresować wcale.

David Huffman sfotografowany jako profesor Uniwersytetu Kalifornijskiego w Santa Cruz. Jako doktorant MIT w 1951 roku znalazł swój optymalny kod w pracy semestralnej na kurs Roberta Fano.
David Huffman sfotografowany jako profesor Uniwersytetu Kalifornijskiego w Santa Cruz. Jako doktorant MIT w 1951 roku znalazł swój optymalny kod w pracy semestralnej na kurs Roberta Fano.

Kontekst i nadmiarowość

Litery w tekście nie są niezależne. W angielskim po Q przychodzi U, po kropce wielka litera, a słowo zaczynające się od INFORMA niemal na pewno ciągnie się dalej jako TION. Uwzględnienie poprzednich symboli daje entropię warunkową, niższą od entropii symboli liczonych pojedynczo. Różnica to nadmiarowość (redundancja): ta część wiadomości, którą dało się przewidzieć. Programy kompresujące, takie jak ZIP, który używa metody deflate, wyszukują powtarzające się ciągi i zastępują je krótkimi odwołaniami, a nowoczesne kompresory przewidują każdy symbol na podstawie jego kontekstu.

Ile informacji jest w języku angielskim?

Liczona litera po literze, przy częstościach liter angielskich, jedna litera niesie około 4,1 bitu, wobec 4,7 dla liter wybieranych losowo. W 1951 roku Shannon poszedł dalej: pokazywał ludziom początek tekstu i prosił, by odgadli następną literę, licząc, ilu prób potrzebowali. Na podstawie ich odpowiedzi oszacował, że angielski niesie tylko około 0,6–1,3 bitu na literę. Innymi słowy mniej więcej trzy czwarte pisanego angielskiego to nadmiarowość, i dlatego tekst z brakującymi literami zwykle wciąż da się przeczytać.

Losowość i hasła

Entropia mierzy też nieprzewidywalność, od której zależy bezpieczeństwo. Klucz lub hasło wybrane równomiernie spośród N możliwości ma log₂ N bitów entropii, a atakujący musi wypróbować średnio około połowy z nich. Losowe hasło z 12 liter wybieranych spośród 26 małych liter alfabetu angielskiego ma około 56 bitów; popularne słowo ma ich znacznie mniej, bez względu na długość. Generatory liczb losowych testuje się, sprawdzając, czy ich wyjście ma pełną entropię losowego źródła, a systemy operacyjne zbierają entropię z szumu czasowego, aby je zainicjować.

Gdzie pojawia się entropia

Entropia decyduje o tym, ilu bitów potrzebuje rozmowa telefoniczna, zdjęcie lub strumień wideo, i jak blisko przepustowości swojego kanału może się znaleźć modem lub łącze Wi-Fi. Biolodzy używają jej do mierzenia informacji w DNA, gdzie każda z czterech zasad może nieść najwyżej 2 bity, a także różnorodności ekosystemu. W uczeniu maszynowym drzewa decyzyjne wybierają pytanie, które najbardziej zmniejsza entropię, a funkcja straty oparta na entropii krzyżowej służy do trenowania większości sieci neuronowych. Językoznawcy porównują języki pod względem entropii na znak i na słowo.

Wypróbuj to

Otwórz kalkulator entropii, aby zmierzyć dowolny tekst według znaków, słów lub bajtów. Porównaj akapit z losowymi literami, bitami, cyframi i DNA, zobacz zaskoczenie każdego symbolu, ile informacji zawiera tekst w porównaniu z rozmiarem zapisu i jak liczba bitów na symbol spada w miarę poznawania kontekstu, obok tego, co faktycznie osiąga ZIP.

Często zadawane pytania

Dlaczego entropię mierzy się w bitach?

Bo Shannon używał logarytmów o podstawie 2, tak aby jeden wybór tak/nie między równorzędnymi opcjami liczył się jako jedna jednostka. Przy logarytmie naturalnym jednostką jest nat, około 1,44 bitu, a przy podstawie 10 hartley, około 3,32 bitu; posługują się nimi fizycy i niektórzy statystycy.

Czy tekst może mieć entropię większą niż log₂ rozmiaru swojego alfabetu?

Nie. Przy n różnych symbolach entropia wynosi najwyżej log₂ n bitów na symbol i osiąga tę wartość tylko wtedy, gdy wszystkie są jednakowo częste. Każda nierównowaga i każda przewidywalność wynikająca z kontekstu ją obniża.

Czy entropia w teorii informacji to to samo co w fizyce?

Wzory mają tę samą postać: Boltzmann i Gibbs zapisali entropię fizyczną jako sumę po prawdopodobieństwach mikroskopowych stanów układu. Znaczenie jest pokrewne, bo obie mierzą, jak wiele nie wiemy, a fizycy wykazali później, że wymazanie jednego bitu informacji musi uwolnić niewielką ilość ciepła.

Dlaczego kompresowanie skompresowanego pliku nic nie daje?

Dobry kompresor usuwa większość nadmiarowości, więc jego wynik jest bliski losowemu, z prawie 8 bitami entropii na bajt. Nie ma już czego usuwać, a ponowna kompresja zwykle nieco powiększa plik z powodu własnego narzutu kompresora.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz kalkulator entropii