Prawdopodobieństwo a informacja

Filozof może się zadowolić tym, że "wie, że nic nie wie". Fizyk zaś potrzebuje wiedzieć, ile nie wie...

Pojęcie entropii ma swoje źródło w termodynamice i jest związane z tym, jak bardzo nie znamy dokładnego mikrostanu układu. Tylko gdy wiemy o nim wszystko, możemy w pełni wykorzystać jego energię, przekształcając ją na inne formy. Gdy nie - część energii pozostaje niejako uwięziona.

Entropia jest równie cenna w teorii informacji - pozwala ściśle zmierzyć, jak dobrze możemy skompresować daną wiadomość oraz jak bardzo możemy niwelować szum przy jej przesyłaniu. Przydaje się ona również jako miara losowości i korelacji w różnych narzędziach statystycznych.

O ile entropia jest używana w języku potocznym jako chaos i nieuporządkowanie, to sama wielkość (a konkretniej, entropia Shannona) jest ściśle określona następującym wzorem:

n 1 H(p1,...,pn) = Q pilog (-- ), i 1 pi

(*)

gdzie $p1,...,pn$ są prawdopodobieństwami możliwych wyników przeprowadzanego eksperymentu. Będziemy używać logarytmu o podstawie 2, co odpowiada mierzeniu entropii w bitach. Powyższy wzór ma wiele zastosowań i interpretacji.

Ale zanim do nich przejdziemy, spójrzmy na kilka prostych przykładów. Gdy mamy jedną możliwość, entropia wynosi $1log(1) = 0$ - wszak nie ma tu miejsca na losowość. Gdy rzucamy uczciwą monetą, entropia to $1 1 |2 log(2)+ 2 log(2) = 1.$ Entropia jest największa, gdy dla ustalonej liczby zdarzeń wszystkie są równoprawdopodobne - wtedy wynosi ona $|log(n).$ Dla kostki do gry z $|6$ ścianami to $|log(6) ≈ 2,6.$

Warto pamiętać, że entropia jest zawsze miarą niewiedzy. Stąd np. kostka, na której widzimy wyrzucone dwa oczka, ma entropię zero. Dowiadujemy się dokładnie tyle, o ile entropia zmalała, tu:

H(1,-1, 1, 1, 1, 1) −H(0, 1,0,0,0,0) = log(6) − log(1)≈ 2,6. 6 6 6 6 6 6

Gdyby ktoś nam powiedział "wypadło jedno, dwa lub trzy oczka", nasza wiedza końcowa byłaby niepełna i dowiedzielibyśmy się $|log(6) − log(3),$ czyli 1 bit informacji.

Dlaczego potrzebujemy w tym wzorze logarytmu? Gdy mamy dwa niezależne zdarzenia, chcemy, by ich entropia była sumą entropii składników. Powiedzmy, że chcemy dowiedzieć się, jaki jest znak zodiaku naszego obiektu westchnień oraz czy nas kocha. Nie powinno grać roli, czy dowiemy się jednej informacji naraz czy po kawałku. Oznaczymy prawdopodobieństwa znaków zodiaku jako $|p,...,p 1 12$ oraz uczucie do nas jako $q ,q . 1 2$ Tym samym prawdopodobieństwa poszczególnych, niezależnych zdarzeń to iloczyny $piq j.$ Zatem jak jest z entropią?

$pict$

zatem entropia niezależnych zdarzeń dodaje się. W szczególności: $|n$ rzutów uczciwą monetą to $n$ bitów entropii.

Na wzór na entropię Shannona można patrzeć również jak na średnią uzyskaną informację. Zobaczmy to na przykładzie gry w dwadzieścia pytań, w której jedna osoba wymyśla jakąś rzecz, a druga ma za zadanie zgadnąć, o co chodzi, zadając po kolei pytania na "tak" lub "nie". Można się zastanowić, czy warto zadawać pytania, które są z grubsza pół na pół (np. "Czy to jest żywe?"), czy też takie, w których jest niewielka szansa, że dużo się rozjaśni (np. "Czy to element biżuterii?").

Powiedzmy, że na starcie jest $m$ możliwych obiektów i każdy z nich jest równoprawdopodobny. Jeśli zadamy pytanie, dla $|t$ obiektów odpowiedzią jest "tak", dla $m−t$ pozostałych - "nie". Wiąże się to bezpośrednio z prawdopodobieństwami odpowiedzi:

p = -t , p = m−-t--. tak m nie m

Zatem po uzyskaniu odpowiedzi zbiór możliwych obiektów zmniejsza się do $|ptakm$ albo $|pniem.$ Po zadaniu dwóch pytań (dla uproszczenia przyjmując, że po zadaniu pierwszego drugie ma to samo prawdopodobieństwo udzielenia twierdzącej odpowiedzi) dostajemy $4$ możliwości: $|p p m,p p m, tak tak nie tak$ $|ptakpniem$ albo $pniepniem.$ Wygramy w sytuacji, gdy po iluś pytaniach zredukujemy liczbę możliwości do tylko jednej. O ile może być w tym trochę szczęścia, to przy większej liczbie pytań (a mamy do dyspozycji ich aż $|20$ ), możemy śledzić, co się średnio stanie. Skoro przy dodawaniu kolejnych pytań prawdopodobieństwa się mnożą, to wielkością, którą chcemy uśredniać, jest wspomniany logarytm prawdopodobieństwa. Po jednym pytaniu dostajemy

