Pomiar informacji

Rozważcie następujący przykład: Alicja i Bob przesyłają wiadomości pomiędzy domkami na drzewie. Najpierw używali płomienia nocą i żaluzji w ciągu dnia, później przewodu, który trącali z różną siłą. W końcu podłączyli przewód do prądu, by przesyłać impulsy elektryczne. Obecnie pracują nad eksperymentalną metodą bezprzewodową. Tylko że potrzebowali pieniędzy na sprzęt, zaproponowali więc swoje usługi innym, za opłatą. Pierwszego dnia Alicja miała trzech klientów, którzy chcieli przesłać wiadomości do znajomych w domku Boba. Pierwszy klient chciał wysłać wyniki 10 rzutów monetą. Drugi klient miał do wysłania sześcioliterowe słowo. A trzeci chciał wysłać pokerową rękę. Pytanie: ile powinna za to zażądać? Cóż, cena za wiadomość powinna zależeć od tego, ile czasu zajmie Alicji jej przesłanie. Ale jaką wspólną jednostką zmierzyć długość różnych typów wiadomości? Przekonajmy się, grając w pewną grę. Wcielcie się w rolę Boba. Wiecie, że Alicja chce wam przesłać wiadomości, a wy możecie tylko uzyskać odpowiedź „tak” lub „nie” na pytania, które zadacie. Alicja będzie odpowiadać, wysyłając ciągi zer i jedynek, według jakiejś metody różnicowania. Pamiętajcie, że transmisja wiadomości to w istocie wymiana różnic. Zatem „1” może być oznaczane np. przez ogień, otwarte żaluzje albo impuls elektryczny. Niezależnie od formy, możemy je nazwać cyframi binarnymi, bo cyfra binarna może mieć tylko jedną z dwu wartości: 0 lub 1. Powiedzmy, że 0 znaczy „nie”, a 1 znaczy „tak”. Wasze zadanie polega na tym, by określić tę wiadomość za pomocą minimalnej liczby pytań. Zacznijmy od rzutów monetą. Każdy symbol wysłany przez Alicję można uznać za wybór jednej z dwu różnych możliwości. Orzeł lub reszka. Ile pytań musicie postawić, by określić, co wybrała? Wystarczy jedno pytanie, np. „Czy to reszka?”. A jaka jest minimalna liczba pytań dla dziesięciu wyników? 10 wyników razy jedno pytanie na wynik, to 10 pytań. 10 cyfr binarnych do przesłania tej wiadomości. A teraz pomyślmy o literach. Każdy symbol, który wysyła Alicja, jest jednym z 26 możliwych. Zacznijmy od najprostszej wiadomości, czyli jednej litery. Ilu trzeba pytań? „Czy to A?”, „Czy to B?”, „Czy to C?”, „Czy to D?” itd. Ale ta liczba pytań nie będzie minimalna. Najlepiej jest zadawać pytania eliminujące połowę możliwości. Alfabet dzieli się na pół między M a N. Możemy więc najpierw spytać, czy litera jest przed N. Otrzymujemy odpowiedź 1, czyli „tak”, i obcinamy połowę możliwości. Zostaje nam 13 liter. A ponieważ nie przetniemy litery na pół, podzielmy możliwe symbole na dwa zbiory, 6- i 7-elementowy, I spytajmy: „Czy ta litera jest przed G?”. Jeśli otrzymamy 1, czyli „tak”, to zostanie nam sześć możliwych liter. Dzielimy zbiór na pół i pytamy: „Czy to przed D?”. Odpowiedź 0, czyli „nie” pozostawia nam trzy możliwości. Teraz możemy zapytać: „Czy to D?”. Uzyskujemy odpowiedź 0, czyli „nie”, i zostają dwie możliwości. Pytamy: „Czy to E?”. Dostajemy odpowiedź „nie”. Za pomocą pięciu pytań poprawnie wskazaliśmy symbol F. Wiedzcie, że nigdy nie trzeba zadawać więcej niż pięciu pytań. Zatem liczba pytań wyniesie co najmniej cztery, a co najwyżej pięć. Ogólnie, 2 do potęgi „liczba pytań” to liczba możliwych wiadomości, którą zdefiniowaliśmy jako liczność przestrzeni wiadomości. Jak obliczyć średnią, oczekiwaną liczbę pytań, mając daną przestrzeń wiadomości o wielkości 26? Zapytajmy odwrotnie: do której potęgi trzeba podnieść 2, by uzyskać 26? Na pytania tego typu odpowiadamy używając logarytmu o podstawie 2. Bo logarytm o podstawie 2 z 26 to właśnie wykładnik potęgi, do której trzeba podnieść 2, by uzyskać 26. W przybliżeniu: 4,7. Przeciętnie trzeba około 4,7 pytania na literę, minimalnie. A ponieważ Alicja chce przekazać słowo sześcioliterowe, Bob może oczekiwać, że zada minimum 28,2 pytania. Co oznacza, że Alicja będzie musiała wysłać co najwyżej 29 cyfr binarnych. Zastosujmy tę metodę do kolejnej wiadomości. Ręki pokerowej. Przy każdym symbolu Alicja ma wybrać jedną z 52 różnych możliwości. W tym przypadku liczba pytań wynosi tyle, ile razy trzeba podzielić talię i pytać Alicję, w którym stosiku jest karta. Aż zostanie jedna. Przekonamy się, że zwykle jest to 6 przełożeń lub pytań. Czasami 5. Ale oszczędźmy czas, układając równanie. Logarytm o podstawie 2 z 52 to w przybliżeniu 5,7. Bo 2 do potęgi 5,7 wynosi około 52. Zatem minimalna średnia liczba pytań to 5,7 na kartę. Pokerowa ręka zawiera 5 kart, więc aby ją przekazać, trzeba zadać średnio 28,5 pytania. Skończyliśmy. Mamy jednostkę! Chodzi o minimalną liczbę pytań, które określą wiadomość. A to jest wysokość drzewa decyzyjnego. Alicja przekazuje informację w formie cyfr binarnych. Jednostkę tę nazywamy bitem (to skrót od angielskiego „binary digit”). A zatem: 10 rzutów monetą wymaga dziesięciu bitów, sześcioliterowe słowo wymaga 28,2 bita, a pokerowa ręka - 28,5 bita. Alicja postanawia naliczać jednego centa za bit i zaczyna inkasować opłaty. Ta koncepcja pojawiła się w latach 20. XX wieku. Była jednym z najbardziej abstrakcyjnych zagadnień zaprzątających inżynierów. Ralph Hartley był elektronikiem i wynalazcą. Rozwinął pomysł Harry’ego Nyquista. Obaj po pierwszej wojnie światowej pracowali w Laboratoriach Bella. W 1928 r. Hartley opublikował bardzo ważny artykuł pt. „Przekaz informacji”. Zdefiniował w nim pojęcie informacji i oznaczył je symbolem H. H jest równe n razy logarytm z s, gdzie H to nasza informacja, n to liczba symboli - nut, liter, cyfr itd., zaś s to liczba różnych symboli dostępnych do wyboru. Można też ująć to tak: H równa się logarytm z s do potęgi n. Hartley pisze: „Przyjęliśmy za praktyczną miarę informacji logarytm z liczby możliwych ciągów symboli”. Zatem informacja to logarytm z przestrzeni wiadomości. Pamiętajcie jednak, że podczas tej lekcji zakładaliśmy, iż wybór symbolu jest losowy. To wygodne uproszczenie, ale wiemy, że w rzeczywistości komunikacja, np. mowa, na ogół nie ma charakteru losowego. To połączenie przewidywalności i niespodzianek. Pisząc listy, nie rzucamy kostką. I właśnie ta przewidywalność może nam dać znaczące oszczędności czasu transmisji. Bo przewidując rzeczy z wyprzedzeniem, nie musimy zadawać aż tylu pytań zamkniętych. Jak jednak możemy formalnie określić subtelne różnice? To pytanie prowadzi nas do kluczowej kwestii. Domyślacie się, jakiej?