1 1 H(ptak,pnie) = ptaklog(---) + pnielog (----), ptak pnie

- to samo co (*). Po zadaniu $|k$ pytań dowiadujemy się średnio $|kH$ bitów informacji. Wielkość ta to $Pp plog(1/p),$ gdzie $p$ jest prawdopodobieństwem uzyskania poszczególnego ciągu odpowiedzi. Jeśli jej wartość dojdzie do $|log(m),$ to średnio $p = 1/m,$ a zatem liczba możliwych obiektów zostanie zredukowana do jednej, czyli: zgadliśmy!

Entropia przy dwóch możliwościach, $H$ np. rzutu nieuczciwą monetą ( $p$ to prawdopodobieństwo orła) lub odpowiedzi na pytanie ( $p$ to prawdopodobieństwo "tak"). Maksimum, równe 1 bitowi, osiąga dla $p 1~2$

Gdy zadamy pytanie pół na pół, to niezależnie od odpowiedzi dowiadujemy się $|log 2$ czyli 1 bit informacji. A co gdy, powiedzmy, zadamy pytanie, na które prawdopodobieństwo odpowiedzi "tak" jest równe tylko $|1/1000?$ Jest niewielka szansa, że dowiemy się bardzo dużo $(log(1000) ≈ 10),$ ale najprawdopodobniej dowiemy się niezbyt wiele. A sumarycznie, będzie lepiej czy gorzej? Zobaczmy!

0,001log --1- 0,999log -1-- - 0,0100 0,0014 0,0114, 0,001 0,999

czyli bardzo niewiele! Zresztą, pół na pół średnio dostarcza najwięcej informacji.

Entropia jest też mocno związana z tym, jak dobrze potrafimy skompresować dane. Podstawowe twierdzenie Shannona mówi, że jeśli mamy ciąg $n$ liter, każda niezależna od innych i z entropią $|H,$ to nie możemy ich skompresować do długości krótszej niż $nH.$ Choć stoją za tym pewne szczegóły techniczne, główną ideę można oddać, zliczając ciągi. Liczba słów o długości $n$ z alfabetu z $d$ literami to $|dn = 2nlog d .$ Jeśli chcielibyśmy zakodować owe słowa za pomocą zer i jedynek tak, by każde słowo miało swój kod binarny, potrzebujemy $|m= nlog(d)$ bitów. A co, jeśli nie wszystkie litery są równie często używane?

Gdy przesyłamy wiele liter, niektóre ciągi staną się skrajnie mało prawdopodobne. Dla ustalenia uwagi, zróbmy to na ciągu z zer i jedynek, z prawdopodobieństwami $p$ i $|q,$ odpowiednio. Typowy ciąg o długości $n$ będzie miał $|np$ zer i $|nq$ jedynek. Prawdopodobieństwo tego ciągu to $np nq |p q .$ O ile, rzecz jasna, często można otrzymać ciągi z mniejszą lub większą liczbą zer i jedynek, to czym dłuższy ciąg, tym udział zer i jedynek będzie się bardziej zbliżał do $p$ i $|q,$ odpowiednio; innych ciągów jest skrajnie niewiele. Skoro typowe ciągi są mniej więcej równoprawdopodobne, a całkowite prawdopodobieństwo musi się sumować do jedności, to liczba tych typowych ciągów to około $p−npq−nq.$ Czyli potrzebujemy

-1 -1 m= n (p log (p ) +q log (q ))

bitów do ich opisu. Przy obliczaniu prawdopodobieństwa jesteśmy dość liberalni - wszak np. dla $| p = 0,8$ i $| q = 0,2$ zamiana nawet jednego znaku zmienia prawdopodobieństwo o czynnik 4.

Niemniej, jest to kompensowane przez niewielkie zmiany $| n$ (czasem potrzeba kilku mniej lub więcej bitów do zakodowania owego ciągu). Innymi słowy, liczba typowych ciągów zer i jedynek rośnie jak $2nH.$

Zastosowania? Zobaczmy, jak dobrze można skompresować tekst! W języku polskim używa się $35$ liter (wliczając q, x i v z zapożyczonych słów). Jednak niektóre litery występują znacznie częściej niż inne, np. a stanowi 9% liter, podczas gdy ź - tylko 0,06%. Możemy obliczyć, że entropia liter to $|4,56$ bitów. Dla porównania, taką samą entropię jak litery w języku polskim miałby hipotetyczny język z tylko $24,56≈ 24$ równo występującymi literami. Ale jak to się ma do kompresji? Porównując entropię z $|log(35),$ możemy zobaczyć, że, gdy znamy częstość znaków, potrafimy skompresować tekst do 89% objętości. W praktyce kompresja tekstu jest znacznie lepsza - zarówno dlatego, że nieskompresowany znak zwykle zajmuje $|8$ bitów (tu możemy kompresować do $|57%$ ), jak i to, że znaki nie są losowe, tj. łączą się w sylaby, słowa, a te - w teksty, które często używają podobnych słów.

Jako autor wiem, że ten tekst był skompresowany, ale, mam nadzieję, przekazał jakąś informację o entropii.